Хабрахабр

Умный парсер числа, записанного прописью

В данной статье я расскажу о том, как распарсить число, записанное прописью на русском языке. Добрый день, уважаемые читатели.

Умным данный парсер делает возможность извлечения чисел из текста с ошибками, допущенными в результате некорректного ввода или в результате оптического распознавания текста из изображения (OCR).

Для ленивых:
Ссылка на проект github: ссылка.

Осторожно, много букв! В данном разделе будут описаны использованные алгоритмы.

Постановка задачи

Из-за соглашения о неразглашении информации я не могу привести пример фотографии, но суть в том, что в документе имеется таблица, в которой записаны некие показатели числом и прописью, и эти данные необходимо прочитать. По работе мне требуется распознать текст из печатного документа, сфотографированного камерой смартфона/планшета. Но, как известно, OCR не гарантирует точного распознавания текста. Парсинг текста прописью необходим как дополнительный инструмент валидации, чтобы убедиться, что число распознано верно. Нужно это учесть и извлечь максимальное количество информации, оценив величину возможной ошибки. Например, число двадцать, записанное прописью, может быть распознано как «двадпать» или даже как «двапать».

Для . Примечание. Для распознавания текста я использую tesseract 4. Tesseract4. NET нет готового NuGet-пакета четвертой версии, поэтому я создал такой из ветки основного проекта, может кому пригодится: Genesis.

Базовый алгоритм парсинга числа

Если вам интересен именно умный парсинг, данный раздел можно пропустить. Начнем с простого, а именно с алгоритма распознавания текста, записанного прописью, пока без ошибок.

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

Оно состоит из трех слов (токенов), каждому из которых соответствует число, все эти числа суммируются: Итак, возьмем небольшое число, например «сто двадцать три».

"сто двадцать три" = сто + двадцать + три = 100 + 20 + 3 = 123

Пока все просто, но копнем глубже, например рассмотрим число «двести двенадцать тысяч сто пять».

"двести двенадцать тысяч сто пять" = (двести + двенадцать) × тысяч + (сто + пять) = 212 * 1.000 + 105 = 212.105.

Таких фрагментов может быть несколько, но все они идут по убыванию множителя, например, за тысячей не может последовать миллион или еще одна тысяча. Как видим, когда в числе присутствуют тысячи (а также миллионы и прочие степени тысячи), число делится на части, состоящие из локального маленького числа, в примере выше – 212, и множителя (1000). Характеристику, относящую два токена к одному типу, назовем уровнем, например, токены «сто» и «триста» имеют один уровень, и он больше, чем у токена «пятьдесят». Это верно также и для частей маленького числа, так за сотнями не могут последовать сотни, а за десятками — десятки, поэтому запись «сто пятьсот» неверна.

Давайте выпишем все возможные токены (образцы), каждому из которых поставим в соответствие число, а также два параметра – уровень и признак множителя. Из этих рассуждений и рождается идея алгоритма.

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

Заведем четыре величины: Теперь перейдем к парсингу.

  1. Глобальный уровень (globalLevel). Указывает, какой уровень был у последнего множителя. Изначально не определен и необходим для контроля. Если мы встретим токен-множитель, у которого уровень больше или равен глобальному, то это ошибка.
  2. Глобальное значение (globalValue). Общий сумматор, куда складывается результат результат перемножения локального числа и множителя.
  3. Локальный уровень (localLevel). Указывает, какой уровень был у последнего токена. Изначально не определен, работает аналогично глобальному уровню, но сбрасывается после обнаружения множителя.
  4. Локальное значение (localValue). Сумматор токенов, не являющихся множителями, т.е. чисел до 999.

Алгоритм выглядит следующим образом:

  1. Разбиваем строку на токены с помощью регулярки "\s+".
  2. Берем очередной токен, получаем информацию о нем из образца.
  3. Если это множитель:
    • Если задан глобальный уровень, то убеждаемся, что он больше или равен уровню токена. Если нет – это ошибка, число некорректно.
    • Устанавливаем глобальный уровень на уровень текущего токена.
    • Умножаем величину токена на локальное значение и добавляем результат к глобальному значению.
    • Очищаем локальное значение и уровень.
  4. Если это не множитель:
    • Если задан локальный уровень, то убеждаемся, что он больше или равен уровню токена. Если нет – это ошибка, число некорректно.
    • Устанавливаем локальный уровень на уровень текущего токена.
    • Прибавляем к локальному значению величину токена.
  5. Возвращаем результат как сумму глобального и локального значений.

Пример работы для числа «два миллиона двести двенадцать тысяч сто восемьдесят пять».

212. Результатом будет 2. 185.

