Использование расстояния Левенштейна в проверке орфографии

Question

Я работаю над проверкой орфографии в C ++ и застрял на определенном этапе реализации.

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

Теперь сложная часть: что, если введенная строка представляет собой комбинацию слов с ошибками?Например, "iloevcokies".Учитывая, что «i», «love» и «cookies» - это слова, которые можно найти в текстовом файле, как я могу использовать уже реализованную функцию Левенштейна, чтобы определить, какие слова из файла подходят для исправления?Кроме того, как бы я вставил пробелы в правильные позиции?

Любая идея приветствуется:)

Answer 1

Корректировка орфографии для фраз может быть выполнена несколькими способами. Один из способов требует наличия индекса слова би-граммы и три-граммы. Это, конечно, может быть огромным. Другой вариант - попробовать перестановки слова со вставленными пробелами, а затем выполнить поиск по каждому слову в результирующей фразе. Взгляните на простую реализацию проверки орфографии от Peter Norvig от Google. В любом случае, рассмотрите возможность использования индекса n-граммы для повышения производительности, для справки есть библиотеки, доступные на C ++.

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

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

Answer 2

Я предполагаю, что у вас есть существующий индекс, по которому вы пробегаете свое расстояние Левенштейна (например, Trie, но любой отсортированный индекс обычно работает хорошо).

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

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

Answer 3

Отправная точка для идеи: один из главных хитов вашего L-расстояния для "iloevcokies" должен быть "куки".Если вы можете изменить функцию L-расстояния так, чтобы она также отслеживала и возвращала минимальный и максимальный индексы (т. Е. Это соответствие лучше всего начинать с символа 5 и переходить к символу 10), то вы можете удалить эту подстроку и повторно проверить L-дистанция для строки до и после нее, затем объединить их для предложения ....

Просто мысль, удачи ....