代码之家 › 专栏 › 技术社区 › valerius21

两个或两个以上相似数据的匹配列表

sequencematcher difflib algorithm python-3.x python

valerius21 · 技术社区 · 6 年前

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

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

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

这篇课文有750字长。我们通过使用适当的过滤函数来减少单词的数量,该函数首先按空格进行分割,从每个元素中剥离更多的空格,删除所有长度小于5个字符的单词并删除重复的单词,得到的列表长度为200个单词。

因为每个收件人有4个字符串(姓名、街道、邮政编码和城市),剩下的字母有200个单词长,所以我的比较器必须运行4*1000*200 =80万次。

我使用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小时。我确信这是一个瓶颈,因为其他任务正在快速和完美地工作。

有更好(更快)的方法吗?

2 回复 | 直到 6 年前

juvian 6 年前

一些快速提示:

1) 让我知道用quick\u ratio()或real\u quick\u 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所描述的

J_H 6 年前

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

也许你更愿意 autojunk=False

考虑字谜问题,你会被问到一个输入词和一个字典里的词是否是彼此的字谜。简单的解决方案是比较排序后的字符串是否相等。让我们看看是否可以将这个想法改编成适合您的问题的数据结构。

将字典中的单词预处理成易于查找的规范键,并在每个键上挂起一个或多个单词的列表。使用排序形成键。例如,我们可以:

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

按键存储此地图。

给定一个输入单词,您需要知道该单词是否准确地出现在字典中,或者字典中是否出现了编辑距离有限的版本。对输入字进行排序,并在映射图中查找大于或等于该值的第一个条目。检索(非常短的)候选词列表,并计算它们与输入词之间的距离。输出最佳匹配。这种情况发生得很快。

对于模糊匹配,请同时使用第一个和第二个条目 >=

如果您愿意pip安装软件包,请考虑 import soundex import fuzzywuzzy .