WM>Ну так хранить нужно не сами слова, а ссылки на них в виде индекса в глобальном массиве слов. Будет тратится [log₂N] бит на каждое вхождение слова. Хотя, конечно, индекс все равно растёт.
WM>Их простых подходов — хранить все слова в TRIE (или в DAWG для экономии памяти). Тогда процедура поиска слова в trie с k ошибками будет выглядеть так: WM>Если k == 0, то делается точный поиск (который может завершиться успехом или нет). WM>Если k > 0, то переходим из текущего узла trie по всем ссылкам, и если переход по ссылке был по несовпадающей букве, уменьшаем k.
WM>Такой рекурсивный алгоритм найдёт все слова с указанным ограничением на расстояние Левенштейна без явного его вычисления для каждого слова с нуля. Собственно trie часто используется для подсчёта расстояния до всех слов — это известный алгоритм. Тут лишь отличие в том, что если для какого-то узла trie уже установлено, что расстояние превысило k, то это означает, что и у всех дочерних узлов оно не меньше, а это отсекает большое число слов, которые уже можно не проверять.
Мм.. а что можете сказать про скорость? Мне кажется я где-то читал, что trie деревья в несколько раз медленнее индексирования по суффиксам
WM>Есть отличный обзор "Indexing Methods for Approximate Dictionary Searching: Comparative Analysis". WM>Либо просто смотреть как работают известные программы проверки орфографии вроде aspell (или даже сразу задействовать их).
Спасибо за статью. А аспел по внешнему виду хорошая штука, но дело в том, что мне надо написать всё на чистом С и желательно покороче. В С++ я только делаю наброски.
