python - Fuzz Ratio 的增加速度

Question

我是 python 的新手，正在努力加速这段代码。

我在 zz1 中有大约 100 万个字符串，在 a3 中有 250,000 个字符串。 zz1 中的字符串有错误，我想将其匹配到 a3 中具有最高模糊匹配率的字符串。

我对结果很满意，但处理 zz1 中的一行大约需要 9 秒。有没有办法加快速度？

import csv
import string
import time
import sys
from fuzzywuzzy import fuzz
op=[]
for i in range(1,len(zz1)):
    num=zz1[i][1] 
    start2 = time.clock()
    forecast = []

    if not num in zz4 and zz5:

       for j in range (1,len(a3)):
           forecast.append(fuzz.ratio(num,a3[j][1]))

       if (max(forecast)>60):
           index=forecast.index(max(forecast))
           op.append(a3[index][1])

    elapsed2 = (time.clock() - start2)    
    print (i,elapsed2)

Answer 1

由于数据表示的是缩写字符串而不是拼写错误或其他错误，因此您应该能够通过消除简单的选择来执行此操作。

考虑这两个例子(我不知道 GRAND CANYON 怎么缩写，所以这只是一个说明问题的猜测):

GRAND CANYON    -> GR CANYON
MELBOURNE REEF  -> MELBRNE REEF

GR CANYON 不可能与 MELBOURNE REEF 相关，因此没有必要对其进行测试。按字符串的左前缀分组以编纂此测试，您应该会看到非常高的命中率，因为缩写通常会保留第一个字母。

因此，您只能比较以“G”开头的缩写与同样以“G”开头的全名，以及“M”与“M”等。

另请注意，这不一定要提供完美匹配；您将维护不匹配字符串的列表并在找到它们时删除匹配项，因此在比较分组字符串并删除匹配项之后，您的最终不匹配项列表将是原始数据的一个非常小的子集，可以是使用您原来的蛮力方法相对较快地进行比较。

仅使用第一个字符，您可以将每个列表中要比较的字符串数量减少 26 倍，从而将比较次数减少 26*26 倍，即快 676 倍!

由于在最初的消除步骤中不需要完美的准确性，因此您可以将此分组扩展到不仅仅是第一次迭代的第一个字符，从而减少每次额外迭代的字符数，直到达到零个字符。使用 2 字符分组，您可以将每个列表中要比较的项目数减少 26*26，从而将比较总数减少 26*26*26*26，即从 2500 亿次减少到大约 50 万次比较。用 3 个字符分组，从 2500 亿减少到大约 809。

通过使用这种迭代方法，您将执行以指数方式减少的模糊操作，而不会降低准确性。