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

Ответ 1

Дерево оснований - это сжатая версия trie. В trie, на каждом краю вы пишете одну букву, в то время как в дереве PATRICIA (или в дереве оснований) вы сохраняете целые слова.

Теперь предположим, что у вас есть слова hello, hat и have. Чтобы сохранить их в trie, это будет выглядеть так:

    e - l - l - o
  /
h - a - t
      \
       v - e

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

В дереве оснований вы будете иметь:

            *
           /
        (ello)
         /
* - h - * -(a) - * - (t) - *
                 \
                 (ve)
                   \
                    *

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

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

Ответ 2

Мой вопрос: является ли структура данных Trie и Radix Trie одной и той же?

Короче говоря, нет. Категория Radix Trie описывает определенную категорию Trie, но это не означает, что все попытки являются попытками radix.

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

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

Аналогично, PATRICIA обозначает определенный тип trix radix, но не все попытки radix - попытки PATRICIA.

Что такое trie?

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

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

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

Что такое radix trie?

"Radix trie", похоже, описывает форму trie, которая конденсирует общие префиксные части, как описал Ивайло Странджев в своем ответе. Подумайте, что 256-way trie, который индексирует клавиши "улыбаться", "улыбаться", "улыбается" и "улыбается", используя следующие статические задания:

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;

Каждый индекс получает доступ к внутреннему node. Это означает, что для извлечения smile_item необходимо получить доступ к семи узлам. Восемь node доступа соответствуют smiled_item и smiles_item, а девять - smiling_item. Для этих четырех элементов всего четырнадцать узлов. Тем не менее, все они имеют первые четыре байта (соответствующие первым четырем узлам). Конденсацией этих четырех байтов для создания root, который соответствует ['s']['m']['i']['l'], четыре node доступа были оптимизированы. Это означает, что меньше памяти и менее node доступа, что является очень хорошим показателем. Оптимизация может быть применена рекурсивно, чтобы уменьшить необходимость доступа к ненужным байтам суффикса. В конце концов вы дойдете до точки, в которой вы сравниваете различия между ключом поиска и индексированными ключами в местах, проиндексированных trie. Это ради-трек.

root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;

Чтобы получить элементы, каждая node нуждается в позиции. С помощью ключа поиска "улыбки" и root.position из 4 мы получаем доступ к root["smiles"[4]], который оказывается root['e']. Мы сохраняем это в переменной с именем current. current.position равно 5, то есть расположение разницы между "smiled" и "smiles", поэтому следующий доступ будет root["smiles"[5]]. Это приводит нас к smiles_item и концу нашей строки. Наш поиск завершен, и элемент был извлечен, всего три node доступа вместо восьми.

Что такое PATRICIA trie?

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

Возможно использование более сложного алгоритма PATRICIA с ключами длины варианта, хотя некоторые технические свойства PATRICIA теряются в процессе (а именно, что любой node содержит общий префикс с node до него):

Разветвляясь таким образом, существует ряд преимуществ: каждый node содержит значение. Это включает в себя корень. В результате длина и сложность кода становятся намного короче и, вероятно, немного быстрее в реальности. По крайней мере одна ветвь и не более k ответвлений (где k - количество бит в ключе поиска), чтобы найти элемент. Узлы крошечные, потому что они хранят только по две ветки, что делает их достаточно подходящими для оптимизации локализации кэша. Эти свойства делают PATRICIA моим любимым алгоритмом до сих пор...

Я сокращу это описание здесь, чтобы уменьшить тяжесть моего надвигающегося артрита, но если вы хотите узнать больше о PATRICIA, вы можете обратиться к книгам, таким как "Искусство компьютерного программирования, том 3", Дональдом Кнутом или любым из "Алгоритмов в вашем любимом языке", части 1-4 "от Sedgewick.

Ответ 3

TRIE:
У нас может быть схема поиска, где вместо сравнения всего ключа поиска со всеми существующими ключами (например, хэш-схема) мы также можем сравнить каждый символ ключа поиска. Следуя этой идее, мы можем построить структуру (как показано ниже), которая имеет три существующих ключа - "папа", "dab" и "cab".

         [root]
     ...// | \\...
           |  \
           c   d
           |    \
          [*]    [*]
      ...//|\.  ./|\\...        Fig-I
        a       a
       /       /
     [*]      [*]
 ...//|\..  ../|\\...
    /        /   \
   B        b     d
  /        /       \
 []       []       []

(cab)   (dab)     (dad)

