Levenshtein距离用来描述两个字符串之间的差异代码,Python代码库,德仔网

代码语言

代码分类

【Python】 Levenshtein距离用来描述两个字符串之间的差异

作者:王明杰 / 发布于2012/10/22/ 740

Levenshtein算法，用于计算两个字符串之间的Levenshtein距离。而Levenshtein距离又称为编辑距离，是指两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

<div>!/bin/python</div>
<div>coding: gbk</div>
<div>http://www.cnblogs.com/ymind/archive/2012/03/27/fast-memory-efficient-Levenshtein-algorithm.html</div>
<div>def strcmp(s, t):</div>
<div>  if len(s) > len(t):</div>
<div>    s, t = t, s</div>
<div>  #第一步</div>
<div>  n = len(s)</div>
<div>  m = len(t)</div>
<div></div>
<div>  if not m : return n</div>
<div>  if not n : return m</div>
<div> </div>
<div>  #第二步</div>
<div>  v0 = [ i for i in range(0, m+1) ]</div>
<div>  v1 = [ 0 ] * (m+1)</div>
<div></div>
<div>  #第三步</div>
<div>  cost = 0</div>
<div>  for i in range(1, n+1):</div>
<div>    v1[0] = i</div>
<div>    for j in range(1, m+1):</div>
<div>      #第四步,五步</div>
<div>      if s[i-1] == t[j-1]:</div>
<div>        cost = 0</div>
<div>      else:</div>
<div>        cost = 1</div>
<div></div>
<div>      #第六步</div>
<div>      a = v0[j] + 1</div>
<div>      b = v1[j-1] + 1</div>
<div>      c = v0[j-1] + cost</div>
<div>      v1[j] = min(a, b, c)</div>
<div>    v0 = v1[:]</div>
<div>  #第七步</div>
<div>  return v1[m]</div>
<div></div>
if __name__ == '__main__':</div>
<div>  print strcmp( "GUMBO", "GAMBOL")</div>
<div>  print strcmp( u"我爱你中国", u"我爱共产党")</div>
<div></div>

试试其它关键字

　两个字符串之间的差异　

同语言下

可能有用的

王明杰贡献的其它代码(1)

.Levenshtein距离用来描述两个字符串之间的差异