A trieket többféleképpen lehet ábrázolni, ami a memóriahasználat és a műveletek sebessége közötti különböző kompromisszumoknak felel meg. Az alapvető forma a csomópontok összekapcsolt halmaza, ahol minden csomópont gyermekmutatók tömbjét tartalmazza, egyet-egyet az ábécé minden egyes szimbólumához (így az angol ábécé esetében 26 gyermekmutatót, a bájtábécé esetében pedig 256 mutatót tárolnánk). Ez egyszerű, de pazarló a memória szempontjából: a 256 bájtos ábécét és négybájtos mutatókat használva minden egyes csomópont egy kilobájtnyi tárhelyet igényel, és ha a karakterláncok előtagjai között kevés átfedés van, a szükséges csomópontok száma nagyjából a tárolt karakterláncok együttes hosszának felel meg.:341 Másképpen fogalmazva, a fa aljához közeli csomópontoknak általában kevés gyermekük van, és sok van belőlük, így a struktúra a nullmutatók tárolására pazarolja a helyet.
A tárolási probléma enyhíthető az ábécécsökkentésnek nevezett implementációs technikával, amelynek során az eredeti karakterláncokat hosszabb karakterláncokként értelmezzük újra egy kisebb ábécén. Például egy n bájtos karakterláncot alternatív módon 2n négybites egységből álló karakterláncnak is tekinthetünk, és egy csomópontonként tizenhat mutatóval rendelkező trie-ben tárolhatjuk. A kereséseknek legrosszabb esetben kétszer annyi csomópontot kell meglátogatniuk, de a tárolási igény nyolcszorosára csökken.:347-352
Egy alternatív megvalósítás egy csomópontot hármasként (szimbólum, gyermek, következő) ábrázol, és egy csomópont gyermekeit egyenként összekapcsolt listaként kapcsolja össze: a gyermek a csomópont első gyermekére mutat, a következő a szülő csomópont következő gyermekére. A gyermekek halmaza bináris keresőfaként is ábrázolható; ennek az ötletnek az egyik példája a Bentley és Sedgewick által kifejlesztett terner keresőfa.:353
Egy másik alternatíva annak érdekében, hogy elkerüljük a korábban javasolt 256 mutatóból álló (ASCII) tömb használatát, az ábécétömböt az ASCII ábécét reprezentáló 256 bitből álló bittérképként tároljuk, ami drasztikusan csökkenti a csomópontok méretét.
Bitwise triesEdit
A bitwise próbálkozások nagyjából ugyanolyanok, mint a normál karakteralapú trie, kivéve, hogy az egyes biteket használjuk az áthaladásra, ami gyakorlatilag egyfajta bináris fává válik. Általában a megvalósítások egy speciális CPU-utasítást használnak arra, hogy nagyon gyorsan megtalálják az első beállított bitet egy fix hosszúságú kulcsban (pl. a GCC __builtin_clz() intrinsic-je). Ezt az értéket ezután egy 32 vagy 64 bejegyzésű táblázat indexelésére használják, amely a bitsebesség-triász első olyan elemére mutat, amely az adott számú vezető nulla bitet tartalmazza. A keresés ezután a kulcs minden további bitjének tesztelésével és a child vagy child megfelelő kiválasztásával folytatódik, amíg az elemet meg nem találjuk.
Noha ez a folyamat lassúnak hangzik, a regiszterfüggőségek hiánya miatt nagyon cache-lokális és jól párhuzamosítható, ezért valójában kiváló teljesítményt nyújt a modern out-of-order execution CPU-kon. A piros-fekete fa például papíron sokkal jobban teljesít, de rendkívül cache-barát, és a modern CPU-kon többszörös pipeline- és TLB-akadásokat okoz, ami miatt ezt az algoritmust inkább a memória késleltetése, mint a CPU sebessége köti le. Ehhez képest egy bitwise trie ritkán lép be a memóriába, és ha mégis, akkor is csak olvasásra, így elkerülhető az SMP cache koherencia overhead. Ezért egyre inkább ez az algoritmus válik a választott algoritmussá olyan kódok esetében, amelyek sok gyors beillesztést és törlést végeznek, mint például a memóriaallokátorok (pl. a híres Doug Lea allokátorának (dlmalloc) és leszármazottainak legújabb változatai). A legrosszabb esetben a kereséshez használt lépések száma megegyezik a fában a bitek indexelésére használt bitekkel.
Alternatívaként a “bitwise trie” kifejezés általánosabban utalhat egy olyan bináris fa struktúrára, amely egész számértékeket tárol, és bináris előtagjuk szerint rendezi őket. Erre példa az x-fast trie.
Tries tömörítéseEdit
A trie tömörítése és a közös ágak összevonása néha nagy teljesítménynövekedést eredményezhet. Ez a következő feltételek mellett működik a legjobban:
- A trie (többnyire) statikus, így nincs szükség kulcsok beillesztésére vagy törlésére (pl. a trie tömeges létrehozása után).
- Csak keresésekre van szükség.
- A trie csomópontjai nem csomópont-specifikus adatokkal vannak kulcsozva, vagy a csomópontok adatai közösek.
- A tárolt kulcsok teljes halmaza nagyon ritka a reprezentációs terükön belül (így a tömörítés kifizetődő).
Ez használható például ritka bitsorozatok reprezentálására; azaz egy sokkal nagyobb, fixen felsorolható halmaz részhalmazainak reprezentálására. Ilyen esetben a trie kulcsát a teljes halmazon belüli bitelem pozíciója adja. A kulcsot az egyes elemek integrális pozíciójának kódolásához szükséges bitsorozatból hozzuk létre. Az ilyen próbák nagyon degenerált formájúak, sok hiányzó ággal. A közös minták ismétlődésének felismerése vagy a kihasználatlan hézagok kitöltése után az egyedi levélcsomópontok (bitsorozatok) könnyen tárolhatók és tömöríthetők, csökkentve a trie teljes méretét.
Az ilyen tömörítést használják az Unicode karaktertulajdonságok lekérdezésére szolgáló különböző gyors keresőtáblák megvalósításánál is. Ezek közé tartozhatnak a nagy- és kisbetű-táblázatok (pl. a görög pi betű esetében a Π-ről π-re), vagy az alap- és kombinációs karakterek kombinációját normalizáló keresőtáblázatok (mint a németben az a-umlaut, ä, vagy a bibliai héberben a dalet-patah-dagesh-ole, דַּ֫). Az ilyen alkalmazások esetében a reprezentáció hasonló ahhoz, mintha egy nagyon nagy, egydimenziós, ritka táblázatot (pl. Unicode kódpontok) átalakítanánk a kombinációik többdimenziós mátrixává, majd a hiper-mátrixban lévő koordinátákat egy tömörítetlen trie stringkulcsaként használnánk a kapott karakter ábrázolására. A tömörítés ezután a hiper-mátrixon belüli közös oszlopok felismeréséből és összevonásából áll a kulcs utolsó dimenziójának tömörítéséhez. Például a mátrix oszlopát alkotó minden egyes elem teljes, több bájtos Unicode kódpontjának tárolásának elkerülése érdekében a hasonló kódpontok csoportosítása kihasználható. A hiper-mátrix minden dimenziója tárolja a következő dimenzió kezdőpozícióját, így csak az eltolás (jellemzően egyetlen bájt) tárolására van szükség. Az így kapott vektor maga is tömöríthető, ha szintén ritka, így minden dimenzió (a trie egy rétegszintjéhez társítva) külön-külön tömöríthető.
Egyes implementációk támogatják az ilyen adattömörítést a dinamikus ritka próbákon belül, és lehetővé teszik a tömörített próbákon belüli beszúrásokat és törléseket. Ennek azonban általában jelentős költségei vannak, amikor a tömörített szegmenseket szét kell osztani vagy egyesíteni kell. Valamilyen kompromisszumot kell kötni az adattömörítés és a frissítési sebesség között. Egy tipikus stratégia a globális keresések körének korlátozása a ritka trie közös ágainak összehasonlítására.
Az ilyen tömörítés eredménye hasonló lehet ahhoz, mintha a trie-t egy irányított aciklikus gráffá (DAG) próbálnánk átalakítani, mivel a DAG-ból egy trie-be történő fordított átalakítás nyilvánvaló és mindig lehetséges. A DAG alakját azonban a csomópontok indexeléséhez választott kulcs formája határozza meg, ami viszont korlátozza a lehetséges tömörítést.
Egy másik tömörítési stratégia az adatstruktúra “kibontása” egyetlen bájt tömbre.Ez a megközelítés megszünteti a csomópontmutatók szükségességét, ami jelentősen csökkenti a memóriaigényt. Ez viszont lehetővé teszi a memória leképezését és a virtuális memória használatát az adatok hatékony betöltéséhez a lemezről.
Egy másik megközelítés a trie “becsomagolása”. Liang leírja az automatikus kötőjelképzésre alkalmazott ritkán csomagolt trie helytakarékos megvalósítását, amelyben az egyes csomópontok leszármazottai átlapolhatók a memóriában.
Külső memóriapróbálkozásokSzerkesztés
Egy sorozatok halmazainak külső memóriában való tárolására több trie-változat is alkalmas, köztük a szuffixfák. A trie és a B-fa kombinációját, az úgynevezett B-trie-t is javasolták erre a feladatra; a szuffixfákhoz képest korlátozottak a támogatott műveletekben, de kompaktabbak is, miközben gyorsabban végzik a frissítési műveleteket.