Время прочтения: 5 мин.

Данный алгоритм является модифицированным и переписанным на Python с C# алгоритмом из этой статьи.

GitHub c реализацией автора на C#. GitHub c реализацией на Python.

В данной реализации отсутствует перевод числа в прописном виде из-за отсутствия потребности в такой задаче.

Суть задачи

Есть большой объём данных отсканированных через Adobe File reader документов в виде txt файлов, разного формата. Нам нужно распарсить эти документы по некоторым параметрам и достать из них число, записанное прописью. Для того чтобы вытаскивать параметры мы используем Natasha, но из-за «мусорных» данных, вызванных либо качеством сканов, либо не идеальности самого сканера, она не всегда справляется со своей задачей. Тут нам и приходит на помощь алгоритм, о котором далее пойдёт речь.

Типы встречаемых «мусорных» данных

  1. Приклеивание лишних символов к словам. Таких как: “(  _ . , / “, и прочие.
  2. Точки между слов или иные символы: Пример: “два . миллиона _ три”.
  3. Неправильное распознавание букв. Пример: “н0ль”, “одиннадщать”.
  4. Склеивание слов. Примеры: “тридцатьтри”, “двадцатьодинземлекоп”.
  5. Строки с длинным хвостом. Примеры: “двадцать три_______________”, “_______________двадцать три”, “двадцать__три”.
  6. Разделение по строкам и подмешивание лишних данных.
    Пример: “Одна
    сумма
    тысяча
    подпись
    триста тридцать три”.
  7. Слова в начале и конце строки, которые не являются токенами.

Описание базового алгоритма

Базовый алгоритм хорошо описан в статье автора , поэтому не буду его пересказывать, скопирую лишь его краткое описание.

Входящую строку, представляющую число прописью, мы разбиваем на подстроки с помощью регулярки \s+, затем каждую из подстрок пытаемся сопоставить с токенами-образцами или разбить на более мелкие подстроки, выбирая при этом лучшие результаты. В итоге получаем набор токенов, по которым генерируем число, а величину ошибки принимаем как среднее арифметическое ошибок среди токенов, использованных при генерации.

Описание модификаций

Исследуя оригинальный алгоритм, мы встретились с одной интересной, но неприятной особенностью. Если отдать алгоритму любое слово, то он преобразует его в какое-то число. Алгоритм просто найдёт токен с минимальной ошибкой по алгоритму Вагнера-Фишера (частный случай расстояния Левенштейна) и вернёт его несмотря на то, что слово вообще не похоже на число.

Для удобства использования была добавлена функция-обёртка text_to_ number над оригинальной функцией, которая возвращает только целочисленное значение.

В процессе работы алгоритма мы считаем среднюю ошибку, которая для адекватных случаев не превышает значения 0.3, поэтому в функции text_to_number мы ограничили среднее значение добавив переменную класса _MAX_ERROR_LIMIT. Это значение можно поставить меньше или больше в зависимости от специфики задачи.

@classmethod
def text_to_number(cls, text):
    num = cls.text_to_numeral(text)
    if num.Error > cls._MAX_ERROR_LIMIT:
        return -1

    return num.Value

Ограничение ошибки для токенов

Так как у нас могут подмешиваться различные «мусорные» данные между реальными токенами алгоритм был модифицирован так, что мы удаляем все токены с показателем ошибки больше, чем _MAX_TOKEN_ERROR_LIMIT, который у нас также равен 0.3. С этими параметрами можно поэкспериментировать, так как конкретно в нашей ситуации _MAX_ERROR_LIMIT также равен 0.3, и мы никогда его не превысим из-за того, что сравниваем со средней оценкой.

tokens_for_del = list()

for item in tokens:
    if item.error > cls._MAX_TOKEN_ERROR_LIMIT:
        tokens_for_del.append(item)

for item in tokens_for_del:
    tokens.remove(item)

Проблемы алгоритма

Проблема длинных токенов и ошибок «с хвостом»

В ситуации, когда к нам приходит длинный токен, что может произойти в ситуации ошибки с «длинным хвостом» или при склеивании строк, алгоритм пытается разделить токен на несколько и при передаче строки вида “два_________________________________” может отрабатывать несколько минут. Таких ситуаций нужно избегать. В идеале нужно выкидывать из входной строки все явно лишние символы. На данный момент алгоритм удаляет символ ‘_’ самостоятельно.

Без удаления символа ‘_’:

C удалением символа ‘_’:

Слова похожие на токены

Во входных документах иногда встречаются слова, которые очень похожи на токены, но ими не являются. Одно из таких слов — это слово “срок”, которое отличается от слова “сорок” всего на одно добавление. Уверены, что такое слово не единственное и их необходимо исключать из входной строки, так как они не проходят по ограничению допустимого порога ошибки.

Скорость выполнения алгоритма

Алгоритм хорошо справляется в сложных случаях, но если отдавать ему строку с «мусором», то время его выполнения увеличивается во много раз. Возможно, это получится исправить, используя другие структуры данных или каким-то образом вычислять относительную похожесть без использования алгоритма Вагнера-Фишера, чтобы не проходить по всему списку токенов каждый раз.

Мы используем этот алгоритм только в сложной ситуации, когда Natasha возвращает сообщение о том, что она не справилась, что во много раз ускоряет процесс парсинга.

Алгоритму желательно подавать на вход максимально чистую строку насколько это возможно, чтобы уменьшить время, затраченное на парсинг или подавать файл по предложению. Алгоритм больше подходит для распознавания сложных случаев, которые не в состояние распознать Natasha, Yargy и прочие парсеры, а не постоянного использования. Алгоритм нуждается в доработке и оптимизации.

Конкретно в нашей задаче этот алгоритм обработал 20% документов, которые не смогла обработать Natasha, что является довольно хорошим результатом.