Какое точное определение неправильного слова и как определить правильное?
Что сильнее делает слово неправильным, отсутствие буквы? перестановка? подмена? а какое более неправильное? есть ли разница, в какой позиции слова произошла ошибка, в первом символе или остальных?
Например список слов без ошибок:
море
мор
март
И вот у нас слова:
мар - это мор или март?
маре - это март или море?
так - это
Т.е. первое, нужно определить функцию сравнения слова из анализируемого файла со словами из списка правильных.
Я бы взял уже готовую функцию levenshtein (с разными оценками на типы изменений) и для упрощения например брал бы первое слово из списка с минимальной оценкой ошибки.
Дальше алгоритм
* Если решать в лоб, никаких ресурсов не хватит, просто для каждого слова из списка вычисляешь оценку на ошибку с правильным, перебирая их до тех пор пока не встретится с оценкой 0.
Трудоемкость - квадрат на экспоненту от средней длины слова - т.е. долго
* Предварительно можно исходные анализируемые данные собрать в map слов, чтобы исключить повторения
* Можно чуть чуть оптимизировать этот алгоритм, если слов с ошибкой в исходном файле мало, перед сравнением искать слово по словарю, построив map заранее, и искать первую минимальную ошибку сравнения, т.е.
для правильных слов использовать максимально быстрый алгоритм поиска, исключив их из медленного алгоритма сравнения
* Дальнейшая оптимизация - расширение последнего шага - можно заранее создать структуру в памяти для всех возможных значений строк
с единичным изменением правильных слов (т.е. для каждого правильного слова поместить в map это измененное слово и ссылку на правильное) - получим массив ошибочных слов с ошибкой 1, т.е. все слова с ошибкой 1 могут быть обнаружены со скоростью работы map, так как количество изменений в данном случае сравнимо с количеством используемых символов (умножить на 3) а в задаче речь о словах, т.е. количество символов мало? то на каждое слово в map будет 3*n записей
* Точно так же можно сделать массив всех ошибочных слов для 2-ух изменений (например 1-изменение на каждую запись от списка с 1-изменением)
* 3-ех,..4-ех и т.п.
Очевидно что хранить в памяти такое количество данных очень дорого (можно не хранить в map сами значения, а только хеши для поиска и разруливание коллизий использования этого хеша), плюс предварительное заполнение таких массивов долгое, и имеет смысл только для небольшой глубины (например известно что основное количество ошибочных слов имеет малое количество ошибок, а слова с большим количеством ошибок бесполезны - в реальной задаче поиска ошибок так и есть, никого не интересует случаи когда в слове все буквы ошибочны, обычно речь идет о 2-3 ошибках)
* Дальнейшая оптимизация - перевернуть алгоритм на поиск в ширину по графу всех возможных изменений правильных слов (это не дерево а граф, так как правильные слова за конечное количество изменений будут переходить друг в друга или другие ошибочные слова, созданные из других правильных слов), т.е. запускаем поиск и на каждом шаге делаем сравнение полученной строки с ошибкой со всеми словами из анализируемого списка, тут поиск быстрый по map)
Этот подход имеет смысл если анализируемых слов сильно много (и они все с ошибками) и накладные расходы на сравнение со всеми комбинациями ошибок - не велики, по памяти - она так же потребуется на поддержание самого поиска в ширину