Python内置字符串比较函数类似于N-gram

Question

在Python里有没有什么内置的函数，可以像 Ngram.Compare('text','text2') 这样比较字符串？我不想安装N-gram这个模块。我试过用 dir('text') 找到的所有公共和私有函数。

我想要比较两个字符串时得到一个匹配的百分比。

Answer 1

你想要计算“莱文斯坦距离”，这个功能可以通过以下链接找到实现：

http://pypi.python.org/pypi/python-Levenshtein/

如果你不想安装任何东西，那就意味着你需要自己写代码来实现这个功能。

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

Answer 2

标准库里有一个叫做 difflib 的工具。

你还可以计算一个叫做莱文斯坦距离的东西：

def lev(seq1, seq2):
    oneago = None
    thisrow = range(1, len(seq2) + 1) + [0]
    for x in xrange(len(seq1)):
        twoago, oneago, thisrow = oneago, thisrow, [0] * len(seq2) + [x + 1]
        for y in xrange(len(seq2)):
            delcost = oneago[y] + 1
            addcost = thisrow[y - 1] + 1
            subcost = oneago[y - 1] + (seq1[x] != seq2[y])
            thisrow[y] = min(delcost, addcost, subcost)
    return thisrow[len(seq2) - 1]

def di(seq1,seq2):
    return float(lev(seq1,seq2))/min(len(seq1),len(seq2))

print lev('spa','spam')
print di('spa','spam')