Algorytmy i struktury danych/Algorytmy tekstowe II: Różnice pomiędzy wersjami

Wersja z 06:40, 24 sie 2006

Zaawansowane algorytmy tekstowe II

W module tym zajmiemy się strukturami danych reprezentującymi zbiór wszystkich podsłów danego słowa $x$ ,zapisywany jako $S u b w o r d s (x)$ . Oznaczmy wszystkie wystąpienia (początkowe pozycje) słowa $z$ w słowie $x$ przez $O c c (z, x)$ . ( $O c c$ jest skrótem od ang. Occurrences).

Chcemy znaleźć taką reprezentację zbioru $S u b w o r d s (x)$ by można było łatwo odpowiedzieć na pytanie $z \in S u b w o r d s (x)$ , (co jest równoważne $O c c (z, x) \neq \emptyset$ ) jak również rozwiązywać inne problemytekstowe. Poza tym chcemy by rozmiar tej eprezentacji był liniowy, podczas gdy rozmiar $S u b w o r d s (x)$ może być kwadratowy. Spośród wielu dobrych reprezentacji najbardziej znanymi są tablice sufiksowe (oznaczane przez $S U F$ ) i drzewa sufiksowe.

Niech $x = a_{1} a_{2} \dots a_{n}$ , oraz niech $x_{n + 1} = #$ będzie specjalnym znakiem leksykograficznie mniejszym od każdego innego symbolu.

Oznaczmy przez $s u f i k s_{i} = a_{i} a_{i + 1} \dots a_{n}$ sufiks tekstu x zaczynający się na pozycji i-tej.

Niech $S U F [k]$ będzie pozycją od której zaczyna się k-ty leksykograficznie sufiks x.

Sufiks zaczynający się na pozycji $(n + 1)$ -szej nie jest brany pod uwagę.

Ciąg sufiksów posortowany leksykograficznie wygląda następująco:

s u f i x_{S U F [1]} < s u f i x_{S U F [2]} < s u f i x_{S U F [3]} < \dots s u f i x_{S U F [n]}

Rysunek 1: Tablicą sufiksową tekstu $x = b a b a a b a b a b b a #$ jest ciąg Parser nie mógł rozpoznać (błąd składni): {\displaystyle SUF\ =\ [4,\ 2,\ 5,\ 7,\ 9,\ 12,\ 3,\ 1,\ 6,\6,\ 8,\ 11,\ 10]}
Oznaczmy przez $l c p [k]$ długść wspólnego prefisku $k$ -tego i następnego sufiksu w kolejności leksykograficznej. Na rysunku wartości najdłuższego wspólnego prefiksu między kolejnymi słowami są przedstawione jako zacienione segmenty. Odpowiadają one tablicy $l c p = [1, 3, 4, 2, 1, 0, 2, 4, 3, 2, 1]$ .
Tablica sufiksowa ma następująca miłą własność: Niech

$m i n_{z} = \min {k : z jest prefiksem s u f i k s_{S U F [k]}}$ , $m a x_{z} = \max {k : z jest prefiksem s u f i k s_{S U F [k]}}$ .

Wtedy $O c c (z, x)$ jest przedziałem w tablicy sufiksowej od $m i n_{z}$ do $m a x_{z}$ .

Drzewo sufiskowe jest drzewem, w którym każda ścieżka jest etykietowana kolejnymi symbolami pewnego sufiksu, oraz każdy sufiks $x$ jest obecny w drzewie. Gdy dwie ścieżki się rozjeżdżają tworzy się wierzchołek. Mówiąc bardziej formalnie każdej krawędzi jest przypisane jako etykieta pewne podsłowo $x$ . Krawędzie wychodzące z tego samego węzła różnią się pierwszymi symbolami swoich etykiet,patrz rysunek.

Etykiety są kodowane przedziałami w tekście $x$ : para liczb $[i, j]$ reprezentuje podsłowo Parser nie mógł rozpoznać (nieznana funkcja „\ldotsa”): {\displaystyle a_ia_{i+1}\ldotsa_j} , zobacz prawe drzewo na rysunku. Dzięki temu reprezentacja ma rozmiar $O (n)$ . Wagą krawędzi jest długość odpowiadającego jej słowa.

Rysunek 2: Drzewo sufiksowe dla tekstu $x = b a b a a b a b a b b a$ . Na końcu jest dodany zank $#$ . Końcowe węzły zawierają informację gdzie zaczyna się sufiks, którym dochodzimy do danego węzła.

Obie reprezentacje rozwiązują szybko problem string-matchingu, oraz mają rozmiar liniowy. Niech z będzie wzorcem o długości m, a $x$ słowem długośći n. Z reguły $m < < n$ .

Szukanie podsłów

Pokażemy jak sprawdzać, czy $z$ występuje w $x$ .

Używając drzewa sufiskowego (czas $O (m)$ )

Idziemy od korzenia w dół czytając kolejne symbole $z$ , czasami posuwamy się po wewnętrznej etykiecie pewnej krawędzi. Zbiór wystąpie"n odpowiada zbiorowi liści w poddrzewie węzła do którego doszliśmy. Jeśli po drodze utknęliśmy i nie dało siędalej schodzić po drzewie to oznacza, że $z \notin S u b w o r d s (x)$

Używając tablicy sufiksowej (czas $O (m \log n)$ )

Możemy sprawdzić czy $z$ jest prefiksem $i$ -tego sufiksu w czasie $O (m)$ . Korzystając z tego wykonujemy rodzaj binarnego szukania. W ten sposób znajdujemy pierwszy sufiks, którego prefiksem jest z. Jeśli jest taki sufiks to Parser nie mógł rozpoznać (nieznana funkcja „\inSubwords”): {\displaystyle z \inSubwords(x)} . W przeciwym wypadku z nie jest podsłowem x.

Podobnie znajdujemy ostatni sufiks. Zbiór wystąpie"nodpowiada przedziałowi w tablicy $S U F$ między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od z.

Liczenie liczby podsłów

Pokażemy jak liczyć liczbę podsłów słowa $x$ mając tablicę sufiksową lub drzewo sufiksowe. Końcowy marker $#$ nie traktujemy jako części słowa $x$ . Liczba podsłów jest równa $| S u b w o r d s (x) |$ . Jeśli wszystkie symbole słowa są różne to $| S u b w o r d s (x) | = (\binom{n}{2})$ .

Używając drzewa sufiskowego, czas $O (n)$

Sumujemy wagi krawędzi drzewa.

Używając tablicy sufiksowej, czas $O (n)$

Niech $S U M A (l c p)$ będzie sumą elementów tablicy $l c p$ . Liczbę podsłów obliczamy jako

(\binom{n + 1}{2}) - S U M A (l c p)

Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona (korzystając z drzewa sufisowego lub z tablicy sufiksowej).

Przykład

Dla przykładowego Parser nie mógł rozpoznać (nieznana funkcja „\babaabababba”): {\displaystyle x\ =\babaabababba} mamy

| S u b w o r d s (x) | = 55

. Proponujemy to wyliczyć z tablicy sufiksowej i drzewa sufiskowego dla

x

, danego na rysunku. Suma elementów tablicy

l c p

wynosi 23. Mamy liczbę podsłów jako:

78 - 23 = 55

Podobnie jak tablicę sufiksową możemy zdefiniować tablicę $R O T$ odpowiadającą posortowanemuciągowi wszystkich cyklicznych przesunięć słowa $x$ (rotacji $x$ ).

Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu liczącego tablicę $R O T$ , zakładając, że mamy liniowy algorytm liczeniatablicy sufiksowej.

Dysgresja. Ciekawą klasą słów dla których tablice $S U F, R O T$ sąszczególnie interesujące są słowa Fibonacciego $F_{n}$ . W tym szczególnym przypadku załóżmy, że pozycjenumerujemy od zera. Dla każdego $n$ tablica $R O T$ jest postępem arytmetycznym (modulo długość słowa).Natomiast tablica $S U F$ jest postępem arytmetycznym gdy $n$ jest parzyste.

Słowa Fibonacciego definiujemy następująco: $F_{0} = a, F_{1} = a b, F_{n + 1} = F_{n} \cdot F_{n - 1}$ \Na przykład: $F_{3} = a b a a b, F_{4} = a b a a b a b a, F_{5} = a b a a b a b a a b a a b .$ Oznaczmy przez $S U F_{n}$ tablicę $S U F$ dla słowa Fibonacciego $F_{n}$ , wtedy:

Parser nie mógł rozpoznać (nieznana funkcja „\SUF”): {\displaystyle SUF_4\ =\ [7\;2\;5\;0\;3\;6\;1\;4],\ \SUF_5\ =\ [10\;7\;2\;11\;8\;5\;0\;3\;12\;9\;6\;1\;4].}

