Zaawansowane algorytmy i struktury danych/Wykład 2

Moduł ZASD:\ zaawansowane algorytmy tekstowe II \myskipW module tym zajmiemy się strukturami danych reprezentującymi zbiór wszystkich podsłów danego słowa $x$,zapisywany jako $Subwords(x)$. Oznaczmy wszsytkie wystąpienia (początkowe pozycje) słowa $z$ w słowie $x$przez $Occ(z,x)$. ($Occ$ jest skrótem od ang. {\em Occurrences}) Chcemy znaleźć taką reprezentację zbioru $Subwords(x)$ by można było łatwo odpowiedzieć na pytanie $z\in Subwords(x)$, (co jest równoważne $Occ(z,x)\ne \mathrm{\varnothing }$) jak również rozwiązywać inne problemytekstowe. Poza tym chcemy by rozmiar tej eprezentacji był liniowy, podczas gdy rozmiar $Subwords(x)$ może byćkwadratowy. Spośród wielu dobrych reprezentacji najbardziej znanymi są tablice sufiksowe (oznaczane przez$SUF$) i drzewa sufiksowe.

Niech

$x=a_1{a}_2\dots a_n$

, oraz niech

$x_{n+1}=\mathrm{\#}$

będzie specjalnym znakiemleksykograficznie mniejszym od każdego innego symbolu. Oznaczmy przez

$sufik{s}_i=a_i{a}_{i+1}\dots a_n$

sufiks tekstu x zaczynający się na pozycji i-tej. Niech

$SUF[k]$

będzie pozycją od której zaczyna się k-tyleksykograficznie sufiks x. Sufiks zaczynający się na pozycji

$(n+1)$

-szej nie jest brany pod uwagę. \noindentCiąg sufiksów posortowany leksykograficznie wygląda następująco:

$sufi{x}_{SUF[1]}<sufi{x}_{SUF[2]}<sufi{x}_{SUF[3]}<\dots sufi{x}_{SUF[n]}$

\begin{figure}[hbt]\begin{center}\includegraphics[width=7cm]{teksty_fig20.eps} \caption{Tablicą sufiksową tekstu

$x=babaabababba\mathrm{\#}$

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]}

Wartości najdłuższego wspólnego prefiksu między kolejnymi słowami są przedstawione jakozacienione segmenty. Odpowiadają one tablicy

$lcp=[1,3,4,2,1,0,2,4,3,2,1]$

. }\end{center}\end{figure}

\noindentOznaczmy przez $lcp[k]$ długść wspólnego prefisku $k$-tego i następnego sufiksuw kolejności leksykograficznej.\myskip \noindent Tablica sufiksowa ma następująca miłą własność: Niech \begin{center}$mi{n}_z=\min \{k:z\text{ jest prefiksem }sufik{s}_{SUF[k]}\}$,\\$ma{x}_z=\max \{k:z\text{ jest prefiksem }sufik{s}_{SUF[k]}\}$.\end{center}Wtedy $Occ(z,x)$ jest przedziałem w tablicy sufiksowej od $mi{n}_z$ do $ma{x}_z$.\myskip Drzewo sufiskowe jest drzewem, w którym każda ścieżka jest etykietowana kolejnymi symbolamipewnego sufiksu, oraz każdy sufiks $x$ jest obecny w drzewie. Gdy dwie ścieżki się {\em rozjeżdżają}tworzy się wierzchołek. Mówiąc bardziej formalnie każdej krawędzi jest przypisane jako etykieta pewnepodsł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 jestdługość odpowiadającego jej słowa. \myskip\begin{figure}[bh]\begin{center}\includegraphics[width=15cm]{teksty_fig15.eps} \caption{Drzewo sufiksowe dla tekstu $x=babaabababba$. Na ko"ncu jest dodany zank $\mathrm{\#}$. Ko"ncowe węzły zawierająinformację gdzie zaczyna się sufiks, którym dochodzimy do danego węzła.}\end{center}\end{figure}\myskip Obie reprezentacje rozwiązują szybko problem string-matchingu, oraz mają rozmiar liniowy.

\noindent Niech z będzie wzorcem o długości m, a

$x$

słowem długośći n. Z reguły

$m<<n$

.\subsection*{Szukanie podsłów}Pokażemy jak sprawdzać, czy

$z$

występuje w

$x$

.\begin{description}\item{Używając drzewa sufiskowego}, czas

