Drzewo wawełkowe

Rekurencyjne podział alfabetu

Drzewo wawełkowe jest budowane z ciągu S o długości n nad alfabetem wielkości sigma, zazwyczaj po tym, jak symbole są mapowane na kolejne liczby całkowite od 0 do sigma minus 1. Konstrukcja zaczyna się w korzeniu z pełnym ciągiem i pełnym zakresem alfabetu. Na każdym węźle zakres alfabetu przypisany do tego węzła jest podzielony na dolną połowę i górną połowę, zwykle jak najbardziej równo, aby drzewo pozostawało zbalansowane. Dla każdego miejsca w sekwencji węzła algorytm sprawdza do której połowy należy symbol na tym miejscu i dodaje 0 lub 1 do wektora bitowego, podobnie jak w lewo-naprzemiennym porządku sekwencji samej. Po zbudowaniu wektora bitowego pozycje są podzielone według ich wartości bitowej: wszystkie pozycje o 0 są zbierane, zachowując kolejność względną, do sekwencji stającej się wejściem dla lewego dziecka, a wszystkie pozycje o 1 tworzą podobnie sekwencję dla prawego dziecka. Kluczowe jest to, że ta krotna podział nie musi być przechowywana jawnie podczas zapytania, ponieważ operacja rank wektora bitowego może przywrócić mapowanie między pozycjami rodzica a poziomami dzieci na żądanie. Węzeł lewy rekurencyjnie przeszukuje swoją połowę alfabetu i podciąg wygenerowany przez nią, a węzeł prawy wykonuje to samo, aż zakres alfabetu w danym węźle zawiera tylko jedno symbole. Wtedy ten węzeł jest liściem i nie potrzebuje wektora bitowego, ponieważ każda pozycja dotykająca go musi już posiadać to jedno symbol. Głębokość rekurencji jest ograniczona do surowego logarytmu dwumianowego z sigma, ponieważ każdy poziom podzielony jest na połowę zakresu alfabetu. Ponieważ każda oryginalna pozycja przekazuje dokładnie jeden bit na każdym poziomie przez który przechodzi, a przechodzi ona dokładnie jeden węzeł na każdym poziomie, całkowita liczba bitów przechowywanych w wektorach bitowych drzewa wynosi n razy wysokość drzewa, co jest rzędu n log sigma. To już blisko informacji brzytwowej ciągu nad danym alfabetem, a z kodowaniami wektorów bitowych świadczącymi o entropii można dalej zmniejszyć pojemność w stronę zero-odernej empirycznej entropii S, która jest zwykle znacznie mniejsza niż log sigma, gdy częstotliwości symboli są niezrównoważone.

Succinctne wektory bitowe: silnik podziemny

Gwarancje drzewa wawełkowego opierają się całkowicie na tym, że wektory bitowe na każdym węźle obsługują rank i select efektywnie, a to jest tam, gdzie słowo succinct zasługuje na swój nazwany tytuł. Naive wektor bitowy przechowywany jako prosty tabliczny ciąg bitów może odpowiadać na dostęp, czyli odczytanie bitu w pozycji i, w czasie stały, ale obliczanie ranka, liczebności 1-bitów wśród pierwszych i pozycji, wymagałoby przeprowadzenia skanowania do najwyżej i bitów, a select, znalezienie położenia k-tego 1-bitu, byłby jeszcze wolniejszy. Szkice rank i select rozwiązują ten problem poprzez dodanie małego indeksu na górę nad puste bity: klasyka podejścia podzieliło wektor bitowy na bloki i superbloki, przeliczając popcount w blokach granicznych i używając szybkich instrukcji sprzętowych popcount lub małych tabel look-up do zakończenia liczenia wewnątrz bloku. Kluczowym osiągnięciem tych struktur jest to, że pomocniczy indeks zajmuje tylko rzędu n przez log n, lub czasami rzędu n log log n przez log n bitów nad n pustymi bitami, co asymptotycznie jest niewyraźne w porównaniu z samym wektorem bitowym, często opisane jako o(n) dodatkowych bitów, czyli prawie wolne miejsce dla zapytań w czasie stałym. Select jest obsługiwany albo przez podobny strukturę pomocniczą, albo, bardziej powszechnie w praktyce, poprzez wyszukiwanie binarne nad indeksem ranka połączone z lokalnym skanowaniem, dając czas logarytmiczny lub prawie stały w zależności od wybranego wariantu. Każdy pojedynczy wektor bitowy wewnątrz drzewa wawełkowego, na każdym poziomie rekurencji, jest jednym z tych struktur rank i select, a nie prostym tablicą. To szczegół, który łatwo można odbić, ale jest całym powodem dla którego działa drzewo wawełkowe: bez wsparcia succinct na każdym węźle, zapytanie rank na całe sekwencje spadłoby do liniowego skanowania na każdym poziomie, zniszczając granicę czasową logarytmiczną, którą struktura jest zaprojektowana do dostarczyć. Z powodu podliniarnego obciążenia na poziomie, drzewo wawełkowe jako całość dziedziczy zarówno granicę prawie entropii miejsca, jak i szybkie zapytania jednocześnie, co jest niezwykłe wśród struktur danych, które zwykle muszą trzymać się jednego za drugim.

