Tablica sufiksowa: indeksowanie każdego zakończenia ciągu znaków

Co to jest exactly sufiks?

Sufiks napisu to wszystko od pewnej pozycji początkowej do końca napisu. Jeśli napis to banana, ma dokładnie sześć sufiksy, jeden zaczynający się na każdym indeksie: banana, anana, nana, ana, na i a. Zauważ, że cała sama niespodziewana napis też liczy się jako sufiks, ten który zaczyna się w pozycji zero. Ogólnie rzecz biorąc, napis o długości n ma dokładnie n sufiksy, jeden dla każdego możliwego indeksu początkowego, w tym pusty sufiks, jeśli chcesz go liczyć, choć większość implementacji zatrzymuje się przed nim. To jest inaczej niż prefiks, który to wszystko od początku napisu do pewnego punktu końcowego, i znów inaczej niż dowolny podciąg, który może zaczynać się i kończyć gdziekolwiek w środku. Kluczowe odkrycie, które sprawia, że sufiksy są tak przydatne, to to: każdy podciąg pierwotnego tekstu jest prefiksem dokładnie jednego sufiksu, a mianowicie tego sufiksu, który zaczyna się tam, gdzie zaczyna się ten podciąg. Więc jeśli chcesz wiedzieć, czy wzór ana występuje w banana, na prawdę pytasz, czy ana jest prefiksem jakiegoś z sześciu sufiksów banana. Przyjrzyjmy się powyższej liście: ana rzeczywiście jest prefiksem sufiksu ana samego i również prefiksem anana. To odnowienie jest całą tajemnicą za tzw. tablicą sufiksową: zamiast szukać wzoru w niespodziewanym tekście, organizujesz wszystkie sufiksy tak, aby znalezienie wzoru stało się znalezieniem zakresu sufiksów, które mają wspólny prefiks. Warto podkreślić, że ta technika dotyczy jednego napisu i jego własnych wewnętrznych odbić, powtarzanych fragmentów, symetrycznych wzorów, a nie zbioru wielu różnych słów, jak to byłoby w przypadku trie słownika.

Tworzenie tablicy: proste podejście

Najprostszym i niewątpliwie bezpośredniem sposobem na tworzenie tablicy sufiksowej jest generowanie wszystkich n sufiksy ciągu znaków. Następnie sortowanie tych sufiksy przy użyciu zwykłego porównania leksykograficznego. Trzecim krokiem jest zapisanie tylko początkowych indeksów każdego sufiksu w tym porządku posortowanym, odrzucając sam tekst sufiksu, ponieważ można go zawsze odzyskać na podstawie oryginalnego ciągu znaków i indeksu. Dla słowa banana sortowanie sześciu sufiksy leksykograficznie daje: a, ana, anana, banana, na, nana, które odpowiadają pozycjom początkowym 5, 3, 1, 0, 4, 2. Ta sekwencja pozycji, 5, 3, 1, 0, 4, 2, jest tablicą sufiksową. Problem z tym podejściem leży w efektywności. Porównywanie dwóch sufiksy znak po znaku może zajmować czas proporcjonalny do długości ciągu znaków w najgorszym przypadku, ponieważ dwa sufiksy mogą dzielić się bardzo długim wspólnym początkiem przed różnicy. Dla n sufiksów do posortowania i ogólnej metody sortowania potrzebującej na order n log n porównań, a każda operacja porównania kosztuje do n sprawdzeń znakowych, cała praca osiąga order n kwadratowy log n w najgorszym przypadku. Dla krótkiego słowa jak banana to jest natychmiastowe, ale dla cromosomu ludzkiego zawierającego setki miliardów baz, lub dużego zbioru dokumentów, order n kwadratowy log n staje się całkowicie niepraktyczne, potencjalnie wymagając więcej czasu niż wiek wszechświata na zakończenie. To proste podejście jest wartościowe do budowania intuicji i dla małych przykładów, ale w dowolnej rzeczywistej implementacji, szczególnie w procedurach sekwencjonowania genomu, które muszą indeksować całe cromosomy, potrzebne są o wiele szybsze strategie konstrukcyjne.

Efektywne budowanie tablicy: podwójne przedłużanie prefiksów i skośność

Szybsze algorytmy do tworzenia tablicy sufiksowej unikają porównywania sufixów znak po znaku z powrotem od początku. Najbardziej szeroko nauczany podejście nazywa się podwójne przedłużanie prefiksów. Pracuje w rundach. W pierwszej rundzie każdy sufix jest rangowany na podstawie swojego pierwszego znaku, używając standardowego porządku alfabetycznego, co oznacza, że identyczne pierwsze znaki otrzymują tę samą rangę. W drugiej rundzie każdy sufix jest rangowany przy użyciu pary rang: własnej aktualnej rangi plus aktualna ranga sufixu zaczynającego się dwa znaki później, co sumarycznie opisuje pierwsze dwa znaki efektywnie. W kolejnej rundzie okno porównania podwójnia się do czterech znaków, potem osiem, szesnaście i tak dalej, zawsze wykorzystując rangi obliczone w poprzedniej rundzie zamiast czytania raw text od nowa. Ponieważ okno podwójnie się rośnie w każdej rundzie, potrzebne są tylko około log n rund przedtem, aby każdy sufix miał unikalną rangę, a każda runda może być zakończona w czasie order n log n przy użyciu efektywnego sortowania, co daje całe czas budowy rzędu n log n pomnożone przez log n, co jest już znaczące poprawieniem nad podstawowym podejściem, a zastosowanie sztucznych technik sortowania po radiksie może jeszcze bardziej skrócić ten czas. Dalsza szybsza rodzina algorytmów, najbardziej sławnie DC3 (skośność), osiąga prawdziwe rzędu n czasu. Konceptualnie, DC3 dzieli sufiksy na grupy oparte na ich pozycji początkowej modulo trzy, rekurencyjnie sortuje jedną manewrzaną grupę, używając ciekawego zredukowania do mniejszej wersji tej samej problemu, a następnie łączy resztę sufiksów korzystając z wyników tego kroku rekurencyjnego. Szczegóły są skomplikowane, ale nagradzająca jest to, że nawet tablice sufiksowe dla całych genomów lub masowych korpusów tekstowych mogą być budowane w czasie około proporcjonalnym do wielkości wejścia, co jest powodem, dla którego te algorytmy podpinają rzeczywistą bioinformatykę i infrastrukturę wyszukiwania.

