Сравнение слова с целенаправленными словами в словаре

Question

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

Я уже придумал алгоритм сравнения (например, Needleman-Wunsch then Levenshtein distance) и т. Д., Но застрял, когда выяснилось, какие слова в словаре-hashmap сравнить слово с i.e. «hellooo».

Я не могу сравнить «ohelloo» [следует исправить «привет» каждому слову в словаре b/c, который займет слишком много времени, и я не могу сравнить его со всеми словами в словаре, начиная с «o» b/c он должен быть «привет».

Любые идеи?

Answer 1

Наиболее распространенные орфографические ошибки

• Удалить письмо (меньше слова или слово раскол)
• свопа смежных букв
• Alter письмо (QWERTY соседних букв)
• Вставить письмо

Некоторые сообщения говорят о том, что 70-90% ошибок относятся к вышеуказанным категориям (расстояние редактирования 1)

Посмотрите на приведенный ниже адрес, который предлагает решение для одиночных или двойных ошибок (отредактируйте расстояние 1 или 2). Здесь есть все, что вам нужно!

How to write a spelling corrector

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

--Based на OP-х comment-- Если вы не хотите, чтобы предварительно вычислять все возможные изменения, а затем поиск на карте, я полагаю, что вы используете Patricia (radix tree синтаксического дерева) вместо HashMap. К сожалению, вам снова понадобится обработать «ошибку первой буквы» (например, удалить первую букву или сначала поменять местами со второй или просто заменить ее соседним Qwerty), и вы можете ограничить свой поиск с высокой вероятностью.

Вы можете даже комбинировать его с дополнительной таблицей индексов или Trie с «обратными» словами или дополнительным индексом, который пропускает первые N символов (например, первые 2), поэтому вы можете ловить ошибки, возникающие только при префиксе.