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

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

---

 {{{3}}}

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 {\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