В чем разница между структурами данных trie и radix trie?
Структуры данных trie и radix trie - это одно и то же?
Если они одинаковы, то в чем смысл radix trie (AKA Patricia trie)?
4 ответа
Основное дерево - это сжатая версия дерева. В древовидной структуре на каждом ребре вы пишете одну букву, а в дереве PATRICIA (или радикальном дереве) вы сохраняете целые слова.
Теперь предположим, что у вас есть слова hello, hat а также have, Чтобы хранить их в дереве, это будет выглядеть так:
e - l - l - o
/
h - a - t
\
v - e
И вам нужно девять узлов. Я поместил буквы в узлы, но на самом деле они помечают края.
В радикальном дереве у вас будет:
*
/
(ello)
/
* - h - * -(a) - * - (t) - *
\
(ve)
\
*
и вам нужно всего пять узлов. На рисунке выше узлы звездочки.
Таким образом, в целом основополагающее дерево занимает меньше памяти, но его сложнее реализовать. В противном случае вариант использования обоих практически одинаков.
Мой вопрос заключается в том, являются ли структура данных Trie и Radix Trie одинаковыми?
Короче нет. Категория Radix Trie описывает конкретную категорию Trie, но это не означает, что все попытки являются радикальными попытками.
Если они не одно и то же, то в чем смысл Radix Trie (ака Patricia Trie)?
Я предполагаю, что вы хотели написать не в вашем вопросе, следовательно, мое исправление.
Точно так же PATRICIA обозначает конкретный тип радикальных попыток, но не все радикальные попытки являются попытками PATRICIA.
Что такое три?
"Три" описывает древовидную структуру данных, подходящую для использования в качестве ассоциативного массива, где ветви или ребра соответствуют частям ключа. Здесь определение частей довольно расплывчато, потому что разные реализации попыток используют разные битовые длины для соответствия ребрам. Например, двоичное дерево имеет два ребра на узел, которые соответствуют 0 или 1, в то время как 16-полосное дерево имеет шестнадцать ребер на узел, которые соответствуют четырем битам (или шестнадцатеричной цифре: от 0x0 до 0xf).
Эта диаграмма, взятая из Википедии, кажется, изображает три с (по крайней мере) вставленными клавишами "A", "to", "tea", "ted", "ten" и "inn":
Если бы это было хранить элементы для ключей "t", "te", "i" или "in", в каждом узле должна была бы присутствовать дополнительная информация, чтобы различать нулевые узлы и узлы с фактическими значениями.
Что такое основа?
"Radix Trie", по-видимому, описывает форму trie, которая объединяет общие части префикса, как описал Ивайло Странджев в своем ответе. Предположим, что это 256-элементный три, который индексирует ключи "улыбка", "улыбка", "улыбка" и "улыбка", используя следующие статические назначения:
root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;
Каждый нижний индекс обращается к внутреннему узлу. Это значит, чтобы получить smile_item, вы должны получить доступ к семи узлам. Восемь доступов к узлам соответствуют smiled_item а также smiles_item и девять к smiling_item, Для этих четырех элементов всего четырнадцать узлов. Однако все они имеют первые четыре байта (соответствующие первым четырем узлам). Сжимая эти четыре байта, чтобы создать root что соответствует ['s']['m']['i']['l']четыре доступа к узлам были оптимизированы. Это означает, что меньше памяти и меньше обращений к узлам, что является очень хорошим показателем. Оптимизация может быть применена рекурсивно, чтобы уменьшить потребность в доступе к ненужным байтам суффикса. В конце концов, вы попадаете в точку, где вы сравниваете только различия между ключом поиска и индексированными ключами в местах, индексируемых с помощью дерева. Это основа.
root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;
Чтобы получить элементы, каждому узлу нужна позиция. С ключом поиска "улыбки" и root.position из 4 мы получаем доступ root["smiles"[4]], который случается root['e'], Мы храним это в переменной с именем current, current.position 5, где находится разница между "smiled" а также "smiles" поэтому следующий доступ будет root["smiles"[5]], Это подводит нас к smiles_item и конец нашей строки. Наш поиск был прекращен, и элемент был найден, с тремя доступами к узлам вместо восьми.
Что такое ПАТРИЦИЯ?
PATRICIA Trie - это вариант радикальных попыток, который должен быть только когда-либо n узлы, используемые для содержания n Предметы. В нашем грубо продемонстрированном псевдокоде radix trie всего пять узлов: root (который является нулевым узлом; он не содержит фактического значения), root['e'], root['e']['d'], root['e']['s'] а также root['i'], В ПАТРИЦИИ должно быть только четыре. Давайте посмотрим, как эти префиксы могут отличаться, посмотрев на них в двоичном виде, поскольку PATRICIA - это двоичный алгоритм.
smile: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0000 0000 0000 0000
smiled: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0110 0100 0000 0000
smiles: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0111 0011 0000 0000
smiling: 0111 0011 0110 1101 0110 1001 0110 1100 0110 1001 0110 1110 0110 0111 ...
Будем считать, что узлы добавляются в том порядке, в котором они представлены выше. smile_item это корень этого дерева. Разница, выделенная жирным шрифтом, чтобы ее было легче обнаружить, заключается в последнем байте "smile" в бите 36. До этого момента все наши узлы имеют одинаковый префикс. smiled_node принадлежит в smile_node[0], Разница между "smiled" а также "smiles" происходит в бите 43, где "smiles" имеет бит "1", так smiled_node[1] является smiles_node,
Вместо того, чтобы использовать NULL в качестве ветвей и / или дополнительной внутренней информации, обозначающей, когда поиск завершается, ветви связывают обратно с деревом где-то обратно, поэтому поиск прекращается, когда проверяемое смещение уменьшается, а не увеличивается. Вот простая диаграмма такого дерева (хотя PATRICIA на самом деле является скорее циклическим графом, чем деревом, как вы увидите), которая была включена в книгу Седжвика, упомянутую ниже:
Возможен более сложный алгоритм PATRICIA, включающий ключи переменной длины, хотя некоторые технические свойства PATRICIA теряются в процессе (а именно то, что любой узел содержит общий префикс с предшествующим ему узлом):
Подобное ветвление дает ряд преимуществ: каждый узел содержит значение. Это включает в себя корень. В результате длина и сложность кода становятся намного короче и, возможно, немного быстрее в реальности. Хотя бы одну ветку и не более k филиалы (где k количество битов в ключе поиска), которые следуют, чтобы найти элемент. Узлы крошечные, потому что они хранят только две ветви каждая, что делает их вполне подходящими для оптимизации локальности кэша. Эти свойства делают PATRICIA моим любимым алгоритмом...
Я собираюсь вкратце описать это описание, чтобы уменьшить тяжесть моего надвигающегося артрита, но если вы хотите узнать больше о ПАТРИЦИИ, вы можете обратиться к таким книгам, как "Искусство компьютерного программирования, Том 3" Дональда Кнута. или любой из "Алгоритмов на {ваш-любимый-язык}, части 1-4" Седжвика.
TRIE:
У нас может быть схема поиска, где вместо сравнения всего ключа поиска со всеми существующими ключами (например, хэш-схемы) мы также можем сравнивать каждый символ ключа поиска. Следуя этой идее, мы можем построить структуру (как показано ниже), которая имеет три существующих ключа - " папа ", " мазок " и " такси ".
[root]
...// | \\...
| \
c d
| \
[*] [*]
...//|\. ./|\\... Fig-I
a a
/ /
[*] [*]
...//|\.. ../|\\...
/ / \
B b d
/ / \
[] [] []
(cab) (dab) (dad)
По сути, это M-арное дерево с внутренним узлом, представленным как [ * ], и листовым узлом, представленным как [ ]. Эта структура называется три. Решение о ветвлении в каждом узле можно сохранить равным количеству уникальных символов алфавита, скажем, R. Для строчных букв английского алфавита az, R=26; для расширенных алфавитов ASCII R=256 и для двоичных цифр / строк R=2.
Компактная TRIE:
Как правило, узел в дереве использует массив с размером =R и, таким образом, приводит к пустой трате памяти, когда каждый узел имеет меньше ребер. Чтобы обойти проблему памяти, были сделаны различные предложения. Основываясь на этих вариациях, три также называются " компактное дерево " и " сжатое дерево ". Хотя последовательная номенклатура встречается редко, наиболее распространенная версия компактного дерева формируется путем группировки всех ребер, когда узлы имеют одно ребро. Используя эту концепцию, вышеупомянутый (рис. I) три с клавишами "папа", "мазок" и "кабина" может иметь форму ниже.
[root]
...// | \\...
| \
cab da
| \
[ ] [*] Fig-II
./|\\...
| \
b d
| \
[] []
Обратите внимание, что каждый из 'c', 'a' и 'b' является единственным ребром для своего соответствующего родительского узла и, следовательно, они объединены в одно ребро "cab". Точно так же "d" и "a" объединяются в один край, помеченный как "da".
Radix Trie:
Термин основание в математике означает основание системы счисления и, по существу, указывает количество уникальных символов, необходимых для представления любого числа в этой системе. Например, десятичная система - основание десять, а двоичная система - основание два. Используя аналогичную концепцию, когда мы заинтересованы в характеристике структуры данных или алгоритма по количеству уникальных символов базовой системы представления, мы помечаем концепцию термином "основание". Например, "radix sort" для определенного алгоритма сортировки. В той же логике все варианты дерева, чьи характеристики (такие как глубина, потребность в памяти, время выполнения поиска / попадания и т. Д.) Зависят от радиуса базовых алфавитов, мы можем назвать их основанием "три". Например, несжатый, а также сжатый три при использовании алфавитов az, мы можем назвать это основанием с основанием 26. Любое дерево, в котором используются только два символа (традиционно "0" и "1"), можно назвать "основанием 2". Тем не менее, многие литературные источники ограничивают использование термина "Radix Trie" только для сжатого дерева.
Прелюдия к ПАТРИЦИИ Три / Три
Было бы интересно отметить, что даже строки в качестве ключей могут быть представлены с использованием двоичных алфавитов. Если мы предполагаем кодировку ASCII, то ключ "папа" можно записать в двоичной форме, записав двоичное представление каждого символа в последовательности, скажем, как " 01100100 01100001 01100100 ", записав двоичные формы "d", "a" и 'D' последовательно. Используя эту концепцию, можно создать три (с Radix Two). Ниже мы изобразим эту концепцию, используя упрощенное предположение, что буквы "a", "b", "c" и'd "взяты из меньшего алфавита вместо ASCII.
Примечание к рисунку III: Как уже упоминалось, для упрощения описания, давайте предположим, что алфавит состоит всего из 4 букв {a,b,c,d} и соответствующие им двоичные представления - "00", "01", "10" и "11" соответственно. При этом наши строковые ключи "папа", "папа" и "кабина" становятся соответственно "110011", "110001" и "100001". Это будет показано ниже на рис. III (биты читаются слева направо так же, как строки читаются слева направо).
[root]
\1
\
[*]
0/ \1
/ \
[*] [*]
0/ /
/ /0
[*] [*]
0/ /
/ /0
[*] [*]
0/ 0/ \1 Fig-III
/ / \
[*] [*] [*]
\1 \1 \1
\ \ \
[] [] []
(cab) (dab) (dad)
ПАТРИЦИЯ Три / Дерево:
Если мы сжимаем вышеупомянутый двоичный файл (рис. III), используя сжатие с одним ребром, у него будет намного меньше узлов, чем показано выше, и все же число узлов будет больше, чем 3, количество ключей, которое он содержит. Дональд Р. Моррисон нашел (в 1968 году) инновационный способ использования двоичного дерева для отображения N ключей, используя только N узлов, и назвал эту структуру данных PATRICIA. Его структура дерева по существу избавилась от одиночных краев (одностороннее ветвление); и при этом он также избавился от понятия двух видов узлов - внутренних узлов (которые не изображают никаких ключей) и конечных узлов (которые изображают ключи). В отличие от логики уплотнения, объясненной выше, его три использует другую концепцию, где каждый узел включает в себя указание, сколько бит ключа должно быть пропущено для принятия решения о ветвлении. Еще одна особенность его алгоритма PATRICIA состоит в том, что он не хранит ключи - это означает, что такая структура данных не будет подходящей для ответов на вопросы, такие как, перечисление всех ключей, которые соответствуют данному префиксу, но это хорошо для обнаружения, существует ли ключ или не в три. Тем не менее, термин "дерево Патрисии" или "Патриция Три" с тех пор использовался во многих различных, но сходных смыслах, например, для обозначения компактного дерева [NIST] или для обозначения радиального дерева с основанием два [как указано в тонком путь в вики] и так далее.
Trie, который не может быть Radix Trie:
Тернарное поисковое дерево (также известное как троичное поисковое дерево), часто сокращенно обозначаемое как TST, представляет собой структуру данных (предложенную Дж. Бентли и Р. Седжвиком), которая очень похожа на структуру с трехсторонним ветвлением. Для такого дерева каждый узел имеет характерный алфавит "x", поэтому решение о ветвлении зависит от того, является ли символ ключа меньше, равен или больше, чем "x". Благодаря этой фиксированной функции трехстороннего ветвления, она обеспечивает эффективную для памяти альтернативу для trie, особенно когда R (radix) очень велико, например, для алфавитов Unicode. Интересно, что TST, в отличие от (R-way) trie, не имеет своих характеристик, на которые влияет R. Например, промах поиска для TST равен ln(N) в отличие от log R (N) для R-way Trie. Требования к памяти TST, в отличие от R-way, также НЕ являются функцией R. Поэтому мы должны быть осторожны, чтобы назвать TST основополагающим. Лично я не думаю, что мы должны называть это основанием, поскольку ни одна (насколько я знаю) его характеристик не зависит от основ R, его основных алфавитов.
При попытках большинство узлов не хранят ключи и представляют собой просто переходы по пути между ключом и теми, которые его расширяют. Большинство этих переходов необходимы, но когда мы храним длинные слова, они, как правило, создают длинные цепочки внутренних узлов, каждый из которых имеет только один дочерний элемент. Это основная причина, по которой для попыток требуется слишком много места, иногда даже больше, чем для BST.
Попытки Radix (также известные как деревья с основанием, иначе деревья Патрисии) основаны на идее, что мы можем каким-то образом сжать путь, например, после «промежуточного t-узла» мы могли бы иметь «край» в одном узле или «идоте» в одном узле. .
Вот график для сравнения trie и radix trie:
Исходное дерево имеет 9 узлов и 8 ребер, и если мы примем 9 байтов для ребра с 4-байтовыми накладными расходами на узел, это означает
9 * 4 + 8 * 9 = 108 bytes.
Сжатое дерево справа имеет 6 узлов и 5 ребер, но в этом случае каждое ребро несет строку, а не только символ; однако мы можем упростить операцию, отдельно учитывая ссылки на края и метки строк. Таким образом, мы все равно будем считать 9 байтов на ребро (потому что мы включили бы байт ограничителя строки в стоимость ребра), но мы могли бы добавить сумму длин строк в качестве третьего члена в окончательном выражении; общее количество необходимых байтов определяется выражением
6 * 4 + 5 * 9 + 8 * 1 = 77 bytes.
Для этого простого дерева сжатая версия требует на 30% меньше памяти.