5

我试图将一组字符串与一组已经定义的字符串进行比较。例如，您想查找一封信的收件人，该文本通过 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 小时。我确信这是瓶颈，因为其他任务运行迅速且完美无缺。

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

4

2 回答 2

2

一些快速提示：

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 描述的

于 2019-01-03T18:35:34.093 回答
1

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

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

考虑 Anagram 问题，其中询问您输入单词和字典单词是否是彼此的字谜。直接的解决方案是比较排序后的字符串是否相等。让我们看看我们是否可以将该想法改编为适合您的问题的数据结构。

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

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

存储此地图按键排序。

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

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

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

于 2019-01-03T18:34:00.710 回答