Trie

Trie pro klíče „A“, „to“, „tea“, „ted“, „ten“, „i“, „in“ a „inn“

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ě. +more 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ř. +more permutace na seznamu číslic, permutace na seznamu tvarů atd.

Výhody a nevýhody trie vzhledem k binárnímu vyhledávacímu stromu

Výhody oproti binárnímu vyhledávacímu stromu:

* Nalezení klíče je rychlejší. Nalezení klíče délky m trvá v nejhorším případě O(m). +more BVS to trvá O(log n), kde n je počet prvků ve stromě, protože vyhledávání závisí na hloubce stromu, která je logaritmická v počtu klíčů. Jednoduché operace, které používá trie během vyhledávání, jako je indexování pole pomocí znaku, jsou v praxi rychlejší. * Trie potřebuje méně paměti, pokud obsahuje velký počet krátkých řetězců, protože klíče nejsou uchovávány explicitně, a uzly jsou tak sdíleny klíči se společnými začátky. * Trie pomáhají při hledání nejdelšího prefixu, kde je úkolem najít klíč sdílející nejdelší možný prefix unikátních znaků. Konstrukce trie, ať už dávková nebo postupným přidáváním, je implementačně trochu složitější než u binárního vyhledávacího stromu. To platí zvláště při použití optimalizací a optimalizovaných variant.

Užití

Jako náhrada jiných datových struktur

Trie může nahradit hašovací tabulku, oproti které má následující výhody:

* Vyhledání dat v trie je rychlejší v nejhorším případě, tj. O(m), oproti hašovací tabulce s kolizemi O(N), typicky však O(1). +more * Nenastávají žádné kolize různých klíčů. * Datová struktura pro uchovávání kolizních klíčů je potřeba pouze v případě, že více hodnot má přiřazeno totožný klíč. * Není třeba hašovací funkce nebo její změna při přidávání dalších klíčů. * Trie může poskytnout abecední řazení záznamů podle klíče.

Má také ale nevýhody: * Trie může být v některých případech pomalejší než hašovací tabulka při vyhledávání dat, zejména pokud je k nim přistupováno na pevném disku nebo podobných zařízeních, kde je doba náhodného přístupu velká vůči hlavní paměti. * Trie je často méně paměťově efektivní než hašovací tabulka.

Reprezentace slovníku

Častou aplikací trie je uložení slovníku, např. v mobilních telefonech. +more To využívá schopnosti trie rychle vyhledávat, vkládat a odstraňovat záznamy.

Trie je také vhodné pro implementaci algoritmů přibližného matchování, jako jsou ty používané v programech pro kontrolu pravopisu.

Algoritmy

Následující pseudokód ukazuje obecný algoritmus zjišťující, jestli je daný řetězec v trie. Pole naslednici obsahuje následníky uzlu, koncový uzel je ten, který obsahuje platné slovo. +more function jeVTrie(uzel, klic): if (klic je prazdny retezec): # výchozí případ return je uzel koncový. else: #rekurzivní případ c = prvni znak v klici #funguje, protože klíč není prázdný sufix = klic minus prvni znak naslednik = uzel. naslednici[c] if (naslednik je prazdny): #nelze rekurze, ale klíč je neprázdný return false else: jeVTrie(naslednik, sufix).

Řazení

Lexikografické řazení skupiny prvků může být provedeno jednoduchým algoritmem založeným na trie:

* Vlož všechny klíče do trie. * Vrať všechny klíče v trie +moreC3. A1zen. C3. AD_stromem_do_hloubky'>průchodem preorder, který způsobí, že výstup je ve lexikograficky vzestupném pořadí, nebo postorder, díky němuž bude výstup v sestupném pořadí. Průchod preorder a postorder jsou dva druhy průchodu do hloubky.

Tento algoritmus je formou číslicového řazení.

Trie tvoří základní datovou strukturu burstsortu, v současné době nejrychlejšího známého algoritmu pro řazení řetězců založeném na využití cache.

Paralelní algoritmus pro řazení N klíčů založený na trie je O(1), pokud je N procesorů a klíče mají konstantní horní omezení. Existuje možnost, že klíče mohou kolidovat tím, že mají společné prefixy, nebo jsou identické, což snižuje výhodu rychlosti zpracování více paralelně pracujícími procesory.

Fulltextové vyhledávání

K indexování všech sufixů v textu za účelem rychlého fulltexového vyhledávání může být použit speciální druh trie, sufixový strom. Dalším využitím může být hledání nejdelšího společného prefixu.

Odkazy

Literatura

Externí odkazy

[url=http://ivankuckir. blogspot. +morecom/2010/11/trie-v-as3. html]Animace trie ve flashi + implementace[/url] * [url=https://web. archive. org/web/20071001002932/http://www. cs. mu. oz. au/~rsinha/papers/SinhaRingZobel-2006. pdf]Cache-Efficient String Sorting Using Copying[/url].

Kategorie:Stromy (datové struktury)