Вы будете делать несколько поисков слов по фиксированному словарю. Поэтому вам нужно подготовить свой словарь. По логике вещей, вы можете быстро исключить кандидатов, которые «просто слишком разные».
Например, слова car и dissimilar могут иметь общий суффикс, но они очевидно не являются орфографическими ошибками друг друга. Теперь, почему это так очевидно для нас, людей? Для начала длина совсем другая. Это немедленная дисквалификация (но с одним исключением - ниже). Итак, ваш словарь должен быть отсортирован по длине слова. Сопоставьте введенное слово со словами одинаковой длины. Для коротких слов это означает +/- 1 символ; более длинные слова должны иметь больший запас (насколько точно ваше демографическое заклинание?)
Как только вы ограничите себя кандидатами в слова одинаковой длины, вы захотите удалить слова, которые совершенно не похожи друг на друга. Под этим я подразумеваю, что они используют совершенно разные буквы. Это проще всего сравнить, если отсортировать буквы в слове по алфавиту. Например. car становится "acr"; rack становится "ackr". Вы будете делать это при предварительной обработке для вашего словаря и для каждого входного слова. Причина в том, что дешево определить (размер) разницу двух отсортированных наборов. (Добавить комментарий, если вам нужно объяснение). car и rack имеют разницу в размере 1, car и hat имеют разницу в размере 2. Это еще больше сужает набор кандидатов. Обратите внимание, что для более длинных слов вы можете выручить рано, когда вы нашли слишком много различий. Например. dissimilar и biography имеют общую разницу в 13, но, учитывая длину (8/9), вы, вероятно, сможете выручить, когда найдете 5 отличий.
Это оставляет вам набор слов-кандидатов, которые используют почти одинаковые буквы, а также имеют практически одинаковую длину. С этого момента вы можете начать использовать более совершенные алгоритмы; вам больше не нужно выполнять 150 000 сравнений для каждого входного слова.
Теперь, для исключения длины, упомянутого ранее: проблема в «словах», подобных greencar. Это не совсем соответствует слову длины 8, но для людей совершенно очевидно, что это значит. В этом случае вы не можете по-настоящему разбить входное слово на любой случайной границе и выполнить дополнительные неточные совпадения N-1 для обеих половин. Однако выполнимо проверить только пропущенное место. Просто найдите все возможные префиксы. Это эффективно, потому что вы будете использовать одну и ту же часть словаря снова и снова, например, g gr, gre, gree и т. Д. Для каждого найденного префикса проверьте, есть ли оставшийся суффикс в словаре, например, reencar, eencar. Если обе части входного слова есть в словаре, а само слово - нет, можно предположить пропущенный пробел.