任意文本间的单词相似度评分

Question

我有一个500多个非常重要但任意的字符串的列表。它们看起来像：

list_important_codes = ['xido9','uaid3','frps09','ggix21']

我所知道的 *大小写并不重要，但所有其他字符必须完全匹配。 *每个字符串以4个字母字符开头，以一个或两个数字字符结尾。 *我有一个大约100000个字符串的列表，list_recorded_codes是手工输入的，应该完全匹配list_important_codes，但其中大约10000个不匹配。因为这些字符串是手动键入的，所以不正确的字符串通常只差1个字符。（错误如下：*增加了空格，*切换了两个字母，*将“1”改为“01”，等等）

我需要做什么 我需要遍历list_recorded_codes，并在list_important_codes中找到它们的所有完美匹配

我尝试的 我花了大约10个小时试图手动编写一种修复每个单词的方法，但这似乎不切实际，令人难以置信地乏味。更不用说，当我的列表在以后翻倍时，我将不得不再次手动执行该过程

我认为我需要的解决方案，以及预期输出

我希望Python的NLTK能够有效地“评分”这些任意术语，以找到“最佳评分”。例如，如果所讨论的单词是inputword = "gdix88"，那么该单词将与score(inputword,"gdox89")=.84和score(inputword,"sudh88")=.21进行比较。我的预期输出为highscore=.84, highscoreword='gdox89'

for manually_entered_text in ['xido9','uaid3','frp09','ggix21']:
--get_highest_score_from_important_words()  #returns word_with_highest_score
--manually_entered_text = word_with_highest_score

如果需要，我也愿意使用一套不同的工具来解决这个问题。而且，越简单越好！谢谢大家!

Answer 1

您要查找的“分数”称为编辑距离。有相当多的文献和算法可用-很容易找到，但只有在您知道正确的术语：）

请参阅相应的wikipedia article

nltk包提供了所谓的Levenshtein编辑距离的实现：

from nltk.metrics.distance import edit_distance

if __name__ == '__main__':
    print(edit_distance("xido9", "xido9 "))
    print(edit_distance("xido9", "xido8"))
    print(edit_distance("xido9", "xido9xxx"))
    print(edit_distance("xido9", "xido9"))

在本例中，结果为1、1、3和0

下面是相应的nltk module的文档

这个分数有更专门的版本，考虑到各种打字错误的频率（例如，可能经常出现“e”而不是“r”，因为qwert键盘上的键彼此相邻）

但经典的Levenshtein会让我开始

Answer 2

您可以对这个问题应用动态规划方法。一旦您设置了评分矩阵、校准矩阵以及本地和全局校准函数，您就可以遍历列表重要代码，并在列表记录的代码中找到得分最高的校准。这是我为DNA序列比对做的一个项目：DNA alignment。你可以很容易地使它适应你的问题