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)
|