| dbpprop:abstract
|
- In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree shows what key it is associated with. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. The term trie comes from "retrieval. " Following the etymology, the inventor, Edward Fredkin, pronounces it /ˈtriː/ "tree". However, it is pronounced /ˈtraɪ/ "try" by other authors. In the example shown, keys are listed in the nodes and values below them. Each complete English word has an arbitrary integer value associated with it. A trie can be seen as a deterministic finite automaton, although the symbol on each edge is often implicit in the order of the branches. It is not necessary for keys to be explicitly stored in nodes. (In the figure, words are shown only to illustrate how the trie works. ) Though it is most common, tries need not be keyed by character strings. The same algorithms can easily be adapted to serve similar functions of ordered lists of any construct, e.g. , permutations on a list of digits or shapes.
- Ein Trie oder Präfixbaum ist eine Datenstruktur, die in der Informatik zum Suchen nach Zeichenketten verwendet wird. Es handelt sich dabei um einen speziellen Suchbaum zur gleichzeitigen Speicherung mehrerer Zeichenketten. Das Wort Trie wurde von Edward Fredkin empfohlen und leitete sich aus dem englischen Wort Information Retrieval ab. In einem Trie repräsentiert jede Kante des Baums einen zusätzlichen Buchstaben. Jeder Knoten entspricht der Zeichenkette, die aus der Verkettung aller Kantenbuchstaben entsteht. Der Wurzelknoten eines Trie entspricht einer leeren Zeichenkette. Um Daten in komprimierter Form in einem Trie abzulegen, werden Patricia-Tries benutzt.
- Un trie és un cas especial d'autòmat finit determinista <math>(S, \Sigma, T, s, A)</math>, que serveix per a emmagatzemar un conjunt de cadenes <math>E</math> en el qual: <math>\Sigma</math> és l'alfabet sobre el qual estan definides les cadenes; <math>S</math>, el conjunt d'estats, cadascun dels quals representa un prefix de E; la funció de transició: <math>T : S \times \Sigma \to S</math>; està definida com segueix: <math>T(x,\sigma)=x\sigma</math> si <math>x, x\sigma \in S</math>, i indefinida altrament; l'estat inicial <math>s</math> correspon a la cadena buida <math>\lambda;</math> el conjunt d'estats d'acceptació <math>A \subseteq S</math> és igual a <math>E</math>. El seu nom procedeix del terme anglés retrieval.
- Trie nebo prefixový strom je datová struktura, která se používá pro uchovávání asociativního pole, kde klíči jsou obvykle řetězce. Na rozdíl od binárního vyhledávacího stromu, kde se podle hodnoty uzlu rozhoduje, do které větve sestoupit, trie v každém uzlu obsahuje všechny podřetězce, kterými může pokračovat řetězec v dosud prohledané cestě. Všichni následníci uzlu mají společný prefix, který je shodný s řetězcem přiřazeným k danému uzlu. Kořen je asociovaný s prázdným řetězcem. Hodnoty obvykle nejsou asociovány se všemi uzly, ale jen s listy a některými vnitřními uzly, které odpovídají klíčům. Slovo trie pochází z anglického „retrieval“ – získávání, vyhledávání. V uvedeném příkladu jsou klíče v uzlech a hodnoty pod nimi. Na trie může být nazíráno jako deterministický konečný automat, ačkoli symbol na každé hraně je často implicitní v pořadí větví. Přestože je to obvyklé, trie nemusí mít jako klíče textové řetězce. Stejné algoritmy mohou být snadno upraveny, aby sloužily podobným funkcím na seznamech jakékoliv podoby, např. permutace na seznamu číslic, permutace na seznamu tvarů atd.
- Su nombre procede del término inglés retrieval.
- En informatique, un trie (prefix-tree) est un arbre numérique ordonné qui est utilisé pour stocker une table associative où les clés sont généralement des chaînes de caractères. Contrairement à un arbre binaire de recherche, aucun nœud dans le trie ne stocke la chaîne à laquelle il est associé. C'est la position du nœud dans l'arbre qui détermine la chaîne correspondante. Pour tout nœud, ses descendants ont en commun le même préfixe. La racine est associée à la chaîne vide. Des valeurs ne sont pas attribuées à chaque nœud, mais uniquement aux feuilles et à certains nœuds internes se trouvant à une position qui désigne l'intégralité d'une chaîne correspondant à une clé. Le terme de trie vient de l'anglais retrieval.
- トライ木（Trie）とは、順序付き木構造 (データ構造)の一種。プレフィックス木（Prefix Tree）とも呼ばれる。キーが文字列である連想配列の実装構造として使われる。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。 Trie という名称は "retrieval"（探索、検索）が語源であるため、"tree" と同じ発音を用いる（リトゥリーヴァル）。しかし、ツリー構造との混同を避けるために「トライ」という読み方を奨励する人もいる。日本語では、「トライ木」という呼び方がほぼ定着している。 右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。 キーは必ずしもノードに格納される必要はない。右図はトライ木の概念を示したもので実装は一般に異なる。 トライ木のキーは必ずしも文字列である必要はない。トライ木のアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。
- Drzewo trie (wym. traj; od ang. retrieval, czyli odczyt) — drzewo poszukiwań przechowujące w węzłach fragmenty kluczy ("zwykłe" drzewa poszukiwań - np. BST, AVL - przechowują w węzłach całe klucze). To pozwala przyspieszyć wyszukiwanie, gdy koszt porównania całego klucza jest duży. Przechowując fragmenty kluczy, drzewa trie są najlepiej przystosowane do kluczy reprezentowanych jako ciąg elementów skończonego alfabetu. Przez to są stosowane do sprawdzania poprawności pisowni i dzielenia wyrazów. Do reprezentacji drzew trie w pamięci RAM stosuje się drzewa łączone, gdzie każdy węzeł zawiera znak klucza, a liść zawiera odnośnik do danych, drzewa indeksowane, gdzie każda gałąź to tablica zawierająca cały alfabet z odnośnikami do danych i następnych gałęzi. W programie TeX82 użyto spakowane drzewa trie, które łączyły czas wyszukiwania drzew indeksowanych z małym zużyciem pamięci drzew łączonych. Ze względu na trudność dodawania elementów do tej reprezentacji, do ich tworzenia zastosowano drzewa łączone. Modyfikacją drzew trie są drzewa Patricia, w których węzły mające tylko jednego syna są usuwane, a drzewo odpowiednio modyfikowane. Dzięki temu skracane są ścieżki w drzewie, co przekłada się na mniejszą liczbę koniecznych porównań.
- Em ciência da computação, uma trie, ou árvore de prefixos, é uma estrutura de dados do tipo árvore ordenada, que pode ser usada para armazenar um array associativo em que as chaves são normalmente cadeias de caracteres. O termo trie vem do inglês "retrieval" (recuperação), porque essa estrutura é basicamente usada na recuperação de dados. De acordo com essa etimologia ele é pronunciado [tri] ("tree"), embora alguns encoragem o uso de [traɪ] ("try") de modo a diferenciá-lo do termo mais geral tree. Ao contrário de uma árvore de busca binária, nenhum nó nessa árvore armazena a chave associada a ele; ao invés disso, ela é determinada pela sua posição na árvore. Todos os descendentes de qualquer nó têm um prefixo comum com a cadeia associada com aquele nó, e a raiz é associada com a cadeia vazia. Normalmente, valores não são associados com todos os nós, apenas com as folhas e alguns nós internos que correspondem a chaves de interesse. No exemplo mostrado na imagem, as chaves estão listadas nos nós e os valores abaixo dos mesmos. Cada palavra completa tem um valor inteiro associado a ela. Uma trie pode ser vista como um autômato finito determinístico, embora o símbolo em cada aresta é freqüentemente implícito na ordem dos galhos. Não é necessário que as chaves sejam explicitamente armazenadas nos nós. (Na imagem, as palavras são mostradas apenas para ilustrar como a trie funciona. ) Embora seja o mais comum, tries não precisam utilizar cadeias de caracteres como chaves. Os mesmos algoritmos podem facilmente ser adaptados para funções similares de listas ordenadas de qualquer construção, como permutações em uma lista de dígitos, etc.
- Префиксное дерево — абстрактный тип данных, структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. В отличие от бинарных деревьев, в листьях дерева не хранится ключ. Значение ключа можно получить просмотром всех родительских узлов, каждый из которых хранит один или несколько символов алфавита. Корень дерева связан с пустой строкой. Таким образом, потомки узла имеют общий префикс, откуда и произошло название данного АТД. Значения, связанные с ключом, обычно не связаны с каждым узлом, а только с листьями и, возможно, некоторыми внутренними узлами. Альтернативные названия на русском — бор (первый перевод монографии Д. Кнута, Т.3), луч (второй перевод монографии Д. Кнута, Т.3), нагруженное дерево (книга Ахо и др. «Структуры данных и алгоритмы», стр.152), там же и происхождение названия. На английском — Trie.
- Префіксне дерево — абстрактний тип даних, структура даних, що дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами.
- Trie，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
|
| rdfs:comment
|
- In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree shows what key it is associated with. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.
- Ein Trie oder Präfixbaum ist eine Datenstruktur, die in der Informatik zum Suchen nach Zeichenketten verwendet wird. Es handelt sich dabei um einen speziellen Suchbaum zur gleichzeitigen Speicherung mehrerer Zeichenketten. Das Wort Trie wurde von Edward Fredkin empfohlen und leitete sich aus dem englischen Wort Information Retrieval ab. In einem Trie repräsentiert jede Kante des Baums einen zusätzlichen Buchstaben.
- Trie nebo prefixový strom je datová struktura, která se používá pro uchovávání asociativního pole, kde klíči jsou obvykle řetězce. Na rozdíl od binárního vyhledávacího stromu, kde se podle hodnoty uzlu rozhoduje, do které větve sestoupit, trie v každém uzlu obsahuje všechny podřetězce, kterými může pokračovat řetězec v dosud prohledané cestě. Všichni následníci uzlu mají společný prefix, který je shodný s řetězcem přiřazeným k danému uzlu.
- Su nombre procede del término inglés retrieval.
- En informatique, un trie (prefix-tree) est un arbre numérique ordonné qui est utilisé pour stocker une table associative où les clés sont généralement des chaînes de caractères. Contrairement à un arbre binaire de recherche, aucun nœud dans le trie ne stocke la chaîne à laquelle il est associé. C'est la position du nœud dans l'arbre qui détermine la chaîne correspondante. Pour tout nœud, ses descendants ont en commun le même préfixe.
- Drzewo trie (wym. traj; od ang. retrieval, czyli odczyt) — drzewo poszukiwań przechowujące w węzłach fragmenty kluczy ("zwykłe" drzewa poszukiwań - np. BST, AVL - przechowują w węzłach całe klucze). To pozwala przyspieszyć wyszukiwanie, gdy koszt porównania całego klucza jest duży. Przechowując fragmenty kluczy, drzewa trie są najlepiej przystosowane do kluczy reprezentowanych jako ciąg elementów skończonego alfabetu.
- Em ciência da computação, uma trie, ou árvore de prefixos, é uma estrutura de dados do tipo árvore ordenada, que pode ser usada para armazenar um array associativo em que as chaves são normalmente cadeias de caracteres. O termo trie vem do inglês "retrieval" (recuperação), porque essa estrutura é basicamente usada na recuperação de dados.
- Префиксное дерево — абстрактный тип данных, структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. В отличие от бинарных деревьев, в листьях дерева не хранится ключ.
- Префіксне дерево — абстрактний тип даних, структура даних, що дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ.
- Trie，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
|
![[RDF Data]](/statics/sw-cube.png)
