Каждый из нас из школы помнит определение Евклидова расстояния между двумя точками на плоскости. С помощью расстояния Евклида можно вычислить расстояние между двумя точками на карте, например, между вашим местоположением и станцией метро. Но для пешехода в Нью-Йорке расстояние между двумя точками в городе будет отличаться от расстояния Евклида между двумя точками из-за невозможности передвигаться иначе, как по проезжим улицам, пересекающимся под прямыми углами. Такое расстояние так и называется: "расстояние городских кварталов" или манхэттенское расстояние. При любом способе расстояние характеризует меру близости точек. В сегодняшней статье мы расскажем о способах вычисления расстояния между двумя словами.

Расстояние между двумя точками и в городе можно вычислить различными способами (см. примеры на рис. 1). В случае отсутствия препятствий оно может быть оценено евклидовым расстоянием, вычисленным как  (красный отрезок на рис. 1). Из-за городской застройки для пешехода логично использовать манхэттенское расстояние, вычисляемое как (черная траектория на рис. 1). А для автомобилиста расстояние, оцененное одометром, может отличаться и от Евклидова, и от манхэттенского расстояния (фиолетовая ломаная на рис. 1). То есть для автомобилиста расстояние между двумя точками в городе может отличаться и от евклидова, и от манхэттенского расстояния.

Расстояние как мера близости вычисляется не только для точек на плоскости или точек n-мерного пространства, но и для объектов различной природы. Например, может быть вычислено расстояние между графиками функций или расстояние между распределениями случайных величин. Известно большое число различных расстояний, но для решения новых задач мы можем сами придумывать новые расстояния. Расстояние или метрика d между двумя объектами должно быть неотрицательной функцией двух аргументов, которая удовлетворяет 3-м аксиомам:

• аксиома тождества:

• аксиома симметрии:

• неравенство треугольника:

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

В качестве объектов могут выступать слова (строки) или последовательности символов. Так же, как и расстояние между двумя точками на плоскости, расстояние между двумя словами может вычисляться различными способами. Простым способом является расстояние Хэмминга между словами одинаковой длины – это количество позиций, в которых соответствующие символы слова отличаются.

Мы будем рассматривать задачу отождествления слов при анализе распознанных образов документов. Известно много задач анализа текстовых документов. К ним относятся: классификация документов, извлечение данных, анализ тональности и другие. Решение таких задач может основываться на словах. Если мы заранее создали словари – наборы слов, каждое из которых может быть снабжено дополнительными признаками, мы можем попробовать найти эти слова в анализируемом тексте. Некоторые слова будет найдены однозначно, некоторые слова найдены не будут, а для некоторых слов найдётся несколько совпадений. Термин "найдены" означает, что для слова из словаря и слова текста мы можем сказать, что эти слова тождественны. Простейшее отождествление состоит в проверке совпадения всех символов, то есть и .Такое отождествление будет работать, если анализируемый текст не содержит ошибок или число ошибок (опечаток) мало.

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

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

Для сравнения словарного и распознанного слов мы будем использовать популярное расстояние Левенштейна (редакционное расстояние), основанное на редакционных операциях вставки, удаления и замены символа. Расстояние было описано Владимиром Левенштейном для бинарных последовательностей ещё в 1960 году. Известны различные алгоритмы вычисления расстояния Левенштейна, позволяющие найти как число операций для нахождения редакционного предписания, так и последовательность операций. Оригинальное расстояние Левенштейна между двумя текстовыми строками и определяется как минимальное число редакционных операций для трансформации в . Оригинальное расстояние Левенштейна вычисляется следующим образом:

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

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

Некоторые ошибки OCR не являются случайными. Ошибочное распознавание образа символа "Х" как символа "О" маловероятно. В то же время образ символа "Ъ" может быть ошибочно распознан как символ "Ь" из-за сходства образов "Ъ" и "Ь". Примерами сходных образов для латинского алфавита являются пары символов “B8”, “DO”, “1I”. То есть, некоторые ошибки распознавания символов случаются чаще, чем другие. Поэтому можно уточнить штрафы за несовпадение символов, заданные с помощью функции . Для этого нужно построить так, чтобы при вычислении расстояния Левенштейна штраф за сходные символы был меньше, чем за символы несходные. Выберем такую функцию для цены операции замены символа, чтобы для одинаковых символов она была равна нулю, для различных несходных символов - равна 1.0, а для сходных же символов была невелика. Описанная модификация позволяет уменьшить расстояние, вычисляемое для слов с ошибками в виде сходных символов. Например, если при стандартной цене операции сравнения , то при получаем

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

Эти близкие слова, размещенные в тексте документа отождествлять нежелательно. Например, ключевое слово АДРЕС из статического текста не должно отождествляться со словом АНДРЕЙ из заполнения поля документа. Идентификаторы TF-3201-302 и TF-3201-301 сходны, но различие в один символ как раз и является признаком того, что идентификаторы различным.

На вопрос из заголовка статьи мы можем дать чёткий ответ: расстояние между словами "Будапештом" и "Бухарестом" равняется 3 при использовании расстояния Левенштейна или расстояния Хэмминга. Нормализованное расстояние Левенштейна между слова "Будапештом" и "Бухарестом" равняется 0.26.

Но можем ли мы отождествить слова "Будапештом" и "Бухарестом"? Такое решение может быть принято только в контексте конкретной задачи. Если мы извлекаем реквизит "место рождения", то отождествить нельзя. Если же мы ищем слово "Будапештом" в некотором документе, в котором появление слова "Бухарестом" маловероятно, то отождествить можно.

Пример сходства слов "Будапештом" и "Бухарестом" является умозрительным, а в реальных документах часто различать следующие слова из статического текста: "КРЕДИТНОЙ" и "КРЕДИТНОГО", "ВЫДАН" и "ВЫДАЧИ", "СЕРИЯ" и "СЕРИЯ,№" и т.д.

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

Для исключения рассмотренных случаев ложного отождествления предлагается применять шаблоны словарных слов следующего вида:

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

Применение описанных модификаций превращает расстояние Левенштейна в новое расстояние между словарным словом и распознанным словом :

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

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

Расстояние Левенштейна является адекватным способом сравнить два слова. Мы рассказали о модификации расстояния Левенштейна для отождествления распознанных слов документа и слов из модели (словаря). Существует возможность придумать и другие функции для сравнения слов. Если придумаете, то напишите статью и расскажите об особенностях вашей метрики!