Automat sufiksowy: Skompresowana mapa każdego podciągu

Jakie Problem Automat Sufiksowy Rozwiązuje?

Dane ciąg o długości n, zbiór jego różnych podciągów może być ogromny: do około kwadratu liczby n dla ciągu bez powtarzających się znaków. Zapisywania je jawnie, jeden po drugim, jest nieefektywne i często niemożliwe dla długich tekstów. Automat sufiksowy uniknie tej sytuacji budując rozpoznawcę zamiast listy. Jest to automat skończony deterministyczny: zestaw stanów połączonych przekazaniami etykietowanych, z jednym stanem początkowym, takim że podążając za przekazaniami opisanymi przez dowolny podciąg oryginalnego ciągu zawsze spadamy na jakiś stan, a podążając za przekazaniami opisanymi przez dowolny niepodciąg zatrzymujemy się pośrednio. Krytycznie, każdy stan, który można osiągnąć, odpowiada zaakceptowaniu co najmniej jednego podciągu, więc każdy stan jest niejawnie akceptujący dla podciągów prowadzących doń. Wspaniałość konstrukcji polega na tym, że nawet jeśli liczba różnych podciągów może być kwadratowa w stosunku do n, liczba stanów w tym automacie nigdy nie przekracza około dwóch razy n minus jeden, a liczba przekazan nigdy nie przekracza około trzech razy n minus cztery dla n większego niż dwa. To możliwe dlatego że pojedynczy stan w automatzie reprezentuje całą klasę równoważności podciągów, które się zdarzają dokładnie na tej samej grupie pozycji końcowych w tekście. Dwa podciągi połączają się w jeden stan dokładnie wtedy, gdy każda wystąpienie krótszego jest natychmiastem połączone z każdym wystąpieniem dłuższego w tekście — formalnie, dzielą się tym samym zestawem pozycji końcowych, nazywanymi endpos. Ta równość stanowi koncepcyjny serduszko całej struktury: zamiast reprezentować podciągi osobno, automat reprezentuje klasy endpos i takich nie ma tyle. Ponieważ automat jest deterministyczny, testowanie członkostwa jest mechaniczne i szybkie: zaczynając od stanu początkowego, podążając za przekazaniem etykietowanym przez każdy znak kandydatów do wzoru w kolejności, jeśli nigdy nie opusczamy automatu, wzorzec jest podciągiem. Jeśli jakikolwiek przekaz brakuje, to on go nie jest. Brak cofania się, żadnych porównań poza odczytanie każdego znaku wzoru tylko raz.

Stan, klasy końcowe i drzewo linków sufiksowych

Każdy stan automatu sufiksowego odpowiada niepustemu zbiorowi podciągów, które mają taką samą klasę końcową (endpos). Ten zbiór podciągów zawsze jest ciągiem kontynuowanym długości: najkrótszym i najdłuższym podciągiem mapowanym na dany stan, oraz wszystko między nimi, dzielą one tę samą klasę końcową. Stąd każdy stan przechowuje dwie długości — minimalną i maksymalną długość podciągów, które reprezentuje — a każdy podciąg w tym zakresie jest uzyskiwany z najdłuższego przez usunięcie znaków z początku. To jest miejsce, gdzie wchodzą linki sufiksowe. Każdy stan, z wyjątkiem początkowego, ma link sufiksalny wskazujący na stan reprezentujący klasę końcową (endpos) najdłuższego sufiksu właściwego podciągu jego najdłuższego podciągu, który należy do innej, stricte większej klasy końcowej. Przechodząc po linkach sufiksowych z dowolnego stanu, przechodzimy przez coraz krótsze podciągi z coraz bardziej ogólnej (większej) klasą końcową, a ta łańcuch zawsze kończy się początkowym stanie, który reprezentuje pusty ciąg. Zbiór linków sufiksowych, wraz, tworzy drzewo o korzeniu w początkowym stanie — często nazywane drzewem linków sufiksowych lub drzewem rodziców. To drzewo nie jest efektem ubocznym; to druga, równie ważna struktura położona na topie grafu przejść automatu. Wiele najbardziej użytecznych obliczeń automatu rzeczywiście polega na operacjach drzewiastych wykonywanych na nim. Na przykład liczba razy, w jakich dany podciąg występuje w oryginalnym tekście, równa się rozmiarowi klasy końcowej (endpos) stanu do którego jest mapowany, a ten rozmiar można obliczyć dla każdego stanu jednocześnie, wykonując pojedyncze przejście od dołu na drzewie linków sufiksowych: liście odpowiadające pozycjom w których kończy się sufiksy całego ciągu dodają liczbę jeden, a każda stanowa interna jest sumą liczb jej potomków w drzewie.

