\documentclass[a4paper,10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{polski}
\usepackage{indentfirst}
\usepackage{amsmath,amssymb}
\usepackage{algorithm}
% \usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{amsthm}


%opening
\title{ \LARGE \textbf{Drzewa i tablice suf\mbox{}iksowe}\\
  \small referat z seminarium 
    \textit{zaawansowane struktury danych}
    prowadzonego przez \\ mgr Pawła Rzechonka w semestrze zimowym 2010/2011}
\author{Grzegorz Myszkier}

\newtheorem{defi}{Definicja}

\newtheorem{lem}{Lemat}


%\newenvironment{proof}[1][Dowód]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\begin{document}

\maketitle

\section{Wstęp}

Wyszukiwanie wzorca jest zadaniem znanym z dziedziny algorytmów tekstowych. Oparte na automatach skończonych
algorytmy Boyera{\dywiz}Moore'a, Morrisa{\dywiz}Pratta, Knutha{\dywiz}Morrisa{\dywiz}Pratta i ich dalsze 
modyfikacje dobrze spełniają swoją rolę pod warunkiem, że zależy nam na wyszukaniu zadanego, pojedynczego 
wzorca w tekście. Gdy interesuje nas wyszukiwanie wielu wzorców w tym samym tekście, porównywanie tekstów lub 
określanie samopodobieństwa tekstu, te algorytmy wciąż są użyteczne. Istnieją natomiast struktury danych, które mogą nam 
pomóc w wyszukiwaniu z lepszą złożonością czasową, takie jak drzewa i tablice sufiksowe. Są one dwiema różnymi 
strukturami danych, które nadają się do przeprowadzania użytecznych zapytań związanych z wyszukiwaniem w
tekście na wejściu. 

\section{Definicje}
Przypomnijmy i zdefiniujmy podstawowe pojęcia:\\
\\
\begin{tabular}{r @{ -- } l}
$\Sigma$ & \emph{alfabet}\\
$\cdot$ & operator \emph{konkatenacji}, zwyczajowo $a\cdot b$ oznaczamy przez $ab$ \\
$|w|$ & długość słowa $w$\\
$ \preccurlyeq $ & porządek leksykograficzny \\
$T = t_{0}t_{1}t_{2}{\ldots}t_{n-1}$ & \emph{tekst} długości $n$, w którym $t_{i} \in \Sigma $\\
$T_{i} = t_{i}t_{i+1}t_{i+2}{\ldots}t_{n-1}$ & $i$-ty \emph{sufiks} $T$
\end{tabular}
\\
\\

Aby ustalić ścisły porządek na sufiksach danego tekstu, będzie wygodnie dołożyć na koniec tekstu znak $\#$.
Przyjmujemy, że jest leksykograficznie mniejszy od dowolnego symbolu z $\Sigma$.

\section{Drzewa sufiksowe}

\emph{Drzewo sufiksowe} dla tekstu $T$ jest drzewem \emph{trie} przechowującym każdy sufiks $T_i$. 

\subsection{Wyszukiwanie}

\subsection{Budowanie drzewa sufiksowego}

\section{Tablice sufiksowe}

Tablica sufiksowa (ang. \emph{suffix array}) ${\mathit{SA}}_{T}$ dla tekstu $T$ to tablica zawierająca 
indeksy sufiksów $T$ posortowane według porządku leksykograficznego tych sufiksów. Weźmy dla przykładu słowo\\

\begin{center}
  \begin{tabular}{r @{ } c @{ } c @{ } c @{ } c @{ } c @{ } c @{ } c @{ } c @{ } c @{ } c @{ } c @{ } c}
    $T=$ & \textsc{m} & \textsc{i} & \textsc{s} & \textsc{s} & \textsc{i} & \textsc{s} & \textsc{s} & \textsc{i} & \textsc{p} & \textsc{p} & \textsc{i} & \# 
    \cr  & \scriptsize 0 & \scriptsize 1 & \scriptsize 2 & \scriptsize 3 & \scriptsize 4 & \scriptsize 5 & \scriptsize 6 & \scriptsize 7 & \scriptsize 8 & \scriptsize 9 & \scriptsize 10 & \scriptsize 11 
  \end{tabular}
\end{center}

Porządek sufiksów przedstawia poniższa tabela
\\
\begin{center}
  \begin{tabular}{r | c | l}
    $i$ & ${\mathit{SA}}_{T}[i]$ 	& $T_{{\mathit{SA}}_{T}[i]}$ \\ \hline
    0 & 11 & \textsc{\#} \\
    1 & 10 & \textsc{i\#} \\
    2 & 7 & \textsc{ippi\#} \\
    3 & 4 & \textsc{issippi\#} \\
    4 & 1 & \textsc{ississippi\#} \\
    5 & 0 & \textsc{mississippi\#} \\
    6 & 9 & \textsc{pi\#} \\
    7 & 8 & \textsc{ppi\#} \\
    8 & 6 & \textsc{sippi\#} \\
    9 & 3 & \textsc{sissippi\#} \\
    10 & 5 & \textsc{ssippi\#} \\
    11 & 2 & \textsc{ssissippi\#} \\
  \end{tabular}
\end{center}

Czasami będziemy potrzebować informacji na temat podobieństw dwóch sufiksów sąsiadujących w tablicy ${\mathit{SA}}_{T}$.
Może być wtedy przydatny dostęp do tablicy $\mathit{LCP}_T$ najdłuższych wspólnych prefiksów (ang. \emph{longest common 
prefix}).

\begin{defi}
  \begin{center}
    $\mathit{LCP_T[i]}$ = max\{$|w|$ : $w$ jest prefiksem $T_{{\mathit{SA}}_{T}[i]}$ i $T_{{\mathit{SA}}_{T}[i+1]}$ \}
  \end{center}
\end{defi}

Dla naszego słowa \textsc{missisipi\#} będzie to

\begin{center}
  $\mathit{LCP}_T$ = (0, 1, 1, 4, 0, 0, 1, 0, 2, 1, 3) .
\end{center}

\subsection{Wyszukiwanie wzorca}

Dany jest wzorzec $P = p_{0}p_{1}p_{2}{\ldots}p_{m-1}$. Wyszukiwanie wzorca M w tekście T można wykonać
za pomocą algorytmu 1, który realizuje wyszukiwanie binarne. Nie jest to najszybszy algorytm służący do 
znajdowania wystąpienia wzorca. Jest jednak szybszy od algorytmu Knutha-Morrisa-Pratta dla T znacznie
dłuższych od P. Łatwo udowodnić jego złożoność czasową.

W algorytmie stosujemy porównywanie dwóch 
słów w porządku $\preccurlyeq$. Jedno takie porównanie trwa proporcjonalnie długo do długości wzorca $m$.
Binarne przeszukiwanie zakresu dostępnych indeksów tekstu gwarantuje, że porównań słów będzie $O$($\log n$). 
Całość dokona się zatem w czasie $O$($m \log n$).

\newpage

\begin{algorithm}
\caption{Szukanie wzorca w tekście} 
\begin{algorithmic}[1]
\Procedure{Find}{$\mathit{String}$ $P$, $\mathit{String}$ $T$, $\mathit{Integer[]}$ $\mathit{SA}$}
  \If{$P \preccurlyeq T_{{\mathit{SA}}_{T}[0]}$}
    \State \textbf{return} $0$
  \ElsIf{$P \succ T_{{\mathit{SA}}_{T}[n-1]}$}
    \State \textbf{return} $n-1$
  \Else
    \State $l \gets 0 $
    \State $r \gets n-1 $
    \While{$r-l > 1$}
      \State $m \gets (l+r)/2 $
      \If{$P \preccurlyeq T_{{\mathit{SA}}_{T}[m]}$}
	\State $r \gets m$
      \Else
	\State $l \gets m$
      \EndIf
    \EndWhile
  \EndIf
  \State \textbf{return} $r$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\subsection{Budowa tablicy sufiksowej}

Zaprezentowany niżej algorytm Kärkkäinena-Sandersa buduje tablicę sufiksową w czasie i pamięci $O$($n$)
Pozwolę sobie na niezałączenie pseudokodu procedur \textsc{RadixSortThrees}, \textsc{RadixSortPairs} i 
\textsc{Merge} i pozostanę przy opisie słownym. Nie są one na tyle ciekawe, by zapełniać treść tej pracy.
Aby czytelnik zrozumiał działanie tej metody, trzeba przybliżyć pojęcie rangi. Ranga sufiksu $T_i$ określa
jego pozycję w porządku sufiksów. Tablica rang $R$ jest w pewnym sensie odwrotnością tablicy sufiksowej. 
Ściślej rzecz ujmując $R[i]=j \Leftrightarrow SA[j]=i$.

Algorytm $\mathit{KS}$ jest algorytmem rekurencyjnym. Spójrzmy na zapis procedury \textsc{ComputeRanks} z algorytmu
2. Na wstępie dzieli indeksy na dwa zbiory względem reszty z dzielenia indeksu przez 3. Indeksy podzielne przez
3 zostają spisane w tablicy $S_{0}$ a pozostałe w $S_{12}$.

Wykorzystajmy $S_{12}$ do utworzenia nowego słowa.Niech 
\begin{center}
$\overline{S_{12}} = (t_1t_2t_3)(t_2t_3t_4)(t_4t_5t_6)(t_5t_6t_7)\ldots(t_kt_{k+1}t_{k+2})$, 
\end{center}
gdzie $k$ jest rozmiarem tablicy $S_{12}$ po przejściu kroków 2-9. Jak widać, jest to konkatenacja kolejnych trójek
słowa $T$ pomijając te zaczynające się na litery o indeksach podzielnych przez 3. Warto zwrócić uwagę na jeden
szczegół techniczny. Jeśli pierwszy lub drugi symbol ostatniej trójki jest ostatnim symbolem T, wówczas na kolejne
pozycje tej (i być może wcześniejszej) trójki dokładamy brakujące \#. Każdą trójkę traktujemy jako pojedynczy symbol
pewnego nowego alfabetu.

Na tym etapie chcielibyśmy znać lokalne rangi słowa $\overline{S_{12}}$. Będą one użyte do określenia rang słowa $T$.
Aby to osiągnąć, wykonujemy sortowanie pozycyjne trójek. Pozycje trójek w posortowej tablicy mogą stanowić
lokalne rangi, pod warunkiem, że każde dwie trójki rożnią się. Jeśli tak nie jest, wywołujemy \textsc{ComputeRanks}
z argumentem $R_{12}$. To nam gwarantuje, że po wykonaniu kroków 10-12 $R_{12}$ jest tablicą różnowartościową.

W kolejnym kroku chcielibyśmy określić lokalne rangi dla pozycji podzielnych przez 3. Na tym etapie jest już łatwiej.
Możemy skorzystać z tablicy $R_{12}$. Niech
\begin{center}
$\overline{S_{0}} = (t_0,R_1)(t_3,R_4)(t_6,R_7)\ldots(t_j, R_{j+1})$. 
\end{center}

Mając dane lokalne rangi $R_{12}$ i symbole bez problemu przeprowadzimy sortowanie pozycyjne par słowa $\overline{S_{0}}$.
Podobnie jak wcześniej, otrzymujemy tablicę $R_{0}$.

\begin{algorithm}
\caption{Kärkkäinena-Sandersa} 
\begin{algorithmic}[1]
\Procedure{ComputeRanks}{$\mathit{String}$ $T$}
  \State $j \gets 0$, $k \gets 0$
  \For{$i=0\ldots |T|-1$}
    \If{$i\equiv_30$}
      \State $S_0[j++] \gets i$
    \Else
      \State $S_{12}[k++] \gets i$ 
    \EndIf
  \EndFor
  \State $R_{12} \gets $ \Call{RadixSortThrees}{$S_{12}$}
  \If{$\exists i\neq j$ . $R_{12}[i]=R_{12}[j] $}
    \State $R_{12} \gets $ \Call{ComputeRanks}{$R_{12}$}
  \EndIf
  \State $R_{0} \gets $ \Call{RadixSortPairs}{$S_{0}$, $R_{12}$}
  \State $R \gets $ \Call{Merge}{$R_{0}$, $R_{12}$}
  \State \textbf{return} $R$
\EndProcedure
\Statex
\Procedure{SuffixArray}{$\mathit{String}$ $T$}
  \State $R \gets $ \Call{ComputeRanks}{$T$}
  \For{$i=0\ldots |T|-1$}
    \State $\mathit{SA}[R[i]] = i$
  \EndFor
  \State \textbf{return} $\mathit{SA}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

Pozostało scalić $R_0$ i $R_{12}$. Nie jest to trudne, gdy na potrzeby scalania wyliczymy sobie ich odwrotności.
Dzięki temu wyznaczymy częściową kolejność wybierania elementów. Trzeba jeszcze zdefiniować porządek na pozycjach
z dwóch różnych klas. Należy przyjąć, że dla $i\equiv_3 0$

\small
\begin{displaymath}
\left\{
  \begin{array}{lr}
    (t_i, R_{i+1}) \prec (t_j, R_{j+1}) 
      \Leftrightarrow t_i\prec t_j \vee (t_i=t_j \wedge R_{i+1}<R_{j+1}) & j\equiv_3 1 \\

    (t_i, t_{i+1}, R_{i+2}) \prec (t_j, t_{j+1}, R_{j+2})
      \Leftrightarrow 
	\begin{array}{l}
	  (t_i\prec t_j) \vee \\
	  (t_i=t_j \wedge t_{i+1}\prec t_{j+1}) \vee \\
	  (t_it_{i+1}=t_jt_{j+1} \wedge R_{i+2}<R_{j+2}) \\
	\end{array} & j\equiv_3 2
  \end{array}
\right. .
\end{displaymath}
\normalsize
\\

Prześledźmy czas wykonania jednego wywołania procedury \textsc{ComputeRanks}. Przebiegnięcie tablicy w krokach
3-9 zajmuje czas $O(n)$. Wykonanie sortowania pozycyjnego w linii 10 trwa $O(n)$ czasu, podobnie jak w linii
14. Utworzenie dwóch odwrotnych tablic i scalenie w linii 15 odbywa się również w czasie liniowym. Zauważmy, że 
przy rekursji przekazujemy w argumencie tablicę o rozmiarze $\frac{2}{3}$ rozmiaru tablicy wejściowej, z dokładnością
do jednego elementu. Stąd wzór rekurencyjny na złożoność procedury \textsc{ComputeRanks}
$T(n) = T(\frac{2}{3}n) + O(n)$ a to prowadzi do wniosku, że $T(n) = O(n)$.

\subsection{Tworzenie tablicy $LCP$}

Tablicę $LCP$ możemy obliczyć, gdy mamy już daną tablicę sufiksową dla danego tekstu. Zanim obejrzymy algorytm
warto najpierw rozważyć niezbyt skomplikowaną tezę.

\begin{lem}
Niech $R_T$ i $\mathit{LCP_T}$ oznaczają odpowiednio tablice rang i najdłuższych wspólnych prefiksów dla danego
tekstu $T$. Wówczas dla $i \in [1\ldots n-2]$ zachodzi
\begin{center}
$\mathit{LCP_T}[R_T[i]] \geq \mathit{LCP_T}[R_T[i-1]]-1$ 
\end{center}
\end{lem}

\begin{proof}
Gdy $\mathit{LCP_T}[R_T[i-1]]-1 = 0$, wówczas nierówność zawsze zachodzi. Przyjmijmy, że
$\mathit{LCP_T}[R_T[i-1]] = l > 1$. Wtedy 
\begin{center}
$\exists T[j..k)$ . $T[j..j+l) = T[i-1..i+l-1)$.
\end{center}

Czyli $T[j+1..j+l) = T[i..i+l-1)$. 
\end{proof}

Przejdźmy do algorytmu.

\begin{algorithm}

\caption{obliczanie LCP} 
\begin{algorithmic}[1]
\Procedure{ComputeRanks}{$\mathit{String}$ $T$}
  \State $l \gets 0$
  \For{$i=0\ldots n-1$}
    \If{$R[i]\geq 1$}
      \State $j \gets \mathit{SA}[R[i]-1]$
      \While{$S[i+l]=S[j+l]$}
	\State $l++$
      \EndWhile
      \State $\mathit{LCP}[R[i]] \gets l$
      \State $l \gets \max\{l-1, 0\}$
    \EndIf
  \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

Poprawność algorytmu wynika z lematu 1. Jeśli policzyliśmy wcześniej długość prefiksu dwóch sufiksów, możemy
to wykorzystać przy liczeniu długości dla kolejnego sufiksu. Algorytm obliczający tablicę najdłuższych wspólnych
prefiksów przebiega wszystkie $i$ od $0$ do $n-1$. Wydaje się, że liniowy czas działania jest zaburzony przez
działającą wewnątrz pętlę \textit{while} inkrementującą wartość $l$. Ale wystarczy tylko zauważyć, że $l$ nie może
inkrementować więcej niż $n$ razy a liczba dekrementacji jest też nie większa od $n$. Dzięki temu algorytm 3
działa w czasie $O(n)$;

\section{Podsumowanie}

\begin{thebibliography}{4}
 \bibitem{} M. Crochemore, W. Rytter: \emph{Jewels of stringology}, World Scientific Publishing Co. Pte. Ltd, 2002
 \bibitem{} J. Kärkkäinen, P. Sanders: \emph{Simple Linear Work Suffix Array Construction}
 \bibitem{e3} J. Karkkainen, P. Sanders, S. Burkhardt: \emph{Linear Work Suffix Array Construction} 
 \bibitem{} P.~Ko,~S.~Aluru: \emph{Space Efficient Linear Time Construction of Suffix Arrays} 
\end{thebibliography}


\end{document}
