Der er flere måder at repræsentere trieer på, svarende til forskellige afvejninger mellem hukommelsesforbrug og hastighed af operationerne. Den grundlæggende form er et linket sæt af knuder, hvor hver knude indeholder et array af child-pointere, én for hvert symbol i alfabetet (så for det engelske alfabet ville man gemme 26 child-pointere og for alfabetet af bytes 256 pointere). Dette er simpelt, men spild af hukommelse: ved brug af byte-alfabetet (størrelse 256) og fire-byte-pointere kræver hver knude en kilobyte lagerplads, og når der kun er lidt overlapning i strengenes præfikser, er antallet af nødvendige knuder omtrent lig med den samlede længde af de lagrede strenge.:341 Sagt på en anden måde: knuderne nær bunden af træet har tendens til at have få børn, og der er mange af dem, så strukturen spilder plads på at lagre null-pointere.
Lagerproblemet kan afhjælpes ved en implementeringsteknik kaldet alfabetreduktion, hvorved de oprindelige strenge omfortolkes som længere strenge over et mindre alfabet. F.eks. kan en streng på n bytes alternativt betragtes som en streng på 2n fire-bit-enheder og lagres i en trie med seksten pointere pr. knudepunkt. Opslag skal i værste fald besøge dobbelt så mange knuder, men lagerbehovet falder med en faktor otte.:347-352
En alternativ implementering repræsenterer en knude som en tripel (symbol, child, next) og knytter knudens børn sammen som en enkeltkoblet liste: child peger på knudens første barn, next på moderknudens næste barn. Sættet af børn kan også repræsenteres som et binært søgetræ; et eksempel på denne idé er det ternære søgetræ, der er udviklet af Bentley og Sedgewick.:353
Et andet alternativ for at undgå brugen af et array af 256 pointere (ASCII), som foreslået tidligere, er at gemme alfabetarrayet som et bitmap af 256 bits, der repræsenterer ASCII-alfabetet, hvilket reducerer størrelsen af knuderne dramatisk.
Bitvise forsøgRediger
Bitwise tries er stort set det samme som en normal tegnbaseret trie, bortset fra at individuelle bits bruges til at gennemløbe det, der effektivt bliver en form for binært træ. Generelt bruger implementeringer en særlig CPU-instruktion til meget hurtigt at finde den første indstillede bit i en nøgle af fast længde (f.eks. GCC’s __builtin_clz() intrinsic). Denne værdi bruges derefter til at indeksere en tabel med 32 eller 64 poster, som peger på det første element i den bitvise trie med det pågældende antal ledende nulbits. Søgningen fortsætter derefter ved at teste hver efterfølgende bit i nøglen og vælge child eller child på passende vis, indtil elementet er fundet.
Og selv om denne proces kan lyde langsom, er den meget cache-lokal og meget paralleliserbar på grund af manglende registerafhængigheder og har derfor faktisk fremragende ydeevne på moderne CPU’er med udadgående udførelse. Et rødt-sort træ yder f.eks. meget bedre på papiret, men er meget cache-uvenlig og forårsager flere pipeline- og TLB-stalls på moderne CPU’er, hvilket gør denne algoritme bundet af hukommelseslatensitet snarere end CPU-hastighed. Til sammenligning har en bitvis trie sjældent adgang til hukommelsen, og når den gør det, gør den det kun for at læse, hvorved den undgår SMP-cache-kohærensoverhead. Derfor bliver den i stigende grad den foretrukne algoritme for kode, der udfører mange hurtige indsættelser og sletninger, som f.eks. hukommelsesallokatorer (f.eks. nyere versioner af den berømte Doug Lea’s allocator (dlmalloc) og dens efterkommere). Det værste tilfælde af trin til opslag er det samme som de bits, der bruges til at indeksere binærer i træet.
Alternativt kan udtrykket “bitvis trie” mere generelt henvise til en binær træstruktur, der indeholder hele talværdier, og som sorterer dem efter deres binære præfiks. Et eksempel er x-fast trie.
Komprimering af trieEdit
Komprimering af trie’en og sammenlægning af de fælles grene kan nogle gange give store ydelsesgevinster. Dette fungerer bedst under følgende betingelser:
- Den trie er (for det meste) statisk, så der kræves ingen nøgleindsættelser til eller sletninger (f.eks. efter bulkoprettelse af trien).
- Der er kun behov for opslag.
- Den trie-knuder er ikke nøglebelagt af knudespecifikke data, eller knudernes data er fælles.
- Det samlede sæt af lagrede nøgler er meget sparsomt inden for deres repræsentationsrum (så komprimering betaler sig).
Det kan f.eks. bruges til at repræsentere sparsomme bitsæt; dvs. delmængder af et meget større, fast enumerbart sæt. I et sådant tilfælde er trie’en nøgle af bitelementets position inden for det fulde sæt. Nøglen skabes ud fra den streng af bits, der er nødvendig for at kode den integrale position for hvert element. Sådanne tries har en meget degenereret form med mange manglende grene. Efter at have opdaget gentagelsen af fælles mønstre eller udfyldt de ubrugte huller kan de unikke bladknuder (bitstrenge) nemt lagres og komprimeres, hvilket reducerer den samlede størrelse af trien.
Sådan komprimering anvendes også i implementeringen af de forskellige hurtige opslagstabeller til at hente Unicode-tegnegenskaber. Det kan f.eks. være tabeller for case-mapping (f.eks. for det græske bogstav pi, fra Π til π) eller opslagstabeller, der normaliserer kombinationen af grund- og kombinationstegn (som a-umlaut i tysk, ä, eller dalet-patah-dagesh-ole i bibelhebraisk, דַּ֫). For sådanne anvendelser svarer repræsentationen til at omdanne en meget stor, endimensional, sparsom tabel (f.eks. Unicode-kodepunkter) til en flerdimensional matrix af deres kombinationer og derefter bruge koordinaterne i hypermatrixen som strengnøglen i en ukomprimeret trie for at repræsentere det resulterende tegn. Komprimeringen består derefter i at registrere og sammenlægge de fælles kolonner i hypermatrixen for at komprimere den sidste dimension i nøglen. For at undgå at lagre det fulde multibyte Unicode-kodepunkt for hvert element, der udgør en matrixkolonne, kan man f.eks. udnytte grupperingerne af lignende kodepunkter for at undgå at lagre det fulde multibyte Unicode-kodepunkt for hvert element, der udgør en matrixkolonne. Hver dimension i hypermatricen lagrer startpositionen for den næste dimension, således at kun forskydningen (typisk en enkelt byte) behøver at blive lagret. Den resulterende vektor kan i sig selv komprimeres, når den også er sparsom, så hver dimension (knyttet til et lagniveau i trien) kan komprimeres separat.
Nogle implementeringer understøtter en sådan datakomprimering inden for dynamiske sparsomme forsøg og tillader indsættelser og sletninger i komprimerede forsøg. Dette har dog normalt en betydelig omkostning, når komprimerede segmenter skal opdeles eller sammenlægges. Der skal foretages en afvejning mellem datakomprimering og opdateringshastighed. En typisk strategi er at begrænse rækkevidden af globale opslag til sammenligning af de fælles grene i den sparsomme trie.
Resultatet af en sådan komprimering kan ligne et forsøg på at omdanne trien til en rettet acyklisk graf (DAG), fordi den omvendte omdannelse fra en DAG til en trie er indlysende og altid mulig. DAG’ens form bestemmes imidlertid af formen af den nøgle, der er valgt til at indeksere knuderne, hvilket igen begrænser den mulige komprimering.
En anden komprimeringsstrategi er at “udrede” datastrukturen til et enkelt byte array.Denne fremgangsmåde eliminerer behovet for nodepointere, hvilket reducerer hukommelseskravene betydeligt. Dette giver igen mulighed for hukommelseskortlægning og brug af virtuel hukommelse til effektivt at indlæse dataene fra disken.
En anden fremgangsmåde er at “pakke” trien. Liang beskriver en pladsbesparende implementering af en sparsomt pakket trie, der anvendes til automatisk bindestreger, hvor efterkommerne af hver knude kan være interleaved i hukommelsen.
Trieer til ekstern hukommelseRediger
Flere trie-varianter er velegnede til at vedligeholde sæt af strenge i ekstern hukommelse, herunder suffixtræer. En kombination af trie og B-tree, kaldet B-trie, er også blevet foreslået til denne opgave; sammenlignet med suffixtræer er de begrænset i de understøttede operationer, men også mere kompakte, samtidig med at de udfører opdateringsoperationer hurtigere.