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

мой вопрос заключается в том,Бор структуры данных и Radix Trie это одно и то же?

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

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

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

аналогичным образом, Патриция обозначает определенный тип radix trie, но не все попытки radix являются попытками Патриции.

---

что такое trie?

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

эта диаграмма, извлеченная из Википедии, похоже, изображает trie С (по крайней мере) ключами "A", "to", "tea", "ted", " ten " и " inn " вставлены:

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

---

что такое radix trie?

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

root['s']['m']['i']['l']['e'][''] = smile_item;
root['s']['m']['i']['l']['e']['d'][''] = smiled_item;
root['s']['m']['i']['l']['e']['s'][''] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g'][''] = smiling_item;

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

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

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

---

что такое Патрисия три?

Патрисия три - это вариант radix пытается, для которого должно быть толькоn узлы, используемые для содержания n предметы. В нашем грубо продемонстрированном псевдокоде radix trie выше всего пять узлов:root (который является нулевым узлом; он не содержит фактического значения),root['e'],root['e']['d'],root['e']['s'] и root['i']. В Патрисии три должно быть только четыре. Давайте посмотрим, как эти префиксы могут отличаться, глядя на них в двоичном формате, так как Патрисия является двоичным алгоритм.

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] is smiles_node.

вместо NULL как ветви и / или дополнительная внутренняя информация для обозначения, когда поиск завершается, ветви ссылаются назад до дерево где-то, поэтому поиск завершается, когда смещение для проверки уменьшается, а не растет. Вот простая схема такого дерево (хотя Патрисия действительно больше циклический граф, чем дерево, как вы увидите), который был включен в Книгу Седжвика упоминается ниже:

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

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

я собираюсь сократить это описание здесь, чтобы уменьшить но если вы хотите узнать больше о Патрисии, вы можете обратиться к таким книгам, как "искусство компьютерного программирования, Том 3" Дональда Кнута или любой из "алгоритмов на {вашем любимом языке}, части 1-4" Седжвика.

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

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

(cab)   (dab)     (dad)

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

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

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

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

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

прелюдия к PATRICIA Tree / Trie:
Было бы интересно заметить, что даже строки как ключи могут быть представлены с использованием двоичных алфавитов. Если мы примем кодировку ASCII, то ключ " dad "можно записать в двоичной форме, записав двоичное представление каждого символа в последовательности, скажем, как"011001000110000101100100 " путем записи двоичного кода формы ‘d’, ‘a’ и ' d ' последовательно. Используя эту концепцию, а trie (С основанием два) могут быть сформированы. Ниже мы описываем эту концепцию, используя упрощенное предположение, что буквы "a", "b", " c " и " D " взяты из меньшего алфавита вместо ASCII.

Примечание Для фиг-III: Как уже упоминалось, чтобы сделать изображение легким, давайте предположим, что алфавит только с 4 буквами {a,b, c, d} и их соответствующие двоичные представления являются "00", "01", "10" и "11" соответственно. При этом наши строковые ключи "папа", "dab" и "cab" становятся "110011", "110001" и "100001" соответственно. Боре за это будет, как показано ниже на фиг-III степени (биты читаются слева направо как строки читаются слева направо).

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

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

Trie это может быть не Radix Trie:
Троичный Поиск Trie (он же троичное дерево поиска) часто сокращается как TST - это структура данных (предложение J. Bentley и R. Sedgewick), который очень похож на trie с трехсторонним ветвлением. Для такого дерева каждый узел имеет характерный алфавит "x", так что решение о ветвлении зависит от того, является ли символ ключа меньше, равен или больше "x". Благодаря этой фиксированной 3-полосной функции ветвления он обеспечивает эффективную альтернативу памяти для 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, поскольку ни одна (насколько мне известно) из его характеристик не зависит от radix,R, его основных алфавитов.