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

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

where:

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

这样我就可以得到一个列表，例如，[1,0,0,0] if word1="NUMB" and word2="LUMB"

Answer 1

看起来 Shawn Chin 提供了最好的解决方案，但是如果您被阻止使用非内置模块，则似乎 get_close_matches 可能会有所帮助：

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

可以使用 SequenceMatcher 并使用它的返回值。

Answer 2

使用 pylevenshtein 计算 Levenshtein distance：

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

---

ps 如果您想避免额外的依赖关系，您始终可以实现自己的函数来计算距离。例如，wikibook 中提出了多个版本，每个版本都有自己的优点和缺点缺点。

但是，如果性能是一个问题，请考虑坚持使用定制模块。除了 pylevenshtein 之外，还有 python-levenshtein 和 nltk.metrics.distance （如果您碰巧已经使用NLTK）。