Algorytm Z dla dopasowywania napisów

Co NaFactura Z-Węzeł Występuje

Dla ciągu S o długości n, tablica Z również ma długość n. Każdy element Z dla indeksu i jest zdefiniowany w stosunku do całego ciągu S od jego pierwszego znaku. Konkretnie, wartość Z dla indeksu i to długość najdłuższego wspólnego prefiksu między S a sufiksami S, które się zaczynają na pozycji i. W prostych słowach: porównujemy S od początku z tym samym S, ale zaczynając od pozycji i, liczymy ilość znaków, które pasują przed pierwszą niezgodność, a ta liczba to Z dla indeksu i. Pozycja 0 jest przypadkiem szczególnym i zwykle zostaje zdefiniowana jako nieokreślona lub ustawiona na n, ponieważ porównanie S ze sobą zawsze pasuje całkowicie; interesujące informacje zawierają się w pozycjach od 1 do n-1. Rozważmy ciąg abcabcabx. Na pozycji 3 sufiks to abcabx, a porównując go z pełnym ciągiem od początku otrzymujemy pasujący-prefix abc przed pierwszą niezgodnością, więc Z dla 3 wynosi 3. Na pozycji 6 sufiks to abx, który pasuje tylko do ab w stosunku do prefiksu, dając Z dla 6 równy 2. Na pozycji 1 sufiks bcabcabx nie ma żadnych znaków wspólnych z prefiksem zaczynającym się od a, więc Z dla 1 wynosi 0. Przegladając każdą pozycję dostajemy pełny profil podobieństwa samoczynnego ciągu na każdym przesunięciu, co dokładnie odpowiada potrzebom dalszej analizy wzorców. Pomysł jest, że tablica Z odwzorowuje, jak bardzo dany punkt początkowy w ciągu wygląda tak samo jak początek. Ciągi o silnej powtarzalności wewnętrznego, takie jak aaaaa lub abcabcabc, tworzą tablice Z z dużymi, strukturalnymi wartościami, podczas gdy ciągi o niewielkiej powtarzalności wewnętrznej tworzą tablice Z dominowane przez zera i małym liczbach. Zrozumienie tej definicji dokładnie jest kluczowe, ponieważ cała technika budowania liniowego czasu opiera się na rozpatrywaniu nawiązywanych przedziałów pasujących znaków zamiast rekonstrukcji każdego elementu od podstawowej porównania.

Naiwny podchód i dlaczego jest nieefektywny

Najprostszym sposobem na obliczenie tablicy Z jest przejście po każdym pozycji początkowej i od 1 do n-1, a dla każdego porównanie znaków S zaczynając od pozycji 0 przeciwko znakom S zaczynając od pozycji i, licząc dopasowania aż do wystąpienia niezgodności lub do końca ciągu. To absolutnie działa i tworzy poprawną tablicę Z, ale koszt może być kwadratowy w najgorszym przypadku. Wyobraźmy sobie ciąg składający się entirely z powtarzającego się znaku, na przykład aaaaaaaaaa. Na pozycji 1 porównanie przechodzi prawie do końca ciągu przed znalezieniem niezgodności, ponieważ wszystko dopasowuje. Na pozycji 2 to samo długie porównanie ponownie się powtarza, a ponownie na pozycji 3 i tak dalej dla każdej pozycji początkowej. Całkowita ilość pracy staje się proporcjonalna do n kwadratowego, co jest zbyt wolne dla długich ciągów, takich jak sekwencje genomu, pliki logi lub duże dokumenty, w których n może wynosić miliony. Nieszczęśliwe jest to, że wszystkie te powtarzające się porównania są na bardzo rzeczywisty poziomie bezużyteczne, ponieważ porównania wykonane podczas obliczania Z dla 1 już odrzucają wiele informacji o tym, co się stanie podczas obliczania Z dla 2, Z dla 3 i dalej. Jeśli ciąg dopasowuje się do prefiksu na długim odcinku zaczynając od pozycji 1, to ten sam odcinek jest podciągiem S, a jego struktura wewnętrzna została już zapisana przez wcześniejsze wartości Z obliczone dla pozycji zawierających się w tym odcinku. Naiwny algorytm rzuca te informacje i zaczyna porównanie od nowa, znak po znaku, zaczynając od pozycji 0. Kluczowe osiągnięcie, które prowadzi do algorytmu działającego w liniowym czasie, polega na utrzymywaniu śledzenia najdalszej prawej części ciągu, która została już potwierdzona jako dopasowana do prefiksu, oraz ponownym wykorzystywaniu wcześniejszych wartości Z zawierających się w tej części zamiast je ponownie odczytywać, tylko opadając do bezpośredniego porównania znaków, gdy naprawdę nowe tereny są eksplorowane poza tym, co już zostało zweryfikowane.

