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

Question

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

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

我所知道的 *大小写不重要，但所有其他字符必须完全匹配。 *每个字符串以 4 个字母字符开头，以一个或两个数字字符结尾。 *我有一个大约 100,000 个字符串的列表，list_recorded_codes 是手写的，应该与 list_important_codes 完全匹配，但其中大约 10,000 个不匹配。因为这些字符串是手动输入的，所以错误的字符串通常只有大约 1 个字符。（错误如：*添加了 space、*两个字母互换、*有“01”而不是“1”等）

我需要做什么 我需要遍历 list_recorded_codes 并在 list_important_codes.

中找到他们所有的完美匹配

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

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

我希望 Python 的 NLTK 可以有效地 'score' 这些任意术语找到 'best score'。例如，如果有问题的单词是 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

你可以应用动态规划方法来解决这个问题。一旦你有了你的评分矩阵，你 alignment_matrix 和你的局部和全局对齐函数设置，你可以遍历 list_important_codes 并在 list_recorded_codes 中找到最高得分对齐。这是我为 DNA 序列比对所做的项目：DNA alignment。您可以轻松地使其适应您的问题。

Answer 2

您要查找的'score'称为编辑距离。有很多可用的文献和算法 - 很容易找到，但前提是你知道正确的术语:)

见对应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。

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

Scoring word similarity between arbitrary text

python

string

word

matching

nltk