Potrzeba wydajnej pamięci do przechowywania ton ciągów (było: implementacja HAT-Trie w Javie)

Pracuję z dużym zestawem (5-20 milionów) kluczy łańcuchowych (Średnia długość 10 znaków) które muszę przechowywać w strukturze danych w pamięci, która obsługuje następującą operację w stałym czasie lub blisko stałym czasie:

// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)
[2]}Hashmap w Javie okazuje się być bardziej niż zadowalający, jeśli chodzi o przepustowość, ale zajmuje dużo pamięci. Szukam rozwiązania, które jest wydajne w pamięci i nadal obsługuje przepustowość, która jest przyzwoity (porównywalny lub prawie tak dobry jak haszowanie). Nie obchodzi mnie czas wstawiania/usuwania. W mojej aplikacji będę wykonywać tylko wstawiania (tylko w czasie uruchamiania), a następnie będę tylko sprawdzać strukturę danych za pomocą metody contains przez cały okres użytkowania aplikacji.

Czytałem, że struktura danych HAT-Trie jest najbliższa moim potrzebom. Zastanawiam się, czy istnieje biblioteka, która ma implementację.

Inne propozycje ze wskazówkami do wdrożenia mile widziane.

Dziękuję.
Author: hashable, 2010-02-08
Source

4 answers

Trie wydaje się bardzo dobrym pomysłem na twoje ograniczenia.

Alternatywa "myślenie nieszablonowe":

Jeśli możesz sobie pozwolić na pewne prawdopodobieństwo odpowiedzi "teraźniejszości" Dla ciągu, który jest nieobecny

EDIT: jeśli możesz sobie pozwolić na fałszywe alarmy, użyj filtru Bloom zgodnie z sugestią WizardOfOdds w komentarzach.

Dla K=1, Filtr Bloom jest jak tabela hash bez klawiszy: każdy "bucket" jest po prostu logicznym, który mówi, czy co najmniej jedno wejście z tym samym hash był obecny. Jeśli 1% fałszywych alarmów jest dopuszczalne, twoja tabela hash może być tak mała, jak około 100 * 20 milionów bitów lub około 200 MiB. Dla 1 na 1000 fałszywych alarmów, 2GiB.

Użycie kilku funkcji skrótu zamiast jednej może poprawić szybkość fałszywie dodatnią dla tej samej ilości bitów.

 13
Author: Pascal Cuoq,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-08 17:41:57

Google wyświetla wpis na blogu HAT próbuje w Javie . Ale nie wiem, jak to rozwiąże twój problem bezpośrednio: struktura jest płytkim trie nad prefiksami kluczy, z liśćmi będącymi hashtablami trzymającymi sufiksy wszystkich kluczy z podanym prefiksem. Tak więc w sumie masz wiele hashtabli przechowujących wszystkie klucze, które są w bieżącej jednej dużej hashtable (być może zapisując kilka bajtów na klucz ogólnie ze względu na wspólne prefiksy). Tak czy inaczej, Potrzebujesz więcej zajmująca dużo miejsca tabela hashtable niż domyślna Java, lub narzut na obiekt równie mocno cię uderzy. Więc dlaczego nie zacząć od wyspecjalizowanej klasy hashtable tylko dla kluczy ciągów, jeśli wziąć tę trasę, i martwić się o części trie tylko jeśli nadal wydaje się warto wtedy?

 4
Author: Darius Bacon,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-08 01:14:46

Dla wydajności przestrzeni, o(log (N)) lookup i prostego kodu, spróbuj wyszukać binarnie na tablicy znaków. 20 milionów klawiszy o średniej długości 10 daje 200 milionów znaków: 400MB jeśli potrzebujesz 2 bajty / znak; 200MB jeśli możesz uciec z 1. Poza tym musisz w jakiś sposób reprezentować granice między kluczami w tablicy. Jeśli możesz zarezerwować znak separatora, to jest jeden sposób; w przeciwnym razie możesz użyć równoległej tablicy przesunięć int.

Najprostszy wariant wykorzystywałby tablica ciągów, przy wysokim koszcie przestrzeni od napowietrznych na obiekt. Powinien nadal bić hashtable w wydajności przestrzeni, choć nie tak imponująco.

 2
Author: Darius Bacon,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-08 01:06:18

Podobne do trie jest trójnawowe drzewo wyszukiwania, ale trójnawowe drzewo wyszukiwania ma tę zaletę, że zużywa mniej pamięci. Możesz przeczytać o drzewach wyszukiwania trójdzielnego tutaj, Tutaj i tutaj. Również jedna z głównych prac na ten temat autorstwa Jona Bentleya i Roberta Sedgewicka jest tutaj. Mówi również o szybkim sortowaniu łańcuchów, więc nie zniechęcaj się tym.

 2
Author: Justin Peel,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-02-10 02:52:26