Умный парсинг

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

Теперь давайте подумаем, какие ошибки могут быть при неверной записи числа, полученного в результате OCR. С парсингом корректно записанного числа разобрались. Другие варианты я не рассматриваю, но вы можете модифицировать алгоритм под конкретную задачу.

Я выделил три вида ошибок, с которыми столкнулся в процессе работы:

  1. Замена символов на другие со схожим начертанием. Например, буква «ц» почему-то заменяется на «п», а «н» на «и» и наоборот. При использовании третьей версии tesseract возможна замена буквы «о» на ноль. Эти ошибки, навскидку, самые распространенные, и требуют тюнинга под конкретную библиотеку распознавания. Так так принципы работы tesseract версий 3 и 4 имеют кардинальные различия, поэтому и ошибки там будут разными.
  2. Слияние токенов. Слова могут сливаться воедино (обратного пока не встречал). В комбинации с первой ошибкой порождает демонические фразы типа «двапатьодин». Попробуем раздраконить и таких монстров.
  3. Шум – левые символы и фразы в тексте. К сожалению, здесь мало что можно сделать на данный момент, но перспектива есть при сборе достаточно весомой статистики.

При этом сам алгоритм разбора, описанный выше, почти не меняется, главное различие в разбиении строки на токены.

Из 33 букв русского языка при написании неотрицательных целых чисел используются только 20, назовем их хорошими буквами: Но начнем со сбора небольшой статистики использования букв в токенах.

авдеиклмнопрстцчшыья

Максимальный размер токена при этом составляет 12 символов (13 при счете до квадриллионов). Остальные 13, соответственно, назовем плохими буквами. Подстроки длиной больше этой величины нужно разбивать.

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

В нашей задаче это не так. Небольшой ликбез: расстояние Левенштейна – частный случай алгоритма Вагнера-Фишера, когда стоимость вставки, удаления и замены символов статичны. Вообще говоря, нельзя, но ситуация зависит от конкретной задачи. Очевидно, что если в подстроке мы встречаем плохую букву, то ее нужно заменить на хорошую, а вот заменять хорошую на плохую крайне нежелательно.

Пока она заполнена методом трех П (пол, палец, потолок), но если заполнить ее данными на основе статистики OCR, то можно значительно улучшить качество распознавания чисел. Для описания стоимости вставки, удаления и замены символов я создал такую таблицу: ссылка на таблицу с весами. В коде библиотеки присутствует файл ресурсов NumeralLevenshteinData.txt, в который можно вставить данные из подобной таблицы с помощью Ctrl+A, Ctrl+C и Ctrl+V.

Если в тексте встречается нетабличный символ, например, ноль, то стоимость его вставки приравнивается к максимальной величине из таблицы, а стоимость удаления и замены – к минимальной, таким образом алгоритм охотнее заменит ноль на букву «о», а если вы используете третью версию tesseract, то имеет смысл добавить ноль в таблицу и прописать минимальную цену для замены его на букву «о».

Для этого каждый токен мы подвергнем дополнительному анализу, но перед этим расширим информацию о токене следующими характеристиками: Итак, данные для алгоритма Вагнера-Фишера мы подготовили, давайте внесем изменения в алгоритм разбиения строки на токены.

  • Уровень ошибки. Вещественное число от 0 (ошибки нет) до 1 (токен некорректен), означающее, насколько хорошо токен был сопоставлен с образцом.
  • Признак использования токена. При разборе строки с вкраплениями мусора, часть токенов будет отброшена, для них данный признак выставляться не будет. При этом итоговая величина ошибки будет считаться как среднее арифметическое от ошибок использованных токенов.

Алгоритм анализа токенов:

  1. Пытаемся найти токен в таблице как есть. Если находим – все хорошо, возвращаем его.
  2. Если нет, то составляем список возможных вариантов:
  3. Данный вариант состоит из одного токена (сопоставленного образца) и его ошибка равна лучшему расстоянию, поделенному на длину образца. Пытаемся сопоставить токен с образцом с помощью алгоритма Вагнера-Фишера.

    Пример: токен «нуль» сопоставляется с образцом «ноль», при этом расстояние равно 0.5, т.к. стоимость замены плохой буквы «у» на хорошую «о» равна 0.5. Общая ошибка для данного токена будет 0.5 / 4 = 0.125.

  4. Для строки в 6 символов будет единственный вариант деления: 3+3 символа. Если подстрока достаточно большая (у меня это 6 символов), пытаемся поделить ее на две части минимум по 3 символа в каждой. Для каждого из вариантов вызываем рекурсивно эту же функцию анализа токенов, заносим полученные варианты в список. Для строки в 7 символов – уже два варианта, 3+4 и 4+3, и т.д.

    Кроме того, варианты полученные в результате деления искусственно ухудшаем на некую величину (опция, по умолчанию 0. Чтобы не умирать в рекурсии, определяем максимальный уровень проваливания. Эту операцию пришлось добавить, т.к. 1), чтобы вариант прямого сопоставления был более ценным. Увы, таковы особенности русского языка. подстроки типа «двапать» успешно делились на токены «два» и «пять», а не приводились к «двадцать».

    25. Пример: токен «двапать» имеет прямое сопоставление с образцом «двадцать», ошибка 0. 25 (замена «а» на «я»), ухудшенная искусственно до 0. Кроме того, лучшим вариантом деления является «два» + «пять» стоимостью 0. 35, в результате чего предпочтение отдается токену «двадцать».

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