Z-Box: Wspakrywane Przez Okno

Trucizna zachowującą czas liniowy utrzymuje dwie wskaźniki, konwencjonalnie nazywane L i R, które wspólnie definiują to, co nazywa się Z-boxem: przedział od L do R reprezentujący prawym końcem najdłuższą znaną dotychczas sekwencję, która pasuje do prefiksu S, odkrytą podczas obliczania pewnej wcześniejszej wartości Z. Podczas skanowania pozycji od lewej do prawej, algorytm utrzymuje L i R w aktualnym stanie, aby zawsze reprezentować najdłuższy znaleziony pasujący przedział. Gdy obliczany jest Z dla i, istnieją dwie przypadki. Jeśli i leży poza bieżącym Z-boxem, co oznacza, że i znajduje się poza R, nie ma tu szlaków do skrócenia, więc algorytm wraca do bezpośredniej porównywania znak po znaku od pozycji 0, dokładnie tak jak metoda naiwna. Jeśli to powoduje pasującą długość różną od zera, L i R są aktualizowane, aby reprezentować nowy, bardziej rozszerzony Z-box. Drugi przypadek jest ciekawym: jeśli i znajduje się w istniejącym Z-boxie, co oznacza, że L jest mniej niż lub równe i, a i jest mniej niż lub równe R, to pozycja i odpowiada na pewną pozycję k w prefiksu, konkretnie k równa się i odejmij L, ponieważ podciąg od L do R jest już znany jako równy prefiksu tej samej długości. To oznacza, że wartość Z dla k, już obliczona wcześniejszy, daje silne informacje na temat Z dla i bez potrzeby nowych porównań. Jeśli Z dla k jest stringiem niższy od pozostającej odległości do R, co oznacza, że pasowanie w pozycji k zakończyło się bez naruszenia granic, to wartość Z dla i może być skopiowana bezpośrednio z Z dla k, nie potrzebując żadnych porównań. Ale jeśli Z dla k osiąga lub przekracza tę pozostającą odległość, algorytm nie jest pewny, że pasowanie kontynuuje się poza R, ponieważ nie ma informacji na temat znaków poza granicami Z-boxu, więc musi rozszerzyć porównanie zaczynając dokładnie w pozycji R plus jeden, sprawdzając tylko nowe, dotychczas niewidziane znaki, a następnie aktualizując L i R odpowiednio. To prawo, że wykorzystujemy to, co już udowodnił Z-box, i walidujemy tylko nieznane resztę, jest to, co sprowadza całą pracę po całym skanie do czasu liniowego: każdy znak jest włączony w najwyżej małą stałą liczbę porównań ogólnie, ponieważ R porusza się tylko naprzód i nigdy wstecz.

Od tablicy Z do dopasowywania wzorców

