Rozdział 4: String-matching w małej pamięci

Załóżmy, że alfabet jest liniowo uporządkowany. Pokażemy, że porównywanie symboli w sensie porządku liniowego można istotnie wykorzystać w algorytmach tekstowych. Porządek liniowy na symbolach implikuje porządek leksykograficzny na słowach, na przykład:
$$ab < ababab < abb < abbaa < abbaaaaaaaaaaa < abbaaaaaab$$

String-matching w pamięci stałej dla specjalnych wzorów

Oznaczmy przez $MaxSuf(w)$ maksymalny leksykograficznie sufiks słowa $w$. Słowo $x$ nazwiemy specjalnym gdy $MaxSuf(x)=x$.

Przykład

$bajtocja$ nie jest słowem specjalnym, ale rotacja tego słowa $tocjabaj$ jest.

Dlaczego słowa o tej własności są interesujące? Większość szybkich algorytmów szukania podsłów korzysta z okresów $p$ prefiksów słowa. Liczenie tych okresów w ogólnym przypadku jest ,,wąskim gardłem'' w projekcie algorytmu. Natomiast dla słów specjalnych liczenie okresów jest trywialne.

Jeśli $x$ jest specjalny to okres każdego prefiksu słowa $x$ można policzyć następującym naiwnym algorytmem.

Algorytm funkcja Naiwne-Liczenie-Okresu(j)

period := 1;
for i := 2 to j do
    if x[i] <> x[i - period] then
        period := i;
return period;

Funkcja Naiwne-Liczenie-Okresu daje zły wynik dla tekstów które nie są specjalne, na przykład załóżmy że $x= (aba)^6a = abaabaabaabaabaabaa$. Wtedy kolejne wartości okresów dla pozycji $j=1,\, 2,\, \ldots$ są:

a	b	a	a	b	a	a	b	a	a	b	a	a	b	a	a	b	a	a
1	2	2	4	5	5	7	8	8	10	11	11	13	14	14	16	17	17	19

Zatem Naiwne-Liczenie-Okresu(19) = 19, dla $x = (aba)^6a$, wynik całkowicie niepoprawny.

Opiszemy teraz program szukający wzorca $x$ w słowie $y$ zakładając, że $x$ jest specjalne. Program wczytuje dwa słowa, pierwsze z nich jest specjalne: $x$ pamiętamy w tablicy $x[0 \ldots m-1]$, $y$ w tablicy $y[0 \ldots n-1]$. Program wypisuje wszystkie wystąpienia $x$ w $y$, tzn. wszystkie takie pozycje $i$, że $y[i \ldots i+m-1] = x$. Zapisujemy szkielet programu w języku C++:

Algorytm Specjalny-String-Matching

#include <iostream>
#include <string.h>
 
int i = 0, j = 0, p = 1;
 
void przesun() {
	if (j - 1 < 2 * p) {
		i = i + p;
		j = 0;
		p = 1;
	} else {
		j = j - p;
		i = i + p;
	}
}
 
int main() {
	std::string x, y;
	std::cin >> x >> y;
	int m = x.size(), n = y.size();
 
	while (i <= n - m) {
		if (j == m) {
			std::cout << i << "\n";
			przesun();
		} else if (x[j] == y[i + j]) {
			j = j + 1;
			if (x[j - 1] != x[j - 1 - p])
				p = j;
		} else {
			przesun();
		}
	}
}

Powyższy kod jest wstępem do programu szukającego dowolnego podsłowa, niekoniecznie będącego specjalnym. Podstawowym niezmiennikiem w programie przed każdym wykonaniem i po każdym zakończeniu pętli while jest:

$x[0 \ldots j-1] = y[i \ldots i + j - 1]$,
Program wypisał wszystkie wcześniejsze wystąpienia $i' < i$,
$p$ jest okresem słowa $x[0 \ldots j - 1]$.

Algorytm Specjalny-String-Matching działa w czasie liniowym, można to udowodnić obserwując zmiany wartości $2i + j$. Zauważmy bowiem, że wartość ta nie zmniejsza się, a w wypadku pozytywnego testu (x[j] == y[i + j]) zwiększa się co najmniej o 1. Jednocześnie $2i + j \leq 3n$.

String-matching w pamięci stałej dla dowolnych wzorców

Algorytm Specjalny-String-Matching można łatwo zmodyfikować tak, aby znajdował on wystąpienia dowolnego słowa (niekoniecznie specjalnego) w czasie liniowym i stałej pamięci. Niech $x = uv$, gdzie $v$ jest leksykograficzne maksymalnym sufiksem $x$. Oznaczmy $r=|u|$. Technicznie informacja o rozkładzie $uv$ sprowadza się do pamiętania $r$.

Własność rozkładu. Niech $x=uv$ będzie rozkładem jak wyżej opisany. Wtedy słowo $v$ występuje tylko raz w słowie $uv$. Jeśli $i' < i$ są początkami wystąpień $v$ oraz $i - i' < r$, to na pozycji $i - 1$ nie kończy się wystąpienie $u$.

Z powyższego faktu wynika stosunkowo prosty algorytm szukania $x$ w czasie liniowym i pamięci stałej. Algorytm ten jest modyfikacją algorytmu Specjalny-String-Matching, w którym rolę $x$ pełni $v$.

Algorytm String-matching w pamięci stałej

