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

您想要识别与字典单词类似的输入，例如“St0ckholm”->“Stockholm”。应该处理换位错别字。好的。

可能您更愿意设置autojunk=False. 但如果你赶时间的话，二次或三次算法听起来很麻烦。

考虑一下字谜问题，系统会询问您输入的单词和字典中的单词是否互为字谜。最简单的解决方案是比较排序后的字符串是否相等。让我们看看是否可以将这个想法改编成适合您的问题的数据结构。

将字典单词预处理为易于查找的规范键，并在每个键上挂出一个或多个单词的列表。使用排序来形成键。例如我们会有：

    'dgo' -> ['dog', 'god']

按键排序存储此地图。

给定一个输入单词，您想知道该单词是否准确地出现在词典中，或者编辑距离有限的版本是否出现在词典中。对输入单词进行排序，并在映射中查找大于或等于该单词的第一个条目。检索（非常短的）候选单词列表并评估每个单词与输入单词之间的距离。输出最佳匹配。这发生得很快。

对于模糊匹配，请使用第一个和第二个条目>=目标，加上前面的条目，这样您就有了更大的候选集。此外，到目前为止，由于升序排序，这种方法对删除“a”或“b”等“小”字母很敏感。因此，另外形成降序排序的键，并探测两种类型键的映射。

如果您愿意 pip install 软件包，请考虑import soundex，它会故意丢弃单词中的信息，或者import fuzzywuzzy。