Det finns flera sätt att representera tries, vilket motsvarar olika avvägningar mellan minnesanvändning och operationshastighet. Den grundläggande formen är en länkad uppsättning noder, där varje nod innehåller en matris av barnpekare, en för varje symbol i alfabetet (för det engelska alfabetet skulle man alltså lagra 26 barnpekare och för bytesalfabetet 256 pekare). Detta är enkelt men slösaktigt i fråga om minne: med bytesalfabetet (storlek 256) och pekare på fyra byte kräver varje nod en kilobyte lagringsutrymme, och när strängarnas prefix inte överlappar varandra i någon större utsträckning är antalet nödvändiga noder ungefär lika stort som den sammanlagda längden på de lagrade strängarna.:341 Med andra ord tenderar noderna nära trädets botten att ha få barn och det finns många av dem, så strukturen slösar utrymme på att lagra nollpekare.
Lagringsproblemet kan lindras genom en implementeringsteknik som kallas alfabetreducering, där de ursprungliga strängarna omtolkas som längre strängar över ett mindre alfabet. Exempelvis kan en sträng på n bytes alternativt betraktas som en sträng med 2n fyrbitarsenheter och lagras i en trie med sexton pekare per nod. Uppslag behöver besöka dubbelt så många noder i värsta fall, men lagringsbehovet minskar med en faktor åtta.:347-352
En alternativ implementering representerar en nod som en trippel (symbol, child, next) och kopplar ihop barnen till en nod som en enkelt länkad lista: child pekar på nodens första barn, next på föräldranodens nästa barn. Mängden barn kan också representeras som ett binärt sökträd; ett exempel på denna idé är det ternära sökträdet som utvecklats av Bentley och Sedgewick.:353
Ett annat alternativ för att undvika att använda en matris med 256 pekare (ASCII), som tidigare föreslagits, är att lagra alfabetmatrisen som en bitmapp med 256 bitar som representerar ASCII-alfabetet, vilket minskar storleken på noderna dramatiskt.
Bitvisa försökRedigera
Bitwise tries är i stort sett samma sak som en normal teckenbaserad trie förutom att enskilda bitar används för att genomkorsa vad som i praktiken blir en form av binärt träd. I allmänhet använder implementeringarna en särskild CPU-instruktion för att mycket snabbt hitta den första inställda biten i en nyckel med fast längd (t.ex. GCC:s __builtin_clz() intrinsik). Detta värde används sedan för att indexera en tabell med 32 eller 64 poster som pekar på det första objektet i den bitvisa trion med det antalet ledande nollbitar. Sökningen fortsätter sedan genom att testa varje efterföljande bit i nyckeln och välja child eller child på lämpligt sätt tills objektet har hittats.
Men även om denna process kan låta långsam är den mycket cachelokal och mycket parallelliserbar på grund av avsaknaden av registerberoenden och har därför i själva verket utmärkt prestanda på moderna CPU:er med exekvering utan ordningsföljd. Ett röd-svart träd till exempel presterar mycket bättre på pappret, men är mycket cache-ovänligt och orsakar flera pipeline- och TLB-stallningar på moderna CPU:er, vilket gör att algoritmen är bunden till minneslatens snarare än CPU-hastighet. En bitvis trie har däremot sällan tillgång till minnet, och när den gör det är det bara för att läsa, vilket gör att den undviker överbelastning av SMP-cachelagring. Därför blir den i allt högre grad den algoritm som väljs för kod som utför många snabba insättningar och borttagningar, t.ex. minnesallokatorer (t.ex. de senaste versionerna av den berömda Doug Lea’s allokatorn (dlmalloc) och dess efterföljare). Det värsta fallet av steg för uppslag är detsamma som de bitar som används för att indexera binärer i trädet.
Alternativt kan termen ”bitvis trie” mer allmänt hänvisa till en binär trädstruktur som innehåller heltalsvärden och som sorterar dem efter deras binära prefix. Ett exempel är x-fast trie.
Komprimering av triesEdit
Komprimering av trie och sammanslagning av de gemensamma grenarna kan ibland ge stora prestandavinster. Detta fungerar bäst under följande förhållanden:
- Triexemplet är (mestadels) statiskt, så att det inte krävs några nyckelinföranden till eller borttagningar (t.ex. efter masskapande av triexemplet).
- Endast sökningar behövs.
- Triexemplets noder har inte nycklar av nodspecifika data, eller så är nodernas data gemensamma.
- Den totala mängden lagrade nycklar är mycket gles inom deras representationsutrymme (så komprimering lönar sig).
Det kan till exempel användas för att representera glesa bitmängder; dvs. delmängder av en mycket större, fast uppräkningsbar mängd. I ett sådant fall är trie nyckeln av bitelementets position i den fullständiga uppsättningen. Nyckeln skapas av den sträng av bitar som behövs för att koda den integrala positionen för varje element. Sådana tries har en mycket degenererad form med många saknade grenar. Efter att ha upptäckt upprepning av gemensamma mönster eller fyllt de oanvända luckorna kan de unika bladnoderna (bitsträngar) lagras och komprimeras enkelt, vilket minskar den totala storleken på trian.
Den här typen av komprimering används också vid genomförandet av de olika snabba uppslagstabellerna för att hämta Unicode-tecknens egenskaper. Dessa kan inkludera tabeller för att ändra stor- och småskalighet (t.ex. för den grekiska bokstaven pi, från Π till π), eller uppslagstabeller som normaliserar kombinationen av bas- och kombinationsbokstäver (som a-umlaut i tyskan, ä, eller dalet-patah-dagesh-ole i biblisk hebreiska, דַּ֫). För sådana tillämpningar liknar framställningen en omvandling av en mycket stor, endimensionell, sparsam tabell (t.ex. Unicode-kodpunkter) till en flerdimensionell matris av deras kombinationer, och sedan använda koordinaterna i hypermatrisen som strängnyckel i en okomprimerad trie för att representera det resulterande tecknet. Komprimeringen kommer sedan att bestå av att upptäcka och slå samman de gemensamma kolumnerna i hypermatrisen för att komprimera den sista dimensionen i nyckeln. För att undvika att lagra den fullständiga, multibyte Unicode-kodpunkten för varje element som bildar en matriskolumn kan man till exempel utnyttja grupperingarna av liknande kodpunkter. Varje dimension i hypermatrisen lagrar startpositionen för nästa dimension, så att endast förskjutningen (vanligtvis en enda byte) behöver lagras. Den resulterande vektorn är i sig själv komprimerbar när den också är sparsam, så varje dimension (associerad med en lagernivå i trie) kan komprimeras separat.
Vissa implementationer stöder sådan datakomprimering inom dynamiska sparsamma försök och tillåter insättningar och borttagningar i komprimerade försök. Detta medför dock vanligtvis en betydande kostnad när komprimerade segment måste delas eller slås samman. En viss avvägning måste göras mellan datakomprimering och uppdateringshastighet. En typisk strategi är att begränsa området för globala sökningar för att jämföra de gemensamma grenarna i den glesa trian.
Resultatet av en sådan komprimering kan likna ett försök att omvandla trian till en riktad acyklisk graf (DAG), eftersom den omvända omvandlingen från en DAG till en trian är uppenbar och alltid möjlig. DAG:s form bestäms dock av formen på den nyckel som väljs för att indexera noderna, vilket i sin tur begränsar den möjliga komprimeringen.
En annan komprimeringsstrategi är att ”avveckla” datastrukturen till en enda byte-array.Detta tillvägagångssätt eliminerar behovet av nodpekare, vilket avsevärt minskar minneskraven. Detta möjliggör i sin tur minneskartläggning och användning av virtuellt minne för att effektivt läsa in data från disken.
En annan strategi är att ”packa” trie. Liang beskriver en utrymmeseffektiv implementering av en sparse packed trie tillämpad på automatisk avstavning, där efterkommande till varje nod kan interfolieras i minnet.
Försök med externt minneRedigera
Vissa trie-varianter lämpar sig för att upprätthålla uppsättningar av strängar i externt minne, bland annat suffixträd. En kombination av trie och B-tree, kallad B-trie, har också föreslagits för denna uppgift. Jämfört med suffixträd är de begränsade när det gäller de operationer som stöds men också mer kompakta, samtidigt som de utför uppdateringsoperationer snabbare.