Теперь, когда компьютерные инструменты стали повсеместными, я полагаю, вы все используете инструменты для обработки текстов, такие как Microsoft Word. Если да, то вы, вероятно, уже задавались вопросом, как Microsoft Word может предложить вам релевантные слова, если вы неправильно написали слово в своем тексте. В этой статье я отвечу на этот замечательный вопрос и покажу вам, как создать свою собственную систему коррекции орфографии на Java.

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

Алгоритм Soundex

Для начала необходимо немного теоретизировать. Soundex - это фонетический алгоритм, используемый для индексации слов в соответствии со звуками, используемыми для их произношения на английском языке. Цель состоит в том, чтобы получить идентичное представление для омофонов. Напоминаем, что омофоны - это слова с одинаковым фонетическим произношением, но их можно писать по-разному.

Soundex в основном кодирует согласные. Таким образом, гласная не будет кодироваться, если это не первая буква слова. Следует отметить, что Soundex, вероятно, является наиболее известным фонетическим алгоритмом и реализован как стандарт в большинстве программ баз данных от Oracle до PostgreSQL и MySQL.

Конкретно, Soundex создаст код для слова, состоящий из буквы, за которой следуют три цифровые цифры. Буква - это просто первая буква слова, используемого при входе в Soundex. Следующие три цифры соответствуют кодировке остальных согласных.

Чтобы внедрить Soundex, вы должны выполнить следующие 4 шага:

  1. Сохраните первую букву слова. Отбросьте все другие вхождения A, E, I, O, U, Y, H, W.
  2. Замените согласные после первой буквы цифрами следующим образом:
    B, F, P, V → 1
    C, G, J, K, Q, S, X, Z → 2
    D , T → 3
    L → 4
    M, N → 5
    R → 6
  3. Если в исходном слове (до шага 1) соседствуют две или более букв с одной и той же цифрой, сохраняется только первая буква.
  4. Если в вашем слове слишком мало букв, и вы не можете назначить три цифры, правый блокнот с нулями. Если у вас больше трех цифр, вы должны усечь.

Это дает нам следующую реализацию на Java:

Мы можем протестировать выполнение нашей реализации Soundex и увидеть, что мы получаем тот же результат для «Роберта» и «Руперта» с кодом R163:

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

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

Для реализации нашей системы коррекции орфографии нам нужно будет использовать расстояние Левенштейна. Итак, мы реализуем это на Java следующим образом:

Мы можем протестировать выполнение нашей реализации Levenshtein Distance и увидеть значение расстояния между словами «Роберт» и «Руперт», например:

Создание словаря омофонов

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

Чтобы упростить задачу, я использую файл dict.txt, содержащий только слова без диакритических знаков. Каждая строка файла содержит слово, которое дает нам файл следующей формы:

Вы можете скачать файл dict.txt прямо здесь: https://gist.github.com/ssaurel/a3c52eb19c083f78730ee496c8228f91

Чтобы создать словарь омофонов, мы прочитаем каждую строку файла dict.txt, а затем вычислим код Soundex слова. Затем мы добавим это слово в карту, которая может содержать несколько значений для каждого ключа.

Этот тип карты доступен в различных библиотеках кода, например в Google Guava или Apache Commons. В моем случае я использую специальную реализацию под названием MultiMap:

Таким образом, создание нашего словаря омофонов, проиндексированных кодом Soundex каждого слова в нашем файле dict.txt, выполняется следующим образом:

Поиск совпадающих слов

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

Затем мы будем искать омофоны этого слова, вычисляя его код Soundex. Наконец, чтобы отсечь и получить релевантные результаты, мы будем держать только омофоны с расстоянием Левенштейна строго меньше 3 с нашим словом исправлять.

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

Это дает нам следующий полный код для класса Main нашей Системы исправления орфографии:

Наша система исправления орфографии в действии

Лучшая часть учебника здесь, так как мы собираемся задействовать нашу систему коррекции орфографии. Слово неправильно написано - «revoluton».

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

Итак, наша система исправления орфографии показывает нам, что лучший результат для исправления слова «revoluton» - это «революция», что является отличным результатом.

Не стесняйтесь использовать комментарии, если у вас есть вопросы по этому руководству.