67). Кроме того, в основной алгоритм генерации числа вводится проверка токенов, чтобы их ошибка не превышала некую величину (опция, по умолчанию 0. С помощью этого мы отсеиваем потенциальный мусор, хотя и не очень успешно.

Алгоритм в двух словах для тех, кому было лень читать текст выше

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

Заточка алгоритма под конкретную задачу

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

Дальнейшее улучшение

У существующего алгоритма есть и недоработки:

  1. Контроль падежей. Строки «две тысячи» и «два тысячей» будут с нулевой ошибкой распознаны как 2000. В моей задаче контроль падежей не требуется, он даже вреден, но если вам нужна такая функция, это решается введением дополнительного флага в токен, отвечающего за падеж следующего токена.
  2. Отрицательные числа. Вводится дополнительный токен «минус» с особой обработкой. Ничего сложного, но не забудьте, что буква «у» является плохой, и не встречается в числительных, нужно будет изменить ее весовые характеристики или надеятся, что она не изменится в процессе OCR.
  3. Дробные числа. Решается заменой типа long на double и введением токенов «десятых», «сотых» и т.п… Не забудьте пересмотреть весы букв.
  4. Распознавание чисел, введенных пользователями. Т.к. при вводе текста вручную мы чаще всего допускаем ошибки, связанные с переТСановкой сиВМолов, следует добавить эту операцию в алгоритм Вагнера-Фишера.
  5. Поддержка других языков. Вводим новые токены, расширяем таблицу весов.
  6. Обработка мусора. В некоторых документах на данные налезает печать, качество изображением может быть плохим, ячейка может быть банально пустой. В этом случае в строку попадает мусор, который нужно как-то чистить. Лучшее, что я могу предложить на данный момент – производить предварительную обработку документа перед OCR. Мне очень сильно помогло удаление линий таблицы и заливка их цветом, близким к цвету свободного пространства ячейки. Это не решило все проблемы, но улучшило качество распознавания текста с документов, где таблица имела искривления из-за помятости документа или криворукого фотографа. В идеале стоит доворачивать саму ячейку и распознавать ее отдельно, если у вас, конечно, вообще имеется таблица.

Вот скриншот результатов: В проекте есть пример консольного приложения, бегущего по файлу samples.txt с примерами для парсера.

Величина ошибки для реальных примеров распознавания не превышает 0. Оценивать результат поручаю вам, но как по мне, он неплох. 25, хотя я еще не прогонял весь набор имеющихся документов, наверное, не все там будет так гладко.

Также программа дала вполне себе адекватный ответ, сколько нужно принимать на посошок (я не употребляю, но все же) и даже точно определила значение древнерусского слова «тьма». Что касается последнего раздела, мне всегда было интересно, сколько же это – «дофига». И да, в вывод не вошла еще одна мера, которую воспитание добавить не позволило, но программа считает, что она равна тысяче =)

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

NET Standart 2. Сама библиотека написана под . 0 и C# 7.x, а алгоритмы легко переводятся на другие языки.

CV. На случай возможного расширения библиотеки добавлю состав важных составляющих парсера чисел прописью (пространство имен Genesis. NumberUtils):

  • RussianNumber.cs – непосредственно парсер
  • RussianNumber.Data.cs – файл с описанием токенов
  • RussianNumber.ToString.cs – конвертер числа в текст прописью
  • RussianNumberParserOptions.cs – опции парсера
  • NumeralLevenshtein.cs – реализация алгоритма Вагнера-Фишера
  • NumeralLevenshteinData.txt – ресурс, данные весов букв

Использование:

  • RussianNumber.ToString(value) – преобразование числа в текст
  • RussianNumber.Parse(value, [options]) – преобразование текста в число

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

Посмотрите другие: Понравилась статья?

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть