模糊比率增长速度

Question

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

我有大约100万串zz1和250000串a3。zz1中的字符串有错误，我想把它匹配到a3中的字符串上，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

不确定这将节省多少时间，但这一点似乎不必要地复杂：

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])

每次创建一个新列表，其中包含250000个元素，然后检查新列表中的max元素，然后找到max元素的索引，从原始列表中检索关联的值。做一些类似的事情可能更有意义：

^{pr2}$

这样你就不会每次都创建和存储一个大的新列表，你只是保留你找到的最好的匹配项，只有在找到更好的匹配项时才替换它。在

Answer 2

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

考虑这两个例子（我不知道大峡谷是如何缩写的，所以这只是一个猜测来说明这一点）：

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

GR峡谷不可能与墨尔本礁有关，所以没有必要对此进行测试。按字符串的左前缀分组来编写这个测试，您应该会看到一个非常高的命中率，因为缩写通常会保留第一个字母。在

所以，你只比较以“G”开头的缩写词与同样以“G”开头的全名，“M”与“M”开头的缩写词等等

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

只需使用第一个字符，就可以将每个列表中要比较的字符串数量减少26倍，这将使比较数量减少26*26倍，速度快了676倍！在

由于在最初的消除步骤中不需要完全精确，所以您可以将此分组扩展到第一次迭代的不止第一个字符，从而减少每次额外迭代的字符数，直到达到零个字符为止。使用2字符分组，可以将每个列表中要比较的项目数减少26*26，这将使比较总数减少26*26*26*26，或者从2500亿减少到大约50万个比较。有3个字符的分组，从2500亿下降到809个。在

通过使用这种迭代方法，您将执行指数级更少的模糊操作，而不会失去准确性。在