Konstrukcja Online, Jednoznakowo Po Jednym

Co sprawia, że automat sufiksowy jest praktycznie użyteczny, a nie tylko estetycznie elegancki, to jego zdolność do budowy w sposób inkrementalny. Zaczynamy od automatu dla pustego ciągu, który składa się z jednego stanu początkowego. Następnie rozszerzamy go, dodając znaki jeden po drugim: po przetworzeniu prefiksu długości k, automat na bieżąco jest dokładnie automatem sufiksowym dla tego prefiksu. Dodanie kolejnego znaku aktualizuje go do automatu sufiksowego dla prefiksu o długości k plus jeden, bez odwrotnej wizyty wcześniejszych znaków tekstu. Każda kroka rozszerzający tworzy nowy stan reprezentujący całą widoczną dotychczasowo sekwencję prefiksu jako podciąg, a następnie przechodzi od tyłu po linkach sufiksowych z poprzedniego stanu końcowego, dodając przejście dla nowego znaku tam, gdzie jest brakujące, aż albo dojdzie do drzewa (dotrze do stanu początkowego) lub znajdzie stan, który już ma przejście dla nowego znaku. W przypadku drugiej sytuacji dokładne sprawdzenie ustala, czy istniejące przejście już reprezentuje dokładnie odpowiedni klasę endpos, czy musi być podzielone na dwa stany — jeden dla dłuższych podciągów, które nadal dzielą się tą samą zbiorem endpos, a drugi, klon, dla krótszych podciągów, których zbiór endpos właśnie rozrosł się do włączenia nowego położenia. To kroku klonowania jest to, co utrzymuje kontynuowany zakres każdego stanu jako podciąg i dobrze definiuje każdą klasę endpos, a jest najtrudniejszą częścią algorytmu do zaimplementowania poprawnie. Nieważne, jak wydajne wydają się pojedyncze kroki, analiza amortyzowana (każdy znak może spowodować ograniczony wysiłek odwrotnej wizyty i klonowania na całym procesie konstrukcji) pokazuje, że cała procedura działa w czasie liniowym względem długości ciągu, dla dowolnego alfabetu o ustalonej wielkości, i używa liniowego miejsca. Ta właściwość online ma praktyczne korzyści: możesz zapytać automat o tekst widocznego dotychczasowo w dowolnym momencie konstrukcji, co dokładnie jest potrzebne dla aplikacji streamingowych do dopasowywania podciągów.

Co można obliczyć po zbudowaniu automatu

Posiadając automat i drzewo linków sufiksowych, wiele klasycznych problemów związanych z napisami redukuje się do prostych przebiegów. Testowanie podciągu: śledź przejścia oznaczone znakami kandydatów na wzór od stanu początkowego; sukces, jeśli nigdy nie zostaniesz zablokowany, w czasie proporcjonalnym tylko do długości wzoru, niezależnie od długości oryginalnego tekstu. Liczenie różnych podciągów: każdy stan poza początkowym odpowiada kontynuowanemu zakresowi długości podciągu (takich o wielkości różnica między jego długością a długością linka sufiksowego), więc sumując tę ilość dla wszystkich stanień daje dokładną liczbę różnych podciągów w całym tekście, obliczona w czasie liniowym względem liczby stanów. Liczenie wystąpień konkretnego podciągu: znajdź stan do którego mapuje się przez śledzenie jego znaków, a następnie odczytaj z przeliczonego rozmiaru zbioru endpos dla tego stanu (opisane wcześniej suma drzewa od dołu). Znalezienie najmniejszego lub największego leksykograficznie podciągu danego długości, lub wypisanie podciągów w uporządkowanej kolejności, można zrobić przez przebieganie grafu przejść, ponieważ przejścia z danego stanu są naturalnie uporządkowane według znaków. Najbardziej zaskakującym zastosowaniem jest najdłuższy wspólny podciąg dwóch napisów. Buduj automat sufiksowy tylko dla pierwszego napisu. Następnie wprowadzaj drugi napis jako strumień pytania o doczytelność: utrzymuj bieżący stan i długość bieżącego dopasowania, a następnie dla każdego znaku drugiego napisu próbuj rozszerzyć dopasowanie; jeśli przejście istnieje, rozszerzaj; jeśli nie, wracaj po linkach sufiksowych (skracając bieżące dopasowanie) do momentu znalezienia pasującego przejścia lub osiągnięcia stanu początkowego. Monitorując najlepszą długość dopasowania podczas jednej przechodniowej iteracji drugiego napisu, uzyskuj najdłuższy wspólny podciąg obu napisów w czasie liniowym względem ich łącznej długości — nie ma potrzeby budowania struktury nad łączeniem obu napisów, a dodatkowa struktura nie musi być budowana dla drugiego napisu w ogóle.

