| dbo:abstract
|
- في علوم الكمبيوتر، يُطلق على trie أيضًا اسم الشجرة الرقمية أو شجرة البادئة ، وهو نوع من شجرة البحث، وهي بنية بيانات شجرة تُستخدم لتحديد موقع مفاتيح معينة من داخل مجموعة. وغالبًا ما تكون هذه المفاتيح عبارة عن سلاسل، ومع روابط بين العقد لا يتم تعريفها بواسطة المفتاح بأكمله، ولكن بواسطة الأحرف الفردية. ومن أجل الوصول إلى مفتاح (لاستعادة قيمته أو تغييره أو إزالته)، يتم اجتياز الثلاثي في العمق أولاً، باتباع الروابط بين العقد، والتي تمثل كل حرف في المفتاح. وعلى عكس شجرة البحث الثنائية، لا تخزن العقد الموجودة في المثلث المفتاح المرتبط بها. بدلاً من ذلك، يحدد موضع العقدة في المثلث المفتاح الذي يرتبط به. يوزع هذا قيمة كل مفتاح عبر بنية البيانات، ويعني أنه ليس بالضرورة أن يكون لكل عقدة مفتاح مرتبط. وجميع توابع العقدة لديهم بادئة مشتركة للسلسلة المرتبطة بالعقدة الأصلية، والجذر مرتبط بالسلسلة الفارغة. حيث يمكن إنجاز مهمة تخزين البيانات التي يمكن الوصول إليها من خلال بادئتها بطريقة محسّنة للذاكرة من خلال استخدام شجرة الجذر. وعلى الرغم من إمكانية تحديد المحاولات بسلاسل الأحرف، إلا أنه لا يلزم أن تكون كذلك. ويمكن تكييف نفس الخوارزميات للقوائم المرتبة من أي نوع أساسي، مثل تبديل الأرقام أو الأشكال. وعلى وجه الخصوص، يتم تمييز ثلاثي أحادي البتات على البتات الفردية التي تشكل قطعة من البيانات الثنائية ذات الطول الثابت، مثل رقم صحيح أو عنوان الذاكرة. (ar)
- Trie nebo prefixový strom je datová struktura, která se používá pro uchovávání dvojic klíč-hodnota, 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. 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. (cs)
- Un trie és un cas especial d'autòmat finit determinista , que serveix per a emmagatzemar un conjunt de cadenes en el qual:
* és l'alfabet sobre el qual estan definides les cadenes;
* , el conjunt d'estats, cadascun dels quals representa un prefix de E;
* la funció de transició: ; està definida com segueix: si , i indefinida altrament;
* l'estat inicial correspon a la cadena buida
* el conjunt d'estats d'acceptació és igual a . El seu nom procedeix del terme anglés retrieval. (ca)
- 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. Dabei beinhalten Tries eine Art der Datenkompression, da gemeinsame Präfixe der Zeichenketten nur einmal gespeichert werden. Ein Trie wird über eine Menge von beliebigen Zeichenketten aufgebaut. Jede ausgehende Kante eines Knotens innerhalb eines Tries ist mit einem einzelnen Zeichen versehen, sodass ein Pfad beginnend bei der Wurzel bis zu einem Blatt im Trie eine der Zeichenketten darstellt, aus denen der Baum konstruiert worden ist. Tries finden ihre Anwendung im Bereich des Information Retrieval. Dort werden sie zur Indexierung von Texten verwendet, um effizient bestimmte Anfragen an den Text zu beantworten. Kompakte Tries oder auch Patricia-Tries (eine spezielle Variante von kompakten Tries) sind im Bezug auf Speicherplatzverbrauch optimierte Varianten des Tries. Hier werden alle Knoten, von denen nur eine Kante ausgeht, mit ihrem jeweiligen Nachfolger zusammengefasst. Der Ausdruck Trie wurde von Edward Fredkin in Anlehnung an den Begriff Information Retrieval vorgeschlagen. Dieser Autor spricht ihn wie den englischen Begriff tree ['triː] aus. Eine andere übliche Aussprache ist wie der englische Begriff try ['traɪ], wodurch der Trie verbal von der Datenstruktur Tree unterschieden wird. Diese zweite Variante hat sich mittlerweile durchgesetzt. (de)
- Introducidos en 1959 independientemente por y , un trie es una estructura de datos de tipo árbol que permite la recuperación de información (de ahí su nombre del inglés reTRIEval). La información almacenada en un trie es un conjunto de claves, donde una clave es una secuencia de símbolos pertenecientes a un alfabeto. Las claves son almacenadas en las hojas del árbol y los nodos internos son pasarelas para guiar la búsqueda. El árbol se estructura de forma que cada letra de la clave se sitúa en un nodo de forma que los hijos de un nodo representan las distintas posibilidades de símbolos diferentes que pueden continuar al símbolo representado por el nodo padre. Por tanto la búsqueda en un trie se hace de forma similar a como se hacen las búsquedas en un diccionario: Se empieza en la raíz del árbol. Si el símbolo que estamos buscando es A entonces la búsqueda continúa en el subárbol asociado al símbolo A que cuelga de la raíz. Se sigue de forma análoga hasta llegar al nodo hoja. Entonces se compara la cadena asociada al nodo hoja y si coincide con la cadena de búsqueda entonces la búsqueda ha terminado en éxito, si no entonces el elemento no se encuentra en el árbol. Por eficiencia se suelen eliminar los nodos intermedios que sólo tienen un hijo, es decir, si un nodo intermedio tiene sólo un hijo con cierto carácter entonces el nodo hijo será el nodo hoja que contiene directamente la clave completa. Es muy útil para conseguir búsquedas eficientes en repositorios de datos muy voluminosos. La forma en la que se almacena la información permite hacer búsquedas eficientes de cadenas que comparten prefijos. (es)
- En informatique, un ou une trie (prononcé [ˈtriː] ou [ˈtraɪ]) ou arbre préfixe, est une structure de données ayant la forme d'un arbre enraciné. Il 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, signifiant extraction, recherche. (fr)
- In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key. Unlike a binary search tree, nodes in the trie do not store their associated key. Instead, a node's position in the trie defines the key with which it is associated. This distributes the value of each key across the data structure, and means that not every node necessarily has an associated value. All the children of a node have a common prefix of the string associated with that parent node, and the root is associated with the empty string. This task of storing data accessible by its prefix can be accomplished in a memory-optimized way by employing a radix tree. Though tries can be keyed by character strings, they need not be. The same algorithms can be adapted for ordered lists of any underlying type, e.g. permutations of digits or shapes. In particular, a bitwise trie is keyed on the individual bits making up a piece of fixed-length binary data, such as an integer or memory address. The key lookup complexity of a trie remains proportional to the key size. Specialized trie implementations such as compressed tries are used to deal with the enormous space requirement of a trie in naive implementations. (en)
- 트라이(trie)는 컴퓨터 과학에서 의 일종이다. 동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조이다. 주로 문자열이 키인 경우가 많다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. 일부 내부 노드가 키에 대응할 수도 있지만, 일반적으로 키는 단말에 연관되는 경향이 있다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 메모리에 최적화 된 경우는 가 된다. 예시에서 키는 노드에, 값은 그 아래에 있다. 완전한 단어 키마다 연관된 임의의 정수가 있는 식이다. 트라이는 트리 모양인 결정적 유한 오토마타로 볼 수도 있다. 트라이 오토마타로 생성한 각 유한 언어(finite language)는 로 압축할 수 있다. 트라이는 문자열이 키인 경우가 흔하지만, 꼭 그래야 하는 것은 아니다. 어떻게 구성된 정렬된 리스트라도 비슷한 기능을 제공할 수 있는 동등한 알고리즘을 적용할 수만 있다면 상관 없다. 이를테면 숫자나 도형의 리스트로 구성한 순열 같은 것이 가능하다. 정수나 메모리 주소 같은 고정 길이 이진 자료를 표현하는 각각의 비트로 구성된 트라이를 특별히 비트 트라이라고 부른다. (ko)
- トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。 トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。 キーは必ずしもノードに格納される必要はない。右図はトライ木の概念を示したもので実装は一般に異なる。 トライ木のキーは必ずしも文字列である必要はない。トライ木のアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。 trie という名称は "retrieval"（探索、検索）が語源であるため、"tree" と同じ発音を用いる（リトゥリーヴァル）。しかし、ツリー構造との混同を避けるために「トライ」という読み方を奨励する人もいる。日本語では、「トライ木」という呼び方がほぼ定着している。 (ja)
- In informatica, un trie (pronunciato /ˈtriː/ oppure /ˈtraɪ/) è un tipo di struttura dati ad albero ordinato usata per rappresentare un set o un array associativo le cui chiavi sono tipicamente stringhe. A differenza di un albero binario di ricerca, i nodi non conservano una copia della propria chiave, che dipende invece dalla posizione del nodo nell'albero. La radice dell'albero è associata alla stringa vuota, e tutti i discendenti di un nodo condividono il prefisso associato a quel nodo. Non tutti i nodi rappresentano necessariamente una chiave significativa, che tipicamente si trova invece nelle foglie ed eventualmente in alcuni, ma non necessariamente tutti, i nodi interni. Un trie può essere visto come una particolare istanza di automa a stati finiti deterministico: tutti i linguaggi finiti hanno un corrispondente trie che li rappresenta, e ogni trie può essere associato a un automa a stati finiti deterministico aciclico. (it)
- Drzewo trie (wym. tri od ang. retrieval – odczyt; lub traj by odróżnić od tree) – 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. Działania jakie można zrealizować za pomocą drzew trie:
* sprawdzenie, czy słowo jest w drzewie (w czasie gdzie długość słowa);
* znalezienie najdłuższego prefiksu słowa występującego w drzewie (w czasie gdzie długość prefiksu);
* wyszukanie wszystkich słów o podanym prefiksie. W słowach mogą występować również lokalne znaki wieloznaczne, co nie komplikuje znacząco wyszukiwania. 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ń. (pl)
- Префиксное дерево (также бор, луч, нагруженное дерево, англ. trie) — структура данных, позволяющая хранить ассоциативный массив, ключами которого чаще всего являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до некоторого (единственного для этой строки) выделенного узла. В некоторых приложениях удобно считать все узлы дерева выделенными. Таким образом, в отличие от бинарных деревьев поиска, ключ, идентифицирующий конкретный узел дерева, не явно хранится в данном узле, а задаётся положением данного узла в дереве. Получить ключ можно выписыванием подряд символов, помечающих рёбра на пути от корня до узла. Ключ корня дерева — пустая строка. Часто в выделенных узлах хранят дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья и, возможно, некоторые внутренние узлы. (ru)
- 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. Edward Fredkin, o inventor, usa o termo trie (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. (pt)
- Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса. Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами. (uk)
- 在计算机科学中，trie，又称前缀树或字典樹，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 Trie这个术语来自于retrieval。根据词源学，trie的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是，其他作者把它读作/ˈtraɪ/ "try"。 在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。 键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示trie的原理。 trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie中的键是一串位元，可以用于表示整数或者内存地址。 (zh)
|
| rdfs:comment
|
- Un trie és un cas especial d'autòmat finit determinista , que serveix per a emmagatzemar un conjunt de cadenes en el qual:
* és l'alfabet sobre el qual estan definides les cadenes;
* , el conjunt d'estats, cadascun dels quals representa un prefix de E;
* la funció de transició: ; està definida com segueix: si , i indefinida altrament;
* l'estat inicial correspon a la cadena buida
* el conjunt d'estats d'acceptació és igual a . El seu nom procedeix del terme anglés retrieval. (ca)
- 在计算机科学中，trie，又称前缀树或字典樹，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 Trie这个术语来自于retrieval。根据词源学，trie的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是，其他作者把它读作/ˈtraɪ/ "try"。 在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。 键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示trie的原理。 trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie中的键是一串位元，可以用于表示整数或者内存地址。 (zh)
- في علوم الكمبيوتر، يُطلق على trie أيضًا اسم الشجرة الرقمية أو شجرة البادئة ، وهو نوع من شجرة البحث، وهي بنية بيانات شجرة تُستخدم لتحديد موقع مفاتيح معينة من داخل مجموعة. وغالبًا ما تكون هذه المفاتيح عبارة عن سلاسل، ومع روابط بين العقد لا يتم تعريفها بواسطة المفتاح بأكمله، ولكن بواسطة الأحرف الفردية. ومن أجل الوصول إلى مفتاح (لاستعادة قيمته أو تغييره أو إزالته)، يتم اجتياز الثلاثي في العمق أولاً، باتباع الروابط بين العقد، والتي تمثل كل حرف في المفتاح. (ar)
- Trie nebo prefixový strom je datová struktura, která se používá pro uchovávání dvojic klíč-hodnota, 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. 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. (cs)
- 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. Dabei beinhalten Tries eine Art der Datenkompression, da gemeinsame Präfixe der Zeichenketten nur einmal gespeichert werden. Tries finden ihre Anwendung im Bereich des Information Retrieval. Dort werden sie zur Indexierung von Texten verwendet, um effizient bestimmte Anfragen an den Text zu beantworten. (de)
- Introducidos en 1959 independientemente por y , un trie es una estructura de datos de tipo árbol que permite la recuperación de información (de ahí su nombre del inglés reTRIEval). La información almacenada en un trie es un conjunto de claves, donde una clave es una secuencia de símbolos pertenecientes a un alfabeto. Las claves son almacenadas en las hojas del árbol y los nodos internos son pasarelas para guiar la búsqueda. El árbol se estructura de forma que cada letra de la clave se sitúa en un nodo de forma que los hijos de un nodo representan las distintas posibilidades de símbolos diferentes que pueden continuar al símbolo representado por el nodo padre. Por tanto la búsqueda en un trie se hace de forma similar a como se hacen las búsquedas en un diccionario: (es)
- In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key. (en)
- En informatique, un ou une trie (prononcé [ˈtriː] ou [ˈtraɪ]) ou arbre préfixe, est une structure de données ayant la forme d'un arbre enraciné. Il 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. Le terme de trie vient de l'anglais retrieval, signifiant extraction, recherche. (fr)
- In informatica, un trie (pronunciato /ˈtriː/ oppure /ˈtraɪ/) è un tipo di struttura dati ad albero ordinato usata per rappresentare un set o un array associativo le cui chiavi sono tipicamente stringhe. A differenza di un albero binario di ricerca, i nodi non conservano una copia della propria chiave, che dipende invece dalla posizione del nodo nell'albero. La radice dell'albero è associata alla stringa vuota, e tutti i discendenti di un nodo condividono il prefisso associato a quel nodo. Non tutti i nodi rappresentano necessariamente una chiave significativa, che tipicamente si trova invece nelle foglie ed eventualmente in alcuni, ma non necessariamente tutti, i nodi interni. (it)
- トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。 トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。 キーは必ずしもノードに格納される必要はない。右図はトライ木の概念を示したもので実装は一般に異なる。 トライ木のキーは必ずしも文字列である必要はない。トライ木のアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。 (ja)
- 트라이(trie)는 컴퓨터 과학에서 의 일종이다. 동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조이다. 주로 문자열이 키인 경우가 많다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. 일부 내부 노드가 키에 대응할 수도 있지만, 일반적으로 키는 단말에 연관되는 경향이 있다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 메모리에 최적화 된 경우는 가 된다. 예시에서 키는 노드에, 값은 그 아래에 있다. 완전한 단어 키마다 연관된 임의의 정수가 있는 식이다. 트라이는 트리 모양인 결정적 유한 오토마타로 볼 수도 있다. 트라이 오토마타로 생성한 각 유한 언어(finite language)는 로 압축할 수 있다. (ko)
- Drzewo trie (wym. tri od ang. retrieval – odczyt; lub traj by odróżnić od tree) – 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. Działania jakie można zrealizować za pomocą drzew trie: (pl)
- 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. Edward Fredkin, o inventor, usa o termo trie (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. (pt)
- Префиксное дерево (также бор, луч, нагруженное дерево, англ. trie) — структура данных, позволяющая хранить ассоциативный массив, ключами которого чаще всего являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены (на рисунке они подписаны цифрами) и считается, что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до некоторого (единственного для этой строки) выделенного узла. В некоторых приложениях удобно считать все узлы дерева выделенными. (ru)
- Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса. (uk)
|
