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小时。我相信这是瓶颈，因为其他任务都能快速无误地完成。

有没有更好（更快）的方法来做到这一点？

- valerius21

---

文档中提到SequenceMatcher可能是二次的，这非常慢。你为什么选择了SequenceMatcher？ - Dani Mesejo

不仅文档中说它可能是二次时间，而且您还没有提供任何帮助，因为您指定了什么是垃圾和一个双重循环，这本身就是O(n^2)。 - gold_cy

你正在比较字母中的单词与可以有多个单词的地址项，所以像街道这样的东西总是得分很低，这可能会导致错误的结果。而且，如果你删除了所有少于5个字符的单词，为什么信件还会显示税务？ - juvian

@aws_apprentice 谢谢，我会去了解一下！ - valerius21

多线程对于像这样的计算密集型任务没有帮助。 - martineau

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所描述的那样。

- juvian

Answer 2

您希望识别与字典单词相似的输入，例如 "St0ckholm" -> "Stockholm"。应处理转置打字错误。可以设置autojunk=False。但是如果时间紧迫，则二次或三次算法可能会有麻烦。考虑变位词问题，其中要求您确定输入单词和字典单词是否互为变位词。直接的解决方案是比较排序后的字符串是否相等。让我们看看是否可以将这个想法调整为适合您的问题的合适数据结构。预处理字典单词成易于查找的规范键，并挂在每个键上一个或多个单词的列表。使用排序形成键。因此，例如我们将拥有：

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

按键排序存储此地图。

给定一个输入单词，您想知道字典中是否正好出现该单词，或者字典中是否出现了具有有限编辑距离的版本。对输入单词进行排序并探测大于或等于该单词的第一个条目。检索（非常短的）候选单词列表，并评估它们每个与您的输入单词之间的距离。输出最佳匹配项。这个过程非常快。

对于模糊匹配，请同时使用第一和第二个条目>=目标，以及前面的条目，这样您就会获得更大的候选集。此外，到目前为止，由于升序排序，该方法对“小”字母（如“a”或“b”）的删除敏感。因此，还要形成降序排序的键，并针对两种类型的键探测地图。

如果您愿意安装软件包，请考虑import soundex，它有意从单词中丢弃信息，或import fuzzywuzzy。

- J_H

Answer 3

我遇到了类似的问题。Python代码如下：

from difflib import SequenceMatcher
def search(list1, list2):
   s = SequenceMatcher(None, list1, list2)
   match = s.find_longest_match(0, len(list1), 0, len(list2))
   return list1[match.a: match.a + match.size]

list1 = [1, 2, 3, 4, 5, 3, 2, 3, 4]
list2 = [8, 7, 6, 7, 2, 3, 4, 5, 4, 5, 3, 2, 3, 4, 9, 0, 9]
ls = search(list1, list2)
print(ls)

输出为：

[4, 5, 3, 2, 3, 4]

- Arman Vesta