Potrzebujesz dobrego przeglądu algorytmów zwięzłej struktury danych

(już pytałem na głównej stronie , ale proszę również tutaj o lepszy zasięg, przepraszam)

Ponieważ wiedziałem o zwięzłych strukturach danych, rozpaczliwie potrzebuję dobrego przeglądu najnowszych osiągnięć w tej dziedzinie.

Poszukałem google i przeczytałem wiele artykułów, które mogłem zobaczyć na górze wyników wyszukiwania Google na prośby z góry mojej głowy. Nadal podejrzewam, że przegapiłem tutaj coś ważnego.

Oto tematy, które mnie szczególnie interesują:

1. Zwięzłe kodowanie drzew binarnych z wydajnymi operacjami pozyskiwania rodzica, lewego / prawego dziecka, liczby elementów w poddrzewie.

   Główne pytanie jest następujące: wszystkie znane mi podejścia zakładają, że węzły drzew są wyliczane w pierwszej kolejności (jak w pionierskiej pracy w tym obszarze Jacobson, G. J (1988). Zwięzłe statyczne struktury danych), które nie wydają się odpowiednie do mojego zadania. Mam do czynienia z ogromnymi drzewami binarnymi podanymi w układzie głębokość-pierwsza, a indeksy głębokości-pierwszy węzeł są kluczami do innych właściwości węzła, więc zmiana układu drzewa wiąże się z pewnymi kosztami, które chciałbym zminimalizować. Stąd zainteresowanie uzyskaniem referencji do prac z uwzględnieniem innych niż BF układów drzew.

2. Duże tablice przedmiotów o zmiennej długości w pamięci zewnętrznej. Tablice są niezmienne: nie muszę dodawać / usuwać / edytować elementów. Jedynym wymaganiem jest czas dostępu do elementu O (1) i możliwie jak najmniejszy narzut, lepszy niż proste przesunięcie i podejście do wielkości. Oto kilka statystyk, które zebrałem na temat typowych danych do mojego zadania:

   typowa liczba przedmiotów - setki milionów, nawet dziesiątki miliardów;

   około 30% przedmiotów ma długość nie większą niż 1 bit ;

   40% -60% przedmiotów ma długość mniejszą niż 8 bitów;

   tylko kilka procent przedmiotów ma długość od 32 do 255 bitów (255 bitów jest limitem)

   średnia długość elementu ~ 4 bity +/- 1 bit.

   jakikolwiek inny rozkład długości elementów jest teoretycznie możliwy, ale wszystkie praktycznie interesujące przypadki mają statystyki zbliżone do opisanych powyżej.

Odnośniki do artykułów o dowolnej złożoności, samouczki o wszelkich niejasnościach, mniej lub bardziej udokumentowane biblioteki C / C ++, - wszystko, co było przydatne dla podobnych zadań lub co wygląda tak po wykształconym przypuszczeniu - wszystkie takie rzeczy są wdzięczne.

Aktualizacja : Zapomniałem dodać do pytania 1: drzewa binarne, z którymi mam do czynienia, są niezmienne. Nie mam wymagań, aby je zmieniać, wszystko, czego potrzebuję, to tylko przechodzenie przez nie na różne sposoby, zawsze przenosząc się z węzła na dzieci lub na rodziców, tak aby średni koszt takich operacji wynosił O (1).

Ponadto typowe drzewo ma miliony węzłów i nie powinno być w pełni przechowywane w pamięci RAM.

Zakładam, że interesują Cię zwięzłe struktury danych pamięci zewnętrznej, które są skuteczne w praktyce. W takim przypadku możesz prawdopodobnie uzyskać to, co chcesz, za pomocą kilku podstawowych technik i inżynierii.

W przypadku drzew zacznę od przeczytania Arroyuelo i in .: Succinct Trees in Practice . Artykuł dotyczy drzew w pamięci głównej, ale większość technik można zastosować w pamięci zewnętrznej z podobnymi wyborami jak poniżej.

$\gamma$$\delta$$B$$B$

$n$$S$$n$$S[i] = 1$$i$$j$$rank(j)$

Jeśli chcesz, aby indeks rangi był mały, musisz zwiększyć rozmiar bloku (prawdopodobnie kilobajty lub dziesiątki kilobajtów), co powoduje, że powyższe podstawowe rozwiązanie wymaga dużej mocy obliczeniowej. Można to rozwiązać, dodając niewielki narzut do bloków przechowywanych na dysku. Zasadniczo stosuje się to samo rekurencyjnie, aby każdy blok dysku przechowywał wiele małych bloków, a także inny indeks rangi. Po odzyskaniu poprawnego bloku dysku, użyj indeksu rang w nim, aby znaleźć odpowiedni mały blok do zdekodowania, zamiast dekodowania całego bloku. Dzięki temu indeksowi wtórnemu dostępy losowe prawdopodobnie stają się ograniczone do wejść / wyjść nawet przy najszybszych dostępnych dyskach półprzewodnikowych.