蟒蛇：比较两个字符串

Question

我想知道是否有一个库，它会告诉我两个字符串大约有多相似

我不是在寻找特定的东西，但在这种情况下：

a = 'alex is a buff dude' 
b = 'a;exx is a buff dud' 

我们可以说b和a大概有90％的相似。

有没有可以做到这一点的图书馆？

Answer 1

import difflib 

>>> a = 'alex is a buff dude' 
>>> b = 'a;exx is a buff dud' 
>>> difflib.SequenceMatcher(None, a, b).ratio() 

0.89473684210526316 

Answer 2

查找Levenshtein比较字符串的算法。以下是通过谷歌找到了一个随机的实现：http://hetland.org/coding/python/levenshtein.py

Answer 3

http://en.wikipedia.org/wiki/Levenshtein_distance

上有一些库，但要知道，这是昂贵的，特别是对于更长的字符串。

你也可以想看看python的difflib：http://docs.python.org/library/difflib.html

Answer 4

另一种方法是使用时间最长的公共子。在这里，在Daniweb一个实现我的LCS实现（这也是在difflib定义）

下面是简单的长度只有列表作为数据结构的版本：

def longest_common_sequence(a,b): 

    n1=len(a) 
    n2=len(b) 

    previous=[] 
    for i in range(n2): 
     previous.append(0) 

    over = 0 
    for ch1 in a: 
     left = corner = 0 
     for ch2 in b: 
      over = previous.pop(0) 
      if ch1 == ch2: 
       this = corner + 1 
      else: 
       this = over if over >= left else left 
      previous.append(this) 
      left, corner = this, over 
    return 200.0*previous.pop()/(n1+n2) 

这里是我的第二version which actualy gives the common string与deque的数据结构（也与实施例的数据使用的情况下）：

from collections import deque 

a = 'alex is a buff dude' 
b = 'a;exx is a buff dud' 

def lcs_tuple(a,b): 

    n1=len(a) 
    n2=len(b) 

    previous=deque() 
    for i in range(n2): 
     previous.append((0,'')) 

    over = (0,'') 
    for i in range(n1): 
     left = corner = (0,'') 
     for j in range(n2): 
      over = previous.popleft() 
      if a[i] == b[j]: 
       this = corner[0] + 1, corner[1]+a[i] 
      else: 
       this = max(over,left) 
      previous.append(this) 
      left, corner = this, over 
    return 200.0*this[0]/(n1+n2),this[1] 
print lcs_tuple(a,b) 

""" Output: 
(89.47368421052632, 'aex is a buff dud') 
"""