Создание предложенного алгоритма слова

Question

Я разрабатываю классную проверку орфографии (я знаю, я знаю, что современные браузеры уже имеют это), в любом случае, мне интересно, какие усилия потребуются для разработки довольно простого, но приличного алгоритма подсказки слов.

Моя идея заключается в том, что я сначала посмотрел бы символы слова с ошибкой и посчитал количество символов, которое ему соответствует, в каждом слове в словаре (требует много ресурсов), а затем выбрал 5 лучших совпадений (так что, если слово с ошибкой соответствует большинство символов с 7 словами из словаря, случайным образом отобразит 5 из этих слов в соответствии с предложенным написанием).

Очевидно, что для более углубленного изучения мы бы посмотрели на «общие слова» и получили файл словаря, который пронумерован с рейтингом «частота употребления этого слова в английском языке». Я думаю, что это немного за борт, может быть.

Что ты думаешь? У кого-нибудь есть идеи для этого?

Answer 1

Прежде всего вам нужно будет рассмотреть сложность в поиске «ближе» слов к слову с ошибкой. Я вижу, что вы используете словарь, возможно, хеш-таблицу. Но этого может быть недостаточно. Лучшее и более прохладное решение здесь - использовать структуру данных TRIE . Сложность поиска этих так называемых ближайших слов займет время линейного порядка, и дерево очень легко исчерпать.

Небольшой пример

Возьми слово "njce". Это пример уровня 1, где одно слово явно написано с ошибкой. Ожидаемое очевидное предложение было бы неплохо. Первый шаг очень очевиден, чтобы увидеть, присутствует ли это слово в словаре. Используя функцию поиска TRIE, это может быть сделано O (1) раз, подобно словарю. Более крутая часть находит предложения. Очевидно, вам придется исчерпать все слова, начинающиеся с 'a' до 'z', в которых есть такие слова, как ajce bjce cjce up to zjce. Теперь найти случаи этого типа снова линейно в зависимости от количества символов. Вы не должны увлекаться, умножая это число на 26 слов. Так как TRIE сразу уменьшается по мере увеличения длины. Возвращаясь к проблеме. После того, как будет выполнен поиск, по которому ничего не найдено, вы переходите к следующему символу. Теперь вы будете искать NACE. Фактически вам не придется исследовать все комбинации, поскольку сама структура данных TRIE не будет содержать промежуточных символов. Возможно, в нем не будет ни одного символа, и пространство поиска станет безумно простым. Как и дальнейшие события. Вы можете развить эту концепцию дальше, основываясь на совпадениях второго и третьего порядка. Надеюсь, это помогло.

Answer 2

Я не уверен, сколько колес вы пытаетесь изобрести заново, поэтому вы можете попробовать Lucene .

Apache Lucene Core ™ (ранее называвшийся Lucene Java), наш ведущий подпроект, обеспечивает реализацию индексации и поиска на основе Java, а также проверку орфографии, выделение совпадений и расширенные возможности анализа / токенизации.