Алгоритм для сравнения слов (не в алфавитном порядке)
Некоторое простое решение будет выглядеть как
words.replace(/(\n)/g," ");
7 ответов
Вы хотите прочитать, как это делает Google: http://norvig.com/spell-correct.html
Изменить: некоторые люди упоминали алгоритмы, которые определяют метрику между пользовательское слово и слово-кандидат (levenshtein, soundex). Однако это не полное решение проблемы, так как для эффективного выполнения неевклидова поиска ближайшего соседа также потребуется структура данных. Это можно сделать, например, с помощью Дерева обложек: http://hunch.net/~jl/projects/cover_tree/cover_tree.html
Распространенным решением является вычисление расстояния Левенштейна между вводом и фиксированными текстами. Расстояние Левенштейна для двух строк - это просто количество простых операций - вставки, удаления и замены одного символа - необходимых для превращения одной строки в другую.
Рассматривали ли вы алгоритмы, которые сравнивают фонетическими звуками, такими как soundex ? Не должно быть слишком сложно создать звуковое представление вашего списка слов, сохранить их, а затем получить звуковой индекс пользовательского ввода и найти там наиболее близкое совпадение.
Найдите алгоритм Bitap. Он хорошо подходит для того, чем вы хотите заниматься, и даже поставляется с примером исходного кода в Википедии.
Если ваш набор данных действительно невелик, достаточно просто сравнить расстояние Левенштейна по всем элементам независимо друг от друга. Однако, если он больше, вам потребуется использовать BK-Tree или аналогичную систему индексации. В статье, на которую я ссылаюсь, описывается, как найти совпадения в пределах заданного расстояния Левенштейна, но ее довольно просто адаптировать для поиска ближайшего соседа (и оставлено как упражнение для читателя;)
Хотя это может не решить всю проблему, вы можете рассмотреть возможность использования алгоритма soundex как части решения. Быстрый поиск в Google "soundex" и "python" показал некоторые реализации алгоритма на языке Python.
Попробуйте поискать "расстояние Левенштейна" или "расстояние редактирования". Он подсчитывает количество операций редактирования (удаление, вставка, изменение буквы), необходимых для преобразования одного слова в другое. Это общий алгоритм, но в зависимости от проблемы вам может потребоваться что-то особенное с разным весом для разных типов опечаток.