Levenshtein字符串相似度，Levenshtein字符串,概述Levenshtei

Levenshtein字符串相似度，Levenshtein字符串,概述Levenshtei

概述

Levenshtein距离用来描述两个字符串之间的差异。我在一个网络爬虫程序里面使用这个算法来比较两个网页之间的版本，如果网页的内容有足够多的变动，我便将它更新到我的数据库。

#!/bin/python#coding: gbk def strcmp(s, t):    if len(s) > len(t):        s, t = t, s    #第一步    n = len(s)    m = len(t)    if not m : return n    if not n : return m    #第二步    v0 = [ i for i in range(0, m+1) ]    v1 = [ 0 ] * (m+1)     #第三步    cost = 0    for i in range(1, n+1):        v1[0] = i        for j in range(1, m+1):            #第四步,五步            if s[i-1] == t[j-1]:                cost = 0            else:                cost = 1            #第六步            a = v0[j] + 1            b = v1[j-1] + 1            c = v0[j-1] + cost            v1[j] = min(a, b, c)        v0 = v1[:]    #第七步    return v1[m]if __name__ == '__main__':    print strcmp( "GUMBO", "GAMBOL")    print strcmp( u"我爱你中国", u"我爱共产党")#该片段来自于http://byrx.net