Szukałem wydajnej implementacji String trie. Przeważnie znalazłem taki kod:
Referencyjna implementacja w Javie (na wikipedię)
Nie podobają mi się te wdrożenia z dwóch powodów:
- Obsługują tylko 256 znaków ASCII. Muszę obejmować takie rzeczy jak cyrylica.
- Są wyjątkowo nieefektywne pod względem pamięci.
Każdy węzeł zawiera tablicę 256 odniesień, czyli 4096 bajtów na 64-bitowej maszynie w Javie. Każdy z tych węzłów może mieć do 256 podwęzłów, z których każdy zawiera 4096 bajtów odniesień. Tak więc pełna Trie dla każdego ciągu znaków ASCII 2 wymagałaby nieco ponad 1 MB. Trzy ciągi znaków? 256 MB tylko dla tablic w węzłach. I tak dalej.
Oczywiście nie zamierzam mieć wszystkich 16 milionów trzech ciągów znaków w mojej Trie, więc dużo miejsca jest po prostu zmarnowane. Większość tych tablic jest po prostu zerowymi referencjami, ponieważ ich pojemność znacznie przekracza rzeczywistą liczbę wstawionych kluczy. A jeśli dodam Unicode, tablice stają się jeszcze większe (char ma 64k wartości zamiast 256 w Javie).
Czy jest jakaś nadzieja na stworzenie skutecznego trie na smyczki? Rozważyłem kilka ulepszeń w stosunku do tego rodzaju wdrożeń:
- Zamiast korzystać z tablicy referencji, mógłbym użyć tablicy pierwotnej liczby całkowitej, która indeksuje do tablicy referencji do węzłów, których rozmiar jest zbliżony do liczby rzeczywistych węzłów.
- Mógłbym rozbić ciągi na 4-bitowe części, które pozwoliłyby na tablice węzłów o rozmiarze 16 kosztem głębszego drzewa.
jeśli kodujesz łańcuchy znaków w UTF8, możesz użyć standardowej wersji 256 rozgałęzień i nadal być kompatybilnym z Unicode
należy również zauważyć, że tylko 70 z około 128 znaków ascii (które wszystkie kodują do 1 bajtu w UTF8) można znaleźć najbardziej, które można zoptymalizować w tym celu (np. uwzględnij wspólne wykreślniki zamiast nieużywanych znaków kontrolnych )
źródło
byte*
aby zakodować dowolny typ w trie bitowym.