$O(m)$

}\mbox{ \ \\{\em Idziemy} od korzenia w dół czytając kolejnesymbole

$z$

, czasami posuwamy się po wewnętrznej etykiecie pewnej krawędzi. Zbiór wystąpie"n odpowiadazbiorowi liści w poddrzewie węzła do którego doszliśmy. Jeśli po drodze {\em utknęliśmy} i nie dało siędalej schodzić po drzewie to oznacza, że

$z\notin Subwords(x)$

.\item{Używając tablicy sufiksowej}, czas

$O(m\log n)$

}\mbox{ \ \\Możemy sprawdzić czy

$z$

jest prefiksem

$i$

-tego sufiksu w czasie

$O(m)$

. Korzystając z tego wykonujemy rodzaj{\em binary search}, 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

$SUF$

między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się odz.\end{description}\subsection*{Liczenie liczby podsłów}Pokażemy jak liczyć liczbę podsłów słowa

$x$

mając tablicę sufiksową lub drzewo sufiksowe. Ko"ncowymarker

$\mathrm{\#}$

nie traktujemy jako części słowa

$x$

. Liczba podsłów jest równa

$|Subwords(x)|$

. Jeśliwszsytkie symbole słowa są różne to Parser nie mógł rozpoznać (błąd składni): {\displaystyle |Subwords(x)|={\choose {n} 2}} .\begin{description}\item{Używając drzewa sufiskowego}, czas

$O(n)$

}\mbox{ \ \\Sumujemy wagi krawędzi drzewa.\item{Używając tablicy sufiksowej}, czas

$O(n)$

}\mbox{ \ \\Niech

$SUMA(lcp)$

będzie sumą elementówtablicy

$lcp$

. Liczbę podsłów obliczamy jako

$(\genfrac{}{}{0ex}{}{n+1}{2})-SUMA(lcp)$

\end{description} \noindent Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona(korzystając z drzewa sufisowego lub z tablicy sufiksowej). \myskip Przykład.\ Dla przykładowego Parser nie mógł rozpoznać (nieznana funkcja „\babaabababba”): {\displaystyle x\ =\babaabababba} mamy

$|Subwords(x)|=55$

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

$x$

, danego na rysunku. Suma elementów tablicy

$lcp$

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

$78-23=55$

\myskip\noindent Podobnie jak tablicę sufiksową możemy zdefiniować tablicę

$ROT$

odpowiadającą posortowanemuciągowi wszystkich cyklicznych przesunięć słowa

$x$

(rotacji

$x$

). \myskip Pozostawiamy jako ćwiczenieznalezienie liniowego algorytmu liczącego tablicę

$ROT$

, zakładając, że mamy liniowy algorytm liczeniatablicy sufiksowej. \myskip Dysgresja.\ Ciekawą klasą słów dla których tablice

$SUF,ROT$

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

$ROT$

jest postępem arytmetycznym (modulo długość słowa).Natomiast tablica

$SUF$

jest postępem arytmetycznym gdy

$n$

jest parzyste.\myskipSłowa Fibonacciego definiujemy następująco:\

$F_0=a,F_1=ab,F_{n+1}=F_n\cdot F_{n-1}$

\Na przykład:\

$F_3=abaab,F_4=abaababa,F_5=abaababaabaab.$

\ Oznaczmy przez

$SU{F}_n$

tablicę

$SUF$

dla słowa Fibonacciego

$F_n$

, wtedy:</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].

Parser nie mógł rozpoznać (nieznana funkcja „\noindent”): {\displaystyle \noindent Pozostawiamy jako ćwiczenie policzenie wzoru na <math>|Subwords(F_n)|} .

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.%%===================================================================================

Pokażemy konstruktywanie następujący istotny fakt: \vskip 0.1cm jeśli znamy tablicę sufiksową i tablicę$lcp$ to drzewo sufiksowe dla danego tekstu możemy {\em łatwo} skonstruować w czasie liniowym.\myskipPrzypuśćmy, że, $SUF=[i_1,i_2,\dots ,i_n]$, a więc:</math>

sufiks_{i_1}< sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.

Parser nie mógł rozpoznać (nieznana funkcja „\begin{center}”): {\displaystyle \begin{center}\begin{minipage}{12cm}\noindent '''Algorytm''' Drzewo-Susfiksowe; <math>T}  := drzewo reprezentujące $sufik{s}_{i_1}$ (jedna krawędź);

for $k:=2$ to $n$ do\\\hspace*{1cm} wstaw nową ścieżkę o sumarycznej etykiecie $sufik{s}_{i_k}$ do $T$; \myskip\end{minipage}\end{center} \begin{figure}[ht]\begin{center}\includegraphics[width=4.7cm]{teksty_fig16.eps}\caption{ Wstawianie kolejnego sufiksu $sufik{s}_{i_k}$ do drzewa sufiskowego, przed włożeniem wszystkiekrawędzie{\em ścieżki roboczej} od $u$ do korzenia {są skierowane } w lewo. } \end{center}\end{figure} Opiszemy w jaki sposób wstawiamy kolejny sufiks $\beta$ 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łnaetykieta od korzenia do węzła). Niech $\alpha$ będzie poprzednio wstawionym sufiksem, a $u$ ostatniopoprzednio utworzonym liściem. Wtedy wstawienie $\beta$ polega na znalezieniu maksymalnego wspólnego prefiksu ${\gamma }_1$tekstów $\alpha$, $\beta$. Niech $\beta ={\gamma }_1\cdot {\gamma }_2$. Znajdujemy węzeł $v$ odpowiadający ścieżceod korzenia etykietowanej ${\gamma }_1$. Podstawowym {\em 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 $\beta$, oraz krawędź $(v,w)$etykietowaną ${\gamma }_2$. Z tablicy $lcp$ odczytujemy długość ${\gamma }_1$. W celu obliczenia $v$ posuwamy się ścieżką od $u$ w górędrzewa, aż znajdziemy węzeł oddalony od korzenia o $|\gamma |$. Przechodząc drzewo posuwamy się po węzłachdrzewa, przeskakując potencjalnie długie teksty na krawędziach. \myskipKoszt operacji wstawienia jestproporcjonalny do sumy: jeden plus zmniejszenie głębokości nowego liścia w stosunku do starego. Suma tychzmniejsze"n jest liniowa. ${\gamma }_1$ jest najdłuższym wspólnym prefiksem słów $sufik{s}_{i_{k-1}}$ i$sufik{s}_{i_k}$. Kluczowe znaczenie w operacji ma znajomość wartości $|{\gamma }_1|=lcp[k-1]$. Wiemy kiedy sięzatrzymać idąc do góry od węzła $u$ w kierunku korzenia. \myskipLokalnie wykonana praca w jednej iteracjijest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego.\myskipHistoria algorytmu jest pokazana dla przykładowego tekstu na rysunkach. \begin{figure}[ht]\begin{center}\includegraphics[width=10cm]{teksty_fig17.eps}\caption{Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu $babaabababba\mathrm{\#}$. } \end{center}\end{figure}

\begin{figure}[htb]\begin{center}\includegraphics[width=14.4cm]{teksty_fig18.eps}\caption{Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu $babaabababba\mathrm{\#}$. } \end{center}\end{figure}

Niech $rank(i)$ b"dzie poycją $sufik{s}_i$ w porządkuleksykograficznym. W naszym przykładowym słowie mamy: </math>

rank\ =\ [8,\ 2,\ 7,\ 1,\ 3,\ 9,\ 4,\ 10,\ 5,\ 12,\11,\ 6]

$Niech<math>lc{p}^{\prime }[k]=lcp[rank[k]-1]$.\ \myskip Załóżmy, dla uproszczenia, że $lcp[0]=0$. Obliczamy tablice$lc{p}^{\prime },lcp$ następująco: \vskip 0.5 cm\begin{center}\begin{minipage}{12cm}\noindent Algorytm Oblicz-lcp;

for $k:=1$ to $n$ do\\\hspace*{0.5cm} oblicz $lc{p}^{\prime }[k]$ korzystając z faktu, że$lc{p}^{\prime }[k]\ge lc{p}^{\prime }[k-1]-1$; \\\hspace*{0.7cm} koszt iteracji $O(lc{p}^{\prime }[k]-lc{p}^{\prime }[k-1]+const)$ for $k:=1$ to $n$ do\\\hspace*{0.5cm} $lcp[rank[k]-1]$ := $lc{p}^{\prime }[k]$ \myskip\end{minipage}\end{center} Pozostawimay jako ćwiczenie dowód tego, że $lc{p}^{\prime }[k]\ge lc{p}^{\prime }[k-1]-1$. Jeśli $lc{p}^{\prime }[k-1]-1=t$ to $lc{p}^{\prime }[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 {\em do przodu} (sprawdzając kolejne symbole). Jest to analiza typu {\em jeden krok do tyłu i kilka doprzodu}. Liczba iteracji jest liniowa, więc liczba kroków do tyłu też. Poniewaź odległość {\em do celu}jest liniowa, to suma kroków też jest liniowa. Opiszemy uproszczoną wersję algorytmu Karpa-Millera-Rosenberga (w skrócie algorytmu {\em KMR})rozwiązywania problemów tekstowych metodą {em słownika bazowego}. Ustalmy pewnie tekst $x$ długości $n$.Załóżmy, że dodatkowym symbolem jest $x_{n+1}=\mathrm{\#}$, leksykograficznie najmniejszy symbol. Przez $k$-bazowysegment rozumiemy segment $x[i..i+2^k-1]$ długości $2^k$ lub ko"nczący się na $x_{n+1}$. Teoretyczniemożemy założyć, że po symbolu $\mathrm{\#}$ mamy bardzo dużo takich symboli na prawo i każde segment startujący w$x[1..n]$ ma {\em dokładnie } długość $2^k$. Słowanik podsłów bazowych} (w skrócie $DBF(x)$, od ang. {\em dictionary of basic factors) składa sięz $\log n$ tablic Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \textsl{NAZWA}_0} ,\ Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \textsl{NAZWA}_1} ,\ Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \textsl{NAZWA}_2} ,\ldots Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \textsl{NAZWA}_{\log n}} . Zakładamy, że Parser nie mógł rozpoznać (nieznana funkcja „\textsl”): {\displaystyle \textsl{NAZWA}_k[i]} jest pozycją słowa $x[i..i+2^k-1]$ na posortowanej liście (bezpowtórze"n) wszystkich podsłów długości $2^k$ słowa $x$. Jeśli długość {\em wystaje} poza koniec $x$ toprzyjmujemy że są tam (wirtualnie) same symbole $\mathrm{\#}$. Poniżej przedsatwiamy przykład słownika podsłówbazowych $DBF(abaabbaa)$. \vskip 0.5cm