改进fuzzywuzzy - 匹配2个列表中的名称

Question

我的要求是找到2个列表的匹配名称。一个列表有400个名称，第二个列表有90000个名称。我得到了理想的结果，但过程需要超过35分钟。很明显，有2个for循环因此需要O（N * N）个操作才是瓶颈。我删除了两个列表中的重复项。你能帮忙改进吗？我检查了很多其他问题，但不知何故无法实现。如果您认为我只是错过了阅读已有的帖子，请指出。我会尽力理解并复制它。

以下是我的代码

from fuzzywuzzy import fuzz
infile=open('names.txt','r')
name=infile.readline()
name_list=[]
while name:
    name_list.append(name.strip())
    name=infile.readline()

print (name_list)

infile2=open('names2.txt','r')
name2=infile2.readline()
name_list2=[]
while name2:
    name_list2.append(name2.strip())
    name2=infile2.readline()

print (name_list2)

response = {}
for name_to_find in name_list:
    for name_master in name_list2:
        if fuzz.ratio(name_to_find,name_master) > 90:
            response[name_to_find] = name_master
            break

for key, value in response.items():
    print ("Key is ->" + key + "  Value is -> " + value)

Answer 1

最明显的方法是使用哈希表。伪代码：

1. 确定较小的清单
2. 基于较小的列表创建哈希表： hash1 ={name: 1 for name in name_list}
3. 遍历第二个列表并检查第一个列表中是否存在名称密钥： l = [name for name in name_list2 if name in hash1]

而已。您将获得两个列表中存在的名称列表

Answer 2

如果不知道fuzz背后的算法，我怀疑我们可以做多少来减少渐近运行时。可能有一些技巧来修剪明显不好的对，但可能没有那么多。另一个答案假设您正在进行完全匹配 - 并且不适用于模糊字符串匹配。

您可以尝试做的是尝试批量调用，并希望fuzzywuzzy已经为其process中的批次优化了一些逻辑。就像是

from fuzzywuzzy import process

for name in names400:
    matches = filter(lambda x: x[1] > 90, process.extract(name, names90000, limit=90000))
    for match_name, score in matches:
         response[match_name] = name

另请注意，在github page for fuzzywuzzy上，他们提到使用python levenshtein可以将计算加速4-10倍。