Radix tree (original) (raw)
Komprimovaná trie je datová struktura, pojem z oboru matematické informatiky. Jedná se o strukturou podobou triím, ale zatímco u trie je na každé hraně jen jediný znak, u komprimované trie jich tam může být víc, pokud jsou společné všem potomkům daného vrcholu. Oproti běžným triím tak použití komprimované trie může šetřit počítačovou paměť. Tento typ struktury má několik alternativních názvů, mj. Patricia-trie, přičemž s názvem PATRICIA coby zkratkou svého stejnojmenného článku je zavedl v roce 1968 . Komprimované trie se používají mj. pro realizaci asociativních polí.
| Property | Value |
|---|---|
| dbo:abstract | Komprimovaná trie je datová struktura, pojem z oboru matematické informatiky. Jedná se o strukturou podobou triím, ale zatímco u trie je na každé hraně jen jediný znak, u komprimované trie jich tam může být víc, pokud jsou společné všem potomkům daného vrcholu. Oproti běžným triím tak použití komprimované trie může šetřit počítačovou paměť. Tento typ struktury má několik alternativních názvů, mj. Patricia-trie, přičemž s názvem PATRICIA coby zkratkou svého stejnojmenného článku je zavedl v roce 1968 . Komprimované trie se používají mj. pro realizaci asociativních polí. (cs) In der Informatik ist ein Patricia-Trie (abgeleitet aus dem engl. reTrieval) eine Datenstruktur, genauer eine spezielle Art eines Tries zur gleichzeitigen Speicherung von mehreren Zeichenketten. Seinen Namen verdankt er dem Akronym PATRICIA, das für Practical Algorithm to Retrieve Information Coded in Alphanumeric steht. Er wurde 1968 von veröffentlicht. Der Patricia-Trie zeichnet sich im Gegensatz zum normalen Trie dadurch aus, dass die Daten komprimiert abgespeichert werden. Dazu werden Zeichen, bei denen keine Verzweigung im Baum entsteht, einfach übersprungen und die Anzahl der ausgelassenen Knoten vor dem nächsten auftretenden Zeichen gespeichert. Somit wird gewährleistet, dass ein Suchbegriff eindeutig zugeordnet werden kann. Die Größe von Patricia-Tries hängt somit nicht von der Länge der gespeicherten Schlüsselwerte ab und jeder neue Eintrag kann durch Erstellen von nur einem neuen Knoten und einer neuen Kante eingefügt werden. Somit wachsen sie langsam, auch wenn eine große Anzahl neuer Elemente eingefügt wird. Patricia-Tries können dazu verwendet werden, assoziative Arrays mit Strings als Schlüsseln zu konstruieren. Hiermit wird Speicherplatz für die Schlüssel gespart. (de) In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent. The result is that the number of children of every internal node is at most the radix r of the radix tree, where r is a positive integer and a power x of 2, having x ≥ 1. Unlike regular trees, edges can be labeled with sequences of elements as well as single elements. This makes radix trees much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes. Unlike regular trees (where whole keys are compared en masse from their beginning up to the point of inequality), the key at each node is compared chunk-of-bits by chunk-of-bits, where the quantity of bits in that chunk at that node is the radix r of the radix trie. When r is 2, the radix trie is binary (i.e., compare that node's 1-bit portion of the key), which minimizes sparseness at the expense of maximizing trie depth—i.e., maximizing up to conflation of nondiverging bit-strings in the key. When r ≥ 4 is a power of 2, then the radix trie is an r-ary trie, which lessens the depth of the radix trie at the expense of potential sparseness. As an optimization, edge labels can be stored in constant size by using two pointers to a string (for the first and last elements). Note that although the examples in this article show strings as sequences of characters, the type of the string elements can be chosen arbitrarily; for example, as a bit or byte of the string representation when using multibyte character encodings or Unicode. (en) En informatique, un arbre radix ou arbre PATRICIA (pour Practical Algorithm To Retrieve Information Coded In Alphanumeric en anglais et signifiant algorithme commode pour extraire de l'information codée en alphanumérique) est une structure de données compacte permettant de représenter un ensemble de mots adaptée pour la recherche. Il est obtenu à partir d'un arbre préfixe en fusionnant chaque nœud n'ayant qu'un seul fils avec celui-ci. On peut alors étiqueter indifféremment chaque arête par un mot ou bien par une unique lettre. (fr) 基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。 (ja) A árvore PATRICIA é uma representação compacta de uma Trie onde os nós que teriam apenas um filho são agrupados nos seus antecessores. É comum que as árvores Trie possuam um grupo disperso de chaves, desse modo, muitos nós possuem apenas um descendente. Isto faz com que as Trie tenham um custo grande de espaço. Uma Trie usa cada uma das partes de uma chave, por vez, para determinar a sub-árvore. Por outro lado, a árvore PATRICIA escolhe um elemento da chave (armazenando a sua posição) para determinar a sub-árvore. Isso remove a necessidade de nós com apenas um descendente. Concebido por , PATRICIA é um algoritmo para realização de buscas em árvores com as chaves dos nós representadas em binário, sem armazenar as chaves nos nós. O nome é um acrônimo de “Practical Algorithm To Retrieve Information Coded In Alphanumeric”, e o método é particularmente útil para tratamento de chaves de tamanho variável extremamente longas, tais como títulos e frases. No caso de pesquisas analíticas, os dados podem tirar proveito deste método desde que as informações sejam armazenadas como cadeias de texto. Uma restrição dessas árvores é a necessidade de não haver um elemento que seja prefixo de outro, o que pode facilmente ser obtido se necessário. (pt) Skompresowane drzewo trie (również: drzewo Patricia, drzewo pozycyjne) – struktura danych przechowująca zbiór ciągów. (pl) Базисное дерево (англ. radix tree, также компактное префиксное дерево, основное дерево, дерево остатков) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел , являющийся единственным потомком узла , сливается с узлом . Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как , где — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве. В отличие от обычных префиксных деревьев, узел базисного дерева может быть помечен как одним элементом (символом, битом и т. д.), так и последовательностью элементов. Это делает базисное дерево более эффективным для небольших наборов строк (особенно если сами строки достаточно длинные), и также для наборов, имеющих небольшое количество длинных префиксов. (ru) В інформатиці, базисне дерево (також компактне префіксне дерево) — структура даних, яка є оптимізованим по пам'яті префіксним деревом, в якому кожна вершина, яка є єдиним нащадком, об'єднується з її батьком. В результаті кількість нащадків кожної внутрішньої вершини не перевищує базис r базисного дерева, де r — натуральне число і степінь x числа 2, x ≥ 1. На відміну від звичайних префіксних дерев, ребра можуть бути позначені як окремими елементами, так і їх послідовностями. Це робить базисні дерева набагато ефективнішими для малих наборів рядків (особливо, якщо рядки мають велику довжину) та для наборів, в яких рядки мають спільний префікс великої довжини. На відміну від звичайних дерев (де ключі масово порівнюються від їх початку до точки нерівності), ключ кожної вершини порівнюється блоками бітів, де кількість бітів в блоці цієї вершини дорівнює базису r базисного дерева. Коли r дорівнює 2, базисне дерево є бінарним (тобто порівнює частину з 1 біта ключа цієї вершини), що мінімізує розрідженість за рахунок максимізації глибини дерева, тобто збільшення до першого неспівпадіння бітів в рядку ключа. Коли r — степінь числа 2 та не менше 4, то базисне дерево є r-нарним, яке зменшує глибину базисного дерева за рахунок потенційної розрідженості. (uk) 在计算机科学中，基数树（Radix Trie，也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的Trie（前缀树），其中作为唯一子节点的每个节点都与其父节点合并，边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数r ，其中r为正整数，x为2的幂，x≥1，这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。 基数树的查找方式也与常规树不同（常规的树查找一开始就对整个键进行比较，直到不相同为止），基数树查找时节点时，对于节点上的键都按块进行逐块比较，其中该节点中块的长度是基数r； 当r为2时，基数树为二进制的（即该节点的键的长度为1比特位），能最大程度地减小树的深度来最小化稀疏性（最大限度地合并键中没有分叉的节点）。 当r≥4且为2的整数次幂时，基数树是r元基数树，能以潜在的稀疏性为代价降低基数树的深度。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Patricia_trie.svg?width=300 |
| dbo:wikiPageExternalLink | http://code.dogmap.org/kart/ http://cprops.sourceforge.net/gen/docs/trie_8c-source.html http://paratechnical.blogspot.com/2011/03/radix-tree-implementation-in-c.html http://cprops.sourceforge.net http://bxr.su/f/sys/net/radix.h https://db.in.tum.de/~leis/papers/ART.pdf http://www.lri.fr/~filliatr/ftp/ocaml/ds https://hackage.haskell.org/package/containers/docs/Data-IntMap-Internal.html https://hackage.haskell.org/package/containers/docs/src/Data.IntMap.Internal.html http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/ https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/lib/radix-tree.c https://nim-lang.org/docs/critbits.html https://redis.io/ https://github.com/agl/critbit https://github.com/antirez/rax https://github.com/armon/libart https://github.com/balena/radixdb https://github.com/rkapsi/patricia-trie http://cr.yp.to/critbit.html http://www.codeproject.com/KB/string/PatriciaTrieTemplateClass.aspx https://code.google.com/p/concurrent-trees/ https://code.google.com/p/hat-trie https://code.google.com/p/patl/ https://lwn.net/Articles/175432/ https://xlinux.nist.gov/dads/HTML/patriciatree.html https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html |
| dbo:wikiPageID | 1481659 (xsd:integer) |
| dbo:wikiPageLength | 18536 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1105756012 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Total_ordering dbr:Deterministic_finite_automata dbr:Unicode dbr:Deterministic_acyclic_finite_state_automaton dbr:Information_retrieval dbr:Internet_Protocol dbr:Inverted_index dbr:Prefix_hash_tree dbr:Thomas_Neumann dbr:Alfons_Kemper dbr:Monash_University dbc:String_data_structures dbr:Computer_science dbr:Burstsort dbr:Trie dbr:Data_structure dbr:HAT-trie dbr:Hash_array_mapped_trie dbr:Hash_trie dbr:Daniel_J._Bernstein dbr:Judy_array dbr:Radix dbr:Hash_table dbr:Technical_University_of_Munich dbc:Trees_(data_structures) dbr:Donald_Knuth dbr:Associative_array dbr:Huffman_coding dbr:Ternary_search_tries dbr:Search_algorithm dbr:Routing dbr:Salvatore_Sanfilippo dbr:Serialization dbr:Extendible_hashing dbr:IP_address dbr:Luleå_algorithm dbr:The_Art_of_Computer_Programming dbr:Hashtable dbr:NIST_Dictionary_of_Algorithms_and_Data_Structures dbr:Interface_(computer_science) dbr:Balanced_trees dbr:Memory_Optimization dbr:Multibyte_character dbr:Prefix_tree dbr:File:An_example_of_how_to_find_a_string_in_a_Patricia_trie.png dbr:File:Patricia_trie.svg |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:CS-Trees dbt:Commons_category dbt:Div_col dbt:Div_col_end dbt:Mvar dbt:Portal dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:String_data_structures dbc:Trees_(data_structures) |
| gold:hypernym | dbr:Structure |
| rdf:type | yago:WikicatStringDataStructures yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 dbo:Building yago:Structure105726345 yago:WikicatDataStructures |
| rdfs:comment | Komprimovaná trie je datová struktura, pojem z oboru matematické informatiky. Jedná se o strukturou podobou triím, ale zatímco u trie je na každé hraně jen jediný znak, u komprimované trie jich tam může být víc, pokud jsou společné všem potomkům daného vrcholu. Oproti běžným triím tak použití komprimované trie může šetřit počítačovou paměť. Tento typ struktury má několik alternativních názvů, mj. Patricia-trie, přičemž s názvem PATRICIA coby zkratkou svého stejnojmenného článku je zavedl v roce 1968 . Komprimované trie se používají mj. pro realizaci asociativních polí. (cs) En informatique, un arbre radix ou arbre PATRICIA (pour Practical Algorithm To Retrieve Information Coded In Alphanumeric en anglais et signifiant algorithme commode pour extraire de l'information codée en alphanumérique) est une structure de données compacte permettant de représenter un ensemble de mots adaptée pour la recherche. Il est obtenu à partir d'un arbre préfixe en fusionnant chaque nœud n'ayant qu'un seul fils avec celui-ci. On peut alors étiqueter indifféremment chaque arête par un mot ou bien par une unique lettre. (fr) 基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。 (ja) Skompresowane drzewo trie (również: drzewo Patricia, drzewo pozycyjne) – struktura danych przechowująca zbiór ciągów. (pl) 在计算机科学中，基数树（Radix Trie，也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的Trie（前缀树），其中作为唯一子节点的每个节点都与其父节点合并，边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数r ，其中r为正整数，x为2的幂，x≥1，这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。 基数树的查找方式也与常规树不同（常规的树查找一开始就对整个键进行比较，直到不相同为止），基数树查找时节点时，对于节点上的键都按块进行逐块比较，其中该节点中块的长度是基数r； 当r为2时，基数树为二进制的（即该节点的键的长度为1比特位），能最大程度地减小树的深度来最小化稀疏性（最大限度地合并键中没有分叉的节点）。 当r≥4且为2的整数次幂时，基数树是r元基数树，能以潜在的稀疏性为代价降低基数树的深度。 (zh) In der Informatik ist ein Patricia-Trie (abgeleitet aus dem engl. reTrieval) eine Datenstruktur, genauer eine spezielle Art eines Tries zur gleichzeitigen Speicherung von mehreren Zeichenketten. Seinen Namen verdankt er dem Akronym PATRICIA, das für Practical Algorithm to Retrieve Information Coded in Alphanumeric steht. Er wurde 1968 von veröffentlicht. Patricia-Tries können dazu verwendet werden, assoziative Arrays mit Strings als Schlüsseln zu konstruieren. Hiermit wird Speicherplatz für die Schlüssel gespart. (de) In computer science, a radix tree (also radix trie or compact prefix tree or compressed trie) is a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent. The result is that the number of children of every internal node is at most the radix r of the radix tree, where r is a positive integer and a power x of 2, having x ≥ 1. Unlike regular trees, edges can be labeled with sequences of elements as well as single elements. This makes radix trees much more efficient for small sets (especially if the strings are long) and for sets of strings that share long prefixes. (en) A árvore PATRICIA é uma representação compacta de uma Trie onde os nós que teriam apenas um filho são agrupados nos seus antecessores. É comum que as árvores Trie possuam um grupo disperso de chaves, desse modo, muitos nós possuem apenas um descendente. Isto faz com que as Trie tenham um custo grande de espaço. Uma Trie usa cada uma das partes de uma chave, por vez, para determinar a sub-árvore. Por outro lado, a árvore PATRICIA escolhe um elemento da chave (armazenando a sua posição) para determinar a sub-árvore. Isso remove a necessidade de nós com apenas um descendente. (pt) Базисное дерево (англ. radix tree, также компактное префиксное дерево, основное дерево, дерево остатков) — это структура данных, представляющая собой оптимизированную по памяти реализацию префиксного дерева. В базисном дереве узел , являющийся единственным потомком узла , сливается с узлом . Временная сложность операций поиска, добавления и удаления элемента из базисного дерева оценивается как , где — длина обрабатываемого элемента. Время работы не зависит от количества элементов в дереве. (ru) В інформатиці, базисне дерево (також компактне префіксне дерево) — структура даних, яка є оптимізованим по пам'яті префіксним деревом, в якому кожна вершина, яка є єдиним нащадком, об'єднується з її батьком. В результаті кількість нащадків кожної внутрішньої вершини не перевищує базис r базисного дерева, де r — натуральне число і степінь x числа 2, x ≥ 1. На відміну від звичайних префіксних дерев, ребра можуть бути позначені як окремими елементами, так і їх послідовностями. Це робить базисні дерева набагато ефективнішими для малих наборів рядків (особливо, якщо рядки мають велику довжину) та для наборів, в яких рядки мають спільний префікс великої довжини. (uk) |
| rdfs:label | Komprimovaná trie (cs) Patricia-Trie (de) Arbre radix (fr) 基数木 (ja) Radix tree (en) Skompresowane drzewo trie (pl) Árvore Patricia (pt) Сжатое префиксное дерево (ru) 基数树 (zh) Базисне дерево (uk) |
| owl:sameAs | freebase:Radix tree yago-res:Radix tree wikidata:Radix tree dbpedia-cs:Radix tree dbpedia-de:Radix tree dbpedia-fa:Radix tree dbpedia-fr:Radix tree dbpedia-ja:Radix tree dbpedia-pl:Radix tree dbpedia-pt:Radix tree dbpedia-ru:Radix tree dbpedia-sr:Radix tree dbpedia-th:Radix tree dbpedia-uk:Radix tree dbpedia-zh:Radix tree https://global.dbpedia.org/id/Mhsp |
| prov:wasDerivedFrom | wikipedia-en:Radix_tree?oldid=1105756012&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/An_example_of_how_to_find_a_string_in_a_Patricia_trie.png wiki-commons:Special:FilePath/Insert_'slower'_with_a_null_node_into_a_Patricia_trie.png wiki-commons:Special:FilePath/Insert_'test'_into_a_Patricia_trie_when_'tester'_exists.png wiki-commons:Special:FilePath/Insert_'toast'_into_a_Patricia_trie_with_a_split_and_a_move.png wiki-commons:Special:FilePath/Inserting_the_string_'water'_into_a_Patricia_trie.png wiki-commons:Special:FilePath/Inserting_the_word_'team'_into_a_Patricia_trie_with_a_split.png wiki-commons:Special:FilePath/Patricia_trie.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Radix_tree |
| is dbo:wikiPageDisambiguates of | dbr:Radix_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Patricia_tree dbr:Patricia_trie dbr:Crit_bit_tree dbr:Crit-bit_tree dbr:PATRICIA dbr:PATRICIA_tree dbr:PATRICIA_trie dbr:Radix_trie dbr:Radixtree dbr:Crit_bit_trie dbr:Patricia-trie dbr:Patricia_trees dbr:Compact_prefix_tree |
| is dbo:wikiPageWikiLink of | dbr:List_of_data_structures dbr:Merkle_tree dbr:Morphological_parsing dbr:Patricia_tree dbr:Patricia_trie dbr:Perst dbr:T-tree dbr:Crit_bit_tree dbr:Array_(data_structure) dbr:Linux_kernel dbr:Trie dbr:Crit-bit_tree dbr:Hash_array_mapped_trie dbr:EXtremeDB dbr:PATRICIA dbr:Forwarding_plane dbr:Judy_array dbr:Radix_(disambiguation) dbr:Binary_decision_diagram dbr:Associative_array dbr:Knot_DNS dbr:Radix_sort dbr:PATRICIA_tree dbr:PATRICIA_trie dbr:Radix_trie dbr:Radixtree dbr:Crit_bit_trie dbr:Patricia-trie dbr:Patricia_trees dbr:Compact_prefix_tree |
| is foaf:primaryTopic of | wikipedia-en:Radix_tree |
