python dict上的模糊搜索操作

Question

我在python中有一个大字典，我需要使用模糊搜索比较所有字符串。我正在使用fuzzywuzzy包。

但是，脚本太慢了，并且想知道是否有人可以帮助我加快速度。

代码如下所示：

outfile = open('out.csv', 'w')
grouped = []
### a chunk of the dict, in reality it is around 100000 unique ID
d = {'1':'{'Name':'Jason Bourne', 'Code':'1234'}', '2':'{'Name':'Jasen Bourne', 'Code':'1234'}','3':'{'Name':'Jason Boune', 'Code':'12345'}'}

for id1, id2 in itertools.combinations(d.keys(),2):
     score = fuzz.partial_ratio(d[id1]['Name'],d[id2]['Name'])
     if id1 in grouped and id2 in grouped:
          continue
     if score > 80 and d[id1]['Code']==d[id2]['Code']:
         grouped.append(id2)
         outfile.write(id1, id2, d[id1]['Name'])

Answer 1

在给定的示例中，首先按'Code'对项目进行分组可能会大大加快速度。

无论如何，你应该试图避免将每个字符串与每个其他字符串进行比较，因为对于100k字符串（10 ^ 5），这是大约100亿（10 ^ 10）个比较。

一个相对简单的过程可以更快：

1. 创建所有字符串的n-gram索引（在规范化大小写，空格等之后）
2. 使用该索引搜索每个字符串的近匹配，然后完全与这些匹配。