Automat sufiksowy w porównaniu do tablicy sufiksowej: Dwie perspektywy na to samo podciągi

Ten artykuł już pokrywa tablicę sufiksową, która sortuje wszystkie n sufiksy ciągu leksykograficznie i przypisuje ten uporządkowany porządek do tablicy LCP (najdłuższego wspólnego prefiksu), która dla każdego paru sąsiednich sufiksi uporządkowanych rejestruje, ile znaków na początku te sufiksy mają wspólnych. Tablica sufiksowa i automat sufiksowy opisują w końcu tę samą podstawową strukturę — strukturę podciągów ciągu — ale reprezentują ją w podstawowo innych kształtach, a jest warto kontrastować je bezpośrednio zamiast traktować je jako wymiennicze. Tablica sufiksowa jest fundamentalnie listą: n sufiksy, uporządkowane, każdy wpis odnajduje się w tekście, plus dodatkowa tablica LCP długości n minus jeden. Jego rozmiar zawsze jest dokładnie proporcjonalny do n, długości ciągu, niezależnie od tego, jak powtarzalne lub jak różnorodne jest zawartość ciągu. Automat sufiksowy, w przeciwieństwie do tego, to graf: liczba jego stanów jest ograniczona około dwukrotnie n, ale dla ciągów z ciężką wewnętrzną powtarzalnością, rzeczywista liczba użytych stanów często jest znacznie mniejsza niż ta granica, ponieważ wiele sufiksy kollapse w klasy koncowych. Nie ma równoważnego kollapse dla formatu tablicy sufiksowej, ponieważ musi zawsze lista każdy sufiks jako odzielny wpis uporządkowany — tablica sufiksowa dla ciągu jak dwadzieścia powtarzania tej samej litery nadal ma tyle samo wpisów co sufiksy, podczas gdy odpowiadający automat sufiksowy pozostaje ekstremalnie mały, ponieważ prawie wszystko kollapse w kilka stanów. Te dwa struktury różnią się także w tym, ile kosztuje pojedyncza zapytanie. Z tablicą sufiksową plus tablicą LCP testowanie, czy wzór długości m jest podciągiem tekstu typowo używa wyszukiwania binarnego nad uporządkowanymi sufiksy, co kosztuje około m razy logarytm n porównań znaków (lub m plus logarytm n z dodatkowym przetwarzaniem). Z automatem sufiksowym, ta sama operacja kosztuje dokładnie m kroków — jeden przejście na każdy znak wzoru — bez zależności od n poza tym, że automat jest już budowany. Automat sufiksowy jest również budowany online, rozszerzając się naturalnie wraz z przybywaniem znaków, podczas gdy tablica sufiksowa jest normalnie obliczana tylko po tym, jak cała długość ciągu jest znana, używając algorytmów opartych na sortowaniu w grupach. W skrócie: wybierz tablicę sufiksową, kiedy chcesz stabilne, przewidywalnie wielkościowe, uporządkowane widok dobrze dopasowany do zapytań zakresu i rangi; wybierz automat sufiksowy, kiedy chcesz najmniejszego możliwego rozpoznawcę dla podciągów, szczególnie dla powtarzalnego tekstu, konstrukcji streamingowej lub czasu zapytania na wzór, który ignoruje całkowitą długość tekstu.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Suffix Automaton: The Compressed Map of Every Substring i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.