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

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

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

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

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

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

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

Например, слова автомобиль и разнородные могут иметь общий суффикс, но они очевидно не являются орфографическими ошибками друг друга. Почему это так очевидно для нас, людей? Для начала длина совсем другая. Это немедленная дисквалификация (но за одним исключением - ниже). Итак, ваш словарь должен быть отсортирован по длине слова. Сопоставьте введенное слово со словами одинаковой длины. Для коротких слов это означает +/- 1 символ; более длинные слова должны иметь больший запас (насколько хорошо ваша демографическая запись?)

Как только вы ' Если вы ограничились словами-кандидатами одинаковой длины, вы бы хотели исключить слова, которые совершенно не похожи друг на друга. Я имею в виду, что они используют совершенно разные буквы. Это легче всего сравнить, если вы отсортируете буквы в слове по алфавиту. Например, автомобиль становится «acr» ; стойка становится «ackr» . Вы сделаете это при предварительной обработке словаря и каждого входного слова. Причина в том, что дешево определить разницу (размер) двух отсортированных наборов. (Добавьте комментарий, если вам нужно объяснение). автомобиль и стойка имеют разницу в размере 1, автомобиль и шляпа имеют разницу в размере 2. Это сужает ваш набор кандидаты даже дальше. Обратите внимание, что для более длинных слов если вы обнаружили слишком много различий, вы можете выручить раньше. Например, разнородные и биографии имеют общую разницу в 13, но, учитывая длину (8/9), вы, вероятно, сможете спастись, когда найдете 5 различий.

Это оставляет. вы с набором слов-кандидатов, которые используют почти те же буквы, а также имеют почти одинаковую длину. На этом этапе вы можете начать использовать более совершенные алгоритмы; вам больше не нужно запускать 150 000 сравнений для каждого входного слова.

Теперь для исключения длины, упомянутого ранее: проблема в «словах» вроде greencar . На самом деле это не соответствует слову длиной 8, но для людей совершенно очевидно, что имелось в виду. В этом случае вы можете ' t действительно разбивает входное слово на любой случайной границе и запускает дополнительные N-1 неточных совпадений для обеих половин. Однако можно проверить только недостающее пространство. Просто найдите все возможные префиксы. Это эффективно, потому что вы будете использовать одну и ту же часть словаря снова и снова, например g gr , gre , gree и т. Д. Для каждого найденного префикса проверьте, есть ли оставшийся суффикс также в словарном словаре, например reencar , eencar . Если обе половины входного слова есть в словаре, а само слово нет, можно предположить, что пробел отсутствует.

Я буду использовать одну и ту же часть словаря снова и снова, например g gr , gre , gree и т. д. Для каждого префикса, который вы ' Если вы нашли, проверьте, есть ли оставшийся суффикс также в словарном аппарате, например reencar , eencar . Если обе половины входного слова есть в словаре, а само слово нет, можно предположить, что пробел отсутствует.

Я буду использовать одну и ту же часть словаря снова и снова, например g gr , gre , gree и т. д. Для каждого префикса, который вы ' Если вы нашли, проверьте, есть ли оставшийся суффикс также в словарном словаре, например reencar , eencar . Если обе половины входного слова есть в словаре, а само слово нет, можно предположить, что пробел отсутствует.

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

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

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