Skonskruowany bitwektor rangi/selekcji

Dlaczego proste podejścia nieudane

Zastanówmy się nad tablicą bitową o długości n oraz dwiema operacjami, które nas interesują. Pierwsza to liczenie liczby 1-ów między pozycjami 0 a i, co nazywamy rank(i). Druga to znalezienie pozycji k-tego bitu równego 1, co nazywamy select(k). Proste podejście do rank polega na przeszukiwaniu od pozycji zero i liczeniu jednych z ustawionych bitów, co kosztuje czas proporcjonalny do i w najgorszym przypadku; proste podejście do select wykonuje podobne liniowe przeszukiwanie, co kosztuje czas proporcjonalny do n. Dla jednej zapytania to jest dobre, ale wielu aplikacji emituje miliony takich zapytań na tą samą stałą tablicę bitową, więc odpowiedzi w czasie liniowym stają się brzegiem problemu. Jasne rozwiązanie polega na wcześniejszym obliczeniu i przechowywaniu odpowiedzi rank dla każdego pojedynczego indeksu, tworząc tablicę odwołań tej samej długości jak pierwotna tablica bitowa, ale z wpisami wystarczająco dużymi do liczenia do n. Ta tablica zwykle wymaga wiele razy więcej miejsca niż sami bity, ponieważ każda przechowywana liczba musi zajmować pełny wiersz bitów, podczas gdy podstawowe dane zajmuje tylko jeden bit na pozycję. To przeciwdziała całkowitej motywacji do używania skompaktowanej tablicy bitowej, która często jest wybrana specjalnie dlatego, że przechowuje informacje w bliskiej do teoretycznego minimum liczby bitów. Potrzebna jest średnia kompromis: struktura pomocnicza mniejsza niż pełna tablica obliczona wszędzie, która nadal pozwala na odpowiednie zapytanie bez przeszukiwania tablicy od początku. To dokładnie to, co sprawia, że struktura jest skróconej, a nie tylko skompaktowana: używa ona miejsca bliskiego do teoretycznego minimum informacji dla reprezentowania danych, plus indeks dodatkowy o rozmiarze asymptotycznie niewyliczalnym w porównaniu, i nadal odpowiada zapytanom w czasie stałym. Schemat superbloków i bloków osiąga dokładnie tę równowagę, a to jest klasycznym punktem wyjścia w każdym kursie struktur danych skróconych przed przejściem do bardziej elaboratywnych konstrukcji.

Dwa poziomy superbloków i indeks bloku

Klasyczna konstrukcja dzieli bitwektor na duże, równoliczne części nazywane superblokami, a każda grupa superbloków jest dalsza podzielona na mniejsze części nazywane blokami. Na granicy każdego superbloku struktura przechowuje jedno liczbę: całkowitą liczbę ustawionych bitów w każdej pozycji przed tym superblokiem, czyli zliczenie od początku tablicy. Na granicy każdego bloku przechowywana jest druga, mniejsza liczba: liczebność ustawionych bitów tylko w tym superbloku, od jego początku do początku aktualnego bloku. Dwa poziomy podziału są kluczowe dla utrzymania małej wielkości indeksu przy zachowaniu szybkości. Liczniki na poziomie superbloków potrzebują wystarczającej liczby bitów do reprezentacji liczebności od 0 do n, więc jest ich stosunkowo mało (około n podzielonego przez wielkość superbloku), a każda z nich to szeroki całkowity. Liczniki na poziomie bloków, w przeciwieństwie do tego, mogą zawsze liczyć tylko do wielkości superbloku, która jest wybrana jako mała, więc każdy licznik bloku można przechowywać używając znacznie mniej bitów, nawet jeśli jest więcej bloków niż superbloków. Wybieranie wielkości superbloku wokół kwadratu wielkości bloku, lub dokładniej łącząc oba z logarytmicznymi funkcjami n, to co sprawia, że całkowita wielkość indeksu maleje do niemal niezauważalnej ułamka od oryginalnych n bitów wraz ze wzrostem n. To, co pozostaje po przeczytaniu obu liczników, to krótki resztkowy odcinek: kilka pozycji bitowych między początkiem odpowiedniego bloku a rzeczywistym pozycją zapytania i. Ten odcinek jest ograniczony wielkością bloku, która jest zamiernie utrzymywana jako mała, typowo na poziomie wielkości słowa maszyny lub mniejsza. Zliczanie ustawionych bitów w tym krótkim resztkowym odcinku to ostatni element zagadki i jest obsługiwane przez szybką operację popcount opisaną w kolejnym sekcji, a nie przez jakiekolwiek dalsze przeanalizowanie tablicy.

