Er zijn verschillende manieren om trials weer te geven, die overeenkomen met verschillende afwegingen tussen geheugengebruik en snelheid van de bewerkingen. De basisvorm is die van een gekoppelde reeks knooppunten, waarbij elk knooppunt een array van kind-punters bevat, één voor elk symbool in het alfabet (dus voor het Engelse alfabet zou men 26 kind-punters opslaan en voor het alfabet van bytes, 256 punters). Dit is eenvoudig, maar verspilling van geheugen: met het alfabet van bytes (grootte 256) en pointers van vier bytes heeft elke node een kilobyte opslagruimte nodig, en als er weinig overlap is in de voorvoegsels van de strings, is het aantal benodigde nodes ruwweg de gecombineerde lengte van de opgeslagen strings.Anders gezegd, de knooppunten onderaan de boom hebben meestal weinig kinderen en er zijn er veel van, zodat de structuur ruimte verspilt aan het opslaan van null pointers.
Het opslagprobleem kan worden verlicht door een implementatietechniek die alfabetreductie wordt genoemd, waarbij de oorspronkelijke tekenreeksen worden geherinterpreteerd als langere tekenreeksen over een kleiner alfabet. Bijvoorbeeld, een string van n bytes kan ook worden beschouwd als een string van 2n vier-bit eenheden en opgeslagen in een trie met zestien pointers per node. Lookups moeten in het ergste geval twee keer zoveel nodes bezoeken, maar de opslagvereisten gaan met een factor acht omlaag.:347-352
Een alternatieve implementatie stelt een node voor als een drievoud (symbol, child, next) en koppelt de kinderen van een node aan elkaar als een singly linked list: child wijst naar het eerste kind van de node, next naar het volgende kind van de parent node. De verzameling kinderen kan ook worden voorgesteld als een binaire zoekboom; een voorbeeld van dit idee is de ternaire zoekboom ontwikkeld door Bentley en Sedgewick.:353
Een ander alternatief om het gebruik van een array van 256 pointers (ASCII) te vermijden, zoals eerder gesuggereerd, is om de alfabet array op te slaan als een bitmap van 256 bits die het ASCII alfabet voorstellen, waardoor de grootte van de nodes drastisch wordt gereduceerd.
Bitwise triesEdit
Bitwise-pogingen zijn grotendeels hetzelfde als een normale tekengebaseerde trie, behalve dat individuele bits worden gebruikt om te doorlopen wat in feite een vorm van een binaire boom wordt. Over het algemeen gebruiken implementaties een speciale CPU-instructie om zeer snel het eerste ingestelde bit in een sleutel met een vaste lengte te vinden (bijv. GCC’s __builtin_clz() intrinsiek). Deze waarde wordt dan gebruikt om een 32- of 64-entry tabel te indexeren die wijst naar het eerste item in de bitwise trie met dat aantal leidende nul bits. Het zoeken gaat dan verder door elk volgend bit in de sleutel te testen en child of child te kiezen totdat het item is gevonden.
Hoewel dit proces langzaam klinkt, is het zeer cache-lokaal en zeer paralleliseerbaar door het ontbreken van registerafhankelijkheden en levert daarom in feite uitstekende prestaties op moderne CPU’s met uitvoering buiten de volgorde. Een rood-zwarte boom bijvoorbeeld presteert op papier veel beter, maar is zeer cache-onvriendelijk en veroorzaakt meerdere pijplijn- en TLB-stops op moderne CPU’s, waardoor dat algoritme gebonden is aan geheugenlatentie in plaats van CPU-snelheid. Ter vergelijking, een bitwise trie gaat zelden naar het geheugen, en als het dat doet, doet het dat alleen om te lezen, waardoor de SMP cache coherency overhead vermeden wordt. Daarom wordt het steeds meer het algoritme van keuze voor code die veel snelle invoegingen en verwijderingen uitvoert, zoals geheugen allocators (b.v. recente versies van de beroemde Doug Lea’s allocator (dlmalloc) en zijn afstammelingen). Het slechtste geval van stappen voor lookup is hetzelfde als bits die worden gebruikt om bins in de boom te indexeren.
Aternatief kan de term “bitwise trie” meer in het algemeen verwijzen naar een binaire boomstructuur die integer waarden bevat, en deze sorteert op hun binaire prefix. Een voorbeeld is de x-fast trie.
Pogingen comprimerenEdit
Het comprimeren van de trie en het samenvoegen van de gemeenschappelijke takken kan soms een grote prestatiewinst opleveren. Dit werkt het beste onder de volgende omstandigheden:
- De trie is (meestal) statisch, zodat geen sleutelinvoegingen of -verwijderingen nodig zijn (bijv. na bulkcreatie van de trie).
- Er zijn alleen lookups nodig.
- De trie-knooppunten zijn niet gecodeerd met knooppuntspecifieke gegevens, of de gegevens van de knooppunten zijn gemeenschappelijk.
- De totale verzameling opgeslagen sleutels is zeer spaarzaam binnen hun representatieruimte (zodat compressie loont).
Zo kan de trie bijvoorbeeld worden gebruikt om spaarzame bitsets weer te geven; d.w.z. deelverzamelingen van een veel grotere, vast telbare verzameling. In zo’n geval wordt de trie gecodeerd door de positie van het bitelement binnen de volledige verzameling. De sleutel wordt gemaakt uit de string van bits die nodig zijn om de integrale positie van elk element te coderen. Dergelijke trials hebben een zeer ontaarde vorm met veel ontbrekende takken. Na het detecteren van de herhaling van gemeenschappelijke patronen of het vullen van de ongebruikte gaten, kunnen de unieke bladknooppunten (bit strings) gemakkelijk worden opgeslagen en gecomprimeerd, waardoor de totale grootte van de trie wordt gereduceerd.
Zulke compressie wordt ook gebruikt bij de implementatie van de diverse snelle opzoektabellen voor het opvragen van Unicode-karakter-eigenschappen. Dit kunnen bijvoorbeeld case-mapping tabellen zijn (voor de Griekse letter pi, van Π naar π), of opzoektabellen die de combinatie van basis- en combinatie-tekens normaliseren (zoals de a-umlaut in het Duits, ä, of de dalet-patah-dagesh-ole in het Bijbels Hebreeuws, דַּ֫). Voor zulke toepassingen is de representatie vergelijkbaar met het transformeren van een zeer grote, unidimensionale, sparse tabel (b.v., Unicode code punten) in een multidimensionale matrix van hun combinaties, en dan de coördinaten in de hyper-matrix te gebruiken als de string sleutel van een ongecomprimeerde trie om het resulterende karakter te representeren. De compressie bestaat dan uit het detecteren en samenvoegen van de gemeenschappelijke kolommen in de hyper-matrix om de laatste dimensie in de sleutel te comprimeren. Om bijvoorbeeld niet het volledige, multibyte Unicode-codepunt op te slaan van elk element dat een matrixkolom vormt, kan gebruik worden gemaakt van de groepering van gelijksoortige codepunten. Elke dimensie van de hyper-matrix slaat de startpositie van de volgende dimensie op, zodat alleen de offset (meestal een enkele byte) hoeft te worden opgeslagen. De resulterende vector is zelf comprimeerbaar als hij ook sparse is, dus elke dimensie (geassocieerd met een laagniveau in de trie) kan apart gecomprimeerd worden.
Sommige implementaties ondersteunen dergelijke datacompressie binnen dynamische sparse tries en staan inserties en deleties toe in gecomprimeerde tries. Dit heeft echter meestal een aanzienlijke kostprijs wanneer gecomprimeerde segmenten moeten worden gesplitst of samengevoegd. Er moet een afweging worden gemaakt tussen gegevenscompressie en updatesnelheid. Een typische strategie is om het bereik van globale lookups te beperken voor het vergelijken van de gemeenschappelijke takken in de sparse trie.
Het resultaat van een dergelijke compressie kan lijken op een poging om de trie te transformeren in een directed acyclic graph (DAG), omdat de omgekeerde transformatie van een DAG naar een trie voor de hand ligt en altijd mogelijk is. De vorm van de DAG wordt echter bepaald door de vorm van de sleutel die wordt gekozen om de knooppunten te indexeren, hetgeen op zijn beurt de mogelijke compressie beperkt.
Een andere compressiestrategie is het “ontrafelen” van de datastructuur in een enkele byte-array. Deze aanpak elimineert de noodzaak voor knooppunt-aanwijzers, waardoor de geheugenvereisten aanzienlijk worden verminderd. Dit maakt op zijn beurt memory mapping mogelijk en het gebruik van virtueel geheugen om de gegevens efficiënt van schijf te laden.
Een andere benadering is het “verpakken” van de trie. Liang beschrijft een ruimte-efficiënte implementatie van een sparse packed trie toegepast op automatische woordafbreking, waarbij de nakomelingen van elke knoop in het geheugen mogen worden tussengevoegd.
Extern geheugen probeertEdit
Er zijn verschillende trie-varianten geschikt om reeksen in het externe geheugen te onderhouden, waaronder suffix trees. Een combinatie van trie en B-tree, genaamd de B-trie is ook voorgesteld voor deze taak; vergeleken met suffix trees zijn ze beperkt in de ondersteunde operaties, maar ook compacter, terwijl ze update operaties sneller uitvoeren.