Zaawansowane algorytmy i struktury danych/Wykład 2

Zaawansowane algorytmy tekstowe II

W 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. 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ę. Cią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]}$

Rysunek 1: 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]$.

Oznaczmy przez $lcp[k]$ długść wspólnego prefisku $k$-tego i następnego sufiksuw kolejności leksykograficznej.

Tablica sufiksowa ma następująca miłą własność: Niech

$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]}\}$.

Wtedy $Occ(z,x)$ jest przedziałem w tablicy sufiksowej od $mi{n}_z$ do $ma{x}_z$.

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ę 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 jest długość odpowiadającego jej słowa.

Rysunek 2: Drzewo sufiksowe dla tekstu $x=babaabababba$. Na końcu jest dodany zank $\mathrm{\#}$. 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 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 utknęliśmy i nie dało siędalej schodzić po drzewie to oznacza, że $z\notin Subwords(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{\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ę 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 $\mathrm{\#}$ nie traktujemy jako części słowa $x$. Liczba podsłów jest równa $|Subwords(x)|$. Jeśli wszystkie symbole słowa są różne to Parser nie mógł rozpoznać (błąd składni): {\displaystyle |Subwords(x)|={\choose {n} 2}} .

Używając drzewa sufiskowego, czas $O(n)$
Sumujemy wagi krawędzi drzewa.

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

Niech

$SUMA(lcp)$

będzie sumą elementów tablicy

$lcp$

. Liczbę podsłów obliczamy jako

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

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 $|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$

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

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

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.

Sł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:

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 $|Subwords(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ę$lcp$ to drzewo sufiksowe dla danego tekstu możemy łatwo skonstruować w czasie liniowym.

Przypuść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}.</math>

Algorytm Drzewo-Susfiksowe

---

$T:=$ drzewo reprezentujące $sufik{s}_{i_1}$ (jedna krawędź);
for $k:=2$ to $n$ do
   wstaw nową ścieżkę o sumarycznej etykiecie $sufik{s}_{i_k}$ do $T$;

Rysunek 3: Wstawianie kolejnego sufiksu $sufik{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 $\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łna etykieta 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żce od korzenia etykietowanej ${\gamma }_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 $\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 jest proporcjonalny do sumy: jeden plus zmniejszenie głębokości nowego liścia w stosunku do starego. Suma tychzmniejszeń 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.

Lokalnie wykonana praca w jednej iteracjijest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego.

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

Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu $babaabababba\mathrm{\#}$.
Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu $babaabababba\mathrm{\#}$.

Oblicanie tablicy lcp

Niech $rank(i)$ będzie poycją $sufik{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 $lc{p}^{\prime }[k]=lcp[rank[k]-1]$.

Załóżmy, dla uproszczenia, że $lcp[0]=0$. Obliczamy tablice$lc{p}^{\prime },lcp$ następująco:

Algorytm Oblicz-lcp

---

for $k:=1$ to $n$ do
   oblicz $lc{p}^{\prime }[k]$ korzystając z faktu, że $lc{p}^{\prime }[k]\ge lc{p}^{\prime }[k-1]-1$;
    koszt iteracji $O(lc{p}^{\prime }[k]-lc{p}^{\prime }[k-1]+const)$
for $k:=1$ to $n$ do
   $lcp[rank[k]-1]:=lc{p}^{\prime }[k]$

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 do przodu (sprawdzając kolejne symbole). Jest to analiza typu jeden krok do tyłu i kilka doprzodu. 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}=\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 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

$NAZW{A}_0$, $NAZW{A}_1$, $NAZW{A}_2$,$\dots NAZW{A}_{\log n}$.

Zakładamy, że $NAZW{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 $\mathrm{\#}$. Poniżej przedstawiamy przykład słownika podsłów bazowych $DBF(abaabbaa)$.

Algorytm liczenia tablic Nazwa jest bardzo prosty. Załóżmy od razu, że symbole sąponumerowane leksykograficznie. Wtedy $NAZW{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 $NAZW{A}_k=>NAZW{A}_{k+1}$

Dla każdego

$i$

tworzymy nazwę kompozycję slowa

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

jako

$NAZW{A}_k[i],NAZW{A}_k[i+2^k]$

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

Zauważmy, że tablica sufiksowa odpowiada tablicy $NAZW{A}_{\lceil \log n\rceil }$. 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.

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

Opiszemy teraz algorytm Karkainena-Sandersa ( w skrócie KS) będący optymalizowaną 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 zastosowania.

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

$x$

:</math>M\ =\ \{1\le i \le n:\ (i-1)\ \textrm{modulo}\ 3 \in \{0,1\}\}\ \ N\ =\ \{1,2,..,n\}-M

$<!--\mathrm{\%}<math>M$ nazwiemy zniorem ozycji pierwszorzędnych, a $N$ drugorzędnych.-->Przez $SUF[M]$, oznaczmy tablicę sufiksowądla pozycji ze zbioru $M$, podobnie zdefiniujmy $SUF[N]$. \myskip $SUF[M]$ daje posortowany ciąg sufiskówzaczynających się na pozycjach ze zbioru $M$.\paragraph{Redukcja liczenia $SUF[M]$ do liczenia tablicysufiksowej rozmiaru $\frac{2}{3}n$}\mbox{ \ }

Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie $x$ korzystając z rdix-sort. Każdemutakiemu słowu przyporządkujmy nazwę będącą jego pozycją w posortowanym leksykograficznie ciągu, oznaczmy$kod(z)$ kod podsłowa długości 3. Zakładamy, że $x$ ko"nczy się dodatkowo dwoma symbolami $\mathrm{\#}$ alerozważamy tylko podsłowa zaczynające się w $x$. Dla uproszczenia załóżmy, że 3 jest dzielnkiem n.

Tworzymy nowe słowo $compress(x)$ w następujący sposób:</math>

y1\ =\ \ kod(a_1a_2a_3)\cdot kod(a_4a_5a_6) \ldots kod(a_{n-2}a_{n-1}a_n)

${\displaystyle }$

y2\ =\ kod(a_2a_3a_4)\cdot kod(a_5a_6a_7) \ldots kod(a_{n-1}a_{n}a_{n+1})

${\displaystyle }$

compress(x)\ =\ y1\ \#\ y2

Parser nie mógł rozpoznać (błąd składni): {\displaystyle <!--%-->Jeśli mamy tablicęsufiksową dla słowa <math>compress(x)} to można łatwo policzyć $SUF[M]$ w czasie liniowym .

\begin{center}\begin{minipage}{12cm}\noindent Algorytm KS;

1. $x^{\prime }:=compress(x)$; \item obliczamy tablicę sufiksową dla x' rekurencyjnie; \item obliczamy $SUF[M]$ wczasie liniowym, znając tablicę sufiksową dla x'; \item obliczamy $SUF[N]$ w czasie liniowym (bez rekursji)znając $SUF[M]$; \item scalamy posortowane ciągi $SUF[M],SUF[N]$ w tablicę sufiksową dla całego słowasłowa $x$

\myskip\end{minipage}\end{center} Krok 1 algorytmu sprowadza się do {\em radix-sort}u, 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ównanialeksykograficznego dwóch sufiksów w czasie stałym. Jeśli oba sufiksy są typu $M$ luboba są typu $N$ to porównanie jest w czasie stałym bo mamy posortowane listy takich sufiksów.

Pokażemy na przykładzie jak porównać sufiks typu M z sufiksem typu N. \myskip Przykład.\\Nierównośc$sufik{s}_2<sufik{s}_{12}$ jest równoważna alternatywie:</math>

(a_2<a_{12}) \ \textrm{lub}\(a_2=a_{12},\ a_3<a_{13}) \ \textrm{lub}\ (a_2=a_{12},\ a_3=a_{13},\ sufiks_4<sufiks_{14})

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Jednakże <math>4,14\in M} , zatem $sufik{s}_4$ i $sufik{s}_{14}$, są typu M i można je porównać w czasie stałym. \myskip \noindentNiech $T(n)$ będzie czasem działania algorytmu KS. Zachodzi </math>

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Rozwiązaniem jest <math>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 (algorytm Weinera, McCreighta, Ukkonena).