python - SequenceMatcher - 找到两个或多个数据列表中两个最相似的元素

Question

我试图将一组字符串与一组已定义的字符串进行比较。 例如，您想要查找一封信件的收件人，该信件的文本通过 OCR 数字化。

有一个地址数组，其中有字典作为元素。 每个元素都是唯一的，包含 ID、姓名、街道、邮政编码和城市。此列表将包含 1000 个条目。

由于 OCR 扫描的文本可能不准确，我们需要找到与包含地址的列表最匹配的候选字符串。

文本长 750 个字。我们通过使用适当的过滤函数来减少单词的数量，该函数首先按空格拆分，从每个元素中剥离更多的空格，删除所有长度小于 5 个字符的单词并删除重复项；结果列表有 200 个单词。

由于每个收件人有 4 个字符串(姓名街道、邮政编码和城市)，其余字母长 200 个字，我的比较必须运行 4 * 1000 * 200 = 800'000 次。

我使用 python 取得了中等成功。已正确找到匹配项。但是，该算法需要很长时间来处理大量字母(每 1500 个字母最多需要 50 小时)。已应用列表理解。有没有办法正确(而不是不必要)实现多线程？如果此应用程序需要在低规范服务器上运行怎么办？我的 6 核 CPU 不会提示此类任务，但是，我不知道在小型 AWS 实例上处理大量文档需要多少时间。

>> len(addressees)
1000
>> addressees[0]
{"Name": "John Doe", "Zip": 12345, "Street": "Boulevard of broken dreams 2", "City": "Stockholm"}
>> letter[:5] # already filtered
["Insurance", "Taxation", "Identification", "1592212", "St0ckhlm", "Mozart"]
>> from difflib import SequenceMatcher
>> def get_similarity_per_element(addressees, letter):
    """compare the similarity of each word in the letter with the addressees"""
    ratios = []
    for l in letter:
        for a in addressee.items():
            ratios.append(int(100 * SequenceMatcher(None, a, l).ratio())) # using ints for faster arithmatic
    return max(ratios)
>> get_similarity_per_element(addressees[0], letter[:5]) # percentage of the most matching word in the letter with anything from the addressee
82
>> # then use this method to find all addressents with the max matching ratio
>> # if only one is greater then the others -> Done
>> # if more then one, but less then 3 are equal -> Interactive Promt -> Done
>> # else -> mark as not sortable -> Done.

我希望每个文档的处理速度更快。 (最多 1 分钟)，而不是每 1500 个字母 50 小时。我确信这是瓶颈，因为其他任务正在快速且完美地运行。

是否有更好(更快)的方法来做到这一点？

Answer 1

一些快速提示:

1) 让我知道执行 quick_ratio() 或 real_quick_ratio() 而不是 ratio() 需要多长时间

2) 反转循环的顺序并使用 set_seq2 和 set_seq1 以便 SequenceMatcher 重用信息

for a in addressee.items():
    s = SequenceMatcher()
    s.set_seq2(a)    
    for l in letter:
       s.set_seq1(l)
        ratios.append(int(100 * s.ratio()))

但更好的解决方案是像@J_H 描述的那样