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

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

所以我得到一个例如[1,0,0,0]如果word1 ="NUMB"和word2 ="LUMB"的列表

Answer 1

看起来像肖恩·奇提供了最佳的解决方案,但如果你使用非内置模块阻止,这似乎是get_close_matches从difflib可能有帮助:

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

可以使用其返回值的get_opcodes方法SequenceMatcher和处理差异的数量来获得差异的数量.

Answer 2

使用pylevenshtein计算Levenshtein距离:

>>> 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如果您想避免其他依赖关系,您可以始终实现自己的函数来计算距离.例如,在wikibooks中提出了几个版本,每个版本都有自己的优点和缺点.

但是,如果需要考虑性能,请考虑坚持使用自定义构建的模块.除了pylevenshtein之外,还有python-levenshtein和nltk.metrics.distance(如果你碰巧已经使用过NLTK).