Где используется исправление опечаток

 

1)    Исправление опечаток реализовано в поисковых системах (при введении запросов пользователями)

§ Google

Функция Google Suggest, которая помогает уточнить поисковый запрос, исправляет опечатки, транслитерирует слова и в случае необходимости меняет раскладку клавиатуры

§ Яндекс

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

§ Rambler

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

2)    Существуют программы для исправления раскладки клавиатуры

·   Punto Switcher - программа для автоматического переключения между различными раскладками клавиатуры в операционных системах семейства Microsoft Windows и Mac OS X. Работая в фоновом режиме, Punto Switcher проводит статистический анализ последовательностей вводимых символов слова, и, если сочетание букв оказывается нетипичным для языка, на котором вводятся символы, Punto Switcher переключает язык ввода, стирает напечатанное, эмулируя нажатия клавиши ← Backspace, и повторно вводит текст уже с правильной раскладкой клавиатуры.

·   Keyboard Ninja - это компьютерная программа для операционных систем Microsoft Windows, предназначенная для автоматического переключения раскладки клавиатуры при наборе текста и автоматического исправления ошибочно набранного не в той языковой раскладке текста. Например, если набрано ghbdtn, программа автоматически исправляет данный текст на привет.

3)    Существуют специальные программы для исправления опечаток в тексте

Microsoft Word (часто - MS Word, WinWord или просто Word) - текстовый процессор, предназначенный для создания, просмотра и редактирования текстовых документов, с локальным применением простейших форм таблично-матричных алгоритмов.

OrfoCheck - программа для проверки текстов на опечатки. В отличие от Word'а и других программ проверки орфографии слова проверяются не по словарю правильных слов, а по словарю опечаток.

 

Алгоритмы, используемые опечаточниками

 

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

 

Алгоритм нечеткого поиска

 

Алгоритмы нечеткого поиска являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

Задачу нечеткого поиска можно сформулировать так:

«По заданному слову найти в тексте или словаре размера n все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом k возможных различий».

Например, при запросе «Машина» с учетом двух возможных ошибок, найти слова «Машинка», «Махина», «Малина», «Калина» и так далее.

Алгоритмы нечеткого поиска характеризуются метрикой - функцией расстояния между двумя словами, позволяющей оценить степень их сходства в данном контексте. Строгое математическое определение метрики включает в себя необходимость соответствия условию неравенства треугольника (X - множество слов, p - метрика)

 

 

 

В числе наиболее известных метрик - Левенштейна и Дамерау-Левенштейна.

 

Расстояние Левенштейна

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

Применение

Расстояние Левенштейна и его обобщения активно применяется:

·   для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированого текста или речи).

·   для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» - файлы.

·   в биоинформатике для сравнения генов, хромосом и белков.

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) - удалить, I (англ. insert) - вставить, R (replace) - заменить, M (match) - совпадение.

Например, для 2-х строк «CONNECT» и «CONEHEAD» можно построить следующую таблицу преобразований:

MMMRRRRI

Найти только расстояние Левенштейна - более простая задача, чем найти ещё и редакционное предписание.

Недостатки

С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:

.   При перестановке местами слов или частей слов получаются сравнительно большие расстояния;

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

Обобщения

Разные цены операций

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность мутаций в биологии, разную вероятность разных ошибок при вводе текста и т. д. В общем случае:(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 равноценных редакционных предписания.