Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.
Рубрика «trie» - 2
Сжатые префиксные деревья
2012-09-17 в 6:31, admin, рубрики: radix tree, trie, Алгоритмы, бор, метки: radix tree, trie, борПрефиксные деревья в Python
2012-07-17 в 11:24, admin, рубрики: python, python3, trie, структуры данных, метки: python, python3, trie, структуры данныхДоделал на днях питонью библиотеку datrie, реализующую префиксное дерево (см. википедию или хабр), спешу поделиться.
Если вкратце, то можно считать, что datrie.Trie — это замена стандартному питоньему dict, которая при определенных условиях (ключи — строки) занимает меньше памяти, имеет сравнимую скорость получения отдельного элемента и поддерживает дополнительные операции (получение всех префиксов данной строки, получение всех строк, начинающихся с данной строки и др.), которые работают примерно так же быстро, как и «словарные» операции.
Работает под Python 2.6-3.3, поддерживает юникод, лицензия LGPL.