Przestrzeń w pamięci struktura dla posortowanego tekstu wspierającego wyszukiwanie prefiksów

Question

Mam problem: Potrzebuję przestrzenno-sprawnego wyszukiwania danych systemu plików na podstawie prefiksu ścieżki pliku. Przedrostek wyszukiwania posortowanego tekstu, innymi słowy. Użyj tria, mówisz, i pomyślałem to samo. Problem polega na tym, że próby nie są wystarczająco wydajne, nie bez innych sztuczek.

mam sporo danych:

• około 450m w zwykły tekst Unix formatu notowań na dysku
• około 8 milionów wierszy
• domyślny gzip kompresuje do 31m
• bzip2 domyślnie kompresuje do 21M

Nie chcę jeść prawie w pobliżu 450M w pamięci. W tym momencie chciałbym być szczęśliwy, używając około 100M, ponieważ jest dużo redundancji w postaci prefiksów.

Używam C# dla tego zadania, a prosta implementacja trie nadal będzie wymagać jednego węzła liści dla każdej linii w pliku. Biorąc pod uwagę, że każdy węzeł liści będzie wymagał jakiegoś odniesienia do końcowego fragmentu tekstu (32 bity, na przykład indeks do tablicy danych łańcuchowych, aby zminimalizować duplikowanie ciągów), a narzut obiektu CLR to 8 bajtów (zweryfikowano przy użyciu windbg/SOS) , Będę wydawać> 96 000 000 bajtów na narzucie strukturalnym bez przechowywania tekstu.

Przyjrzyjmy się niektórym statystycznym atrybutom danych. Gdy nadziewane w trie:

• całkowite niepowtarzalne „porcjach” tekstu około 1,1 miliona
• całkowite unikalne fragmentów od około 16M na dysku w postaci pliku tekstowego
• średnia długość fragmentu wynosi 5,5 znaków, max 136
• przy braku duplikatów, łącznie około 52 milionów znaków w kawałkach
• Wewnętrzne węzły Trie średnio około 6,5 dzieci z max. 44
• około 1,8M węzłów wewnętrznych.

przekroczenie szybkości tworzenia liści wynosi około 15%, nadmiar tworzenie węzeł wewnętrzny wynosi 22% - przez nadmiar stworzenia, to znaczy liści i węzły wewnętrzne powstałe w trakcie budowy trie, ale nie w końcowym trie jako proporcja ostateczna liczba węzłów każdego typu.

Oto analiza sterty od SOS, wskazując, gdzie jest przyzwyczaić najbardziej pamięć:

[MT ]--[Count]----[ Size]-[Class           ] 
03563150  11   1584 System.Collections.Hashtable+bucket[] 
03561630  24   4636 System.Char[] 
03563470  8   6000 System.Byte[] 
00193558  425  74788  Free 
00984ac8 14457  462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]] 
03562b9c  6  11573372 System.Int32[] 
*009835a0 1456066  23297056 StringTrie+InteriorNode 
035576dc  1  46292000 Dictionary`2+Entry[[String],[Int32]][] 
*035341d0 1456085  69730164 System.Object[] 
*03560a00 1747257  80435032 System.String 
*00983a54 8052746  96632952 StringTrie+LeafNode 

Dictionary<string,int> jest używany do mapowania fragmentów ciągów do indeksów w List<string> i można je wyrzucić po zakończeniu budowy trie, chociaż GC nie wydaje się go usuwać (kilka wyraźnych kolekcji zostało zrobionych przed tym zrzutem) - !gcroot w SOS nie wskazuje żadnych korzeni, ale przewiduję, że późniejszy GC go uwolni.

MiniList<T> zastępuje List<T> stosując dokładnie rozmiarze (to wzrost liniowy O(n^2) wykonania dodatkowo) T[] uniknąć straty przestrzeni; jest to typ wartości i jest używany przez InteriorNode do śledzenia dzieci.Ten T[] został dodany do kupki System.Object[].

Tak więc, jeśli podliczę "interesujące" elementy (oznaczone *), otrzymuję około 270M, co jest lepsze niż surowy tekst na dysku, ale nadal nie jest wystarczająco zbliżony do mojego celu. Pomyślałem, że obiekt .NET nad głową było zbyt dużo, i stworzył nową „Slim” Trie, używając tylko tablice wartość typu do przechowywania danych:

class SlimTrie 
{ 
    byte[] _stringData; // UTF8-encoded, 7-bit-encoded-length prefixed string data 

    // indexed by _interiorChildIndex[n].._interiorChildIndex[n]+_interiorChildCount[n] 
    // Indexes interior_node_index if negative (bitwise complement), 
    // leaf_node_group if positive. 
    int[] _interiorChildren; 

    // The interior_node_index group - all arrays use same index. 
    byte[] _interiorChildCount; 
    int[] _interiorChildIndex; // indexes _interiorChildren 
    int[] _interiorChunk; // indexes _stringData 

    // The leaf_node_index group. 
    int[] _leafNodes; // indexes _stringData 

    // ... 
} 

Struktura ta przyniosła dół ilość danych do 139m, a wciąż jest wydajnym traserem do operacji tylko do odczytu. A ponieważ jest to tak proste, mogę trywialnie zapisać je na dysku i przywrócić je, aby za każdym razem uniknąć kosztu ponownego utworzenia gry.

Jakie są więc sugestie dotyczące bardziej wydajnych struktur wyszukiwania prefiksów niż trie? Alternatywne podejścia, które powinienem rozważyć?

Answer 1

Ponieważ istnieje tylko 1,1 miliona porcji, można indeksować porcję przy użyciu 24 bitów zamiast 32 bitów i zaoszczędzić tam miejsca.

Można również skompresować porcje. Być może Huffman coding jest dobrym wyborem. Spróbowałbym również następującą strategię: zamiast używać znaku jako symbolu do kodowania, powinieneś kodować przejścia postaci. Więc zamiast patrzeć na prawdopodobieństwo pojawienia się postaci, spójrz na prawdopodobieństwo przejścia w Markov chain, gdzie stan jest bieżącą postacią.

Answer 2

Idea poza ścianą: Zamiast stołu z hashami. Miałbyś w pamięci tylko hash i dane łańcucha, być może skompresowane.

Czy możesz pozwolić sobie na przeczytanie jednej strony? Tylko hash i pozycja pliku w pamięci, pobierają "stronę" z liniami pasującymi do tego hasha, przypuszczalnie małą liczbą uporządkowanych linii, stąd bardzo szybkie wyszukiwanie w razie kolizji.

Answer 3

Możesz znaleźć artykuł naukowy związany z twoim problemem here (cytat z autorów: "Eksperymenty pokazują, że nasz indeks obsługuje szybkie zapytania w obrębie zajmowanej przestrzeni, które są zbliżone do uzyskiwanych przez kompresję słownika napisanego przez gzip, bzip lub ppmdi. "- ale niestety papier jest tylko płatnością). Nie jestem pewien, jak trudne są te pomysły do ​​wdrożenia. Autorzy tego artykułu mają website, gdzie można znaleźć również implementacje (pod "Index Collection") różnych skompresowanych algorytmów indeksowych .

Jeśli chcesz kontynuować swoje podejście, sprawdź witryny o numerach Crit-bit trees i Radix tree.