Как работает ПРОВЕРКА ЗАПИСАНИЯ

Как работает ПРОВЕРКА ЗАПИСАНИЯ

Мы видим и используем корректор орфографии каждый день, когда используем Google или любое мобильное устройство. Мне всегда было интересно, как они исправляют мое неправильное написание и рекомендуют мне правильное слово.

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

Исправление ошибок, отличных от слов

Шаг 1.
Определите неслово в предложении, проверив каждое слово, существует ли оно в словаре или нет.
Предположим, у нас есть нашел это слово «та» как слово ошибки.

Шаг 2:
Поскольку мы можем угадать, правильным словом будет «тот» или вторым лучшим словом будет «это».
А что, если это слово «ужас». Здесь мы можем угадывать такие слова, как «актер», «поперек» и т. Д.
В общем, нам нужен набор реальных слов, которые похожи на ошибку.

Вопрос: как выбрать слова, похожие на ошибку?

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

Алгоритм минимального расстояния редактирования:

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

Подробнее об операции.

операция удаления:
удаление буквы из ошибки для получения реального слова.
пример:
«controal» - - ›после удаления« a »становится« control »< br /> Здесь Edit Distance = 1

Операция вставки:
Нам пришлось вставить букву по ошибке, чтобы получить реальный пример слова
;
«contrl» → после вставки «o» мы получаем «control
Здесь Edit Distance = 1

Операция замены:
Очевидно, что мы должны подставить букву, чтобы получить настоящее слово.
пример:
«cuntrol» → после замены «o» становится «Control»
Здесь Edit Distance = 1

Операция транспонирования:
здесь мы должны поменять местами две последовательные буквы.
пример;
«contorl» → после перестановки «ro» получаем «control» < br /> Здесь Edit Distance = 1

ПРИМЕЧАНИЕ. Если любая из вышеперечисленных операций выполняется один раз, то Edit Distance = 1, а если дважды с одной и той же ошибкой, то Edit Distance = 2.
Мы можем использовать только слова с Edit Distance = 1 просто так. простоты, так как около 70–80% слов содержат одну ошибку.
Для большей точности мы можем добавить слова с помощью Edit Distance 2 в нашу модель, и этого достаточно для решения задачи.

Продолжение шага 2:
Найдите слова, которые находятся на расстоянии редактирования 1 и 2 от ошибки.
Теперь у нас есть набор реальных слов, похожих на ошибку.

Шаг 3:
Теперь наша цель - найти наиболее подходящее слово для обозначения ошибки. Для этой цели мы будем использовать Оценка максимального правдоподобия.
Предположим, что x - это опечатка, а w - слово из списка похожих слов (W), и для каждого w нам нужно вычислить следующее.

w_estimate = P(w|x) (using Bayes Rule)
  = P(x|w) P(w)/P(x)  
   (we can remove P(x) as it is constant for all w)
  = P(x|w) P(w)

где P (w) - априорная или вероятность w
, а P (x | w) - вероятность x при заданном w

Теперь задача состоит в том, чтобы вычислить априорность и вероятность.

Prior:
Из любого заданного корпуса мы можем напрямую вычислить вероятность слов (P (w))

Вероятность:

Вычислить P (x | w) - немного сложная задача. Поскольку мы должны измерить, насколько вероятно, что не-слово произойдет с реальным словом. Другими словами, мы можем вычислить вероятность операции. Пример. В случае замены буквы «m» на «n» мы можем вычислить, как часто они заменяются, и аналогично для других операций.

Результат:

Поскольку w_estimate = Prior * правдоподобие
Теперь мы можем выбрать реальное слово с наилучшей оценкой, и наш Корректор орфографии готов.

Не стесняйтесь комментировать и задавать вопросы. Следите за новостями о НЛП.