Trie, или нагруженное дерево

[aymeshkov]

Хорошая статья, спасибо!

Все-таки слабым местом trie является память — если никак не сжимать, то оно может разрастись до впечатляющих размеров.

[aymeshkov]

Забыл спросить. Откуда термин «нагруженное дерево»? Раньше просто встречал только «префиксное дерево».

[Flux]

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

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

[burdakovd]

Добавьте хоть в теги альтернативные названия.
А ещё лучше и в начале статьи список названий.
А то до самого конца преследовала мысль «Чем это отличается от бора?»

[PASSTor]

По сравнение с хеш таблицами, как и написано в статье, будет занимать меньше места, если у нескольких ключей префиксы одинаковы.

Да и специфика налицо: поддеревья по префиксу далеко не любая структура выдаст быстро. Так что использование памяти компенсируется.

[kets]

Спасибо большое за статью, а теги мы и читаем (ну иногда точно читаем :))))

[andreycha]

На Хабре появился последователь Skiminok'а? :) Поддерживаю.

[Flux]

Спасибо, спасибо.

Самому очень нравятся его статьи про DSU и декартовы деревья.

[Skiminok]

Спасибо :)
Эта статья, в свою очередь, тоже замечательна.

Стоит упомянуть здесь одну из лучших книг по строковым алгоритмам и структурам данных, связанным с ними:
Дэн Гасфилд, «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология»

[Biga]

Префиксные деревья — это вычислительная ботаника? =)

[Skiminok]

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

[AFC]

Стоило бы раздел «Зачем все это нужно» поставит сразу после «Что это ?» и раскрыть пошире область применения. Почему то не хочется читать как удалять/добавлять/делать что-то, если не понятно зачем вообще все это надо.

[Razoomnick]

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

[andrewsh]

а вот, кстати, неплохая реализация trie на C99: hg.atheme.org/libmowgli/libmowgli/file/tip/src/libmowgli/mowgli_patricia.c

[Laytlas]

*Сглатываю слюну*, мне казалось, что реализация не доходит и до 100 строк, а тут целоая 1000.

Так как комменты могу писать раз в 5 минут, объясните пожалуйста, как алгоритм поиска работатет за O(|Key|)? Разве мы у каждого родителя не должны проверить всех его потомков? В худшем случае это работает O(число потомков), или есть более быстрый способ поиска «нужного» потомка? Или O(|Key|) подразумевает проход по всем потомкам и данного родителя?

[Laytlas]

Ложная тревога. Мощность алфавита — константа, извиняюсь.

[Skiminok]

Там по ссылке гораздо усложнённый вариант.
Я когда бор пишу, он у меня от силы несколько десятков строк занимает.

[andrewsh]

Извините, не я автор, я сам этот код увидел три дня назад, когда отлаживал Audacious :) Тогда же узнал, что это такое и как работает, хотя код до конца покамест не понимаю.

[Laytlas]

Я вот когда был в ЛКШ, попал в параллеь В', и самое зубодробительное что там было — скорее всего геометрия. На пол параллели выше (из параллели В) люди ходили и разбирались с этими деревьями, искали ключи, я стоял как дурак и думал, что за… Какие ключи??!!!
Вывод: После небольшого экскурса автора в деревья я больше не буду стоять деревом при их виде.
И еще вопросик, где можно найти материал почитать про различные алгоритмы и структуры, чтобы было написано понятным языком, примерно как у вас.

[Skiminok]

Кормен же.
Седжвик ещё.
E-maxx, разумеется.
Тысячи их.

[Flux]

Категорически поддерживаю.
Кормен — наше все.

[voidlizard]

Крис Окасаки еще.

[Megadino]

Иллюстрации красивые. В чем вы их рисовали?

[Flux]

В Microsoft Visio 2010.

[Blackened]

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

Думается, можно не вводить дополнительную характеристику, а просто удалять при подъёме пустые узлы до первого непустого.

[Flux]

Можно, однако я написал

для эффективного определения того, является ли узел листом

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

[Blackened]

Да, согласен.

[MikaMikuMik]

Спасибо, почитал перед ГОСАМИ))