Odpowiedzi na dostęp, rangę i wybór

Trzy kanoniczne zapytania, które drzewo wawełkowe obsługuje, wszystkie obowiązują jednym wzorem rekurencyjnym: spadając od korzenia do liścia, używając operacji rangi lub wyboru na bitmapie na każdym poziomie. Dostęp, które pyta o symbol znajdujący się na pozycji i w oryginalnej sekwencji, zaczyna się od korzenia i czyta bajt na pozycji i w bitmapie korzenia. Jeśli ten bajt ma wartość 0, symbol należy do dolnej połowy alfabetu, a zapytanie rekurencyjnie przechodzi do lewego dziecka na pozycję podaną przez rangę 0 do i w bitmapie korzenia, co powinno nam powiedzieć, ile poprzednich pozycji również przeszły w lewo, stąd odpowiadająca pozycja sekwencji lewego dziecka. Jeśli bajt ma wartość 1, analogiczne obliczenie rangi 1 daje pozycję w prawym dziecku. To powtarza się aż do osiągnięcia liścia, a symbol powiązany z tym liściem jest odpowiedzią po dokładnie logarytmie sigma operacjach rangi. Ranga, które pyta o ilość wystąpień symbolu c wśród pierwszych i pozycji, obowiązuje takim samym ścieżką spadającą jak zakres alfabetu dla symbolu c, ale na każdym poziomie konwertuje wartość i na odpowiednią pozycję w sekwencji dziecka używając operacji rangi na bitmapie aktualnego węzła, dokładnie tak jak przy dostępie, podczas gdy śledzi także, którą gałąź należy podejść do, na podstawie tego, która połowa zawiera c. Gdy osiągniemy liść dla symbolu c, wartość pozycji transformowana jest sama w sobie odpowiedzią, ponieważ reprezentuje dokładnie ile razy wzór bitowy symbole c, a więc c, wystąpił w przekazie. Wybór, które pyta o pozycję k-tego wystąpienia symbolu c, działa w odwrotnej kolejności: zaczyna się od liścia dla symbolu c i chodzi w górę ku korzeniowi, na każdym kroku używając operacji wyboru na bitmapie rodzica do przekształcenia pozycji sekwencji dziecka w pozycję sekwencji rodzica, cofając się od opadającej operacji rangi, jaką wykonują dostęp i ranga. Po logarytmie sigma operacjach wyboru pozycja na korzeniu jest odpowiedzią. Wszystkie trzy zapytania kosztują rzędu logarytmu sigma operacji rangi lub wyboru, każda sama stałą albo prawie stałą czasu, więc ogólny czas zapytania to rzędu logarytmu sigma, niezależny od n.

Drzewa wawełkowe w FM-indexie do wyszukiwania genomu

