Python：比较两个字符串

Question

我想知道是否有一个库可以告诉我两个字符串大概有多相似。

我并不需要什么具体的东西，但在这种情况下：

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

我们可以说b和a大约相似度达到了90%。

是否有一种库可以实现这个功能？

- Alex Gordon

---

可能是文本差异算法的重复问题。 - tzot

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

- killown

Answer 2

Levenshtein距离是一个用来衡量两个字符串之间差异的度量方法。

在pypi上有一些库可以使用，但需要注意的是，对于较长的字符串，这种方法比较耗费资源。

您还可以尝试使用Python的difflib库：http://docs.python.org/library/difflib.html

- Radomir Dopieralski

---

昂贵？与半靠谱的Levenshtein实现相比，difflib就像一个怪物。 - John Machin

我的意图并不是要暗示 difflib 更便宜 -- 它只是做了一件类似但略有不同的事情。 - Radomir Dopieralski

Answer 3

寻找Levenshtein算法来比较字符串。这是通过谷歌发现的随机实现：http://hetland.org/coding/python/levenshtein.py

- viraptor

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)

这是我的第二个 版本，实际上它提供了常见字符串，同时使用了双端队列数据结构（并附带使用案例）：

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')
"""

- Tony Veijalainen