Szukanie za pomocą wyszukiwania binarnego

Po zbudowaniu i posortowaniu tablicy sufiksowej, szukanie wzorca o długości m w tekście o długości n staje się niezwykle szybkim. Ponieważ sufiksy są uporządkowane alfabetycznie, wszystkie sufiksy zaczynające się na daną kombinację znaków są grupowane razem w jednym ciągłym bloku tablicy, dokładnie tak samo jak słowa zaczynające się od „cat” są grupowane na stronie słownika. To oznacza, że można użyć wyszukiwania binarnego, powtarzającą się operacji sprawdzania środkowego sufiksu skracającego się zakresu i porównywania wzorca z jego pierwszymi m znakami, aby skoncentrować się na tym bloku. Każde porównanie podczas wyszukiwania binarnego kosztuje najwyżej rzędu m sprawdzeń znaków, ponieważ musisz spojrzieć tylko na pierwsze m znaków kandydatów sufiksu, aby ustalić, czy wzorzec pasuje jako prefix. Wyszukiwanie binarne samego się potrzebuje około log n porównań do zagmatwania z n kandydatami do zakresu docelowego. Mnożenie tych wartości daje całe czas wyszukiwania rzędu m log n, który prawie nie zależy od wielkości otaczającego tekstu, tylko od długości wzorca szukanego i logarytmu długości tekstu. Dwa wyszukiwania binarne, jedno do znalezienia najbardziej lewej pasującej sufiksu, a drugie do najbardziej prawej, odkrywają nie tylko, czy wzorzec istnieje, ale także dokładnie ile razy występuje i w jakich pozycjach, ponieważ każda sufiks w tym zgodnym bloku odpowiada jednej wystąpieniu. To jest ogromne poprawienie w porównaniu do skanowania naganowego tekstu bezpośrednio, które w najgorszym przypadku zajmuje czas proporcjonalny do pełnej długości tekstu pomnożonej przez długość wzorca. W celu wyszukiwania krótkiego fragmentu DNA przeciwko całkowitej chromosomie lub wyszukiwania zapytania motywu w ogromnym indeksowanym dokumencie, ta różnica decyduje o tym, czy wyszukanie zakończy się natychmiastowo, czy zajmie niepraktycznie długą czas.

Tablica LCP, drzewa sufiksowe i tryby

Tablica sufiksowa skutecznie komplementuje się z strukturą o nazwie tablica LCP (najdłuższego wspólnego prefiksu). Każda wpis w tablicy LCP rejestruje, ile znaków na początku mają dwie sąsiadujące sufiksy w porządku posortowanym. To dodatkowe informacje przyspiesza wyszukiwania, ponieważ wyszukiwanie binarne może pomijać powtarzające się porównania znaków, które już efektywnie wykonało, a jednocześnie odpowiada na inne pytania bezpośrednio. Najdłuższa wartość w tablicy LCP natychmiast odkrywa najdłuższy podciąg powtarzający się w tekście, najdłuższy fragment występujący więcej niż raz. Połączenie dwóch ciągów za pomocą unikalnego znacznika oddzielającego i następnie badanie tablicy LCP dla połączonego ciągu odkrywa najdłuższy wspólny podciąg między tymi dwoma pierwotnymi ciągami, technikę używaną do wykrywania plagiatu oraz porównywania DNA między gatunkami. Naturalne jest zapytanie, jak ta struktura porównuje się z innymi podobnymi. Drzewo sufiksowe przechowuje te same informacje o sufiksiach, ale w formie jasno zdefiniowanego drzewa gałęziowego, gdzie powtarzające się prefiksy są skompresowane do wspólnych ścieżek od korzenia; odpowiada na wiele z tych samych pytań i niektóre bardziej zaawansowane tak szybko, ale jego wskaźniki i węzły wewnętrzne zwykle zużywają znacząco więcej pamięci niż proste tablice liczb całkowitych wymagane przez tablicy sufiksowe i tablicę LCP. To prawdziwa korzyść: tablice sufiksowe przekazują trochę mniej elastyczności zapytań i elegancji konstrukcji za mniejsze zużycie pamięci, co ma ogromne znaczenie podczas indeksowania genomów zawierających biliony baz. Warto również jasno rozdzielić to od tryby, na które ta strona poświęca osobny artykuł: tryb jest zazwyczaj budowany z wielu oddzielnych słów lub kluczy do obsługi wyszukiwania prefiksowego w całej tej kolekcji, podczas gdy tablica sufiksowa jest budowana z wszystkich sufiksi jednego ciągu, odkrywając ukrytą strukturę powtarzającą się w tym jednym fragmencie tekstu, a nie relacje między wieloma różnymi wpisami.

Często zadawane pytania

Wypróbuj na żywo

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