Existuje několik způsobů reprezentace tria, které odpovídají různým kompromisům mezi využitím paměti a rychlostí operací. Základní formou je propojená množina uzlů, kde každý uzel obsahuje pole podřízených ukazatelů, jeden pro každý symbol v abecedě (takže pro anglickou abecedu by se uložilo 26 podřízených ukazatelů a pro abecedu bajtů 256 ukazatelů). To je jednoduché, ale z hlediska paměti neekonomické: při použití abecedy bajtů (velikost 256) a čtyřbajtových ukazatelů vyžaduje každý uzel kilobajt paměti, a pokud se prefixy řetězců málo překrývají, je počet potřebných uzlů zhruba roven kombinované délce uložených řetězců.:341 Jinak řečeno, uzly blízko dna stromu mají obvykle málo potomků a je jich mnoho, takže struktura plýtvá místem ukládáním nulových ukazatelů.
Problém s ukládáním lze zmírnit implementační technikou zvanou redukce abecedy, při níž se původní řetězce reinterpretují jako delší řetězce nad menší abecedou. Např. řetězec o délce n bajtů lze alternativně považovat za řetězec o 2n čtyřbitových jednotkách a uložit jej do tria se šestnácti ukazateli na uzel. Vyhledávání musí v nejhorším případě navštívit dvakrát více uzlů, ale nároky na úložiště se sníží osmkrát. 347-352
Alternativní implementace reprezentuje uzel jako trojici (symbol, child, next) a spojuje děti uzlu dohromady jako singly linked list: child ukazuje na prvního potomka uzlu, next na dalšího potomka rodičovského uzlu. Množinu dětí lze také reprezentovat jako binární vyhledávací strom; jedním z příkladů této myšlenky je ternární vyhledávací strom vyvinutý Bentleym a Sedgewickem.:353
Jinou alternativou, jak se vyhnout použití pole 256 ukazatelů (ASCII), jak bylo navrženo dříve, je uložit pole abecedy jako bitovou mapu 256 bitů reprezentující abecedu ASCII, čímž se dramaticky zmenší velikost uzlů.
Bitové pokusyEdit
Bitové pokusy jsou v podstatě stejné jako běžné znakové pokusy s tím rozdílem, že jednotlivé bity se používají k procházení něčeho, co se ve skutečnosti stává formou binárního stromu. Obecně implementace používají speciální instrukci procesoru pro velmi rychlé nalezení prvního nastaveného bitu v klíči pevné délky (např. vnitřní instrukce GCC __builtin_clz()). Tato hodnota se pak použije k indexování tabulky o 32 nebo 64 položkách, která ukazuje na první položku v bitové trojici s daným počtem počátečních nulových bitů. Hledání pak pokračuje testováním každého následujícího bitu v klíči a vhodnou volbou child nebo child, dokud není položka nalezena.
Ačkoli tento proces může znít pomalu, je díky absenci závislostí na registrech velmi lokální na cache a vysoce paralelizovatelný, a proto má ve skutečnosti vynikající výkon na moderních procesorech s out-of-order prováděním. Například červeno-černý strom má na papíře mnohem lepší výkon, ale je velmi nepřívětivý k mezipaměti a na moderních procesorech způsobuje mnohonásobné zastavení pipeline a TLB, což tento algoritmus omezuje spíše latencí paměti než rychlostí procesoru. Oproti tomu bitový trie přistupuje do paměti jen zřídka, a pokud ano, tak pouze pro čtení, čímž se vyhne režii SMP koherence cache. Proto se stále častěji stává algoritmem volby pro kód, který provádí mnoho rychlých vkládání a mazání, jako jsou alokátory paměti (např. poslední verze slavného alokátoru Douga Lea (dlmalloc) a jeho potomci). V nejhorším případě je počet kroků pro vyhledávání stejný jako počet bitů použitých k indexování binů ve stromu.
Obecněji lze termínem „bitový strom“ označit binární stromovou strukturu uchovávající celočíselné hodnoty a řadící je podle jejich binárního prefixu. Příkladem je trie x-fast.
Komprese trieEdit
Komprimace trie a sloučení společných větví může někdy přinést velké zvýšení výkonu. Nejlépe to funguje za následujících podmínek:
- Trie je (většinou) statické, takže není nutné vkládat klíče do tria nebo je mazat (např. po hromadném vytvoření tria).
- Jsou potřeba pouze vyhledávání.
- Uzly tria nejsou klíčovány daty specifickými pro uzel nebo jsou data uzlů společná.
- Celková množina uložených klíčů je v rámci jejich reprezentačního prostoru velmi řídká (takže se vyplatí komprese).
Může se například použít k reprezentaci řídkých bitových množin; tj. podmnožin mnohem větší, pevně spočetné množiny. V takovém případě je trie klíčována pozicí bitového prvku v rámci celé množiny. Klíč je vytvořen z řetězce bitů potřebného k zakódování integrální pozice každého prvku. Taková tria mají velmi degenerovaný tvar s mnoha chybějícími větvemi. Po zjištění opakování společných vzorů nebo vyplnění nevyužitých mezer lze jedinečné listové uzly (řetězce bitů) snadno uložit a komprimovat, čímž se zmenší celková velikost tria.
Taková komprese se používá také při implementaci různých rychlých vyhledávacích tabulek pro získávání vlastností znaků Unicode. Ty mohou zahrnovat tabulky pro mapování velkých a malých písmen (např. pro řecké písmeno pí z Π na π) nebo vyhledávací tabulky normalizující kombinaci základních a kombinujících znaků (jako je a-umlaut v němčině, ä, nebo dalet-patah-dagesh-ole v biblické hebrejštině, דַּ֫). Pro takové aplikace je reprezentace podobná transformaci velmi rozsáhlé, jednorozměrné, řídké tabulky (např. kódových bodů Unicode) na vícerozměrnou matici jejich kombinací a následnému použití souřadnic v hypermatici jako řetězcového klíče nekomprimované trojice pro reprezentaci výsledného znaku. Komprese pak bude spočívat v detekci a sloučení společných sloupců v hypermatici za účelem komprese poslední dimenze v klíči. Aby se například nemusel ukládat celý vícebajtový kódový bod Unicode každého prvku tvořícího sloupec matice, lze využít seskupení podobných kódových bodů. Každá dimenze hypermatice ukládá počáteční pozici následující dimenze, takže je třeba uložit pouze offset (obvykle jeden bajt). Výsledný vektor je sám o sobě komprimovatelný, pokud je také řídký, takže každou dimenzi (přidruženou k úrovni vrstvy v tria) lze komprimovat samostatně.
Některé implementace takovou kompresi dat v rámci dynamických řídkých tria podporují a umožňují vkládání a mazání v komprimovaných tria. To však obvykle přináší značné náklady, když je třeba komprimované segmenty rozdělit nebo sloučit. Mezi kompresí dat a rychlostí aktualizace musí být učiněn určitý kompromis. Typickou strategií je omezení rozsahu globálních vyhledávání pro porovnávání společných větví v řídké trie.
Výsledek takové komprese může vypadat podobně jako pokus o transformaci trie na směrovaný acyklický graf (DAG), protože opačná transformace z DAG na trie je zřejmá a vždy možná. Tvar DAG je však určen tvarem klíče zvoleného pro indexování uzlů, což zase omezuje možnou kompresi.
Další kompresní strategií je „rozbalení“ datové struktury do jediného bajtového pole. tento přístup eliminuje potřebu ukazatelů na uzly, což podstatně snižuje paměťové nároky. To zase umožňuje mapování paměti a použití virtuální paměti pro efektivní načítání dat z disku.
Jedním z dalších přístupů je „zabalení“ tria. Liang popisuje prostorově úspornou implementaci řídkého zabaleného tria aplikovaného na automatické spojování, v němž mohou být potomci každého uzlu v paměti prokládáni.
Tria v externí pamětiEdit
Několik variant trie je vhodných pro udržování množin řetězců v externí paměti, včetně stromů přípon. Pro tuto úlohu byla také navržena kombinace trie a B-stromu, nazývaná B-trie; ve srovnání se sufixovými stromy jsou omezené v podporovaných operacích, ale také kompaktnější a zároveň rychleji provádějí aktualizační operace.
.