Это по существу М-арное дерево с внутренним node, представленное как [*] и leaf node, представленное как []. Эта структура называется trie. Решение ветвления на каждом node можно сохранить равным числу уникальных символов алфавита, скажем R. Для строчных английских алфавитов a-z, R = 26; для расширенных алфавитов ASCII, R = 256 и для двоичных цифр/строк R = 2.

Компактный TRIE:
Как правило, node в trie использует массив с размером = R и, таким образом, создает ненужную память, когда у каждого node меньше ребер. Чтобы обойти проблему памяти, были сделаны различные предложения. На основе этих вариаций trie также называются "компактными trie" и "сжатыми trie". Хотя согласованная номенклатура встречается редко, наиболее распространенная версия компактного trie формируется путем группировки всех ребер, когда узлы имеют одинарное ребро. Используя эту концепцию, приведенные выше (рис. I) trie с ключами "папа", "даб" и "кабина" могут принимать форму ниже.

         [root]
     ...// | \\...
           |  \
          cab  da
           |    \
          [ ]   [*]                Fig-II
               ./|\\...
                 |  \
                 b   d
                 |    \
                []    []

Обратите внимание, что каждый из "c", "a" и "b" является единственным фронтом для своего соответствующего родителя node, и поэтому они конгломератируются в одну "кабину" края. Аналогично, 'd и a объединены в один край, помеченный как "da".

Radix Trie:
Термин radix в математике означает базу системы счисления и, по сути, указывает количество уникальных символов, необходимых для представления любого числа в этой системе. Например, десятичная система является десятичной базой, а двоичная система - второй. Используя подобную концепцию, когда они интересовались характеристикой структуры данных или алгоритмом по числу уникальных символов лежащей в основе репрезентативной системы, мы помечаем понятие термином "радикс". Например, "сортировка по основанию" для определенного алгоритма сортировки. В той же логической схеме все варианты trie, характеристики которых (такие как глубина, потребность в памяти, время простоя поиска/удара и т.д.) Зависят от оснований базовых алфавитов, мы можем назвать их radix "пытается". Например, не уплотненный, а также сжатый trie, когда используются алфавиты a-z, мы можем назвать его основанием 26 trie. Любой trie, который использует только два символа (традиционно "0" и "1" ), можно назвать основанием 2 trie. Однако, как-то многие литераторы ограничивали использование термина "Radix Trie" только для уплотненного trie.

Прелюдия к дереву PATRICIA/Trie:
Было бы интересно заметить, что даже строки в виде ключей могут быть представлены с использованием бинарных алфавитов. Если мы предполагаем кодировку ASCII, тогда ключ "папа" может быть записан в двоичной форме, записав двоичное представление каждого символа в последовательности, например " 01100100 01100001 01100100" путем записи двоичных форм "d", "a" и "d последовательно". Используя эту концепцию, можно создать trie (с Radix Two). Ниже мы изображаем это понятие, используя упрощенное предположение, что буквы a, b, c и d имеют меньший алфавит вместо ASCII.

Примечание для рис. III: Как уже упоминалось, чтобы сделать изображение легким, допустим, что алфавит с 4 буквами {a, b, c, d} и их соответствующими двоичными представлениями являются "00", "01", "10" и "11" соответственно. При этом наши строковые ключи "папа", "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:
Если мы скомбинируем вышеуказанный двоичный trie (рис. III) с использованием однократного уплотнения, у него будет гораздо меньше узлов, чем показано выше, и все же узлы будут по-прежнему больше, чем 3, количество ключей это содержит. Дональд Р. Моррисон нашел (в 1968 году) инновационный способ использования двоичного trie для отображения N ключей, используя только N узлов, и он назвал эту структуру данных PATRICIA strong > , Его три структуры существенно избавились от одиночных краев (одностороннее ветвление); и при этом он также избавился от понятия двух видов узлов - внутренних узлов (которые не изображают ни одной клавиши) и листовых узлов (которые изображают ключи). В отличие от описанной выше алгоритма уплотнения, его trie использует другое понятие, в котором каждый node включает указание количества битов ключа, которое нужно пропустить для принятия решения о ветвлении. Еще одна характеристика его PATRICIA trie заключается в том, что он не хранит ключи - это означает, что такая структура данных не будет подходящей для ответа на такие вопросы, как: список всех ключей, которые соответствуют данному префиксу, но хорошо для определения наличия или отсутствия ключа в три. Тем не менее, термин Patricia Tree или Patricia Trie с тех пор использовался во многих разных, но похожих чувствах, таких как, например, для обозначения компактного trie [NIST] или для обозначения радиуса trie с радикой два [как указано в тонком путь в WIKI] и т.д.

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