Konwersja tablicy Z na pełny narzędzie do wyszukiwania wzorców wymaga jednej dodatkowej idei: tworzenia łączonej napisu. Dla danego wzoru P o długości m i tekstu T o długości n, zbuduj napis łączony, który tożsami z P plus separator plus T, gdzie separator jest wybrany tak, aby nie występować nigdzie w P ani w T, np. znak null lub inny symbol sentinela przeznaczony do tego celu. Oblicz tablicę Z dla tego łączonego napisu przy użyciu opisanego powyżej procedury działającej w liniowym czasie. Teraz sprawdź każdy indeks i w łączonym napisie, który znajduje się w części tekstu, czyli po wzorze i separatorze. Jeśli Z(i) jest równe dokładnie m, długości wzoru, to oznacza to, że sufiks łączonego napisu od pozycji i dopasowuje się do pełnego prefiksu tego samego łączonego napisu, czyli dokładnie wzór P, znak za znakiem. Inaczej mówiąc, indeks i oznacza początek dokładnej wystąpienia wzoru w tekście. Ponieważ znak separatora nie może występować ani w jednym z obu napisów, dopasowanie niemożliwe jest do spowodowania przekroczenia z tekstu na obszar wzoru lub przypadkowego uwzględnienia separatora, co zapewnia kompletną dokładność dopasowania. Ponieważ tablica Z dla łączonego napisu o długości m plus n plus 1 jest budowana w liniowym czasie względem własnej długości, a skanowanie jej na poszukiwanie wpisów równych m również działa w liniowym czasie, cała procedura wyszukiwania wzorców działa w czasie proporcjonalnym do m plus n, co stanowi znaczące ulepszenie nad przypadkowym worst case dla prostego dopasowania proporcjonalnego do m times n. Ta metoda naturalnie zwraca wszystkie wystąpienia, a nie tylko pierwsze, ponieważ skanowanie kontynuuje się przez całą tablicę, i generalizuje się łagodnie do wyszukiwania tego samego wzoru w wielu tekstach, lub do pokrewnych problemów, takich jak znalezienie najdłuższego podciągu wspólnego jako prefiksu oraz gdzieś wewnątrz jednego napisu, czy mierzenie samoszybkości dla zadań takich jak wykrywanie okresowej powtarzalności.

Z-Algorithm versus KMP: Dwa Ścieżki do Linii Czasu

Naturalne jest zapytanie, jak Z-algorytm jest powiązany z podejściem Knutha-Morrisa-Pratta (KMP), ponieważ oba osiągną exact pattern matching w czasie liniowym i oba unikają ponownego sprawdzania znaków, wykorzystując strukturę wewnętrzną wzorca. Podstawowa różnica polega na tym, co dokładnie każdy algorytm oblicza oraz jak używa tej informacji podczas skanowania. KMP buduje funkcję niepowodzenia (prefix function), która jest zdefiniowana jedynie nad wzorcem, gdzie każda wpis rejestruje długość najdłuższego prawdziwego prefiksu wzorca, który również jest sufiksem kończącym się w tym miejscu; podczas faz wyszukiwania KMP przesuwa pojedynczy wskaźnik przez tekst i używa funkcji niepowodzenia do decyzji o tym, jak daleko cofnąć się w wzorcu po nieporządku, bez kiedykolevki cofnięcia się przez tekst. Z-Algorithm z kolei oblicza tablicę Z bezpośrednio nad łączeniem wzorca-separatory-teksu, a pasy są czytane prosto, sprawdzając, gdzie wartość Z jest równa długości wzorca, bez konieczności dodatkowej logiki cofnięcia się i ponownego próbowania podczas faz wyszukiwania, ponieważ budowa tablicy Z już wciąż zawiera wszystkie te rozważania poprzez mechanizm Z-box. W praktyce to sprawia, że logika Z-algorytmu jest nieco łatwiejsza do zrozumienia dla wielu uczących się, ponieważ istnieje jedna, uniformiczna procedura konstrukcji tablicy zamiast dwóch fazy pojęciowo oddzielnych: przeprocesowania wzorca i skanowania tekstu ze zbiorem odrębnych zasad. KMP, z drugiej strony, unika budowy wyraźnej łączonej napisu i jego funkcji niepowodzenia jest często ponownie używana bezpośrednio do innych celów, takich jak detekcja najkrótszego powtarzalnego elementu w napisie. Oba działają w czasie liniowym i oba są całkowicie deterministyczne bez żadnej losowości, więc ani jedno, ani drugie nie jest stricte lepsze; wybór między nimi w praktyce często zależy od preferencji implementacyjnej, czy perspektywa funkcji niepowodzenia lub perspektywa dopasowania prefiksu wydaje się bardziej naturalna, oraz czy inne właściwości tablicy Z, takie jak jej użyteczność dla zapytań o podobieństwo prefiksowe poza proste wyszukiwanie wzorca, są potrzebne w innych miejscach konkretnego zastosowania.

Często zadawane pytania

Wypróbuj na żywo

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