Wydajna implementacja Trie dla ciągów Unicode

12

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.
RokL
źródło

Odpowiedzi:

2

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.

parsifal
źródło
- Odniesienia to 8 bajtów na 32-bitowych, 16 bajtów na 64-bitowych maszynach - Jest to funkcja autouzupełniania - Większość znaków w łańcuchach jest w zakresie ASCII, ale wrzucono kilka znaków z Europy Środkowej. Dlatego chciałem mniejszych rozgałęzień niż 256, ponieważ spowoduje to wycięcie dużej liczby znaków. Nie widzę, aby HashMap <String, List <String>> był lepszy, szybszy lub zajmował mniej pamięci, aczkolwiek naprawdę łatwy do napisania i użycia. Ale zaakceptuję pomysł HashMap <Postać, Mapa>. Byłoby dobrze dla znaków powyżej 128 (rzadkie w moim przypadku - byłoby złe dla chińskiego tekstu).
RokL
4

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 )

maniak zapadkowy
źródło
Wiem, że UTF8 może być tak reprezentowany. Jednak to nadal nie rozwiązuje zużycia pamięci, które jest wciąż dość wysokie. Zamiana znaków na podstawowy zakres 256 wymagałaby sporo zdań zamiany, wątpię, czy warto. Jeśli chodzi o UTF-8 ... to właściwie problem, nad którym teraz się zastanawiam. Łańcuch Java używa znaków UTF-16, które mogę łatwo uzyskać, mogę kodować te bajty po bajcie. Albo mogę przekonwertować na UTF-8 i użyć tego. W tym momencie nie jest dla mnie jasne, czy koszt konwersji z UTF-16 na UTF-8 jest wygórowany, czy nie.
RokL
w jakim języku używasz tego przez większość czasu? próba optymalizacji pod kątem wszystkiego jest niemożliwa (lub byłoby to już zrobione), więc zoptymalizuj pod kątem zwykłego przypadku
maniak zapadkowy
1
Jest to jeden z niewielu przypadków użycia, w których CESU-8 byłby lepszy od UTF-8: jego ogromną zaletą jest to, że przejście z punktu kodowego UTF-8 do odpowiedniego punktu kodowego CESU-8 jest banalne (podczas gdy potrzebujesz aby zdekodować 1-2 punkty kodowe UTF-16, aby dostać się do odpowiednich punktów kodowych UTF-8).
Joachim Sauer
1
@ratchetfreak Java. Chociaż myślę, że pytanie można uogólnić na większość języków. Wydaje mi się, że w C można po prostu rzucić wskaźnik, byte*aby zakodować dowolny typ w trie bitowym.
RokL
@UMad Miałem na myśli, w jakich językach będą się znajdować ciągi wejściowe (angielski, francuski, niemiecki, ...)
maniak zapadkowy