Niech $v$ będzie leksykograficznie maksymalnym sufiksem $x$.
Liczymy algorytmem Specjalny-String-Matching kolejne wystąpienia $v$ w $y$.
Dla każdego wystąpienia $i$ niech $i'$ będzie wystąpieniem poprzednim.
Jeśli $i - i' \ge |v|$, sprawdź czy $u$ występuje na lewo od pozycji $i$ (sprawdzanie to wykonujemy w sposób naiwny).
Jeśli występuje, wypisz kolejne wystąpienie całego wzorca $x$.

Pozostawiamy bardziej precyzyjny zapis algorytmu jako ćwiczenie.

W ten sposób pokazaliśmy, że problem szukania słowa $x$ w słowie $y$ można rozwiązać w czasie liniowym i pamięci (dodatkowej) stałej, jeśli znamy początkową pozycję $r$ leksykograficznie maksymalnego sufiksu $v$ słowa $x$.

Liczenie maksymalnego sufiksu w pamięci stałej

W algorytmie szukania wzorca w pamięci stałej potrzebna jest pozycja $r$, od której zaczyna się maksymalny sufiks. Pokażemy teraz, jak ją znajdować w czasie liniowym i w pamięci stałej. Kluczem do tego jest liczenie czegoś więcej: dla każdego prefiksu liczymy jego maksymalny sufiks, jak również dodatkowo jego okres.

To właśnie liczenie okresu daje efektywność, chociaż na końcu ten okres nie jest nam potrzebny. Przekształcimy najpierw algorytm Naiwne-Liczenie-Okresu na algorytm liczący długość najdłuższego specjalnego prefiksu włącznie z jego okresem.

Algorytm funkcja Najdłuższy-Specjalny-Prefiks(x)

period := 1;
for i := 2 to |x| do
    if x[i] < x[i - period] then
        period := i
    else if x[i] > x[i - period] then
        return (i-1, period);
return (|x|, period);

Skorzystamy z algorytmu Najdłuższy-Specjalny-Prefiks. Funkcja Maksymalny-Sufiks liczy początkową pozycję i okres maksymalnego sufiksu.

Algorytm funkcja Maksymalny-Sufiks(x)

j := 1;
repeat
    (i, period) := Najdłuższy-Specjalny-Prefiks(x[j..n]);
    if i = n then
        return (j, period)
    else
        j := j + i - (i mod period);
forever;

Możemy przepisać algorytm Maksymalny-Sufiks tak, aby nie wywoływał on funkcji Najdłuższy-Specjalny-Prefiks, wpisując tę funkcję do algorytmu.

Arytmetyczna funkcja $\bmod$ może być usunięta i zastąpiona przez operacje dodawania i odejmowania bez zmiany asymptotycznej złożoności. Algorytm Maksymalny-Sufiks wykonuje co najwyżej $2|x|$ porównań symboli. Uzasadnienie pozostawiamy jako ćwiczenie.

Algorytm funkcja Maksymalny-Sufiks(x)

s := 1;
i := 2;
p := 1;
while i <= n do begin
    r := (i - s) mod p;
    if x[i] = x[s+r] then
        i := i + 1
    else if x[i] < x[s+r] then begin
        i := i + 1;
        p := i - s;
    end else begin
        s := i - r;
        i := s + 1;
        p := 1;
    end;
end;
return s;

Równoważność cykliczna słów

Rotacją słowa $u = u[1\ldots n]$ jest każde słowo postaci $u^{(k)} = u[k+1 \ldots n] u[1 \ldots k]$, w szczególności $u^{(0)} = u^{(n)} = u$. Niech $u,\, w$ będą słowami długości $n$. Mówimy, że są one cyklicznie równoważne, gdy $u^{(i)} = w^{(j)}$ dla pewnych $i$, $j$.

Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa $u$ w słowie $ww$, ale podamy algorytm znacznie prostszy, bazujący na liniowym porządku alfabetu. Algorytm ten będzie działał w czasie liniowym i w miejscu (dodatkowa pamięć jest stała). W algorytmie rozszerzamy tablice $u$ i $w$ na $uu$ i $ww$, ale robimy to jedynie dla uproszczenia - w rzeczywistości możemy poruszać się cyklicznie po $u$ i po $w$.

Algorytm Równoważność-Cykliczna

x := uu;
y := ww;
i := 0; j := 0;
while (i < n) and (j < n) do
	k := 1;
	while (x[i + k] = y[j + k]) do
		k := k + 1;
	if (k > n) then
		return true;
	if (x[i + k] > y[i + k]) then
		i := i + k
	else
		j := j + k;
end;
return false;

Zdefiniujmy:

$D(u) = \lbrace k : 1 \leq k \leq n$ i $u^{(k)} > w^{(j)}$ dla jakiegoś $j\rbrace$,
$D(w) = \lbrace k : 1 \leq k \leq n$ i $w^{(k)} > u^{(j)}$ dla jakiegoś $j\rbrace$.

Skorzystamy z prostego faktu:

Fakt.
Jeśli $D(u) = [1 \ldots n]$ lub $D(w) = [1 \ldots n]$, to $u$ i $w$ nie są równoważne cyklicznie. Uzasadnienie pozostawiamy jako ćwiczenie.

Poprawność algorytmu wynika teraz z tego, że po każdej iteracji głównej pętli zachodzi niezmiennik: $D(w) \supseteq [1 \ldots i]$ oraz $D(u)\supseteq [1 \ldots j]$. Liczba porównań symboli w algorytmie jest oczywiście liniowa. Pozostawiamy jako ćwiczenie policzenie dokładnego wzoru na maksymalną liczbę porównań symboli dla tekstów długości $n$.

Informatyka MIMUW