В чем разница между структурами данных trie и radix trie?

Являются ли структуры данных trie и radix trie одним и тем же?

Если они не совпадают, то что означает radix trie (AKA Patricia trie)?

Радикс-дерево - это сжатая версия дерева. В дереве на каждом ребре вы пишете одну букву, а в дереве 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 .

Если они [не] одинаковы, то что означает Radix trie (она же Patricia Trie)?

Я предполагаю, что вы хотели написать не в своем вопросе, поэтому я поправляю.

Точно так же PATRICIA обозначает определенный тип дерева с основанием счисления, но не все попытки счисления являются попытками PATRICIA.

Что такое дерево?

«Trie» описывает древовидную структуру данных, подходящую для использования в качестве ассоциативного массива, где ветви или края соответствуют частям ключа. Определение частей здесь довольно расплывчато, потому что разные реализации попыток используют разные битовые длины для соответствия ребрам. Например, двоичное дерево имеет два ребра на узел, которые соответствуют 0 или 1, а 16-стороннее дерево имеет шестнадцать ребер на узел, которые соответствуют четырем битам (или шестнадцатеричной цифре: от 0x0 до 0xf).

Эта диаграмма, взятая из Википедии, кажется, изображает дерево со вставленными (по крайней мере) клавишами 'A', 'to', 'tea', 'ted', 'ten' и 'inn':

Если бы это дерево было для хранения элементов для ключей 't', 'te', 'i' или 'in', на каждом узле должна была бы присутствовать дополнительная информация, чтобы различать нулевые узлы и узлы с фактическими значениями.

Что такое radix trie?

«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.position4 мы получаем доступ root["smiles"[4]], что и происходит root['e']. Мы сохраняем это в переменной с именем current. current.positionравно 5, где находится разница между "smiled"и "smiles", поэтому следующий доступ будет root["smiles"[5]]. Это подводит нас к smiles_itemконцу нашей строки. Наш поиск был прекращен, и элемент был получен только с тремя обращениями к узлам вместо восьми.

Что такое дерево ПАТРИСИЯ?

Дерево PATRICIA - это вариант попыток счисления, для которого должны использоваться только nузлы, содержащие nэлементы. В нашем грубо продемонстрировали поразрядную TRIE псевдокод выше, есть пяти узлов в общей сложности : root(который является нульарным узлом, он не содержит фактическое значения), root['e'], root['e']['d'], root['e']['s']и root['i']. В дереве PATRICIA должно быть только четыре. Давайте посмотрим, чем эти префиксы могут отличаться, посмотрев на них в двоичном формате, поскольку 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 моим любимым алгоритмом до сих пор ...

Я собираюсь сократить это описание здесь, чтобы уменьшить тяжесть моего надвигающегося артрита, но если вы хотите узнать больше о 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:
термин « основание системы счисления» в математике означает основание числовой системы и по существу указывает количество уникальных символов, необходимых для представления любого числа в этой системе. Например, в десятичной системе счисления используется система счисления десять, а в двоичной системе счисления - два. Используя аналогичную концепцию, когда мы хотим охарактеризовать структуру данных или алгоритм по количеству уникальных символов базовой репрезентативной системы, мы помечаем эту концепцию термином «основание системы счисления». Например, «поразрядная сортировка» для определенного алгоритма сортировки. По той же логике все варианты trieчьи характеристики (такие как глубина, потребность в памяти, время выполнения поиска / совпадения и т. д.) зависят от системы счисления базовых алфавитов, мы можем назвать их основанием счисления «trie's». Например, не-уплотненный, а также уплотнен Trie , когда использование алфавиты аз, мы можем назвать это Radix 26 синтаксического дерева . Любой Trie , который использует только два символа (традиционно «0» и «1») можно назвать радикс 2 Trie . Однако почему-то во многих литературных источниках использование термина «Radix Trie» ограничивалось только для сжатого дерева .

Прелюдия к PATRICIA Tree / 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» соответственно. При этом наши строковые ключи «dad», «dab» и «cab» становятся «110011», «110001» и «100001» соответственно. Дерево для этого будет таким, как показано ниже на рис. III (биты читаются слева направо так же, как строки читаются слева направо).

          [root]
             \1               
              \
              [*]
             0/ \1               
             /   \
           [*]   [*]         
           0/     /               
           /     /0
         [*]    [*]      
        0/      /               
        /      /0
      [*]    [*]
     0/     0/ \1                Fig-III
     /      /   \
    [*]   [*]   [*]
     \1     \1    \1
      \      \     \
      []     []    []
    (cab)   (dab) (dad)

PATRICIA Trie / Tree:
если мы сожмем приведенное выше двоичное дерево (рис. III) с помощью уплотнения по одному краю, то у него будет гораздо меньше узлов, чем показано выше, и все же количество узлов будет больше, чем 3, количество ключей, которые оно содержит . Дональд Р. Моррисон нашел (в 1968 году) инновационный способ использования двоичного дерева для изображения N ключей с использованием только N узлов и назвал эту структуру данных PATRICIA.. Его структура дерева по существу избавилась от одиночных ребер (одностороннее ветвление); Поступая так, он также избавился от понятия двух типов узлов - внутренних узлов (которые не изображают никаких ключей) и листовых узлов (которые изображают ключи). В отличие от логики сжатия, описанной выше, его дерево использует другую концепцию, где каждый узел включает указание того, сколько битов ключа следует пропустить для принятия решения о ветвлении. Еще одной характеристикой его дерева PATRICIA является то, что оно не хранит ключи - это означает, что такая структура данных не подходит для ответов на такие вопросы, как перечисление всех ключей, соответствующих данному префиксу , но хороша для определения того, существует ли ключ или не в дереве. Тем не менее, термин Patricia Tree или Patricia Trie с тех пор использовался во многих разных, но схожих смыслах, например, для обозначения компактного дерева [NIST] или для обозначения корневого дерева с основанием два [как указано в тонком путь в WIKI] и так далее.

Trie, которое может не быть Radix Trie:
Ternary Search Trie (также известное как Ternary Search Tree), часто сокращенно TST, - это структура данных (предложенная Дж. Бентли и Р. Седжвиком ), которая очень похожа на trie с трехсторонним ветвлением. Для такого дерева каждый узел имеет характерный алфавит «x», так что решение о ветвлении определяется тем, является ли символ ключа меньше, равным или большим, чем «x». Благодаря этой фиксированной функции трехстороннего ветвления он обеспечивает альтернативу trie с эффективным использованием памяти, особенно когда R (основание) очень велико, например, для алфавитов Unicode. Интересно, что TST, в отличие от (R-way) trie , не имеет на свои характеристики влияния R. Например, промах при поиске для TST равен ln (N)в отличие от log _R (N) для R-way Trie. Требования к памяти TST, в отличие от R-way trie , также НЕ являются функцией R. Поэтому мы должны быть осторожны, называя TST основанием системы счисления. Я лично не думаю, что мы должны называть это основанием системы счисления, поскольку ни на одну из его характеристик (насколько мне известно) не влияет основание системы счисления R лежащих в его основе алфавитов.