Wydajna implementacja Trie dla ciągów Unicode

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:

1. Obsługują tylko 256 znaków ASCII. Muszę obejmować takie rzeczy jak cyrylica.
2. 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.

Do czego używasz tego trie? Jaka jest łączna liczba słów, które zamierzasz przechowywać i jaka jest rzadkość ich składowych postaci? A co najważniejsze, czy trie jest nawet odpowiednia (w porównaniu z prostą mapą prefiksu do listy słów)?

Twój pomysł na tabelę pośrednią i zastąpienie wskaźników indeksami będzie działał, pod warunkiem, że masz stosunkowo mały zestaw krótkich słów i rzadki zestaw znaków. W przeciwnym razie ryzykujesz brak miejsca w tabeli pośredniej. I jeśli nie patrzysz na bardzo mały zestaw słów, tak naprawdę nie zaoszczędzisz tyle miejsca: 2 bajty na krótki w porównaniu z 4 bajtami na odniesienie na maszynie 32-bitowej. Jeśli korzystasz z 64-bitowej maszyny JVM, oszczędności będą większe.

Twój pomysł na podzielenie znaków na 4-bitowe fragmenty prawdopodobnie nie zaoszczędzi ci wiele, chyba że wszystkie oczekiwane postacie będą w bardzo ograniczonym zakresie (być może OK dla słów ograniczonych do wielkich liter US-ASCII, mało prawdopodobne w przypadku ogólnego korpusu Unicode ).

Jeśli masz rzadki zestaw znaków, HashMap<Character,Map<...>>najlepszym rozwiązaniem może być a. Tak, każdy wpis będzie znacznie większy, ale jeśli nie masz wielu zgłoszeń, otrzymasz ogólną wygraną. (na marginesie: zawsze myślałem, że to zabawne, że artykuł w Wikipedii na temat prób - pokazał - może nadal - przykład oparty na zaszyfrowanej strukturze danych, całkowicie ignorując kompromisy czasoprzestrzenne tego wyboru)

Wreszcie, możesz chcieć całkowicie uniknąć trie. Jeśli patrzysz na zbiór normalnych słów w ludzkim języku (10 000 słów w użyciu, ze słowami o długości 4-8 znaków), prawdopodobnie lepiej będzie O DUŻO HashMap<String,List<String>, gdy kluczem jest cały prefiks.

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 )