Konstantowe czasu liczenie popcount w reszcie

Po dodaniu zapisanego w superbloku całkowitego i częściowego dla bloku, pozostaje tylko liczenie ustawionych bitów w krótkim odcinku reszty, który nie przekracza jednego bloku i kończy się dokładnie na zapytanej pozycji i. Ta ostatnia suma musi również być konstantowa czasu, inaczej cała taka metoda byłaby liniowa w najgorszym przypadku dla tego odcinka. Dwa standardowe techniki realizują to. Pierwsza technika polega na wykorzystaniu instrukcji sprzętowej popcount, dostępnej na prawie wszystkich współczesnych procesorach, która liczy liczbe ustawionych bitów w słowie maszynowym w jednym instrukcji. Jeśli wielkość bloku została wybrana tak, aby pasować do jednego lub dwóch słów maszynowych, maskowanie bitów poza pozycją i oraz wydanie jednego lub dwóch instrukcji popcount zakończy pracę natychmiastowo, bez dostępu pamięciowego poza samo słowo. Druga technika, przydatna wtedy, gdy nie jest dostępna instrukcja sprzętowa, lub gdy pracujemy z modelowaniem programistycznym struktury, polega na wcześniejszym obliczeniu małej tabeli look-up indeksowanej przez każdy możliwy wzór podbloku o wybranym szerokości, wspólnie osiem lub szesnaście bitów. Tabela przechowuje popcount każdego wzoru. Ponieważ liczba różnych wzorów szerokości w wynosi tylko dwie do potęgi w, ta tabela jest mała – na przykład tabela dla wzorów o osiem bitach ma tylko 256 wpisów. Liczenie popcount krótkiego odcinka reszty staje się jednym czy kilka czytani z tabeli plus dodawania, nadal konstantowe czasu i niewielkie w zakresie pamięci. Zagregowując te trzy elementy – całkowite w superbloku, częściowe dla bloku oraz szybkie popcount krótkiego końcowego odcinka reszty – uzyskuje się odpowiedź na rank(i) za pomocą ustalonej, małej liczby operacji arytmetycznych niezależnie od wielkości ogólnej wektora bitowego. Wybranie(k) jest odpowiadane podobną strukturą, zazwyczaj używając tych samego superbloku i granic bloków oraz albo binarnego wyszukiwania nad zapisanymi liczbami, lub paralelnego systemu próbek, który rejestruje pozycję każdego m-tego ustawionego bitu bezpośrednio, umożliwiając wyszukiwanie skrócenia do małej dziedziny przed końcowym liniowym czy tabelarnym skanem, który ustali dokładną pozycję.

Precyzyjne pomiarowanie nadmiaru pamięci