Pozostawiamy jako ćwiczenie policzenie wzoru na $| S u b w o r d s (F_{n}) |$ .

Drzewa sufiksowe =>tablice sufiksowe

W celu znalezenia początkowych pozycji sufiksów w porządku leksykograficznym przechodzimy drzewo sufiksowemetodą DFS, zakładając, że dla każdego węła lista jego synów jest w kolejności leksykograficznej etykietkrawędzi prowadzących do synów. Wystarczy sprawdzać piewsze symbole tych etykiet.

Załóżmy, że w liściach mamy początki sufiksów, które do nich prowadzą.

Kolejność odwiedzania liści w naszym przejściu metodą DFS automatycznie generuje elementy tablicy sufiksowej.

Tablice sufiksowe =>drzewa sufiksowe

Pokażemy konstruktywanie następujący istotny fakt:

jeśli znamy tablicę sufiksową i tablicę $l c p$ to drzewo sufiksowe dla danego tekstu możemy łatwo skonstruować w czasie liniowym.

Przypuśćmy, że, $S U F = [i_{1}, i_{2}, \dots, i_{n}]$ , a więc:

s u f i k s_{i_{1}} < s u f i k s_{i_{2}} < s u f i k s_{i_{3}} < \dots s u f i k s_{i_{n}} .

Algorytm Drzewo-Susfiksowe

$T : =$ drzewo reprezentujące $s u f i k s_{i_{1}}$ (jedna krawędź);
for $k : = 2$ to $n$ do
wstaw nową ścieżkę o sumarycznej etykiecie $s u f i k s_{i_{k}}$ do $T$ ;

Rysunek 3: Wstawianie kolejnego sufiksu

s u f i k s_{i_{k}}

do drzewa sufiskowego, przed włożeniem wszystkie krawędzie ścieżki roboczej od

u

do korzenia są skierowane w lewo.

Opiszemy w jaki sposób wstawiamy kolejny sufiks $β$ do drzewa. Operacja ta jest zilustrowana na rysunku.Załóżmy, że w każdym węźle drzewa trzymamy długość tesktu, który ten węzeł reprezentuje (jako pełna etykieta od korzenia do węzła).

Niech $α$ będzie poprzednio wstawionym sufiksem, a $u$ ostatniopoprzednio utworzonym liściem.

Wtedy wstawienie $β$ polega na znalezieniu maksymalnego wspólnego prefiksu $γ_{1}$ tekstów $α$ , $β$ . Niech $β = γ_{1} \cdot γ_{2}$ . Znajdujemy węzeł $v$ odpowiadający ścieżce od korzenia etykietowanej $γ_{1}$ . Podstawowym trikiem jest to, że węzła $v$ szukamy nie od korzenia,ale od ostatnio utworzonego liścia $u$ . Jeśli takiego węzła $v$ nie ma (jest wewnątrz krawędzi) to gotworzymy. Następnie tworzymy nowy liść $w$ odpowiadający sufiksowi $β$ , oraz krawędź $(v, w)$ etykietowaną $γ_{2}$ .

Z tablicy $l c p$ odczytujemy długość $γ_{1}$ .

W celu obliczenia $v$ posuwamy się ścieżką od $u$ w górę drzewa, aż znajdziemy węzeł oddalony od korzenia o $| γ |$ .

Przechodząc drzewo posuwamy się po węzłach drzewa, przeskakując potencjalnie długie teksty na krawędziach.

Koszt operacji wstawienia jest proporcjonalny do sumy: jeden plus zmniejszenie głębokości nowego liścia w stosunku do starego. Suma tych zmniejszeń jest liniowa. $γ_{1}$ jest najdłuższym wspólnym prefiksem słów $s u f i k s_{i_{k - 1}}$ i $s u f i k s_{i_{k}}$ . Kluczowe znaczenie w operacji ma znajomość wartości $| γ_{1} | = l c p [k - 1]$ . Wiemy kiedy się zatrzymać idąc do góry od węzła $u$ w kierunku korzenia.

Lokalnie wykonana praca w jednej iteracji jest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego. W sumie praca jest liniowa.

Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.

Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu

b a b a a b a b a b b a #

.

Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu

b a b a a b a b a b b a #

.

Oblicanie tablicy lcp

Niech $r a n k (i)$ będzie poycją $s u f i k s_{i}$ w porządku leksykograficznym. W naszym przykładowym słowie mamy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle rank\ =\ [8,\ 2,\ 7,\ 1,\ 3,\ 9,\ 4,\ 10,\ 5,\ 12,\11,\ 6]}

