Kompresja i wyszukiwanie ogromnej listy słów

Question

Mam ogromną listę sekwencji wielobajtowych (pozwala nazywanie ich słowami), które muszę przechowywać w pliku i że muszę mieć możliwość szybkiego wyszukiwania. Ogromny oznacza: około 2 miliony z nich, każde o długości 10-20 bajtów.

Ponadto, każde słowo musi mieć tag wartości związanej z nim, tak, że mogę używać, aby odwoływać się więcej (zewnętrzne) danych dla każdej pozycji (stąd, słownik moduł sprawdzania pisowni nie działa tutaj jak tylko to zapewnia test trafień).

Gdyby to było tylko w pamięci i gdyby pamięć była dużo, mógłbym po prostu przechowywać wszystkie słowa w haszowanej mapie (zwanej też słownikiem, inaczej pary klucz-wartość) lub w posortowanej liście dla wyszukiwania binarnego.

Jednak chciałbym mocno skompresować dane, a także wolałbym nie czytać danych w pamięci, a raczej wyszukiwać w pliku.

Ponieważ słowa w większości oparte są na języku angielskim, istnieje pewne prawdopodobieństwo, że pewne "sylaby" w słowach występują częściej niż inne - co jest prawdopodobnie pomocne dla wydajnego algorytmu.

Czy ktoś może wskazać mi skuteczną technikę lub algorytm?

A może nawet przykłady kodu?

Aktualizacja

ja zorientować, że coś Dawg lub podobnych trasach ścieżkę do wspólnych przyrostków w ten sposób nie będzie pracować dla mnie, bo wtedy nie będzie mógł oznaczyć każdą pełną ścieżkę słowo z osobą wartość. Gdybym miał wykryć pospolite sufiksy, musiałbym umieścić je w ich własnym słowniku (tablicy odnośników), aby węzeł trie mógł je odnieść, ale węzeł zachowałby swój własny węzeł końcowy do przechowywania wartości znacznika tej ścieżki.

W rzeczywistości, to prawdopodobnie do zrobienia:

Zamiast budować węzły TREE tylko pojedyncze znaki, mogę spróbować znaleźć często używane sekwencje znaków, i zrobić węzeł dla tych, jak również. W ten sposób pojedyncze węzły mogą pokrywać wiele znaków, co może prowadzić do lepszej kompresji.

Teraz, jeśli jest to wykonalne, jak mógłbym znaleźć często używane podsekwencje we wszystkich moich wyrażeniach? Przy około 2 milionach zdań składających się zwykle z 1-3 słów, będzie ciężko uruchomić wszystkie permutacje wszystkich możliwych podłańcuchów ...

Answer 1

Istnieje struktura danych o nazwie trie. Uważam, że ta struktura danych doskonale pasuje do twoich wymagań. Zasadniczo trie to drzewo, w którym każdy węzeł jest literą, a każdy węzeł ma węzły potomne.W teście opartym na listach będzie 26 dzieci na węzeł.

W zależności od używanego języka może być łatwiejsze lub lepsze przechowywanie jako lista o zmiennej długości podczas tworzenia. Ta architektura daje: a) Szybkie wyszukiwanie. Po słowie o długości n możesz znaleźć ciąg w n linkach w drzewie. b) Kompresja. Używane są wspólne prefiksy.

Przykład: słowo BANANA i BANAL oba będą miały węzły B, A, N, A równe, a następnie ostatni węzeł (A) będzie miał 2 dzieci, L i N. Twoje węzły mogą również przechowywać inne informacje o słowie .

(http://en.wikipedia.org/wiki/Trie)

Andrew JS

Answer 2

Powinieneś zapoznać się z plikiem zindeksowanym.

Answer 3

Polecam używanie Trie lub DAWG (skierowany acykliczny wykres słowo). Jest świetny wykład ze Stanford na temat robienia dokładnie tego, co chcesz: http://academicearth.org/lectures/lexicon-case-study

Answer 4

Czy próbowałeś już użyć mapy skrótów? Chodzi o to, że w nowoczesnej architekturze OS system operacyjny użyje pamięci wirtualnej do zamiany nieużywanych segmentów pamięci na dysk. Może się więc okazać, że samo ładowanie tego wszystkiego na mapę mieszania jest rzeczywiście wydajne.

I jak wskazuje jkff, twoja lista miałaby tylko około 40 MB, co nie jest aż tak dużo.

Answer 5

Wystarczy popatrzeć na papierze "How to sqeeze a lexicon". Wyjaśnia, w jaki sposób zbudować zminimalizowany automat ze stanem skończonym (co jest tylko inną nazwą dla DAWG) z odwzorowaniem słów na liczby w kolejności jeden-na-jeden i odwrotnie. Dokładnie to, czego potrzebujesz.