Słowo skonskruowany ma określony techniczny znaczenie: struktura danych jest skonskruowaną, gdy jej całkowite użycie pamięci wynosi minimalną informacyjnie-teoretyczną ilość potrzebną do przedstawienia obiektu, plus wyraźnie mniejsza korelacja (lower-order term), która staje się niewyliczalna w stosunku do tej minimum przy rosnącym wejściu. Dla dowolnego bitwektora o długości n bez specjalnej struktury, minimalna informacyjnie-teoretyczna ilość potrzebna do przechowywania go wynosi prosto n bitów, ponieważ istnieje dwie do potęgi n różnych bitwektorów tej długości i każdy musi mieć oddzielną kodację. Opisane tutaj superblok i indeks bloku dodają około n podzielone przez log n bitów na tych oryginalnych n bitach, używając typowych wyborów parametrów, gdzie rozmiar bloku jest proporcjonalny do log n a rozmiar superbloku jest proporcjonalny do kwadratu log n. Gdy n rośnie, stosunek rozmiaru indeksu do rozmiaru danych zanika w kierunku zera, co dokładnie jest charakterystyczną cechą skonskruowanego dodatkowego struktury: jest to asymptotycznie niewyliczalny nadmiar w zamian za stały czas rankingu i selekcji. To przeciwko dwóm innym typom powszechnym. Niejawna struktura użyłaby dokładnie n bitów z zerowym dodatkowym nadmiarem, ale rank i select byliby wówczas ogólnie wymagane do liniowego skanowania, ponieważ nie ma miejsca na przechowywanie żadnych wskazówek przeprowadzonej obliczeniowo. Struktura skonskruowana lub prosta mogłaby przechowywać pełny dodatkowy tablicę z jednym wpisem dla każdej pozycji bitu, używając nadmiaru na tej samej asymptotycznej porządku jak dane same, często kilka razy więcej niż n bitów, co przeciwnie do celu wyboru reprezentacji skonskruowanej. Schemat superbloku i bloków zająć jest punktem idealnym między tymi ekstremami: blisko niejawnej w zakresie pamięci, blisko pełnego tablicy przeprowadzonego obliczeniowo w szybkości zapytania. Realne implementacje dostosowują dokładnie rozmiary superbloku i bloków na podstawie wielkości linii buforu i szerokości słowa, wymieniając mały stały czynnik zwiększenia nadmiaru na lepsze praktyczne wydajność, zachowując przy tym tą samą asymptotyczną gwarancję skonskruowanej.

Podstawa pod drzewami wariacyjnymi i skompaktowanymi drzewami try

Rankowanie i selekcja na prostym bitwektorze mogą wydawać się zbyt specjalistyczną narzędzia, ale to faktycznie jest podstawowy element, na którym opierają się wiele bardziej zaawansowanych skompaktowanych struktur. Drzewo wariacyjne, które służy do reprezentowania sekwencji nad większym alfabetem w zatopionym formacie, jednocześnie umożliwia rankowanie, selekcję i dostępy do dowolnych symboli, dzieli alfabet na połowy rekurencyjnie i zapisuje, na jaką połowę każdy symbol padł, jako bitwektor na każdym poziomie binarnego drzewa. Każda zapytanie dotyczącego całościowego drzewa wariacyjnego rozkłada się na serię zapytań rankowania lub selekcji dotyczących tych bitwektorów na poszczególnych poziomach, dlatego czas wykonania wszystkich zapytań zależy tylko od szybkości rankowania i selekcji na komponentowych bitwektorach; jeśli każda bitwektorowa operacja rank/select jest konstantywna, całe drzewo ma logarytmiczny czas wykonywania w zależności od rozmiaru alfabetu, bez żadnych operacji skanowania liniowego. Skompaktowane reprezentacje drzew i drzew try takie jak drzewa try wariacyjne opierają się na podobnej logice. Popularna technika koduje kształt drzewa za pomocą sekwencji równoważnych nawiasów lub podobnego kodowania bitowego, gdzie operacje takie jak znalezienie rodzica węzła, jego potomków lub rozmiaru poddrzewa są wyrażone jako zapytania rankowanie i selekcja, czasami razem z powiązanym operacją do znalezienia pozycji pasujących nawiasów. Skompaktowane drzewa try oparte na tych kodach drzewowych, używane w aplikacjach takich jak skompaktowane słowniki stringowe i indeksy danych genetycznych, dziedziczą szybkość zapytań bezpośrednio z wydajności rank/select podstawowego bitwektora. Dlatego że wiele struktur skompaktowanych wyższego rzędu redukuje swoje operacje do rankowania i selekcji na prostym bitwektorze, optymalizacja tego jednego podstawowego elementu, wybór odpowiednich wielkości superbloków i bloków, wyboru strategii efektywnej liczenia ilości, ma znaczący wpływ na całą dziedzinę. Tym laboratorium symulacji izoluje ten podstawowy warstwy, aby można było bezpośrednio badać jej zachowanie przed tym, jak zniknie w rekurencyjnym sprzężeniu maszyny drzewa wariacyjnego lub skompaktowanego drzewa try.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Succinct Rank/Select Bitvector i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.