Niech $l c p^{'} [k] = l c p [r a n k [k] - 1]$ .

Załóżmy, dla uproszczenia, że $l c p [0] = 0$ . Obliczamy tablice $l c p^{'}, l c p$ następująco:

Algorytm Oblicz-lcp

for $k : = 1$ to $n$ do
   oblicz $l c p^{'} [k]$ korzystając z faktu, że $l c p^{'} [k] \geq l c p^{'} [k - 1] - 1$ ;
    koszt iteracji $O (l c p^{'} [k] - l c p^{'} [k - 1] + c o n s t)$
for $k : = 1$ to $n$ do
    $l c p [r a n k [k] - 1] : = l c p^{'} [k]$

Pozostawimay jako ćwiczenie dowód tego, że

$l c p^{'} [k] \geq l c p^{'} [k - 1] - 1$ .

Jeśli $l c p^{'} [k - 1] - 1 = t$ to $l c p^{'} [k]$ obliczamy sprawdzając symbol po symbolu (od lewej do prawej) zgodność pefiksów odpowiednich słów startującod pozycji $t$ . W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potemidziemy do przodu (sprawdzając kolejne symbole). Jest to analiza typu jeden krok do tyłu i kilka do przodu. Liczba iteracji jest liniowa, więc liczba kroków do tyłu też. Ponieważ odległość do celu jest liniowa, to suma kroków też jest liniowa.

Konstrukcja tablicy SUF w czasie O(n log n): algorytm KMR

Opiszemy uproszczoną wersję algorytmu Karpa-Millera-Rosenberga (w skrócie algorytmu KMR) rozwiązywania problemów tekstowych metodą słownika bazowego. Ustalmy pewnie tekst $x$ długości $n$ .Załóżmy, że dodatkowym symbolem jest $x_{n + 1} = #$ , leksykograficznie najmniejszy symbol. Przez segement $k$ -bazowy rozumiemy segement tekstu $x [i . . i + 2^{k} - 1]$ długości $2^{k}$ lub ko"nczący się na $x_{n + 1}$ .

Teoretycznie emożemy założyć, że po symbolu $#$ mamy bardzo dużo takich symboli na prawo i każdy segment startujący w $x [1 . . n]$ ma dokładnie długość $2^{k}$ .

Słownik podsłów bazowych (w skrócie DBF(x), od ang. dictionary of basic factors) składa sięz $\log n$ tablic

$N A Z W A_{0}$ , $N A Z W A_{1}$ , $N A Z W A_{2}$ , $\dots N A Z W A_{\log n}$ .

Zakładamy, że $N A Z W A_{k} [i]$ jest pozycją słowa $x [i . . i + 2^{k} - 1]$ na posortowanej liście (bez powtórzeń) wszystkich podsłów długości $2^{k}$ słowa $x$ . Jeśli długość wystaje poza koniec $x$ to przyjmujemy że są tam (wirtualnie) same symbole $#$ . Poniżej przedstawiamy przykład słownika podsłów bazowych $D B F (a b a a b b a a)$ .

Algorytm liczenia tablic Nazwa jest bardzo prosty. Załóżmy od razu, że symbole sąponumerowane leksykograficznie. Wtedy $N A Z W A_{0}$ jest zasadniczo równa tekstowi $x$ .

Rysunek6: Słowo rozmiaru

2^{k + 1}

otrzymuje najpierw nazwę-kompozycję: kombinacją nazw (będących liczbaminaturalnymi z przedziału

[1 . . n]

) dwóch podsłów długości

2^{k}

.

Opis jednej iteracji $(t r a n s f o r m a c j a : N A Z W A_{k} = > N A Z W A_{k + 1}$ )

Dla każdego

i

tworzymy nazwę kompozycję slowa

x [i . . i + 2^{k = 1} - 1]

jako

N A Z W A_{k} [i], N A Z W A_{k} [i + 2^{k}]

Każda taka kompozycja jest parą liczb naturalnych. Sortujemy te pary za pomocą algorytmu radix-sort i w ten sposób otrzymujemy tablicę, która koduje (w porządku leksykograficznym) każdą parę liczbą naturalną (pozycją w porządku leksykograficznym). Warością $N A Z W A_{k + 1} [i]$ jest kod pary $(N A Z W A_{k} [i], N A Z W A_{k} [i + 2^{k}])$ .

Zauważmy, że tablica sufiksowa odpowiada tablicy $N A Z W A_{⌈ \log n ⌉}$ . Możemy to podsumować następująco:
1. słownik DBF(x) możemy skonstruować w czasie $O (n \log n)$ i pamięci $O (n \log n)$ (jest to również rozmiar słownika).
2. Tablicę sufiksową możemy otrzymać,stosując algorytm KMR, w czasie $O (n \log n)$ i pamięci $O (n)$ . (Potrzebujemy pamiętać jedynie ostatnie dwie tablice w każdej iteracji.)

Konstrukcja tablicy SUF w czasie O(n): algorytm KS

Opiszemy teraz algorytm Karkainena-Sandersa ( w skrócie KS) będący zoptymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR liczy znacznie więcej niż tablica sufiksowa, ponieważ liczy słownik podsłów bazowych wielkości $n \log n$ (mający liczne iine zastosowania, ale jako całość być mo¶e niepotrzbny przy liczeniu tablicy sufisksowej)

Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny. Rozważmy dwa zbiory pozycji tekstu $x$ :

M = {1 \leq i \leq n : (i - 1) modulo 3 \in {0, 1}} N = {1, 2, . ., n} - M

Przez $S U F [M]$ , oznaczmy tablicę sufiksowądla pozycji ze zbioru $M$ , podobnie zdefiniujmy $S U F [N]$ .

$S U F [M]$ daje posortowany ciąg sufiskówzaczynających się na pozycjach ze zbioru $M$ .

Redukcja liczenia $S U F [M]$ do liczenia tablicy sufiksowej rozmiaru $\frac{2}{3} n$

Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie $x$ korzystając z radix-sort. Każdemu takiemu słowu przyporządkujmy nazwę będącą jego pozycją w posortowanym leksykograficznie ciągu, oznaczmy $k o d (z)$ otrzymaną nazwę podsłowa długości 3. Zakładamy, że $x$ ko"nczy się dodatkowo dwoma symbolami $#$ ale rozważamy tylko podsłowa zaczynające się w $x$ . Dla uproszczenia załóżmy, że 3 jest dzielnkiem n.

Tworzymy nowe słowo $c o m p r e s s (x)$ w następujący sposób:

y 1 = k o d (a_{1} a_{2} a_{3}) \cdot k o d (a_{4} a_{5} a_{6}) \dots k o d (a_{n - 2} a_{n - 1} a_{n})

$y 2 = k o d (a_{2} a_{3} a_{4}) \cdot k o d (a_{5} a_{6} a_{7}) \dots k o d (a_{n - 1} a_{n} a_{n + 1})$

c o m p r e s s (x) = y 1 # y 2

Symbol # jest tutsj (jak poprzednio) leksykograficznie najmniejszy.
Jeśli mamy tablicę sufiksową dla słowa $c o m p r e s s (x)$ to można łatwo policzyć $S U F [M]$ w czasie liniowym. Pozostawiamy to jako ćwiczenie.

Algorytm KS

1. $x^{'} : = c o m p r e s s (x)$ ;

2. obliczamy tablicę sufiksową dla x' rekurencyjnie;

3. obliczamy $S U F [M]$ wczasie liniowym, znając tablicę sufiksową dla x';

4. obliczamy $S U F [N]$ w czasie liniowym (bez rekursji)znając $S U F [M]$ ;

5. scalamy posortowane ciągi $S U F [M], S U F [N]$ w tablicę sufiksową dla całego słowasłowa $x$

Krok 1 algorytmu sprowadza się do radix-sortu, podobnie jak w algorytmie KMR.Kroki 3,4 są proste i pozostawiamy cztelnikowi jako ćwiczenie.

Najważniejszy jest krok scalania. Mamy dwie posortowane listy sufiksów i trzeba je scalićw jedną posortowaną listę. Zasadniczym problemem jest implementacja operacji porównania leksykograficznego dwóch (długich) sufiksów w czasie stałym. Jeśli oba sufiksy są typu $M$ lub oba są typu $N$ to porównanie jest w czasie stałym bo mamy posortowane listy takich sufiksów.

Pokażemy na przykładzie kluczową operację porównania sufiksu typu M z sufiksem typu N w czasie stałym.

Przykład

Nierównośc $s u f i k s_{2} < s u f i k s_{12}$ jest równoważna temu że zachodzi co najmniej jeden z warunków:

1. $(a_{2} < a_{12})$
2. $(a_{2} = a_{12}, a_{3} < a_{13})$
3. $(a_{2} = a_{12}, a_{3} = a_{13}, s u f i k s_{4} < s u f i k s_{14})$

Jednakże $4, 14 \in M$ , zatem $s u f i k s_{4}$ i $s u f i k s_{14}$ , są typu M i można je porównać w czasie stałym.

Niech

T (n)

będzie czasem działania algorytmu KS. Zachodzi

T (n) = T (⌈ \frac{2}{3} \cdot n ⌉) + O (n)

Rozwiązaniem jest $T (n) = O (n)$ . Tak więc mamy liniowy algorytm liczenia tablicy sufiksowej. Daje to również liniowy algorytm konstrukcji drzewa sufiksowego.

Istnieje kilka interesujących algorytmów, które konstruują drzewo sufiksowe w czasie liniowym, bezkorzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena).

Algorytmy i struktury danych/Algorytmy tekstowe II: Różnice pomiędzy wersjami

Wersja z 06:40, 24 sie 2006

Spis treści

Szukanie podsłów

Liczenie liczby podsłów

Drzewa sufiksowe =>tablice sufiksowe

Tablice sufiksowe =>drzewa sufiksowe

Oblicanie tablicy lcp

Konstrukcja tablicy SUF w czasie O(n log n): algorytm KMR

Konstrukcja tablicy SUF w czasie O(n): algorytm KS

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-<font size="6"> Algorytmy tekstowe II </font>
+<font size="7">Zaawansowane algorytmy tekstowe II</font>
 __TOC__
-Poprzednie algorytmy dokonywały jedynie na tekstach wejściowych operacji sprawdzania symboli na równość.
-Załóżmy teraz, ż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 {\em porządek  leksykograficzny} na słowach, na przykład:
-<center><math> ab < ababab < abb < abbaa < abbaaaaaaaaaaa < abbaaaaaab</math></center>
-== Równoważność cykliczna słów ==
-Pokażemy problem, który prawdopodobie najlepiej pokazuje użyteczność porządku liniowego na alfabecie.
+W module tym  zajmiemy się strukturami danych reprezentującymi zbiór wszystkich podsłów danego słowa <math>x</math>,zapisywany jako <math>Subwords(x)</math>. Oznaczmy wszystkie wystąpienia (początkowe pozycje) słowa <math>z</math> w słowie <math>x</math>przez <math>Occ(z,x)</math>. (<math>Occ</math> jest skrótem od ang. ''Occurrences'').
-Rotacją słowa <math>u=u[1..n]</math> jest kaz'rde słowo postaci <math>u^{(k)}\ =\ u[k+1.. n]u[1.. k]</math>. (w szczególności
-<math>u^{(0)}=u^{(n)}=u)</math>. Niech <math>u,w</math> będą słowami długości <math>n</math>, mówimy, że są one cyklicznie równoważne
-gdy  <math>u^{(i)}=w^{(j)}</math> dla pewnych  <math>i,j</math>.
-Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa <math>u</math> w słowie <math>ww</math>, ale podamy
+Chcemy znaleźć taką reprezentację  zbioru <math>Subwords(x)</math> by można było łatwo odpowiedzieć na pytanie <math>z\in Subwords(x)</math>, (co jest równoważne <math>Occ(z,x)\ne \emptyset</math>) jak również rozwiązywać inne problemytekstowe. Poza tym chcemy by rozmiar tej eprezentacji był liniowy, podczas gdy rozmiar <math>Subwords(x)</math> może być kwadratowy.
-algorytm znacznie prostszy bazujący , który  będzie działal  w czasie liniowym i {\em w miejscu} (dodatkowa
+Spośród wielu dobrych reprezentacji najbardziej znanymi są tablice sufiksowe (oznaczane przez<math>SUF</math>) i drzewa sufiksowe.
-pamięć jest stała).    W algorytmie roszerzamy tablicę <math>u,w</math> na <math>uu,\ ww</math> ale robimy to jedynie dla
-uproszczenia, w rzeczywistości możemy poruszać się cyklicznie po <math>u</math> i po <math>w</math>, pozostawiamy modyfikację jako
-ćwiczenie.
-{{algorytm|Równoważność-Cykliczna|algorytm_rownowaznosc_cykliczna|
+Niech <math>x=a_{1}a_{2}\dots a_{n}</math>, oraz niech <math>x_{n+1}=\#</math> będzie specjalnym znakiem leksykograficznie mniejszym od każdego innego symbolu.
-<math>x:=uu</math>; <math>y:=ww</math>;<br>
-<math>i:=0</math>; <math>j:=0</math>;<br>
+Oznaczmy przez <math>sufiks_{i}=a_{i}a_{i+1}\dots a_{n}</math>sufiks tekstu x zaczynający się na pozycji i-tej.
-'''while''' <math>(i<n)</math> '''and''' <math>(j<n)</math> '''do'''<br>
-&nbsp;&nbsp;&nbsp;<math>k:=1</math>;<br>
+Niech <math>SUF[k]</math> będzie pozycją od której zaczyna się k-ty leksykograficznie sufiks x.
-&nbsp;&nbsp;&nbsp;'''while'''<math>x[i+k]=y[j+k]</math> '''do''' <math>k:=k+1</math>;<br>
-&nbsp;&nbsp;&nbsp;'''if''' <math>k>n</math> '''then return''' true;<br>
+Sufiks zaczynający się na pozycji <math>(n+1)</math>-szej nie jest brany pod uwagę.
-&nbsp;&nbsp;&nbsp;'''if''' <math>x[i+k]>y[i+k]</math> '''then'''<math>i:=i+k</math> '''else''' <math>j:=j+k</math>;<br>
-'''return''' false;<br>
+Ciąg sufiksów posortowany leksykograficznie wygląda następująco:
-}}
+<center><math>sufix_{SUF[1]}< sufix_{SUF[2]}<sufix_{SUF[3]}<\ldots sufix_{SUF[n]}</math></center>
+[[Grafika:Zasd_2_1.jpg]]
+Rysunek 1: Tablicą sufiksową tekstu <math>x\ =\ babaabababba\#</math> jest ciąg  <math>SUF\ =\  [4,\ 2,\ 5,\ 7,\ 9,\ 12,\ 3,\ 1,\ 6,\6,\ 8,\ 11,\ 10]</math>
+<br>
+Oznaczmy przez <math>lcp[k]</math> długść wspólnego prefisku <math>k</math>-tego i następnego sufiksu w kolejności leksykograficznej. Na rysunku wartości najdłuższego wspólnego prefiksu między kolejnymi słowami są przedstawione jako  zacienione segmenty. Odpowiadają one tablicy  <math>lcp\ =\ [1,\ 3,\ 4,\ 2,\ 1,\ 0,\ 2,\ 4,\ 3,\ 2,\ 1]</math>.
+<br>
+Tablica sufiksowa ma następująca miłą własność: Niech
+<math>min_{z}=\min\{k : z  \mbox{ jest prefiksem }  sufiks_{SUF[k]}\}</math>,
+<math>max_{z}=\max\{k : z  \mbox{ jest prefiksem }  sufiks_{SUF[k]}\}</math>.
+Wtedy <math>Occ(z,x)</math> jest przedziałem w tablicy sufiksowej od <math>min_{z}</math> do <math>max_{z}</math>.
+'''Drzewo sufiskowe''' jest drzewem, w którym każda ścieżka jest etykietowana kolejnymi symbolami pewnego sufiksu, oraz każdy sufiks <math>x</math> jest obecny w drzewie. Gdy dwie ścieżki się ''rozjeżdżają'' tworzy się wierzchołek. Mówiąc bardziej formalnie każdej krawędzi jest przypisane jako etykieta pewne podsłowo <math>x</math>. Krawędzie wychodzące z tego samego węzła różnią się pierwszymi symbolami swoich etykiet,patrz rysunek.
+Etykiety są kodowane przedziałami w tekście <math>x</math>:  para liczb  <math>[i,j]</math> reprezentuje podsłowo <math>a_ia_{i+1}\ldotsa_j</math>, zobacz prawe drzewo na rysunku. Dzięki temu reprezentacja ma rozmiar <math>O(n)</math>. Wagą krawędzi jest długość odpowiadającego jej słowa.
+[[Grafika: Zasd_2_2.jpg]] <br> Rysunek 2: Drzewo sufiksowe dla tekstu <math>x\ =\ babaabababba</math>. Na końcu jest dodany zank <math>\#</math>. Końcowe węzły zawierają informację gdzie zaczyna się sufiks, którym  dochodzimy do danego węzła.
+Obie reprezentacje rozwiązują szybko problem string-matchingu, oraz mają rozmiar liniowy.  Niech z będzie wzorcem o długości m, a <math>x</math> słowem  długośći n. Z reguły <math>m << n</math>.
+=== Szukanie podsłów===
+Pokażemy jak sprawdzać, czy <math>z</math> występuje w <math>x</math>.
+'''Używając drzewa sufiskowego''' (czas <math>O(m)</math>)
+''Idziemy'' od korzenia w dół czytając kolejne symbole <math>z</math>, czasami posuwamy się po wewnętrznej etykiecie pewnej krawędzi. Zbiór wystąpie"n odpowiada zbiorowi liści w poddrzewie węzła do którego doszliśmy. Jeśli po drodze '' utknęliśmy'' i nie dało siędalej schodzić po drzewie to oznacza, że <math>z \notin Subwords(x) </math>
+'''Używając tablicy sufiksowej''' (czas <math>O(m \log n)</math>)
+Możemy sprawdzić czy <math>z</math> jest prefiksem <math>i</math>-tego sufiksu w czasie <math>O(m)</math>. Korzystając z tego wykonujemy rodzaj  binarnego szukania. W ten sposób znajdujemy pierwszy sufiks, którego prefiksem jest z. Jeśli jest taki sufiks to <math>z \inSubwords(x)</math>. W przeciwym wypadku z nie jest podsłowem x.
+Podobnie znajdujemy ostatni sufiks. Zbiór wystąpie"nodpowiada przedziałowi w tablicy <math>SUF</math> między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od z.
+=== Liczenie liczby podsłów===
+Pokażemy jak liczyć liczbę podsłów słowa <math>x</math> mając tablicę sufiksową lub drzewo sufiksowe. Końcowy marker <math>\#</math> nie traktujemy jako części słowa <math>x</math>. Liczba podsłów  jest równa <math>|Subwords(x)|</math>. Jeśli wszystkie symbole słowa są różne to <math>|Subwords(x)|={n \choose{2}}</math>.
+'''Używając drzewa sufiskowego''', czas <math>O(n)</math>
+<br>Sumujemy wagi krawędzi drzewa.
-Zdefiniujmy:
+'''Używając tablicy sufiksowej''', czas <math>O( n)</math>
-<center>
-<math>D(u)=\{k:1\leq k\leq n</math> oraz <math>u^{(k)}>w^{(j)}</math> dla pewnego <math>j\}</math>,<br>
-<math>D(w)=\{k:1\leq k\leq n</math> oraz <math>w^{(k)}>u^{(j)}</math> dla pewnego <math>j\}</math>.
-</center>
-Skorzystamy z prostego faktu:
+Niech <math>SUMA(lcp)</math> będzie sumą elementów tablicy <math>lcp</math>. Liczbę podsłów obliczamy jako
-Jeśli <math>D(u)=[1.. n]</math> lub <math>D(w)=[1.. n]</math>, to <math>u,w</math> nie są równoważne.
-Uzasadnienie pozostawiamy jako ćwiczenie. Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:
-<center>
-<math>D(w)\supseteq [1.. i]</math>\ oraz \ <math>D(u)\supseteq [1.. j]</math>.</center>
-Liczba porównań jest oczywiście liniowa. Pozostawiamy jako ćwiczenie policzenie dokładnego wzoru na maksymalną liczbę porównań symboli dla tekstów długości <math>n</math>.
+<center><math>{n+1\choose{2}}-SUMA(lcp)</math></center>
-== String-matching w pamięci stałej dla specjalnych wzorów ==
+Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona (korzystając z drzewa sufisowego lub z tablicy sufiksowej).
-Oznaczmy przez <math>MaxSuf(w)</math> maksymalny leksykograficznie sufiks słowa <math>w</math>. Słowo <math>x</math> nazwiemy specjalnym gdy <math>MaxSuf(x)=x</math>.
 {{przyklad|||
-'bajtocja' nie jest słowem specjalnym, ale rotacja tego słowa 'tocjabaj' jest.}}
+Dla przykładowego <math>x\ =\babaabababba</math> mamy <math>|Subwords(x)|=55</math>. Proponujemy to wyliczyć z tablicy sufiksowej i drzewa sufiskowego dla<math>x</math>, danego na rysunku. Suma elementów tablicy  <math>lcp</math> wynosi 23. Mamy liczbę podsłów jako:  <math>78-23\ =\ 55</math>}}
+Podobnie jak tablicę sufiksową możemy zdefiniować tablicę <math>ROT</math> odpowiadającą posortowanemuciągowi wszystkich cyklicznych przesunięć słowa <math>x</math> (rotacji <math>x</math>).
+Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu liczącego tablicę <math>ROT</math>, zakładając, że mamy liniowy algorytm liczeniatablicy sufiksowej.
+'''Dysgresja.''' Ciekawą klasą słów dla których tablice <math>SUF,\ ROT</math> sąszczególnie interesujące są słowa Fibonacciego <math>F_n</math>. W tym szczególnym przypadku załóżmy, że pozycjenumerujemy od zera. Dla każdego <math>n</math> tablica <math>ROT</math> jest postępem arytmetycznym (modulo długość słowa).Natomiast tablica <math>SUF</math> jest postępem arytmetycznym gdy  <math>n</math> jest parzyste.
+Słowa Fibonacciego definiujemy następująco:<math>F_0=a,\ F_1=ab,\ F_{n+1}\ =\ F_n\cdot F_{n-1}</math>\Na przykład: <math>F_3\ =\ abaab,\ F_4\ =\ abaababa,\ F_5\ =\ abaababaabaab.</math> Oznaczmy przez <math>SUF_n</math> tablicę <math>SUF</math> dla słowa Fibonacciego <math>F_n</math>, wtedy:
+<center><math>SUF_4\ =\ [7\;2\;5\;0\;3\;6\;1\;4],\ \SUF_5\ =\ [10\;7\;2\;11\;8\;5\;0\;3\;12\;9\;6\;1\;4].</math></center>
+Pozostawiamy jako ćwiczenie policzenie wzoru na <math>|Subwords(F_n)|</math>.
+== Drzewa sufiksowe =>tablice sufiksowe ==
+W celu znalezenia początkowych pozycji sufiksów w porządku leksykograficznym przechodzimy drzewo sufiksowemetodą DFS, zakładając, że dla każdego węła lista jego synów jest w kolejności leksykograficznej etykietkrawędzi prowadzących do synów. Wystarczy sprawdzać piewsze symbole tych etykiet.
+Załóżmy, że w liściach mamy początki sufiksów, które do nich prowadzą.
+Kolejność odwiedzania liści w naszym przejściu metodą DFS automatycznie generuje elementy tablicy sufiksowej.
-Dlaczego słowa o tej własności  są interesujące ? Większość szybkich algorytmów szukania podsłów korzysta z okresów <math>p</math> prefiksów słowa. Liczenie tych okresów w ogólnym przypadku jest ''wąskim gardłem'' w projekcie algorytmu. Natomiast dla słow specjalnych  liczenie okresów jest trywialne.
+== Tablice sufiksowe =>drzewa sufiksowe ==
+Pokażemy konstruktywanie następujący istotny fakt:
-Jeśli  <math>x</math> jest specjalny to okres każdego prefiksu słowa <math>x</math> można policzyć następującym naiwnym
+jeśli znamy tablicę sufiksową i tablicę<math>lcp</math> to drzewo sufiksowe dla danego tekstu możemy ''łatwo'' skonstruować w czasie liniowym.
-algorytmem;
-{{ algorytm| Funkcja Naiwne-Liczenie-Okresu (j)|funkcja_naiwne_liczenie_okresu|
+Przypuśćmy, że,
-<math>period:=1</math>;<br>
+<math>SUF\ =\ [i_1,i_2,\ldots,i_n]</math>, a więc:
-'''for''' <math>i:=2</math> to <math>j</math> '''do'''<br>
+<center><math> sufiks_{i_1}< sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.</math></center>
-&nbsp;&nbsp;&nbsp;'''if''' <math>x[i] \ne x[i - period]</math> '''then''' <math>period := i</math>;<br>
-'''return''' <math>period</math>;<br>
+{{algorytm|Drzewo-Susfiksowe|algorytm_drzewo_susfiksowe|
+<math>T :=</math> drzewo reprezentujące <math>sufiks_{i_1}</math> (jedna krawędź);<br>
+'''for''' <math>k:=2</math> '''to''' <math>n</math> '''do'''<br>
+&nbsp;&nbsp;&nbsp;wstaw nową ścieżkę o sumarycznej etykiecie <math>sufiks_{i_k}</math> do <math>T</math>;
 }}
-{{przyklad|||
-Funkcja ''Naiwne-Liczenie-Okresu'' daje zły wynik dla tekstów które nie są specjalne, na przykład  załóżmy że <center>
-<math>x= (aba)^6a = abaabaabaabaabaabaa</math>.} </center> Wtedy kolejne wartości okresów dla pozycji <math>j=1,2,..</math>
-są:
-<center>
-<table>
-<tr>
-<td>a</td>
-<td>b</td>
-<td>a</td>
-<td>a</td>
-<td>b</td>
-<td>a</td>
-<td>a</td>
-<td>b</td>
-<td>a</td>
-<td>a</td>
-<td>b</td>
-<td>a</td>
-<td>a</td>
-<td>b</td>
-<td>a</td>
-<td>a</td>
-<td>b</td>
-<td>a</td>
-<td>a </td>
-</tr>
-<tr>
-<td>
-</td>
-<td>2</td>
-<td>2</td>
-<td>4</td>
-<td>5</td>
-<td>5</td>
-<td>7</td>
-<td>8</td>
-<td>8</td>
-<td>10</td>
-<td>11</td>
-<td>11</td>
-<td>13</td>
-<td>14</td>
-<td>14</td>
-<td>16</td>
-<td>17</td>
-<td>17</td>
-<td>19
-</td>
-</tr>
-</table>
-</center>
-}}
-Zatem ''Naiwne-Liczenie-Okresu''<math>(19)\ =\ 19</math>, dla  <math>x\ = \ (aba)^6a</math>, wynik całkowicie niepoprawny. Poprawność algorytmu jest wyjaśniona na rysunku. Korzystamy z prostej własności, że prefiks specjalnego słowa jest też specjalny.
+<center> [[Grafika:Zasd_2_3.jpg]]<br> Rysunek 3: Wstawianie kolejnego sufiksu <math>sufiks_{i_k}</math> do drzewa sufiskowego, przed włożeniem wszystkie krawędzie ''ścieżki roboczej'' od <math>u</math> do korzenia   są skierowane  w lewo.  </center>
+Opiszemy w jaki sposób wstawiamy kolejny sufiks <math>\beta</math> do drzewa. Operacja ta jest zilustrowana na rysunku.Załóżmy, że w każdym węźle drzewa trzymamy długość tesktu, który ten węzeł reprezentuje (jako pełna etykieta od korzenia do węzła).
+Niech <math>\alpha</math> będzie poprzednio wstawionym sufiksem, a <math>u</math> ostatniopoprzednio utworzonym liściem.
+Wtedy wstawienie <math>\beta</math> polega na znalezieniu  maksymalnego wspólnego prefiksu <math>\gamma_1</math>tekstów <math>\alpha</math>, <math>\beta</math>. Niech <math>\beta=\gamma_1\cdot \gamma_2</math>. Znajdujemy węzeł <math>v</math> odpowiadający ścieżce od korzenia etykietowanej <math>\gamma_1</math>. Podstawowym ''trikiem'' jest to, że węzła <math>v</math> szukamy nie od korzenia,ale od ostatnio utworzonego liścia <math>u</math>. Jeśli takiego węzła <math>v</math> nie ma (jest wewnątrz krawędzi) to gotworzymy. Następnie tworzymy nowy liść <math>w</math> odpowiadający sufiksowi <math>\beta</math>, oraz krawędź <math>(v,w)</math>etykietowaną <math>\gamma_2</math>.
+Z tablicy <math>lcp</math> odczytujemy długość <math>\gamma_1</math>.
+W celu obliczenia <math>v</math> posuwamy się ścieżką od <math>u</math> w górę drzewa, aż znajdziemy węzeł oddalony od korzenia o <math>|\gamma|</math>.
+ Przechodząc drzewo posuwamy się po węzłach drzewa, przeskakując potencjalnie długie teksty na krawędziach.
+Koszt operacji wstawienia jest proporcjonalny do sumy: jeden plus zmniejszenie głębokości nowego liścia w stosunku do starego. Suma tych zmniejszeń jest liniowa. <math>\gamma_1</math> jest najdłuższym wspólnym prefiksem słów <math>sufiks_{i_{k-1}}</math> i<math>sufiks_{i_k}</math>. Kluczowe znaczenie w operacji ma znajomość  wartości <math>|\gamma_1|= lcp[k-1]</math>. Wiemy kiedy się zatrzymać idąc do góry od węzła <math>u</math> w kierunku korzenia.
+Lokalnie wykonana praca w jednej iteracji jest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego. W sumie praca jest liniowa.
+Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.
+<center> [[Grafika:Zasd_2_4.jpg]] <br> Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu
+<math>babaabababba\#</math>. </center>
+<center> [[Grafika:Zasd_2_5.jpg]] <br> Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu <math>babaabababba\#</math>. </center>
+== Oblicanie tablicy ''lcp'' ==
+Niech <math>rank(i)</math> będzie poycją <math>sufiks_i</math> w porządku leksykograficznym. W naszym przykładowym słowie mamy:
+<center><math>rank\ =\ [8,\ 2,\ 7,\ 1,\ 3,\ 9,\ 4,\ 10,\ 5,\ 12,\11,\ 6]</math></center>
-<center>[[Grafika:Naiwneliczenieokresu.jpg]]<br>
+Niech  <math>lcp'[k]\ =\ lcp[rank[k]-1]</math>.
-Rysunek 1: Załóżmy, że w algorytmie  ''Naiwne-Liczenie-Okresu'' <math>x[i-period(i-1)] \ne x[i]</math>.  Niech
-<math>a=x[i]</math>, <math>b=x[i-period]</math>. Ponieważ <math>uz</math> jest prefiksem  słowa specjalnego <math>x</math> zatem  <math>a <b</math>. Gdyby
-<math>period(i)<i</math> to wtedy, ze względu na dwie okresowości,
-<math>zb</math> jest właściwym podsłowem słowa  <math>x[1.. i-1]</math> oraz <math>zb>x</math>.
-Zaprzecza to założeniu, że <math>x</math> jest specjalne. Zatem <math>period(i)=i</math>.
-</center>
-Opiszemy teraz program szukania wzorca <math>x</math>  w slowie <math>y</math>i, zakładając że x jest sepcjalne.
+Załóżmy, dla uproszczenia, że  <math>lcp[0]=0</math>. Obliczamy tablice<math>lcp',\ lcp</math> następująco:
-Program wczytuje dwa teksty, pierwszy z nich jest specjalne:  <math>x</math> pamiętamy w tablicy <math>x[0..m-1]</math>, <math>y</math> w
-tablicy <math>y[0..n-1]</math>.
-Program wypisuje wszystkie wystapienia <math>x</math> w <math>y</math>, tzn. wszystkie takie pozycje
-<math>i</math>, ze <math>y[i\ldots i+m-1]\ =\ x</math>. Zapisujemy program w języku C++.
-{{algorytm|Specjalny-String-Matching|algorytm_specjalny_string_matching|
-#include <iostream.h><br>
-#include string.h<br>
-int i=0,j=0,p=1;<br>
-void przesun();<br>
-main() {<br>
-char[] x,y; cin>>x>>y; m=strlen(x); n=strlen(y);<br>
-while (i <= n-m-1)<br>
-&nbsp;&nbsp;&nbsp;{ if (j==m) {cout<<i<<endl;  przesun();};<br>
-&nbsp;&nbsp;&nbsp;&nbsp;else if (x[j)==y[i+j] {j=j+1; if (j==1)||(x[j-1]!=x[j-1-p]) p=j;};<br>
-&nbsp;&nbsp;&nbsp;&nbsp;else   przesun();  }}<br>
-void przesun()
+{{algorytm|Oblicz-lcp|algorytm_oblicz_lcp|
-{ if (j-1<2p) {i=i+p; j=0;} else {j=j-p; i=i+p;}}
+'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
+&nbsp;&nbsp;&nbsp;oblicz <math>lcp'[k]</math> korzystając z faktu, że <math>lcp'[k]\ge lcp'[k-1]-1</math>; <br>
+&nbsp;&nbsp;&nbsp;&nbsp;koszt iteracji <math>O(lcp'[k]-lcp'[k-1]+const)</math><br>
+'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
+&nbsp;&nbsp;&nbsp;<math>lcp[rank[k]-1] := lcp'[k]</math>
 }}
-Program jest wstępem do programu szukajacego dowolne posłowo, niekoniecznie o wlasnosci bycia
+Pozostawimay jako ćwiczenie dowód tego, że
-specjalnym. Postawowym niezmiennikiem  w programie przed kazdym wykonaniem i po kazdym zakonczeniu pętli ''while' jest:
-'''(A)\ ''' <math>x[0 \ldots j-1]\ =\ y[i \ldots i+j-1]</math>, .
+<math>lcp'[k]\ge lcp'[k-1]-1</math>.
-'''(B)\ ''' Program wypisal wszsytkie wczesniejsze wystapienia <math>i' < i</math>,
-'''(C)\ ''' <math>p</math> jest okresem slowa <math>x[0 \ldots j-1]</math>
+Jeśli <math>lcp'[k-1]-1=t</math> to <math>lcp'[k]</math>obliczamy sprawdzając symbol po symbolu (od lewej do prawej) zgodność pefiksów odpowiednich słów startującod pozycji <math>t</math>. W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potemidziemy  ''do przodu'' (sprawdzając kolejne symbole). Jest to analiza typu ''jeden krok do tyłu i kilka do przodu''. Liczba iteracji jest liniowa, więc liczba kroków do tyłu też.  Ponieważ odległość ''do celu'' jest liniowa, to suma kroków też jest liniowa.
+==Konstrukcja tablicy ''SUF'' w czasie ''O(n log n)'': algorytm KMR ==
-Algorytm  działa w czasie liniowym, można to udowodnić obserwując zmiany wartości <math>2i+j</math>, zauważmy, że wartość ta nie zmniejsza się, a w wypadku pozytywnego testu  <math> x[j)==y[i+j]</math>  zwiększa się co najmniej o 1. Jednocześnie <math>2i+j\le 3n</math>.
+Opiszemy uproszczoną wersję algorytmu  Karpa-Millera-Rosenberga (w skrócie algorytmu ''KMR'') rozwiązywania problemów tekstowych metodą ''słownika bazowego''. Ustalmy pewnie tekst <math>x</math> długości <math>n</math>.Załóżmy, że dodatkowym symbolem jest <math>x_{n+1}=\#</math>, leksykograficznie najmniejszy symbol. Przez segement <math>k</math>-bazowy  rozumiemy segement tekstu <math>x[i..i+2^k-1]</math>  długości <math>2^k</math> lub ko"nczący się na <math>x_{n+1}</math>.
-== String-matching w pamięci stałej dla dowolnych wzorców ==
+Teoretycznie emożemy założyć, że po symbolu <math>\#</math> mamy bardzo dużo takich symboli na prawo i każdy segment startujący w<math>x[1..n]</math> ma ''dokładnie '' długość <math>2^k</math>.
-Algorytym Specjalny-String-Matching  można  łatwo
-zmodyfikować tak, aby znajdował on wystąpinia dowolnego słowa (niekoniecznie specjalnego) w czasie liniowym i
-stałej pamięci.
-Niech <math>x = uv</math>, gdzie <math>v</math> jest leksykograficzne maksymalnym sufiksem <math>x</math>. Oznaczmy <math>r=|u|</math>. Technicznie
-informacja o rozkładzie <math>uv</math> sprowadza się do pamiętania <math>r</math>.
+'''Słownik podsłów bazowych''' (w skrócie DBF(x), od ang. ''dictionary of basic factors'')  składa sięz <math>\log n</math> tablic  <br>
-'''Własność rozkładu. '''Niech <math>x=uv</math> będzie rozkładem jak wyżej opisany. Wtedy
+<math>NAZWA_0</math>, <math>NAZWA_1</math>, <math>NAZWA_2</math>,<math> \ldots NAZWA_{\log n}</math>.
-Słowo <math>v</math> występuje tylko raz w słowie <math>uv</math>.
-Jeśli <math>i'<i</math> są początkami wystąpień <math>v</math>, oraz <math>i-i'<r</math> to
-na pozycji <math>i-1</math> nie kończy się wystąpienie <math>u</math>.
+Zakładamy, że <math>NAZWA_k[i]</math> jest pozycją słowa <math>x[i..i+2^k-1]</math> na posortowanej liście (bez powtórzeń) wszystkich podsłów długości <math>2^k</math> słowa <math>x</math>. Jeśli długość ''wystaje'' poza koniec <math>x</math> to przyjmujemy że są tam (wirtualnie) same symbole <math>\#</math>. Poniżej przedstawiamy przykład słownika podsłów bazowych  <math>DBF(abaabbaa)</math>.
-Z powyższego faktu wynika stosunkowo prosty algorytm szukania <math>x</math> w czasie loiniowym i pamięci
+<center> [[Grafika:Zasd_2_4a.jpg]]</center>
-stałej. Algorytm ten jest modyfikacja agorytmu Specjalny-String-Matching , w ktorym rolę <math>x</math> pełni <math>v</math>.
-{{algorytm |String-matching w pamięci stałej|algorytm_string_matching_pam_st|
+Algorytm liczenia tablic ''Nazwa'' jest bardzo prosty. Załóżmy od razu, że symbole sąponumerowane leksykograficznie. Wtedy <math>NAZWA_0</math> jest zasadniczo równa tekstowi <math>x</math>.
-Niech <math>v</math> będzie  leksykograficznie maksymalnym sufiksem <math>x</math>;
-Liczymy  algorytmem Specjalny-String-Matching  kolejne wystąpienia <math>v</math> w <math>y</math>;
+<center> [[Grafika:Zasd_2_6.jpg]] <br> Rysunek6: Słowo rozmiaru <math>2^{k+1}</math> otrzymuje najpierw nazwę-kompozycję:  kombinacją nazw (będących liczbaminaturalnymi z przedziału <math>[1..n]</math>) dwóch podsłów długości <math>2^k</math> . </center>
-Dla każdego wystąpienia <math>i</math> niech <math>i'</math> będzie wystąpieniem poprzednim;
+'''Opis jednej iteracji <math>  (transformacja: NAZWA_k\ =>\ NAZWA_{k+1}</math>)'''
-jeśli <math>i-i' \ge |v|</math> to sprawdź czy <math>u</math> występuje na lewo od pozycji <math>i</math>;
-(sprawdzanie to wykonujemy w sposób naiwny)
+Dla każdego <math>i</math> tworzymy nazwę kompozycję slowa <math>x[i..i+2^{k=1}-1]</math> jako <center><math>NAZWA_k[i], NAZWA_k[i+2^k]</math></center>
-jeśli występuje to wypisz kolejne wystąpienie całego wzorca <math>x</math>.
+Każda taka kompozycja jest parą liczb naturalnych. Sortujemy te pary za pomocą algorytmu ''radix-sort'' i  w ten sposób otrzymujemy tablicę, która koduje (w porządku leksykograficznym) każdą parę liczbą naturalną (pozycją w porządku leksykograficznym). Warością <math>NAZWA_{k+1}[i]</math> jest kod pary <math>(NAZWA_k[i],NAZWA_k[i+2^k])</math>.
-}}
-Pozostawiamy bardziej precyzyjny zapis algorytmu jako ćwiczenie.
-W ten sposób pokazaliśmy, że problem szukania słowa <math>x</math> w słowie <math>y</math> można rozwiązać
+Zauważmy, że tablica sufiksowa odpowiada tablicy <math>NAZWA_{\lceil \log n \rceil}</math>. Możemy to podsumować następująco:
-w czasie liniowym i pamięci (dodatkowej) stałej, jeśli znamy początkową pozycję <math>r</math>
+<br>
-leksykograficznie maksymalnego sufiksu <math>v</math> słowa <math>x</math>.
+. słownik ''DBF(x)'' możemy skonstruować w czasie <math> O(n \log n) </math>i pamięci <math>O(n \log n)</math> (jest to również rozmiar słownika). <br>
+. Tablicę sufiksową możemy otrzymać,stosując algorytm KMR, w czasie <math>O(n \log n)</math> i pamięci <math>O(n)</math>. (Potrzebujemy pamiętać jedynie ostatnie dwie tablice w każdej iteracji.)
-== Liczenie maksymalnego sufiksu w pamięci stałej ==
+== Konstrukcja tablicy ''SUF'' w czasie ''O(n)'': algorytm KS ==
-W algorytmie szukanie wzorca w pamięci stałej potrzebna jest pozycja <math>r</math>  od której zaczyna się maksymalny
+Opiszemy teraz algorytm Karkainena-Sandersa ( w skrócie ''KS'') będący zoptymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR liczy znacznie więcej niż tablica sufiksowa, ponieważ liczy słownik podsłów bazowych wielkości <math>n \log n</math> (mający liczne iine zastosowania, ale jako całość być mo¶e niepotrzbny przy
-sufiks. Pokażemy teraz jak ją znajdować w czasie liniowym i w pamięci stałej. Kluczem do tego jest liczenie
+liczeniu tablicy sufisksowej)
-czegoś więcej, dla każdego prefiksu liczymy maksymalny sufiks jak również dodatkowo jego okres. To własnie
-liczenie okresu daje efektywność, chociaż na końcu nam ten okres jest  niepotrzebny.
-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)|fun_najdl_spec_pref|
+Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny. Rozważmy dwa zbiory pozycji tekstu <math>x</math>:
-<math>period := 1</math>;<br>
-'''for''' <math>i:=2</math> to <math>|x|</math> '''do''' <br>
-&nbsp;&nbsp;&nbsp;'''if''' <math>x[i] < x[i - period]</math> \textbf{then} <math>period := i</math><br>
-&nbsp;&nbsp;&nbsp;'''else if''' <math>x[i] > x[i - period]</math> ''then'''<br>
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''return''' <math>(i-1, period)</math>;<br>
-'''return''' <math>(|x|, period)</math>;
-}}
-Skorzystamy z algorytmu ''Najdłuższy-Specjalny-Prefiks''. Funkcja ''Maksymalny-Sufiks'' liczy początkową pozycję i okres maksymalnego sufiksu.
+<center><math> M\ =\ \{1\le i \le n:\ (i-1)\ \textrm{modulo}\ 3 \in \{0,1\}\}\ \ N\ =\ \{1,2,..,n\}-M</math></center>
-{{algorytm|funkcja Maksymalny-Sufiks(x)|fun_max_suf|
+Przez <math>SUF[M]</math>, oznaczmy tablicę sufiksowądla pozycji ze zbioru <math>M</math>, podobnie zdefiniujmy <math>SUF[N]</math>.
-<math>j := 1</math>;<br>
-'''repeat'''<br>
-&nbsp;&nbsp;&nbsp;<math>(i,period) :=</math> ''Najdłuższy-Specjalny-Prefiks''<math>(x[j.. n])</math>;<br>
-&nbsp;&nbsp;&nbsp;'''if''' <math>i=n</math> '''then return''' <math>(j, period)</math><br>
-&nbsp;&nbsp;&nbsp;'''else''' <math>j := j+i - (i \mod period)</math>;<br>
-'''forever''' <br>
-}}
-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  <math>\mod</math> może być usunięta i zastąpiona przez operacje dodawania i odejmowania bez zmiany asymptotycznej złożoności.
+<math>SUF[M]</math> daje posortowany ciąg sufiskówzaczynających się na pozycjach ze zbioru <math>M</math>.
-Algorytm Maksymalny-Sufiks wykonuje co najwyżej <math>2.|x|</math> porównań symboli. Uzasadnienie pozostawiamy jako ćwiczenie.
-{{algorytm| funkcja} Maksymalny-Sufiks(x)|fun_max_suf2|
-<math>s := 1</math>;  <math>i := 2</math>;  <math>p := 1</math>;<br>
-'''while''' (<math>i \le n</math>) '''do'''<br>
-&nbsp;&nbsp;&nbsp;<math>r := (i-s) \mod p</math>;<br>
-&nbsp;&nbsp;&nbsp;'''if''' (<math>x[i] = x[s+r])</math> '''then''' <math>i := i+1</math><br>
-&nbsp;&nbsp;&nbsp;'''else if''' (<math>x[i] < x[s+r])</math> '''then begin'''
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>i := i+1</math>; <math>p := i-s</math>;
-&nbsp;&nbsp;&nbsp;'''else'''
-&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>s := i-r</math>; <math>i := s+1</math>; <math>p := 1</math>;<br>
-'''return''' <math>s</math>;<br>
-}}
-== Kodowanie prefiksowe: drzewa i kody Huffmana ==
-Zbiór słów jest prefiksowy gdy żadne słowo nie jest prefiksem drugiego. Taki zbiór słów odpowiada drzewu,
+''' Redukcja liczenia <math>SUF[M]</math> do liczenia tablicy sufiksowej rozmiaru <math>\frac{2}{3}n</math>'''
-którego ścieżki etykietowane są symbolami, w przypadku binarnym możemy przyjąć, że krawędź w lewo jest
-etykietowana zerem, a w prawo jedynką.
-Przez kodowanie rozumiemy funkcję <math>h</math> która każdemu symbolowi <math>s</math> przyporządkowuje niepusty ciąg binarny
-<math>h(s)</math>, całe słowo <math>x</math> zostanie zakodowane na słowo <math>h(x)</math> (każda litera jest zakodowana niezależnie i kody
-są ''skonkatenowane''. Kod jest prefiksowy gdy zbiór kodów symboli jest prefiksowy. Rozważamy
-następujący problem.
-===Optymalne kodowanie prefiksowe===
+Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie <math>x</math> korzystając z radix-sort. Każdemu takiemu słowu przyporządkujmy nazwę będącą jego pozycją w posortowanym leksykograficznie ciągu, oznaczmy <math>kod(z)</math> otrzymaną nazwę  podsłowa długości 3. Zakładamy, że <math>x</math> ko"nczy się dodatkowo dwoma symbolami <math>\#</math> ale rozważamy tylko podsłowa zaczynające się w <math>x</math>. Dla uproszczenia załóżmy, że 3 jest dzielnkiem n.
-Dla danego słowa <math>x</math> znaleźć binarne kodowanie prefiksowe takie,
-że <math>h(x)</math> ma minimalną długość.
+Tworzymy nowe słowo <math>compress(x)</math> w następujący sposób:
-{{przyklad|||
+<center><math> y1\ =\ \ kod(a_1a_2a_3)\cdot kod(a_4a_5a_6) \ldots kod(a_{n-2}a_{n-1}a_n)</math>
-Niech  <math>x=abracadabra</math>. Liczby wystąpień symboli w słowie <math>x</math> są:
-<center><math>w_{a}=5, w_{b}=2, w_{c}=1, w_{d}=1, w_{r}=2.</math></center>
-}}
+<math> y2\ =\ kod(a_2a_3a_4)\cdot kod(a_5a_6a_7) \ldots kod(a_{n-1}a_{n}a_{n+1})</math>
-Optymalnym  kodowaniem jest <math>h(a)=0,h(b)=10,h(c)=1100,h(d)=1101,h(r)=111.</math>  <math>abracadabra</math> zostaje zakodowane na  <math>01011101100011010101110</math>, ciąg binarny długości <math>23</math>.  Optymalne drzewo binarne odpowiadające optymalnemu kodowi prefiksowemu jest pokazane na rysunku.
+<math>compress(x)\ =\ y1\ \#\ y2</math></center>
-<center>[[Grafika:Huffnal.jpg]]<br>
-Rysunek 2:Drzewo Huffmana kodujące optymalnie symbole  <math>a,b,c,d,r</math> z wagami odpowiednio
-<math>S\ =\ (5, 2, 1, 1, 2)</math>. Liczby w wewnętrznych węzłach są sumą wag w liściach odpowiadającego poddrzewa.
-Koszt całkowity kodowania jest ważoną sumą długości ścieżek do liści, jest równeż sumą wartości w
-węzłach wewnętrznych:  <math> 2+4+6+11\ =\ 23.</math>
-</center>
+Symbol # jest tutsj (jak poprzednio) leksykograficznie najmniejszy.
+<br>
+Jeśli mamy tablicę sufiksową dla słowa <math>compress(x)</math> to można  łatwo policzyć <math>SUF[M]</math> w czasie liniowym.
+Pozostawiamy to jako ćwiczenie.
-Długość tekstu <math>h(x)</math> jest równa ważonej sumie długości ścieżek, ważoenj w tym sensie, że
+{{algorytm|KS|algorytm_KS|
-długość ścieżki do danego liścia jest przemnożona przez wagę tego liścia. W przykładzie jest to suma:
+. <math>x' := compress(x)</math>;
-<math>5 *1+2*2+1*4+1*4+2*3\ =\ 23</math>.
-Niech <math>n</math> będzie liczbą różnych symboli w <math>x</math>, <math>w[i]</math> będzie liczbą wystąpień <math>i</math>-tego symbolu. Problem możemy rozwiązać stosując algorytm dla problemu ''Optymalne Sklejanie Par'' dla ciągu <math>w[1],w[2],\ldots
+. obliczamy tablicę sufiksową dla x' rekurencyjnie;
-w[n])</math>. Musimy algorytm zmodyfikować tak, aby nie tylko sklejał pary ale również tworzył lokalnie drzewo.
-Inaczej mówiąc algorytm w momencie sklejania elementów <math>a</math>, <math>b</math> w element <math>c</math> tworzy równieź dowiązania,
-<math>a</math> staje się lewym synem <math>c</math>, natomiast  <math>b</math> staje się prawym synem.
-{{algorytm| Huffmana (nieformalny opis)|algorytm_huffman_nieformalny|
+. obliczamy <math>SUF[M]</math> wczasie liniowym, znając tablicę sufiksową dla x';
-Konfiguracje pośrednie algorytmu to zbiory drzew,
-początkowo każdy pojedyńczy element <math>i</math> z wagą <math>w[i]</math> jest pojedyńczym drzewem.
+. obliczamy <math>SUF[N]</math> w czasie liniowym (bez rekursji)znając <math>SUF[M]</math>;
-Korzeń każdego drzewa reprezentuje sklejenie jego wszystkich liści.
+. scalamy posortowane ciągi  <math>SUF[M],\ SUF[N]</math> w tablicę sufiksową dla całego słowasłowa <math>x</math>
-Za każdym razem sklejamy dwa korzenie drzew o minimalnej wadze.
 }}
-Drzewo które algorytm generuje nazywamy drzewem Huffmana.
+Krok 1 algorytmu sprowadza się do ''radix-sort''u, podobnie jak w algorytmie KMR.Kroki 3,4 są proste i pozostawiamy cztelnikowi jako ćwiczenie.
-Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i
+Najważniejszy jest krok scalania. Mamy dwie posortowane listy sufiksów i trzeba je scalićw jedną posortowaną listę. Zasadniczym problemem jest implementacja operacji porównania leksykograficznego dwóch (długich) sufiksów w czasie stałym. Jeśli  oba sufiksy są typu <math>M</math> lub oba są  typu <math>N</math> to porównanie jest w czasie stałym bo mamy posortowane listy takich sufiksów.
-drzew Huffmana.
-Z analizy algorytmu ''Optymalne Sklejanie Par'' wynika, że problem optymalnych binarnych kodów prefiksowych można rozwiązać w czasie <math>O(n \log n)</math>, a jeśli wagi <math>w[i]</math> są posortowane to w czasie liniowym.
+Pokażemy na przykładzie kluczową operację porównania  sufiksu typu M z sufiksem typu N w czasie stałym.
-===Kodowanie Huffmana słowami <math>k</math>-arnymi.===
+{{przyklad|||
+Nierównośc <math>sufiks_2< sufiks_{12}</math> jest równoważna temu że zachodzi co najmniej jeden z warunków:
-Pozostawiamy jako ćwiczenie podobny problem, ale gdy kodujemy w alfabecie <math>k</math>-arnym, mamy teraz symbole <math>0,1,\ldots, k-1</math>. W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy.
+. <math> (a_2 < a_{12}) </math>  <br>
+. <math> \ (a_2=a_{12}, a_3 < a_{13}) </math> <br>
+. <math> (a_2=a_{12}, a_3=a_{13}, sufiks_4<sufiks_{14})  </math>
-===Kodowanie prefiskowe z symbolami kodowymi nierównej długości===
-Problem robi się skomplikowany,gdy długość symbolu 0 jest 1 a długość symbolu 1 jest <math>c</math>, gdzie <math>c</math> jest pewną stała (jest to po
-angielsku problem tzw. lopsided trees). Inaczej mówiąc szukamy takiego optymalnego drzewa, że ważona suma
-ścieżek jest minimalna, ale długość krawędzi na lewo wynosi 1 a długość krawędzi na prawo wynosi <math>c</math>.
-Pozostawiamy jako ćwiczenie znalezienie efektywnego algorytmu dla małych <math>c</math> (<math>c=2</math> lub <math>c=3</math>). Dla dowolnego
-<math>c</math> (będącego częścia wejścia) i dowolnych wag jest to zbyt trudne, nie znamy algorytmu wielomianowego. Dla
-ustalonego c istnieje algorytm wielomianowy którego stopień zależy od c. Natomiast pozostawiamy jako
-ćwiczenie przypadek gdy <math>c</math> jest dowolne ale wszystkie wagi <math>w[i]</math> są równe.
-=== Kodowanie prefiskowe z kodami o ograniczonej długości===
+Jednakże <math>4,14\in M</math>, zatem <math>sufiks_4</math> i <math>sufiks_{14}</math>, są typu M i można je porównać w czasie stałym.
-Innym ciekawym problemem jest
-też skonstruowanie optymalnego kodu prefiksowego, w którym wszystkie słowa kodowe są ograniczone przez pewną
-zadaną liczbę <math>L</math>. Inaczej mówiąc ograniczamy z góry wysokość drzewa Huffmana. Istnieją algorytmy
-wielomianowe dla tego problemu, stopień wielomianu niezależny od <math>L</math>.
+Niech <math>T(n)</math> będzie czasem działania algorytmu KS. Zachodzi <center><math>T(n) \ =\ T(\lceil \frac{2}{3}\cdot n  \rceil) + O(n)</math></center>
+Rozwiązaniem jest <math>T(n)=O(n)</math>. Tak więc mamy liniowy algorytm liczenia tablicy sufiksowej. Daje to również liniowy algorytm konstrukcji drzewa sufiksowego.
+}}
+Istnieje kilka interesujących algorytmów, które konstruują drzewo sufiksowe w czasie liniowym, bezkorzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena).