Это хорошо изученная проблема, и для этого есть много хороших алгоритмов. Большинство из них работают, создавая какую-то структуру данных для хранения всех допустимых слов таким образом, чтобы слова с одинаковым расстоянием редактирования можно было найти эффективно. Неформально, расстояние редактирования между двумя строками - это количество изменений, которое вам нужно сделать, чтобы преобразовать одну строку в другую. Например, учитывая слова «misspell» и «mispell», расстояние редактирования равно единице (просто вставьте еще одно 's' в слово), а расстояние редактирования между "cat" и "dog" равно трем (замените каждую букву) .
Слово с ошибкой, вероятно, находится на небольшом расстоянии редактирования от слова, которое было предназначено, поэтому, если вы можете хранить слова таким образом, чтобы вы могли, для любой строки, запрашивать слова, которые находятся на небольшом расстоянии редактирования от В строке можно указать список возможных слов, которые мог иметь в виду пользователь.
Одной общей структурой данных для хранения этих данных является trie , структура дерева с 26 путями, где каждый узел хранит префикс слова, а каждое ребро соответствует добавлению некоторой буквы к текущему префиксу. Если у вас есть такая структура, вы можете найти слова, которые «близки» к определенному слову (возможно, на определенном расстоянии редактирования), используя простой рекурсивный поиск по дереву. В каждой точке следите за тем, как далеко от редактируемого расстояния вы хотите быть вдали от целевого слова и сколько слов с орфографической ошибкой вы обработали до сих пор. В каждой точке вы можете либо следовать за ребром в дереве, соответствующем букве в слове, либо использовать одно расстояние редактирования, чтобы вставить новую букву, следуя за другим ребром в дереве.
Другой структурой данных, которая часто используется для этого, является BK-дерево , которое хранит строки таким образом, чтобы вы могли эффективно запрашивать все слова на определенном расстоянии редактирования от некоторой исходной строки. Это напрямую решит вашу проблему, хотя в Интернете меньше ресурсов о том, как создавать BK-деревья, по сравнению с попытками.
Как только вы найдете слова, которые находятся на некотором расстоянии редактирования, вы, вероятно, захотите как-то их ранжировать, прежде чем представлять их пользователю. Это требует, чтобы вы имели представление о том, какие опечатки люди обычно делают на практике. Общие опечатки включают
- Транспозиции , где две буквы поменялись местами: «thme» вместо «них»
- Подстановки , где используется неправильная буква: «арифметическая» вместо «арифметическая»
- Удалений , где пропущена буква: "привет" вместо "привет"
- Повтор , где дублируется буква: "завтра" вместо "завтра"
Чтобы построить хорошую проверку орфографии, в идеале у вас должны быть какие-то вероятности, связанные с каждым типом ошибки. Таким образом, когда у вас был список возможных исправлений, вы могли ранжировать их от наиболее вероятных до наименее вероятных.
Надеюсь, это поможет!