Jedną z najważniejszych aplikacji drzew wawełkowych jest ich zastosowanie w FM-indexie, skompresowanym indeksie pełnego tekstu szeroko stosowanym w narzędziach bioinformatycznych takich jak BWA i Bowtie do przypisania krótkich odcinków DNA do referencyjnej genomu. FM-index opiera się na transformacji Burrowsa-Wheela, odwrotnej permutacji tekstu, która tenduje do grupowania podobnych kontekstów razem, co sprawia, że transformowany ciąg jest bardziej kompresyjny niż oryginalny. Podejście kluczowe, na którym opiera się FM-index, nazywa się wyszukiwanie wsteczne, a jego pętla inner loop wielokrotnie musi liczyć wystąpienia znaku w prefiksach ciągu BWT, operacja, której drzewo wawełkowe jest zaprojektowane do odpowiedzi. Zapamiętywanie ciągu BWT jako proste tablicy pozwala na dostęp w czasie stałym, ale z czasem liniowym rank, co sprawiałoby, że wyszukiwanie wsteczne byłoby zbyt wolne dla genomów zawierających biliony baz. Zapisanie ciągu BWT jako drzewo wawełkowe daje czas logarytmiczny rank dla dowolnego symbolu alfabetycznego, a ponieważ DNA używa małego alfabetu składającego się z czterech baz, dostosowanego do kilku dodatkowych symboli dla kartezji i sentineli, czas efektywny jest bardzo szybki w praktyce, często tylko dwa lub trzy operacje rank. Wyszukiwanie wsteczne rozszerza dopasowany wzór jednym znakiem z końca na raz, używając przy każdym kroku dwóch operacji rank na drzewie wawełkowym kodowanym BWT, aby zmniejszyć przedział reprezentujący wszystkie sufiksy tekstu zaczynające się od dopasowanego wzoru do tej pory. Po przetworzeniu całego wzoru zapytania, szerokość końcowego przedziału bezpośrednio daje liczbę wystąpień tego wzoru w genomie, odpowiedzi na to bez dekompresji pojedynczej bazy oryginalnej sekwencji. Znalezienie rzeczywistych pozycji genetycznych dopasowań dodatkowo używa operacji podobnych do select połączone z przekrojoną tablicą sufiksów, ale sam krok liczenia, który większość narzędzi do przypisania używa do szybkiego odrzucenia lub potwierdzenia kandydatów dopasowań, wykonuje się całkowicie na operacjach rank drzewa wawełkowego. Dzięki temu, że drzewo wawełkowe jednocześnie kompresuje BWT ku jej entropii i obsługuje te zapytania szybko, całe indeksy skali genomu pasują do kilku gigabajtów pamięci, a nie setki gigabajtów potrzebnych dla prostej reprezentacji.

Konstrukcja, warianty i praktyczne kompromisy

budowanie drzewa wawełkowego prosto, poziomo, z wyraźnym przejściem do podziału symboli na każdym węźle, zajmuje czas rzędu n log sigma i podobną ilość miejsca roboczego, co jest wystarczające dla wielu aplikacji, ale może stać się bramą dla bardzo dużych tekstów, takich jak całe genomiki lub duże corpora tekstowe. Istnieją jednak szybsze algorytmy konstrukcyjne, które budują wszystkie bitwektory danego poziomu w jednym liniowym przebiegu nad oryginalną sekwencją, korzystając z faktu, że ścieżka symbolu przez drzewo jest całkowicie wyznaczona przez jego reprezentację bitową. Metody pamięciowa zewnętrzną lub równoległe konstruowanie zmniejszają dalsze zużycie pamięci, co ma znaczenie, gdy wejście samego jest wielokrotnie większym ilością gigabajtów. Drzewa wawełkowe z równomiernym podziałem alfabetu, często nazywane drzewami wawełkowymi z wyraźną formą drzewa binarnego, podzielone są zakres alfabetu równomierno na każdym węźle niezależnie od częstotliwości symboli, co jest proste i daje dokładny górny zakres wysokości log base two sigma. Alternatywą jest drzewo wawełkowe z kodem Huffmana, które buduje drzewo według kodu Huffmana wyznaczonego na podstawie częstotliwości symboli, tak że często występujące symbole są blisko korzenia z krótkimi kodami, a rzadkie symbole leżą głębiej z dłuższymi kodami; to przesunie zużycie pamięci od rzędu n log sigma bitów w kierunku empirycznej entropii zerowej sekwencji, co kosztuje utratą uniformnego górnego zakresu czasu zapytania, ponieważ niektóre zapytania stają się wolniejsze niż inne w zależności od częstotliwości symboli. Dalszym wariantem jest macierz wawełkowa, która zachowuje stały liczbę poziomów równa długości bitowej alfabetu, ale zmienia sposób grupowania pozycji na każdym poziomie, korzystając z stabilnego podziału według wartości bitu na całym poziomie zamiast dla każdego węzła, co uproszcza implementację, poprawia lokalizację bufora i często jest preferowaną strukturą danych w współczesnych bibliotekach skompaktowanych struktur danych. Wszystkie te warianty pozostawiają podstawową konwencję tą samą: zastąpienie sekwencji drzewem skompaktowanego ranku i selekcji bitwektory, a za cenę otrzymuje się dostęp, rangę i selekcję w przybliżonym czasie logarytmicznym w przestrzeni bliskiej własnej informacji sekwencji.

Często zadawane pytania

Wypróbuj na żywo

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