比较两个字符串并返回相似度最高的一个

Question

我需要写一个函数，这个函数接收一个字符串作为参数，然后把这个字符串和另外两个字符串进行比较，最后返回最相似的字符串以及它们之间的不同之处的数量。

def func("LUMB"):
    lst=["JIBM", "NUNE", "NUMB"]
should return:
("NUMB",1)

我尝试过：

def f(word):
    lst=["JIBM", "NUNE", "NUMB"]
    for i in lst:
        d=k(word, lst)
        return differences
        for n in d:
            print min(sum(n))

这里：

def k(word1, word2):
    L=[]
    for w in range(len(word1)):
        if word1[w] != word2[w]:
            L.append(1)
        else:
            L.append(0)
    return L

这样的话，如果word1="NUMB"和word2="LUMB"，我会得到一个列表，比如说[1,0,0,0]。

Answer 1

使用 pylevenshtein 来计算 莱文斯坦距离：

>>> from Levenshtein import distance
>>> from operator import itemgetter
>>> lst = ["JIBM", "NUNE", "NUMB"]
>>> min([(x, distance("LUMB", x)) for x in lst], key=itemgetter(1))
('NUMB', 1)

或者，可以写成一个函数：

from Levenshtein import distance
from operator import itemgetter
def closest(word, lst):
    return min([(x, distance(word, x)) for x in lst], key=itemgetter(1))

print closest("NUMB", ["JIBM", "NUNE", "NUMB"])

---

补充一下，如果你想避免增加额外的依赖库，其实可以自己实现一个计算距离的函数。例如，维基教科书上有几种不同的实现方式，每种都有自己的优缺点。

不过，如果你对性能有要求，建议还是使用那些专门制作的模块。除了 pylevenshtein，还有 python-levenshtein 和 nltk.metrics.distance（如果你已经在使用 NLTK 的话）。

Answer 2

看起来Shawn Chin提供了最好的解决方案，但如果你不能使用非内置模块的话，似乎可以试试来自 difflib 的 get_close_matches，这个方法可能会对你有帮助：

import difflib
difflib.get_close_matches("LUMB", ["JIBM", "NUNE", "NUMB"], 1)

你可以通过 get_opcodes 方法来获取不同之处的数量，这个方法是 SequenceMatcher 的一部分，你可以根据它返回的结果来进行处理。