python 中搜索字符串和字符串列表之间最高百分比编辑距离的最快方法是什么？

Question

我正在编写一个程序，将较小的游戏标题列表与许多游戏的主列表进行比较，以查看较小列表中的哪些游戏与主列表中的游戏标题比其他游戏更匹配。为了做到这一点，我一直在检查较小列表中的每个游戏与主列表中的 every 游戏之间的 Levenshtein 距离（以百分比形式），并取所有的最大值这些值（最大百分比越低，游戏必须越独特）同时使用 difflib 和 fuzzywuzzy 模块。我遇到的问题是使用 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

Answer 1

通过实验和进一步研究，我发现检查 Levenshtein 比率的最快方法是通过 python-Levenshtein 库本身。与使用 fuzzywuzzy 或 difflib 中的任何函数相比，函数 Levenshtein.ratio() 明显更快（对于一个游戏，整个搜索平均只需要 0.05 秒），可能是因为它的简单性和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.ratio() 获取每个字符串的比率字符串与第一个字符串进行比较，然后在每次迭代中检查最高值比率。

python 中搜索字符串和字符串列表之间最高百分比编辑距离的最快方法是什么？

What is the fastest method in python of searching for the highest percent Levenshtein distance between a string and a list of strings?

python

fuzzy-search