Istnieje kilka sposobów reprezentowania trie, odpowiadających różnym kompromisom między użyciem pamięci a szybkością operacji. Podstawową formą jest połączony zbiór węzłów, gdzie każdy węzeł zawiera tablicę wskaźników do dzieci, po jednym dla każdego symbolu w alfabecie (tak więc dla alfabetu angielskiego można by przechowywać 26 wskaźników do dzieci, a dla alfabetu bajtów 256 wskaźników). Jest to proste, ale marnotrawne pod względem pamięci: używając alfabetu bajtów (rozmiar 256) i czterobajtowych wskaźników, każdy węzeł wymaga kilobajta pamięci, a gdy prefiksy łańcuchów niewiele się pokrywają, liczba wymaganych węzłów jest mniej więcej równa łącznej długości przechowywanych łańcuchów.Innymi słowy, węzły na dole drzewa mają mało dzieci i jest ich dużo, więc struktura marnuje miejsce na przechowywanie zerowych wskaźników.
Problem z przechowywaniem może być złagodzony przez technikę implementacji zwaną redukcją alfabetu, dzięki której oryginalne ciągi są reinterpretowane jako dłuższe ciągi w mniejszym alfabecie. Np. ciąg o długości n bajtów może być alternatywnie traktowany jako ciąg 2n jednostek czterobitowych i przechowywany w trie z szesnastoma wskaźnikami na węzeł. W najgorszym przypadku odszukiwania muszą odwiedzić dwa razy więcej węzłów, ale wymagania dotyczące przechowywania zmniejszają się ośmiokrotnie.:347-352
Alternatywna implementacja reprezentuje węzeł jako trójkę (symbol, dziecko, następny) i łączy dzieci węzła razem jako pojedynczo połączoną listę: dziecko wskazuje na pierwsze dziecko węzła, następny na następne dziecko węzła rodzica. Zbiór dzieci może być również reprezentowany jako binarne drzewo wyszukiwania; jednym z przykładów tego pomysłu jest trójdzielne drzewo wyszukiwania opracowane przez Bentleya i Sedgewicka.353
Inną alternatywą w celu uniknięcia użycia tablicy 256 wskaźników (ASCII), jak sugerowano wcześniej, jest przechowywanie tablicy alfabetów jako bitmapy 256 bitów reprezentującej alfabet ASCII, co drastycznie zmniejsza rozmiar węzłów.
Bitwise triesEdit
Bitwise tries są bardzo podobne do normalnych trie opartych na znakach, z wyjątkiem tego, że poszczególne bity są używane do przemierzania tego, co efektywnie staje się formą drzewa binarnego. Generalnie, implementacje używają specjalnej instrukcji CPU do bardzo szybkiego znalezienia pierwszego ustawionego bitu w kluczu o stałej długości (np. __builtin_clz() GCC). Wartość ta jest następnie używana do indeksowania 32- lub 64-pozycyjnej tablicy, która wskazuje na pierwszy element w trie bitowym z taką liczbą zerowych bitów wiodących. Następnie wyszukiwanie przebiega poprzez testowanie każdego kolejnego bitu w kluczu i wybieranie child lub child odpowiednio, aż do znalezienia elementu.
Chociaż proces ten może brzmieć powoli, jest bardzo cache-lokalny i wysoce paralelny ze względu na brak zależności rejestrowych, a zatem w rzeczywistości ma doskonałą wydajność na nowoczesnych procesorach out-of-order execution. Na przykład drzewo czerwono-czarne wykonuje się znacznie lepiej na papierze, ale jest wysoce nieprzyjazne dla pamięci podręcznej i powoduje wielokrotne przeciągnięcia rurociągu i TLB na nowoczesnych procesorach, co powoduje, że ten algorytm jest związany z opóźnieniem pamięci, a nie prędkością procesora. Dla porównania, bitwise trie rzadko uzyskuje dostęp do pamięci, a kiedy to robi, robi to tylko do odczytu, unikając w ten sposób narzutu koherencji pamięci podręcznej SMP. Dlatego też coraz częściej staje się on algorytmem z wyboru dla kodu, który wykonuje wiele szybkich wstawek i usunięć, takich jak alokatory pamięci (np. ostatnie wersje słynnego alokatora Douga Lea (dlmalloc) i jego potomków). Najgorszy przypadek kroków dla lookup jest taki sam jak bity używane do indeksowania koszy w drzewie.
Alternatywnie, termin „bitwise trie” może bardziej ogólnie odnosić się do binarnej struktury drzewiastej przechowującej wartości całkowite, sortując je według ich prefiksu binarnego. Przykładem jest trie x-fast.
Kompresja trieEdit
Kompresja trie i łączenie wspólnych gałęzi może czasami przynieść duży wzrost wydajności. Działa to najlepiej w następujących warunkach:
- Trójkąt jest (w większości) statyczny, więc nie wymaga wstawiania kluczy ani usuwania (np. po masowym utworzeniu trójkąta).
- Potrzebne są tylko odszukiwania.
- Węzły trójkąta nie są kluczowane przez dane specyficzne dla węzła lub dane węzłów są wspólne.
- Całkowity zestaw przechowywanych kluczy jest bardzo rzadki w ich przestrzeni reprezentacji (więc kompresja się opłaca).
Na przykład, może być używany do reprezentowania rzadkich zbiorów bitów; tj. podzbiorów znacznie większego, stałego wyliczalnego zestawu. W takim przypadku trie jest kluczowany przez pozycję elementu bitowego w pełnym zestawie. Klucz jest tworzony z ciągu bitów potrzebnych do zakodowania integralnej pozycji każdego elementu. Takie próby mają bardzo zdegenerowaną postać z wieloma brakującymi gałęziami. Po wykryciu powtórzeń wspólnych wzorców lub wypełnieniu niewykorzystanych luk, unikalne węzły liści (ciągi bitów) mogą być łatwo przechowywane i kompresowane, zmniejszając ogólny rozmiar trie.
Taka kompresja jest również wykorzystywana w implementacji różnych szybkich tabel lookup do pobierania właściwości znaków Unicode. Mogą to być tablice odwzorowania wielkości liter (np. dla greckiej litery pi, z Π na π) lub tablice lookup normalizujące kombinację znaków podstawowych i łączących (jak a-umlaut w języku niemieckim, ä, lub dalet-patah-dagesh-ole w biblijnym języku hebrajskim, דַּ֫). Dla takich zastosowań reprezentacja jest podobna do przekształcenia bardzo dużej, jednowymiarowej, nieliczbowej tablicy (np. punktów kodowych Unicode) w wielowymiarową macierz ich kombinacji, a następnie użycie współrzędnych w hiper-macierzy jako klucza łańcuchowego nieskompresowanego trie do reprezentacji wynikowego znaku. Kompresja będzie wtedy polegała na wykrywaniu i łączeniu wspólnych kolumn w hiper-macierzy, aby skompresować ostatni wymiar w kluczu. Na przykład, aby uniknąć przechowywania pełnego, wielobajtowego punktu kodowego Unicode każdego elementu tworzącego kolumnę macierzy, można wykorzystać zgrupowania podobnych punktów kodowych. Każdy wymiar hiper-macierzy przechowuje pozycję początkową następnego wymiaru, tak że tylko offset (typowo pojedynczy bajt) musi być przechowywany. Wektor wynikowy jest sam w sobie ściśliwy, gdy jest również sparse, więc każdy wymiar (związany z poziomem warstwy w trie) może być skompresowany osobno.
Niektóre implementacje obsługują taką kompresję danych w ramach dynamicznych prób sparse i pozwalają na wstawianie i usuwanie w skompresowanych próbach. Jednak zazwyczaj wiąże się to ze znacznymi kosztami, gdy skompresowane segmenty muszą być dzielone lub łączone. Należy dokonać pewnego kompromisu pomiędzy kompresją danych a szybkością aktualizacji. Typową strategią jest ograniczenie zakresu globalnych odnośników do porównywania wspólnych gałęzi w nieliczbowym trie.
Wynik takiej kompresji może wyglądać podobnie do próby przekształcenia trie w skierowany graf acykliczny (DAG), ponieważ odwrotna transformacja z DAG do trie jest oczywista i zawsze możliwa. Jednak kształt DAG jest określony przez formę klucza wybranego do indeksowania węzłów, co z kolei ogranicza możliwą kompresję.
Inną strategią kompresji jest „rozwikłanie” struktury danych do tablicy jednobajtowej.Takie podejście eliminuje potrzebę wskaźników węzłów, znacznie zmniejszając wymagania pamięciowe. To z kolei pozwala na mapowanie pamięci i użycie pamięci wirtualnej do efektywnego załadowania danych z dysku.
Jeszcze jednym podejściem jest „spakowanie” trie. Liang opisuje wydajną przestrzennie implementację sparse packed trie zastosowaną do automatycznej hiphenation, w której potomkowie każdego węzła mogą być przeplatane w pamięci.
Próby pamięci zewnętrznejEdit
Kilka wariantów trie nadaje się do utrzymywania zbiorów ciągów w pamięci zewnętrznej, w tym drzew przyrostkowych. Do tego zadania zaproponowano również kombinację trie i B-tree, zwaną B-trie; w porównaniu z drzewami sufiksowymi są one ograniczone w obsługiwanych operacjach, ale również bardziej zwarte, a jednocześnie szybciej wykonują operacje aktualizacji.
.