Это чудное слово «словарь»...

Смотря какой поиск, есть такое: https://secure.wikimedia.org/wikipedia/en/wiki/Directed_acyclic_word_graph

- Поиск - логарифмический

Не логарифический от количества слов, а линейный от длины слова. Количество хранимых слов не важно. Ы?

В качестве альтернативы дереву иногда удобно использовать хеш-таблицу (она будет быстрее дерева за счет меньшего количества промахов в кэше процессора).

Принципиально ничего менять не надо и всё правильно, разве что ещё раз почитать про suffix trie, patricia trie (например чтобы оптимизировать размер) и иже с ними.

Ы?

Ы. Да, с логарифмом по поиску мой память дал маху.

она будет быстрее дерева

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

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

Есть техника DOS-атак на приложения путем эксплуатации коллизий в хеш-функции. Парируется это путём подмешивания соли. Кроме того, можно хранить конфликтующие элементы ячейки хэш-таблицы в дереве :)

Тут же про подбор коллизий для dos пока не вспоминали. Или это превентивные меры?)

Есть одна интересная штука — skip list. На ней построен QMap в Qt.

если хочется изврата - можно почитать работы Phil Bagwell

Размер нода = размер символа

Это как??? Вообще то размер нода - длина алфавита на размер пойнтера??

Размер словаря байтах не превышает суммарный размер слов

Умноженный на длину алфавита на размер пойнтера???

Еще есть либо хэш-таблица, либо rb_tree. Хотя большинство хэшей к-е я видел (я правда с ними мало работал), это вычисление хэша (long) + то же дерево по хэшу + разрешение коллизий. В STL std::map (rb_tree) на порядок тормознутее std::unordered_map (хэш + дерево по хэш-значениям), пока коллизии не начинаются.

Для строк ИМНО разумный хэш без коллизий лучше дерева (не надо строки сравнивать, это м.б. долго), но теряется упорядоченность.

Хардкор: http://judy.sourceforge.net/

Медленный поиск какой-то. Хеш таблица должна десятки-сотни миллионов поисков в секунду легко выдавать.

Хеш таблица не подойдет по требованию компактности. В дереве у нас префиксы одинаковые не повторяются, а вот в указанном выше DAWG - еще и суффиксы слов объединяются. В хеш таблице такого «сжатия» нет.

- Размер нода = размер символа

А это как? Где указатели?

Ну, немножко лажанул - размер символа + 4 байта индекса.