Повышение эффективности работы опечаточника
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
?ся значительными.
Обобщения
Разные цены операций
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии, разную вероятность разных ошибок при вводе текста и т. д. В общем случае:(a, b) - цена замены символа a на символ b
w(?, b) - цена вставки символа b
w(a, ?) - цена удаления символа a
Формула
Здесь и далее считается, что элементы строк нумеруются с первого, как принято в математике. Пусть S1 и S2 - две строки (длиной M и N соответственно) над некоторым алфавитом, тогда редакционное расстояние d(S1,S2) можно подсчитать по следующей рекуррентной формуле
где m(a,b) равна нулю, если a = b и единице в противном случае; min(a,b,c) возвращает наименьший из аргументов.
Алгоритм Вагнера - Фишера
Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера - Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).
Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма:
для всех i от 0 до M
для всех j от 0 до N
вычислить D(i, j)
вернуть D(M,N)
Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений:(0,0) = 0
для всех j от 1 до N(0,j) = D(0,j-1) + цена вставки символа S2[j]
для всех i от 1 до M(i,0) = D(i-1,0) + цена удаления символа S1[i]
для всех j от 1 до N(i,j) = min((i-1, j) + цена удаления символа S1[i],(i, j-1) + цена вставки символа S2[j],(i-1, j-1) + цена замены символа S1[i] на символ S2[j]
вернуть D(M,N)
Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M,N) в левый верхний, на каждом шаге ища минимальное из трёх значений:
если минимально (D(i-1, j) + цена удаления символа S1[i]), добавляем удаление символа S1[i] и идём в (i-1, j)
если минимально (D(i, j-1) + цена вставки символа S2[j]), добавляем вставку символа S1[i] и идём в (i, j-1)
если минимально (D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]), добавляем замену S1[i] на S2[j] (если они не равны; иначе ничего не добавляем), после чего идём в (i-1, j-1)
Здесь (i, j) - клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.
Различные модели ошибок опечаточников
Одно из первых упоминаний о проблематике исправления орфографических ошибок можно найти в работе Дамеро [1]. В ней коррекция ошибок предполагает поиск проверяемого слова в эталонном словаре и в случае, если слово отсутствует в словаре, то предлагаются близкие варианты.
В случае поиска по Web для коррекции ошибок в запросах вариант ручной проверки малоэффективен, поэтому используется статистическая языковая модель на основе запросов пользователей. Данный подход прост, но недостаточно эффективен. Отмечается, что если данные содержат опечатки, то опечаточник не будет их исправлять. Эрик Брилл и Роберт Мур предлагают решить эту проблему с помощью более сложной модели ошибок.
Варианты с использованием модели ошибок описаны в работах Цобеля и Дарта[2][3]. В них описывается, что модель ошибок учитывает несколько параметров: статистические данные о реальных опечатках, фонетическую близость слов, а так же близость на клавиатуре. Они также проводили сравнение алгоритмов анализа строк по произношению, и отметили, что этот вариант, плохо подходит для общей задачи коррекции опечаток.
Помимо модели ошибок хорошим средством повышения качества работы опечаточника является использование контекста. Суть метода заключается в анализе слов используемых по-соседству с проверяемым. Но для построения контекстной расширенной модели требуются значительные объемы данных.
Несмотря на наличие расширенной модели языка и достаточно полной и точной модели ошибок, остаются слова с опечаткой, которые не могут исправиться, так как их рейтинг в модели языка слишком велик и модель ошибок не может это компенсировать. А так же слова с более чем одной ошибкой, которые часто исправляются на слова с одной опечаткой. С точки зрения быстродействия сложно и малоэффективно создавать модель ошибок, которая бы покрывала эти проблемные места.
Большинство русских программ проверки орфографии исправляют только однобуквенные опечатки, потому что многобуквенные составляют не более нескольких процентов от их общего количества: как правило, встречаются лишь опечатки типа "баблики с муком". Нежелание разработчиков закладывать в свои программы поиск многобуквенных опечаток объясняется гибкостью русского языка по сравнению с английским, из-за чего список подсказок на русское слово с двумя опечатками получается недопустимо велико.
Исходя из всего этого, можно сделать вывод, что создать универсальную модель ошибок, являющуюся наилучшей в любой ситуации, создать не удается. Во всех вариантах имеются свои плюсы и минусы.
Используемая схема работы
При проведении данной работы использовалась следующая схема работы опечаточника:
Исполь?/p>