Здравствуйте, rp80, Вы писали:

R>Мм.. а что можете сказать про скорость?
Хороший универсальный алгоритм. Лучший из простых. Но можно сделать быстрее.
Я, кстати, путано его рассказал. Если проще, то заранее компилируется trie со словарём. Потом по запросу строится автомат и запускается синхронный поиск в автомате и trie. То есть при посещении узла trie будет известен номер состояния автомата, который ему соответствует, а спускаться к дочерним узлам можно только если и в автомате есть такой же переход. Ответом же станут все слова, до которых удастся спуститься.

А так, должно быть очевидно, что для любого алгоритма из этой области можно подобрать набор данных, на котором его обойдёт другой алгоритм, специально сделанный под этот набор. Идеального алгоритма не существует же. Время работы существенно меняется даже от изменения тематики текста, не говоря уж о более существенных параметрах как язык или количество исправляемых опечаток. Собственно, посмотри обзор.

R>Мне кажется я где-то читал, что trie деревья в несколько раз медленнее индексирования по суффиксам
Непонятно что с чем сравнивали.
А вообще, у trie, как у структуры данных, всё хорошо с производительностью. Но trie — это не алгоритм же. А вот уже алгоритм поиска может разные структуры данных совершенно по разному.