Алгоритм хотел: найти все слова словаря, похожие на слова в свободном тексте

Ответ 1

Взгляните на http://norvig.com/spell-correct.html для простого алгоритма. В статье используется Python, но в конце есть ссылки на реализации на других языках.

Ответ 2

Вы будете делать довольно много поисков слов против фиксированного словаря. Поэтому вам нужно подготовить словарь. Логически, вы можете быстро устранить кандидатов, которые "слишком разные".

Например, слова 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. Если обе половины входного слова находятся в словаре, но само слово не является, вы можете принять недостающее пространство.

Ответ 3

Вероятно, вы захотите использовать алгоритм, который вычисляет расстояние Левенштейна.

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

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

Одним из этих методов индексирования будет использование дерева сущностей . Другим подходом было бы использовать n-grams.

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

Ответ 4

Может показаться интересным рассмотреть некоторые алгоритмы, такие как расстояние Левенштейна, которое может рассчитать величину разницы между двумя строками.

Я не уверен, на каком языке вы собираетесь использовать, но PHP имеет функцию под названием levenshtein, которая выполняет этот расчет и возвращает расстояние. Также существует функция, называемая similar_text, которая делает аналогичную вещь. Здесь пример кода здесь для функции levenshtein, которая проверяет слово против словаря возможных слов и возвращает самые близкие слова.

Надеюсь, это даст вам некоторое представление о том, как может работать решение!