Triisejä voidaan esittää useilla eri tavoilla, jotka vastaavat erilaisia kompromisseja muistin käytön ja operaatioiden nopeuden välillä. Perusmuoto on solmujen linkitetty joukko, jossa jokainen solmu sisältää joukon lapsiviittomia, yksi kutakin aakkoston symbolia kohti (englannin aakkostoa varten tallennettaisiin siis 26 lapsiviittomaa ja tavujen aakkostoa varten 256 viittomaa). Tämä on yksinkertaista mutta muistin kannalta tuhlailevaa: kun käytetään tavujen aakkosia (koko 256) ja neljän tavun osoittimia, jokainen solmu vaatii kilotavun tallennustilaa, ja kun merkkijonojen etuliitteissä on vain vähän päällekkäisyyttä, tarvittavien solmujen määrä on suunnilleen tallennettujen merkkijonojen yhteenlaskettu pituus.:341 Toisin sanoen puun alareunan lähellä olevilla solmuilla on yleensä vähän lapsia, ja niitä on paljon, joten rakenne tuhlaa tilaa nollaosoittimien tallentamiseen.
Tallennusongelmaa voidaan lieventää aakkosten pienentämiseksi kutsutulla toteutustekniikalla, jossa alkuperäiset merkkijonot tulkitaan uudelleen pidemmiksi merkkijonoiksi pienemmillä aakkosilla. Esimerkiksi n tavun mittainen merkkijono voidaan vaihtoehtoisesti katsoa 2n neljän bitin mittaiseksi merkkijonoksi ja tallentaa kolmioon, jossa on kuusitoista osoitinta solmua kohti. Pahimmassa tapauksessa hakujen täytyy käydä kaksi kertaa useammassa solmussa, mutta tallennustarve laskee kahdeksankertaiseksi.:347-352
Vaihtoehtoinen toteutus esittää solmun kolmikkona (symboli, lapsi, seuraava) ja linkittää solmun lapset toisiinsa yksittäin linkitettynä listana: lapsi osoittaa solmun ensimmäiseen lapseen, seuraava vanhemman solmun seuraavaan lapseen. Lasten joukko voidaan esittää myös binäärisenä hakupuuna; yksi esimerkki tästä ideasta on Bentleyn ja Sedgewickin kehittämä ternäärinen hakupuu.:353
Toinen vaihtoehto, jolla vältetään 256 osoittimen (ASCII) joukon käyttö, kuten aiemmin ehdotettiin, on tallentaa aakkosjoukko 256 bitin bittikarttana, joka edustaa ASCII-aakkosia, jolloin solmujen koko pienenee dramaattisesti.
Bittikohtaisia kokeilujaMuutos
Bittikokeilut ovat pitkälti samanlaisia kuin tavalliset merkkipohjaiset kokeilut, paitsi että yksittäisiä bittejä käytetään kulkemaan läpi, mistä tulee käytännössä eräänlainen binääripuu. Yleensä toteutukset käyttävät erityistä CPU-käskyä löytääkseen hyvin nopeasti ensimmäisen asetetun bitin kiinteän pituisesta avaimesta (esim. GCC:n __builtin_clz()-intrinsic). Tätä arvoa käytetään sitten indeksoimaan 32- tai 64-alkuista taulukkoa, joka osoittaa bittikolmikon ensimmäiseen kohteeseen, jossa on kyseinen määrä johtavia nollabittejä. Sen jälkeen haku etenee testaamalla avaimen jokaista seuraavaa bittiä ja valitsemalla child tai child sopivasti, kunnes kohde löytyy.
Vaikka tämä prosessi saattaa kuulostaa hitaalta, se on hyvin välimuistipaikallinen ja hyvin rinnakkaistettavissa rekisteririippuvuuksien puuttumisen vuoksi, ja siksi sen suorituskyky on itse asiassa erinomainen nykyaikaisilla järjestyksen ulkopuolisen suorituksen suorittimilla. Esimerkiksi punamusta puu toimii paperilla paljon paremmin, mutta se on erittäin välimuistiystävällinen ja aiheuttaa useita putkiston ja TLB:n pysähdyksiä nykyaikaisissa suorittimissa, minkä vuoksi algoritmi on sidottu pikemminkin muistin latenssiin kuin suorittimen nopeuteen. Vertailun vuoksi bitwise trie käyttää harvoin muistia, ja kun se käyttää sitä, se käyttää sitä vain lukemiseen, jolloin vältetään SMP-välimuistin koherenssikustannuksia. Siksi siitä on tulossa yhä useammin valinta algoritmiksi koodiin, joka suorittaa monia nopeita lisäyksiä ja poistoja, kuten muistin allokaattorit (esim. viimeaikaiset versiot kuuluisasta Doug Lean allokaattorista (dlmalloc) ja sen jälkeläisistä). Pahimmassa tapauksessa askeleet hakua varten ovat samat kuin bitit, joita käytetään puun bittien indeksointiin.
Vaihtoehtoisesti termi ”bitwise trie” voi yleisemmin viitata binääriseen puurakenteeseen, joka pitää sisällään kokonaislukuarvoja, jotka lajitellaan niiden binäärisen etuliitteen mukaan. Esimerkkinä on x-fast trie.
Tryen pakkaaminenEdit
Trien pakkaaminen ja yhteisten haarojen yhdistäminen voi joskus tuottaa suuria suorituskykyhyötyjä. Tämä toimii parhaiten seuraavissa olosuhteissa:
- Trie on (enimmäkseen) staattinen, joten avainten lisäyksiä tai poistoja ei tarvita (esim. trien massaluomisen jälkeen).
- Tarvitaan vain hakuja.
- Trien solmuja ei ole avaimilla varustettu solmukohtaisilla tiedoilla tai solmujen tiedot ovat yhteisiä.
- Tallennettujen avainten kokonaisjoukko on hyvin harva niiden esitysavaruudessa (joten pakkaaminen kannattaa).
Sitä voidaan käyttää esimerkiksi harvalukuisten bittijoukkojen esittämiseen; eli paljon suuremman, kiinteästi lueteltavan joukon osajoukkojen esittämiseen. Tällaisessa tapauksessa trie:n avaimena on bittielementin sijainti koko joukon sisällä. Avain luodaan bittijonosta, joka tarvitaan kunkin elementin integraaliposition koodaamiseen. Tällaiset trieet ovat hyvin degeneroituneita ja niissä on paljon puuttuvia haaroja. Kun yhteisten kuvioiden toistuminen on havaittu tai käyttämättömät aukot on täytetty, yksilölliset lehtisolmut (bittijonot) voidaan tallentaa ja pakata helposti, mikä pienentää trie:n kokonaiskokoa.
Tällaista pakkausta käytetään myös erilaisten nopeiden hakutaulukoiden toteutuksessa Unicode-merkkien ominaisuuksien hakemiseen. Tällaisia voivat olla esimerkiksi isojen ja pienten kirjainten kartoitustaulukot (esim. kreikkalaisen kirjaimen pi kohdalla Π:stä π:ksi) tai hakutaulukot, jotka normalisoivat perusmerkkien ja yhdistelmämerkkien yhdistelmän (kuten saksan a-umlaut, ä, tai raamatullisen heprean dalet-patah-dagesh-ole, דַּ֫). Tällaisissa sovelluksissa esitys muistuttaa hyvin suuren, yksiulotteisen, harvan taulukon (esim. Unicode-koodipisteet) muuttamista moniulotteiseksi matriisiksi niiden yhdistelmistä ja sen jälkeen hyper-matriisin koordinaattien käyttämistä tiivistämättömän kolmion merkkijonoavaimena tuloksena olevan merkin esittämiseksi. Pakkaus koostuu sitten hyper-matriisin yhteisten sarakkeiden tunnistamisesta ja yhdistämisestä avaimen viimeisen ulottuvuuden pakkaamiseksi. Jos esimerkiksi halutaan välttää jokaisen matriisin sarakkeen muodostavan elementin koko, usean tavun mittaisen Unicode-koodipisteen tallentaminen, voidaan hyödyntää samankaltaisten koodipisteiden ryhmittymiä. Hyper-matriisin jokainen ulottuvuus tallentaa seuraavan ulottuvuuden alkupisteen, joten vain siirtymä (yleensä yksi tavu) on tallennettava. Tuloksena syntyvä vektori on itsessään pakattavissa, kun se on myös harva, joten jokainen ulottuvuus (joka liittyy trie:n kerrostasoon) voidaan pakata erikseen.
Jotkut toteutukset tukevat tällaista tiedonpakkausta dynaamisissa harvalukuisissa yritelmissä ja sallivat lisäykset ja poistot pakatuissa yritelmissä. Tästä aiheutuu kuitenkin yleensä merkittäviä kustannuksia, kun pakattuja segmenttejä on jaettava tai yhdistettävä. Tietojen pakkaamisen ja päivitysnopeuden välillä on tehtävä kompromissi. Tyypillinen strategia on rajoittaa globaalien hakujen valikoimaa harvan trie:n yhteisten haarojen vertailussa.
Tällaisen pakkauksen tulos voi näyttää samankaltaiselta kuin yrittäisi muuttaa trie:n suunnatuksi asykliseksi graafiksi (DAG), koska käänteinen muunnos DAG:sta trie:ksi on ilmeinen ja aina mahdollinen. DAG:n muoto määräytyy kuitenkin solmujen indeksointiin valitun avaimen muodon mukaan, mikä puolestaan rajoittaa mahdollista pakkausta.
Toinen pakkausstrategia on ”purkaa” tietorakenne yhdeksi tavujoukoksi.
Tämä lähestymistapa eliminoi solmujen osoittimien tarpeen, mikä pienentää muistivaatimuksia huomattavasti. Tämä puolestaan mahdollistaa muistikartoituksen ja virtuaalimuistin käytön tietojen tehokkaaseen lataamiseen levyltä.
Yksi toinen lähestymistapa on ”pakata” trie. Liang kuvaa automaattiseen yhdyssanojen muodostukseen sovelletun harvaan pakatun trie:n tilatehokkaan toteutuksen, jossa jokaisen solmun jälkeläiset voidaan lomittaa muistissa.
Ulkoisen muistin trie:tEdit
Monet trie-muunnokset soveltuvat merkkijonojoukkojen säilyttämiseen ulkoisessa muistissa, mukaan lukien suffix-puut. Tähän tehtävään on ehdotettu myös trie:n ja B-puun yhdistelmää, jota kutsutaan B-puuksi; suffiksipuihin verrattuna ne ovat rajoitettuja tuettujen operaatioiden suhteen, mutta myös kompaktimpia ja suorittavat päivitysoperaatiot nopeammin.