SequenceMatcher - поиск двух наиболее похожих элементов из двух или более списков данных

Question

Я пытался сравнить набор строк с уже определенным набором строк.Например, вы хотите найти адресата письма, текст которого оцифровывается через OCR.

Существует массив адресов, в которых в качестве элементов используются словари.Каждый уникальный элемент содержит идентификатор, имя, улицу, почтовый индекс и город.Этот список будет иметь длину 1000 записей.

Поскольку отсканированный текст OCR может быть неточным, нам нужно найти наиболее подходящих кандидатов строк со списком, который содержит адреса.

Текст750 слов.Мы уменьшаем количество слов, используя подходящую функцию фильтра, которая сначала разбивает пробелы, удаляет больше пробелов из каждого элемента, удаляет все слова длиной менее 5 символов и удаляет дубликаты;длина полученного списка составляет 200 слов.

Поскольку у каждого адресата есть 4 строки (название улицы, почтовый индекс и город), а длина оставшейся буквы составляет 200 слов, мой компилятор должен выполнить 4 *1000* 200 = 800'000 раз.

Я использовал Python со средним успехом.Матчи были правильно найдены.Однако алгоритм обрабатывает много писем очень долго (до 50 часов на 1500 писем).Понимание списка было применено.Есть ли способ правильно (и не обязательно) реализовать многопоточность?Что делать, если это приложение должно работать на сервере с низкой спецификацией?Мой 6-ядерный процессор не жалуется на такие задачи, однако я не знаю, сколько времени потребуется для обработки большого количества документов на небольшом экземпляре 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 минута), не 50 часов на 1500 букв.Я уверен, что это узкое место, так как другие задачи работают быстро и безупречно.

Есть ли лучший (более быстрый) способ сделать это?

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, описанное

Answer 2

Вы хотите распознать вводы, которые похожи на слова из словаря, например, "St0ckholm" -> "Стокгольм".Перестановка опечаток должны быть обработаны.Ok.

Возможно, вы бы предпочли установить autojunk=False.Но квадратичный или кубический алгоритм звучит как проблема, если вы спешите.

Рассмотрим проблему анаграммы, где вас спрашивают, являются ли входное слово и словарное слово анаграммами друг друга.Простое решение состоит в том, чтобы сравнить отсортированные строки на равенство.Давайте посмотрим, сможем ли мы адаптировать эту идею в подходящую структуру данных для вашей задачи.

Предварительно обработать слова из вашего словаря в канонические ключи, которые легко найти, и вывесить список из одного или нескольких слов из каждогоключ.Используйте сортировку, чтобы сформировать ключ.Так, например, у нас будет:

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

Сохранить эту карту, отсортированную по ключу.

Учитывая введенное слово, вы хотите знать, есть ли именно это слово в словаре, или есливерсия с ограниченным расстоянием редактирования появляется в словаре.Сортируйте входное слово и исследуйте карту на предмет 1-й записи, большей или равной этомуПолучите (очень короткий) список слов-кандидатов и оцените расстояние между каждым из них и вашим входным словом.Выведите лучшее совпадение.Это происходит очень быстро.

Для нечеткого соответствия, используйте как 1-ю, так и 2-ю записи цели >=, а также предыдущую, чтобы у вас был больший набор кандидатов.Кроме того, пока этот подход чувствителен к удалению «маленьких» букв, таких как «a» или «b», из-за сортировки по возрастанию.Так что дополнительно формируйте ключи с сортировкой по убыванию и проверяйте карту на наличие ключей обоих типов.

Если вы хотите передать установочные пакеты, рассмотрите import soundex, который намеренно отбрасывает информацию из слов, или import fuzzywuzzy.