РАЗДЕЛ 2
АЛГОРИТМЫ И МОДЕЛИ АВТОМАТИЧЕСКОЙ ИДЕНТИФИКАЦИИ И КОРРЕКЦИИ ТИПОВЫХ ОШИБОК
ПОЛЬЗОВАТЕЛЯ НА ОСНОВЕ СЛОВАРЯ ДОПУСТИМЫХ СЛОВ
2.1. Общие положения
Сущность общего метода автоматической идентификации и коррекции по словарю
(АИК) [36, 59] заключается в варьировании обратных искажений ошибочного слова
определенным набором ошибок, поиске соответствующих ближайших слов в словаре,
принятии решения относительно ошибки, которая произошла, и в выборе слова для
коррекции. Уточним для данного метода понятие «ближайшего» слова и связанного с
ним понятия «расстояние», которое, в общем, есть основой введения метрики в
пространстве ошибок ([59], анализ возможных метрических зависимостей между
типовыми ошибками пользователя выполнен совместно с
Кузьменко Г.Е. и Ходаком В.И.).
Как известно, метрика представляет собой число , определяющее расстояние между
точками А и В пространства. Точки А и В задаются своими координатами
(признаками):
Известны различные метрики. Это – евклидово расстояние:
метрика Минковского:
,
метрика для описания слов, представленных двоичными признаками (расстояние
Хемминга):
,
где означает сложение по модулю 2.
В последнем случае определяется суммарное количество несовпадающих двоичных
разрядов.
Расстояние Хемминга легко обобщается для произвольных - ичных признаков:
, где .
Например, расстояние между двумя десятичными словами 5743 и 5473 в соответствии
с приведенной формулой равно 2:
Расстояние Хемминга часто используется для введения метрики в пространстве
ошибок в двоичных словах при автоматической коррекции искажений в каналах
связи.
Заслуживает внимания также понятие о синтаксическом расстоянии, предложенном в
[11]: синтаксическим расстоянием между двумя текстами на некотором формальном
языке названа минимальная длина последовательности элементарных преобразований,
переводящей один текст в другой.
Для реализации поставленных целей – коррекции ошибок в алфавитно-цифровых
словах – удобнее всего две последние метрики. В частности, используя обобщенное
расстояние Хемминга, можно было бы значениям поставить в соответствие значения
разрядов эталонного слова, значениям - разряды корректируемого искаженного
слова. В этом случае расстояние определяется количеством несовпадающих позиций
символов так что слово, искаженное однократной транскрипцией, находилось бы от
своего неискаженного эталона на расстоянии «1», а слово, искаженное двукратной
транскрипцией, - на расстоянии «2». Однако, для специфических ошибок
человека такой подход представляется слишком грубым, а в некоторых
отношениях он является и неверным по существу.
Как известно, практический смысл эффективного выбора меры расстояния для
контроля коррекции ошибок в том, чтобы чаще встречающиеся ошибки давали
переходы с меньшим расстоянием, чем более редкие ошибки. Это приводит к
невозможности появления разных по типу ошибок с одинаковым расстоянием и
обеспечивает уверенную коррекцию с минимальными ложными «исправлениями» (а они
принципиально возможны для любых методов автокоррекции). В связи с этим
расстояние типа Хемминговского целесообразно применять для решения о
правильности коррекции, когда кратность ошибок обратно зависят от вероятности
ее появления, и различия в вероятности ошибок различной кратности существенно
велики. Именно эти условия имеют место для статистики случайных ошибок в
каналах связи.
В нашем же случае, для ошибок оператора-пользователя упомянутые закономерности
отсутствуют.
Ошибки типа пропуска символа имеют кратность от 1 до в зависимости от позиции
пропущенного символа, а вероятность такой ошибки близка к вероятности
транспозиции (двукратная ошибка) и не на много меньше вероятности однократной
транскрипции. Поэтому расстояние Хемминга как основа общего правила
автокоррекции в нашем случае не годится. Неадекватно рассматриваемому случаю и
синтаксическое расстояние [11].
Рассмотрим вопрос также с другой стороны. Метрика в некотором пространстве
должна, как известно, удовлетворять трем аксиомам: тождества, треугольника и
симметрии. Это необходимо для обеспечения корректности формальных
преобразований метрических зависимостей, используемых для определенных целей. В
нашем случае расстояние должно служить лишь для оценки схожести корректируемого
слова и эталона, так что явной необходимости в выполнении упомянутых аксиом
нет.
Учитывая все сказанное выше, отметим, что для решающего правила
относительно ближайшего слова в методе АИК, который рассматривается,
классическое понятие „расстояние” неприемлемо и практически может
использоваться лишь одно „крайнее” значение , т.е. полное совпадение двух
слов.
2.2. Основные понятия и определения
2.2.1. Примем такие обозначения, определения и предположения:
- соответственно правильное слово входного сообщения, искаженное слово , в
котором обнаружена ошибка, и некоторое из эталонных слов словаря, для которого
. Будем считать, что значение слов словаря в алфавите длиной символов
равномерно распределены в интервале . Это предположение разрешает при оценке
вероятности совпадения произвольного слова со словарем слова переменной длины
интерпретировать как слова постоянной длины, в которых отброшенные старшие
незначащие символы (в частности, для цифровых значений - нули) доформированы до
максимальной длинны ;
- ранг ошибки класса , который отвечает вероятности появления ошибки. Значения
вероятностей [10] и рангов для основных классов ошибок пользователя приведены в
табл. 2.1, укрупняющей детализированные данные табл. 1.1.
Вариация - некоторое обратное изменение слова в пределах – го класса ошибок
[36]. Например, в классе в