Python中查找字符串和字符串列表之间最高百分比Levenshtein距离的最快方法是什么？

Question

我正在编写一个程序，将较小的游戏列表与包含许多游戏的主列表进行比较，以确定较小列表中哪些游戏标题与主列表中的游戏标题更相似。为此，我一直在使用difflib和fuzzywuzzy模块检查较小列表中每个游戏与主列表中所有游戏之间的Levenshtein距离（以百分比形式），并取所有这些值的最大值（最大百分比越低，游戏就越独特）。但是，使用process.extractOne()或difflib.get_close_matches()进行典型搜索需要大约5秒以上（主列表中有38000+个字符串），而我需要搜索约4500个游戏（5 * 4500约为6小时15分钟，我没有那么多时间）。

为了寻找更好更快速的字符串搜索方法，我想问一下，在Python中搜索字符串列表中最高百分比Levenshtein距离的最快方法是什么。如果没有比使用上述两个函数或编写其他循环代码更好的方法，请告诉我。

我使用的两个函数具体用于搜索最高距离如下：

metric = process.extractOne(name, master_names)[1] / 100
metric = fuzz.ratio(name, difflib.get_close_matches(name, master_names, 1, 0)[0]) / 100

- Zach K

Answer 1

通过实验和进一步研究，我发现检查Levenshtein比率最快的方法是通过 python-Levenshtein 库本身。函数 Levenshtein.ratio() 的速度 明显更快（对于一个游戏来说，整个搜索平均只需要0.05秒），相比使用fuzzywuzzy或difflib中的任何函数都要快，这可能是由于它的简单性和C实现造成的。我在for循环中使用此函数迭代主列表中的每个名称以获得最佳答案：

from Levenshtein import ratio

metric = 0
for master_name in master_names:
    new_metric = ratio(name, master_name)
    if (new_metric > metric):
        metric = new_metric

总的来说，我认为在字符串和字符串列表之间寻找最高百分比的Levenshtein距离的最快方法是遍历字符串列表，使用Levenshtein.ratio()将每个字符串与第一个字符串进行比较，然后在每次迭代中检查最高值比率。

- Zach K