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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\ =\" na "=")
 
(Nie pokazano 43 wersji utworzonych przez 7 użytkowników)
Linia 1: Linia 1:
<font size="7">Algorytmy tekstowe II</font>
+
__TOC__
  
__TOC__
 
  
  
 +
Najważniejszymi strukturami danych związanymi z tekstami są te, które dotyczą efektywnej reprezentacji zbioru  wszystkich podsłów  tekstu. Przed wszystkim interesuje nas to, żeby taka reprezentacja  przyspieszała wyszukiwanie słów, a jednocześnie żeby była konstruowalna  w czasie liniowym albo prawie liniowym (z dokładnością do logarytmów).
  
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'').
+
Oznaczmy przez <math>Subwords(x)</math>  
 +
wszystkie podsłowa tekstu <math>x</math>,  a wszystkie wystąpienia (początkowe pozycje) słowa <math>z</math> w słowie <math>x</math> oznaczmy  przez <math>Occ(z,x)</math>. (Oznaczenie <math>Occ</math> jest skrótem od ang. ''occurrences'').
  
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 problemy tekstowe. Poza tym chcemy by rozmiar tej reprezentacji był liniowy, podczas gdy rozmiar <math>Subwords(x)</math> może być kwadratowy.
+
Chcemy znaleźć taką reprezentację zbioru <math>Subwords(x)</math>, by można było łatwo odpowiedzieć na pytanie, czy <math>z\in Subwords(x)</math>,  
Spośród wielu dobrych reprezentacji najbardziej znanymi są tablice sufiksowe (oznaczane przez<math>SUF</math>) i drzewa sufiksowe.
+
co jest równoważne <math>Occ(z,x)\ne \emptyset</math>, jak również rozwiązywać inne problemy tekstowe. Poza tym chcemy, by rozmiar tej reprezentacji był liniowy, podczas gdy rozmiar <math>Subwords(x)</math> może być kwadratowy.
 +
Spośród wielu dobrych reprezentacji najbardziej znanymi są ''tablice sufiksowe'' (oznaczane przez <math>SUF</math>), ''drzewa sufiksowe''
 +
i ''grafy podsłów'' (nie rozważane w tym module).
  
 
===Tablice i drzewa sufiksowe===
 
===Tablice i drzewa sufiksowe===
  
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.
+
Niech <math>x=a_{1}a_{2}\dots a_{n}</math> i niech <math>x_{n+1}=\#</math> będzie specjalnym znakiem leksykograficznie większym od każdego innego symbolu 9w przyszłości będziemy również używać <math>x_{n+1}=\#</math> jako najmniejszego
 
+
symbolu).  
Oznaczmy przez <math>sufiks_{i}=a_{i}a_{i+1}\dots a_{n}</math>sufiks tekstu x zaczynający się na pozycji i-tej.  
 
  
Niech <math>SUF[k]</math> będzie pozycją od której zaczyna się k-ty leksykograficznie sufiks x.  
+
Oznaczmy przez <math>sufiks_{i}=a_{i}a_{i+1}\dots a_{n}</math> sufiks tekstu ''x'' zaczynający się na pozycji ''i''-tej.  
  
 +
Niech <math>SUF[k]</math> będzie pozycją, od której zaczyna się ''k''-ty leksykograficznie sufiks ''x''.
 
Sufiks zaczynający się na pozycji <math>(n+1)</math>-szej nie jest brany pod uwagę.  
 
Sufiks zaczynający się na pozycji <math>(n+1)</math>-szej nie jest brany pod uwagę.  
  
Linia 25: Linia 28:
  
  
[[Grafika:Zasd_2_1.jpg]]
+
<center> [[Grafika:Zasd_2_1.jpg]] </center>
 +
<br>
  
Rysunek 1: Tablicą sufiksową tekstu <math>x\ =\ babaabababba\#</math> jest ciąg  <math>SUF\ =\ [4,\ 2,\ 5,\ 7,\ 9,\ 12,\ 3,\ 1,\ 6,\ 8,\ 11,\ 10]</math>
+
Rysunek 1: Tablicą sufiksową tekstu <math>x= babaabababba\#</math> jest ciąg  <math>SUF=  [4,\ 2,\ 5,\ 7,\ 9,\ 12,\ 3,\ 1,\ 6,\ 8,\ 11,\ 10]</math>
 
<br>
 
<br>
Oznaczmy przez <math>lcp[k]</math> długość wspólnego prefiksu <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>
 
<br>
Tablica sufiksowa ma następująca miłą własność: Niech
+
Oznaczmy przez <math>lcp[k]</math> długość wspólnego prefiksu <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 ‘’sympatyczną’’ własność: Niech
  
 
<math>min_{z}=\min\{k : z  \mbox{ jest prefiksem }  sufiks_{SUF[k]}\}</math>,
 
<math>min_{z}=\min\{k : z  \mbox{ jest prefiksem }  sufiks_{SUF[k]}\}</math>,
Linia 38: Linia 43:
 
Wtedy <math>Occ(z,x)</math> jest przedziałem w tablicy sufiksowej od <math>min_{z}</math> do <math>max_{z}</math>.
 
Wtedy <math>Occ(z,x)</math> jest przedziałem w tablicy sufiksowej od <math>min_{z}</math> do <math>max_{z}</math>.
  
'''Drzewo sufiksowe''' 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.
+
'''Drzewo sufiksowe''' 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.  
+
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}\ldots_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.  
 +
<br> <br>
  
[[Grafika: Zasd_2_2.jpg]] <br> Rysunek 2: Drzewo sufiksowe dla tekstu <math>x\ =\ babaabababba</math>. Na końcu jest dodany znak <math>\#</math>. Końcowe węzły zawierają informację gdzie zaczyna się sufiks, którym dochodzimy do danego węzła.
+
<center> [[Grafika: Zasd_2_2.jpg]]  
 +
</center>
 +
<br> Rysunek 2: Drzewo sufiksowe dla tekstu <math>x= babaabababba</math>. Na końcu jest dodany znak <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ści n. Z reguły <math>m << n</math>.
+
Obie reprezentacje pozwalają szybko rozwiązywać 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ści n. Z reguły <math>m << n</math>.
  
 
=== Szukanie podsłów===  
 
=== Szukanie podsłów===  
  
Pokażemy jak sprawdzać, czy <math>z</math> występuje w <math>x</math>.
+
Pokażemy, jak sprawdzać, czy <math>z</math> występuje w <math>x</math>.
  
 
'''Używając drzewa sufiksowego''' (czas <math>O(m)</math>)
 
'''Używając drzewa sufiksowego''' (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ń 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>
+
''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ń 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, oznacza to, że <math>z \notin Subwords(x) </math>
  
 
'''Używając tablicy sufiksowej''' (czas <math>O(m \log n)</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 przeciwnym wypadku z nie jest podsłowem x.  
+
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 \in Subwords(x)</math>. W przeciwnym wypadku z nie jest podsłowem x.  
  
 
Podobnie znajdujemy ostatni sufiks. Zbiór wystąpień odpowiada przedziałowi w tablicy <math>SUF</math> między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od z.
 
Podobnie znajdujemy ostatni sufiks. Zbiór wystąpień odpowiada przedziałowi w tablicy <math>SUF</math> między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od z.
  
=== Liczenie liczby podsłów===  
+
=== Wyznaczanie 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>.
+
Pokażemy, jak znaleźć liczbę podsłów słowa <math>x</math> przy pomocy tablicy sufiksowej lub drzewa sufiksowego. Końcowego markera <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 sufiksowego''', czas <math>O(n)</math>
 
'''Używając drzewa sufiksowego''', czas <math>O(n)</math>
Linia 82: Linia 90:
  
 
{{przyklad|||
 
{{przyklad|||
Dla przykładowego <math>x\ =\babaabababba</math> mamy <math>|Subwords(x)|=55</math>. Proponujemy to wyliczyć z tablicy sufiksowej i drzewa sufiksowego 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>}}
+
Dla przykładowego tekstu <math>x = babaabababba</math> mamy <math>|Subwords(x)|=55</math>. Proponujemy to wyliczyć z tablicy sufiksowej i drzewa sufiksowego dla<math>x</math>, danego na rysunku. Suma elementów tablicy  <math>lcp</math> wynosi 23. Liczba podsłów to:  <math>78-23= 55</math>}}
  
 
Podobnie jak tablicę sufiksową możemy zdefiniować tablicę <math>ROT</math> odpowiadającą posortowanemu ciągowi wszystkich cyklicznych przesunięć słowa <math>x</math> (rotacji <math>x</math>).  
 
Podobnie jak tablicę sufiksową możemy zdefiniować tablicę <math>ROT</math> odpowiadającą posortowanemu cią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 liczenia tablicy sufiksowej.  
+
Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu obliczania tablicy <math>ROT</math>, przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.  
  
  
'''Dygresja.''' Ciekawą klasą słów dla których tablice <math>SUF,\ ROT</math> są szczególnie interesujące słowa Fibonacciego <math>F_n</math>. W tym szczególnym przypadku załóżmy, że pozycje numerujemy 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.
+
'''Dygresja.''' Ciekawą klasę słów, dla których tablice <math>SUF,\ ROT</math> są szczególnie interesujące, stanowią słowa Fibonacciego <math>F_n</math>. W tym szczególnym przypadku załóżmy, że pozycje numerujemy 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:
+
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>
+
<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>.
+
Pozostawiamy jako ćwiczenie znalezienie wzoru na <math>|Subwords(F_n)|</math>.
  
 
== Drzewa sufiksowe =>tablice sufiksowe ==
 
== Drzewa sufiksowe =>tablice sufiksowe ==
Linia 109: Linia 117:
 
Pokażemy konstruktywnie następujący istotny fakt:  
 
Pokażemy konstruktywnie następujący istotny fakt:  
  
jeśli znamy tablicę sufiksową i tablicę<math>lcp</math> to drzewo sufiksowe dla danego tekstu możemy ''łatwo'' skonstruować w czasie liniowym.
+
jeśli znamy tablicę sufiksową i tablicę <math>lcp</math>, to drzewo sufiksowe dla danego tekstu możemy ''łatwo'' skonstruować w czasie liniowym.
  
Przypuśćmy, że,
+
Przypuśćmy, że
<math>SUF\ =\ [i_1,i_2,\ldots,i_n]</math>, a więc:
+
<math>SUF= [i_1,i_2,\ldots,i_n]</math>, a więc:
 
<center><math> sufiks_{i_1}< sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.</math></center>
 
<center><math> sufiks_{i_1}< sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.</math></center>
  
  
  
{{algorytm|Drzewo-Sufiksowe|algorytm_drzewo_susfiksowe|
+
{{algorytm|Drzewo-Sufiksowe|algorytm_drzewo_sufiksowe|
<math>T :=</math> drzewo reprezentujące <math>sufiks_{i_1}</math> (jedna krawędź);<br>
+
<math>T :=</math> drzewo reprezentujące <math>sufiks_{i_1}</math> (jedna krawędź);
'''for''' <math>k:=2</math> '''to''' <math>n</math> '''do'''<br>
+
'''for''' <math>k:=2</math> '''to''' <math>n</math> '''do'''
&nbsp;&nbsp;&nbsp;wstaw nową ścieżkę o sumarycznej etykiecie <math>sufiks_{i_k}</math> do <math>T</math>;  
+
3    wstaw nową ścieżkę o sumarycznej etykiecie <math>sufiks_{i_k}</math> do <math>T</math>;  
 
}}
 
}}
  
Linia 131: Linia 139:
 
Niech <math>\alpha</math> będzie poprzednio wstawionym sufiksem, a <math>u</math> ostatnio utworzonym liściem.
 
Niech <math>\alpha</math> będzie poprzednio wstawionym sufiksem, a <math>u</math> ostatnio 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 go  tworzymy. 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>.
+
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>.  
 +
 
 +
Kluczowym pomyslem algorytmicznym  jest tutaj 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 go  tworzymy. 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>.
  
  
Linia 142: Linia 152:
  
  
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.  
+
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 poprzedniego. W sumie praca jest liniowa.
 
Lokalnie wykonana praca w jednej iteracji jest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do poprzedniego. W sumie praca jest liniowa.
Linia 148: Linia 158:
 
Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.
 
Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.
  
<center> [[Grafika:Zasd_2_4.jpg||500px]] <br> Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu  
+
<center> [[Grafika:Zasd_2_4.jpg||500px]] <br><br> <br> Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu  
 
<math>babaabababba\#</math>. </center>
 
<math>babaabababba\#</math>. </center>
  
<center> [[Grafika:Zasd_2_5a.png||500]] <br> Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu <math>babaabababba\#</math>. </center>
+
<br>
 +
<br>
 +
 
 +
<center> [[Grafika:Zasd_2_5.jpg||600px]] <br> Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu <math>babaabababba\#</math>. </center>
 +
<br><br>
  
 
== Obliczanie tablicy ''lcp'' ==
 
== Obliczanie tablicy ''lcp'' ==
  
Niech <math>rank(i)</math> będzie poyccją <math>sufiks_i</math> w porządku leksykograficznym. W naszym przykładowym słowie mamy:  
+
Niech <math>rank(i)</math> będzie pozycją <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><math>rank = [8, 2, 7, 1, 3, 9, 4, 10, 5, 12, 11, 6]</math></center>
  
Niech  <math>lcp'[k]\ =\ lcp[rank[k]-1]</math>.
+
Niech  <math>lcp'[k] = lcp[rank[k]-1]</math>.
  
Załóżmy, dla uproszczenia, że  <math>lcp[0]=0</math>. Obliczamy tablice<math>lcp',\ lcp</math> następująco:  
+
Załóżmy, dla uproszczenia, że  <math>lcp[0]=0</math> oraz że tekst kończy się specjalnym symbolem
 +
Obliczamy tablice <math>lcp',\ lcp</math> następująco:  
  
  
 
{{algorytm|Oblicz-lcp|algorytm_oblicz_lcp|
 
{{algorytm|Oblicz-lcp|algorytm_oblicz_lcp|
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
+
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''
&nbsp;&nbsp;&nbsp;oblicz <math>lcp'[k]</math> korzystając z faktu, że <math>lcp'[k]\ge lcp'[k-1]-1</math>; <br>
+
2    oblicz <math>lcp'[k]</math> korzystając z faktu, że <math>lcp'[k]\ge lcp'[k-1]-1</math>;  
&nbsp;&nbsp;&nbsp;&nbsp;koszt iteracji <math>O(lcp'[k]-lcp'[k-1]+const)</math><br>
+
3    // koszt iteracji <math>O(lcp'[k]-lcp'[k-1]+const)</math>
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
+
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''
&nbsp;&nbsp;&nbsp;<math>lcp[rank[k]-1] := lcp'[k]</math>  
+
  5    <math>lcp[rank[k]-1] := lcp'[k]</math>  
 +
}}
  
 +
Można to zapisać w języku C++ następująco
 +
 +
{{algorytm|Oblicz-lcp1|algorytm_oblicz_lcp1|
 +
for <math> (int\ \ i=1; i<=n; i++)\ \  R[SUF[i]] = i;</math>
 +
<math>l = 0;</math>
 +
for <math> (int\ \ i=1; i<=n; i++</math>) <math> \{ </math>
 +
  if <math> (R[i] > 1)\ \{</math>
 +
      while <math> (x[l+i] == x[l+SUF[R[i]-1]])\ \ l++</math>;
 +
      <math>lcp[R[i]-1] = l;\ \}</math>
 +
  <math>l = max(0, l-1);\}</math>
 
}}
 
}}
  
Pozostawimay jako ćwiczenie dowód tego, że
 
  
<math>lcp'[k]\ge lcp'[k-1]-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ść prefiksów odpowiednich słów startując od pozycji <math>t</math>. W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potem idziemy  ''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.
+
 
 +
Pozostawiamy jako ćwiczenie dowód tego, że
 +
 
 +
<center> <math>lcp'[k]\ge lcp'[k-1]-1</math>. </center>
 +
 
 +
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ść prefiksów odpowiednich słów startując od pozycji <math>t</math>. W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potem idziemy  ''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.
  
 
==Słownik podsłów bazowych i konstrukcja tablicy sufiksowej w czasie ''O(n log n)''==
 
==Słownik podsłów bazowych i konstrukcja tablicy sufiksowej w czasie ''O(n log n)''==
  
Opiszemy uproszczoną wersję algorytmu  Karpa-Millera-Rosenberga (w skrócie algorytmu ''KMR'') rozwiązywania problemów tekstowych metodą ''słownika podsłów bazowych''. 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 segment <math>k</math>-bazowy  rozumiemy segment tekstu <math>x[i..i+2^k-1]</math>  długości <math>2^k</math> lub kończący się na <math>x_{n+1}</math>.  
+
Opiszemy uproszczoną wersję algorytmu  Karpa-Millera-Rosenberga (w skrócie algorytmu ''KMR'') rozwiązywania problemów tekstowych metodą ''słownika podsłów bazowych''. Ustalmy pewnie tekst <math>x</math> długości <math>n</math>.  
 +
 
 +
Zakładamy w tej sekcji, że dodatkowym symbolem jest <math>x_{n+1}=\#</math>, leksykograficznie najmniejszy symbol. Przez segment <math>k</math>-bazowy  rozumiemy segment tekstu <math>x[i..i+2^k-1]</math>  długości <math>2^k</math> lub kończący się na <math>x_{n+1}</math>.  
  
 
Teoretycznie moż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>.
 
Teoretycznie moż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>.
Linia 195: Linia 226:
 
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>.
 
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>.
  
<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>
+
<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 liczbami naturalnymi z przedziału <math>[1..n]</math>) dwóch podsłów długości <math>2^k</math> . </center>
 +
 
  
 
'''Opis jednej iteracji <math>  (transformacja: NAZWA_k\ =>\ NAZWA_{k+1}</math>)'''
 
'''Opis jednej iteracji <math>  (transformacja: NAZWA_k\ =>\ NAZWA_{k+1}</math>)'''
  
  
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>
+
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>
  
 
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). Wartością <math>NAZWA_{k+1}[i]</math> jest kod pary <math>(NAZWA_k[i],NAZWA_k[i+2^k])</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). Wartością <math>NAZWA_{k+1}[i]</math> jest kod pary <math>(NAZWA_k[i],NAZWA_k[i+2^k])</math>.
Linia 212: Linia 244:
 
== Konstrukcja tablicy ''SUF'' w czasie ''O(n)'': algorytm KS ==
 
== 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 <math>n \log n</math> (mający liczne iine zastosowania, ale jako całość być moe niepotrzbny przy
+
Opiszemy teraz błyskotliwy algorytm Karkkainena-Sandersa ( w skrócie ''KS'') będący zoptymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR oblicza znacznie więcej niż tablica sufiksowa, ponieważ konstruuje słownik podsłów bazowych wielkości <math>n \log n</math> (mający liczne inne zastosowania, ale jako całość być może niepotrzebny przy
liczeniu tablicy sufisksowej)
+
liczeniu tablicy sufiksowej)
 +
 
 +
Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny. Rozbijmy zbiór  pozycji [1..n] tekstu <math>x</math>  na dwa zbiory N, M  :
  
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>:
+
Zbiór  N składa się z co trzeciej pozycji, a M jest zbiorem pozostałych pozycji.
  
N składa się z co trzeciej pozycji, a więc N = {3,6,9,....}, M jest zbiorem pozostałych pozycji.
+
<center>  N = {3,6,9,12,15,....}, M = {1,2,4,5,7,8,10,11,...} </center>
  
 
Przez <math>SUF[M]</math>, oznaczmy tablicę sufiksową dla pozycji ze zbioru <math>M</math>, podobnie zdefiniujmy <math>SUF[N]</math>.  
 
Przez <math>SUF[M]</math>, oznaczmy tablicę sufiksową dla pozycji ze zbioru <math>M</math>, podobnie zdefiniujmy <math>SUF[N]</math>.  
Linia 223: Linia 257:
 
<math>SUF[M]</math> daje posortowany ciąg sufiksów zaczynających się na pozycjach ze zbioru <math>M</math>.
 
<math>SUF[M]</math> daje posortowany ciąg sufiksów zaczynających się na pozycjach ze zbioru <math>M</math>.
  
Dla początkowego przykładowego tekstu <math> x\ =\ babaabababba\# </math> mamy
+
Dla początkowego przykładowego tekstu <math> x= babaabababba\# </math> mamy <br>
  
<center> <math> M\ =\ \{1,2,4,5,7,8,10,11\}\ \ \ N\ =\ \{3,6,9,12\}</math>  </center>
 
  
<center> <math>SUF[M]\ =\ [4,\ 2,\ 5,\ 7, \ 1,  \ 8,\ 11,\ 10]</math> oraz
+
<center> <math> M= \{1,2,4,5,7,8,10,11\}\ \ \ \ \ N= \{3,6,9,12\}</math>  </center>  <br>
<math>SUF[N]\ =\ [ 9,\ 12,\ 3,\ 6,]</math></center>
+
 
 +
<center> <math>SUF[M]=  [4,\ 2,\ 5,\ 7, \ 1,  \ 8,\ 11,\ 10]\ \ \ \ SUF[N]=  [ 9,\ 12,\ 3,\ 6,]</math></center>
 
<br>
 
<br>
  
''' Redukcja liczenia <math>SUF[M]</math> do liczenia tablicy sufiksowej rozmiaru <math>\frac{2}{3}n</math>'''  
+
''' Sprowadzenie obliczania <math>SUF[M]</math> do obliczania tablicy sufiksowej rozmiaru <math>\frac{2}{3}n</math>'''  
  
  
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.
+
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ńczy 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 dzielnikiem n.
  
 
Tworzymy nowe słowo <math>compress(x)</math> w następujący sposób:
 
Tworzymy nowe słowo <math>compress(x)</math> w następujący sposób:
  
<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>
+
<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>
 +
 
 +
<math> y2= kod(a_2a_3a_4)\cdot kod(a_5a_6a_7) \ldots kod(a_{n-1}a_{n}a_{n+1})</math>
 +
 
 +
<math>compress(x)= y1\ \& \ y2\ ;</math> gdzie <math>\&</math> jest nowym maksymalnym symbolem  </center>
 +
 
 +
<br><br> '''Przykład'''. Weźmy początkowy przykład <math>x\ = \ babaababbba\#</math>, gdzie <math>\#</math>jest większe niże a,b. Mamy
 +
 
 +
<center> <math> aab \prec aba\prec bab \prec ba\# \prec bba</math>,</center>
 +
 
 +
Zatem kody tych trójek są kolejno
 +
<math> 1,\ 2,\ 3,\ 4, \ 5</math>.
  
<math> y2\ =\ kod(a_2a_3a_4)\cdot kod(a_5a_6a_7) \ldots kod(a_{n-1}a_{n}a_{n+1})</math>
+
Oznaczmy<math> kod(z)=<z> </math>. Wtedy
  
<math>compress(x)\ =\ y1\ \#\ y2</math></center>
+
<center> <math> y1= <bab><aab><aba><bba>= 3\ 1\ 2\ 5  ;</math></center>  
  
 +
<center> <math>  y2= <aba><aba><bab><ba\#>= 2\ 2\ 3\ 4</math></center>
 +
<br>
  
Symbol # jest tutsj (jak poprzednio) leksykograficznie najmniejszy.
+
<center> <math> compress(x) = = 3\ 1\ 2\ 5 \ \&\ 2\ 2\ 3\ 4</math>,</center>
 
<br>
 
<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.
+
 
 +
<br>
 +
Jeśli mamy tablicę sufiksową dla słowa <math>compress(x)</math>, można łatwo obliczyć <math>SUF[M]</math> w czasie liniowym.
 
Pozostawiamy to jako ćwiczenie.
 
Pozostawiamy to jako ćwiczenie.
  
{{algorytm|<math> {\Large KS} </math> (Karkkainen-Sanders)|algorytm_KS|  
+
 
 +
 
 +
{{algorytm|<math> KS </math> (Karkkainen-Sanders)|algorytm_KS|  
 
1. <math>x' := compress(x)</math>;  
 
1. <math>x' := compress(x)</math>;  
  
 
2. obliczamy tablicę sufiksową dla x' rekurencyjnie;  
 
2. obliczamy tablicę sufiksową dla x' rekurencyjnie;  
  
3. obliczamy <math>SUF[M]</math> wczasie liniowym, znając tablicę sufiksową dla x';  
+
3. obliczamy <math>SUF[M]</math> w czasie liniowym, znając tablicę sufiksową dla x';  
  
4. obliczamy <math>SUF[N]</math> w czasie liniowym (bez rekursji)znając <math>SUF[M]</math>;
+
4. obliczamy <math>SUF[N]</math> w czasie liniowym (bez rekursji), znając <math>SUF[M]</math>;
  
5. scalamy posortowane ciągi  <math>SUF[M],\ SUF[N]</math> w tablicę sufiksową dla całego słowasłowa <math>x</math>
+
5. scalamy posortowane ciągi  <math>SUF[M],\ SUF[N]</math> w tablicę sufiksową dla całego słowa <math>x</math>
  
 
}}
 
}}
  
Krok 1 algorytmu sprowadza się do ''radix-sort''u, podobnie jak w algorytmie KMR.Kroki 3,4 są proste i pozostawiamy czytelnikowi jako ćwiczenie.
+
Krok 1 algorytmu sprowadza się do ''radix-sort''u, podobnie jak w algorytmie KMR. Kroki 3,4 są proste i ich implementację pozostawiamy czytelnikowi 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 <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.
+
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.
  
Pokażemy na przykładzie kluczową operację porównania sufiksu typu M z sufiksem typu N w czasie stałym.
+
Pokażemy na przykładzie kluczową operację porównania sufiksu typu M z sufiksem typu N w czasie stałym.
  
 
{{przyklad|||
 
{{przyklad|||
Nierównośc <math>sufiks_2< sufiks_{12}</math> jest równoważna temu że zachodzi co najmniej jeden z warunków:
+
Nierówność <math>sufiks_2< sufiks_{12}</math> jest równoważna temu, że zachodzi co najmniej jeden z warunków:
  
 
1. <math> (a_2 < a_{12}) </math>  <br>  
 
1. <math> (a_2 < a_{12}) </math>  <br>  
Linia 281: Linia 332:
  
  
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>
+
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.
+
Rozwiązaniem jest <math>T(n)=O(n)</math>. Mamy więc 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, bez korzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena).
+
Istnieje kilka interesujących algorytmów, które konstruują drzewo sufiksowe w czasie liniowym, bez korzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena). W algorytmach tych współczynnik przy złożoności liniowej wynosi \log |A| , gdzie A jest alfabetem.

Aktualna wersja na dzień 12:52, 9 cze 2020


Najważniejszymi strukturami danych związanymi z tekstami są te, które dotyczą efektywnej reprezentacji zbioru wszystkich podsłów tekstu. Przed wszystkim interesuje nas to, żeby taka reprezentacja przyspieszała wyszukiwanie słów, a jednocześnie żeby była konstruowalna w czasie liniowym albo prawie liniowym (z dokładnością do logarytmów).

Oznaczmy przez wszystkie podsłowa tekstu , a wszystkie wystąpienia (początkowe pozycje) słowa w słowie oznaczmy przez . (Oznaczenie jest skrótem od ang. occurrences).

Chcemy znaleźć taką reprezentację zbioru , by można było łatwo odpowiedzieć na pytanie, czy , co jest równoważne , jak również rozwiązywać inne problemy tekstowe. Poza tym chcemy, by rozmiar tej reprezentacji był liniowy, podczas gdy rozmiar może być kwadratowy. Spośród wielu dobrych reprezentacji najbardziej znanymi są tablice sufiksowe (oznaczane przez ), drzewa sufiksowe i grafy podsłów (nie rozważane w tym module).

Tablice i drzewa sufiksowe

Niech i niech będzie specjalnym znakiem leksykograficznie większym od każdego innego symbolu 9w przyszłości będziemy również używać jako najmniejszego symbolu).

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

Niech będzie pozycją, od której zaczyna się k-ty leksykograficznie sufiks x. Sufiks zaczynający się na pozycji -szej nie jest brany pod uwagę.

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


Zasd 2 1.jpg


Rysunek 1: Tablicą sufiksową tekstu jest ciąg

Oznaczmy przez długość wspólnego prefiksu -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 .
Tablica sufiksowa ma następująca ‘’sympatyczną’’ własność: Niech

, .

Wtedy jest przedziałem w tablicy sufiksowej od do .

Drzewo sufiksowe jest drzewem, w którym każda ścieżka jest etykietowana kolejnymi symbolami pewnego sufiksu, oraz każdy sufiks 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 . 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 : para liczb reprezentuje podsłowo (zobacz prawe drzewo na rysunku). Dzięki temu reprezentacja ma rozmiar . Wagą krawędzi jest długość odpowiadającego jej słowa.

Zasd 2 2.jpg


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


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

Szukanie podsłów

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

Używając drzewa sufiksowego (czas )

Idziemy od korzenia w dół czytając kolejne symbole , czasami posuwamy się po wewnętrznej etykiecie pewnej krawędzi. Zbiór wystąpień 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, oznacza to, że

Używając tablicy sufiksowej (czas )

Możemy sprawdzić, czy jest prefiksem -tego sufiksu w czasie . 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 . W przeciwnym wypadku z nie jest podsłowem x.

Podobnie znajdujemy ostatni sufiks. Zbiór wystąpień odpowiada przedziałowi w tablicy między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od z.

Wyznaczanie liczby podsłów

Pokażemy, jak znaleźć liczbę podsłów słowa przy pomocy tablicy sufiksowej lub drzewa sufiksowego. Końcowego markera nie traktujemy jako części słowa . Liczba podsłów jest równa . Jeśli wszystkie symbole słowa są różne to .

Używając drzewa sufiksowego, czas


Sumujemy wagi krawędzi drzewa.

Używając tablicy sufiksowej, czas

Niech będzie sumą elementów tablicy . Liczbę podsłów obliczamy jako



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 tekstu mamy . Proponujemy to wyliczyć z tablicy sufiksowej i drzewa sufiksowego dla, danego na rysunku. Suma elementów tablicy wynosi 23. Liczba podsłów to:

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

Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu obliczania tablicy , przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.


Dygresja. Ciekawą klasę słów, dla których tablice są szczególnie interesujące, stanowią słowa Fibonacciego . W tym szczególnym przypadku załóżmy, że pozycje numerujemy od zera. Dla każdego tablica jest postępem arytmetycznym (modulo długość słowa). Natomiast tablica jest postępem arytmetycznym, gdy jest parzyste.


Słowa Fibonacciego definiujemy następująco: Na przykład: Oznaczmy przez tablicę dla słowa Fibonacciego ; wtedy:


Pozostawiamy jako ćwiczenie znalezienie wzoru na .

Drzewa sufiksowe =>tablice sufiksowe

W celu znalezienia początkowych pozycji sufiksów w porządku leksykograficznym przechodzimy drzewo sufiksowe metodą DFS, zakładając, że dla każdego węzła lista jego synów jest w kolejności leksykograficznej etykiet krawędzi prowadzących do synów. Wystarczy sprawdzać pierwsze 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 konstruktywnie następujący istotny fakt:

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

Przypuśćmy, że , a więc:


Algorytm Drzewo-Sufiksowe


1   drzewo reprezentujące  (jedna krawędź);
2  for  to  do
3    wstaw nową ścieżkę o sumarycznej etykiecie  do ; 


Zasd 2 3.jpg
Rysunek 3: Wstawianie kolejnego sufiksu do drzewa sufiksowego, przed włożeniem wszystkie krawędzie ścieżki roboczej od 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ść tekstu, który ten węzeł reprezentuje (jako pełna etykieta od korzenia do węzła).

Niech będzie poprzednio wstawionym sufiksem, a ostatnio utworzonym liściem.

Wtedy wstawienie polega na znalezieniu maksymalnego wspólnego prefiksu tekstów , . Niech . Znajdujemy węzeł odpowiadający ścieżce od korzenia etykietowanej .

Kluczowym pomyslem algorytmicznym jest tutaj to, że węzła szukamy nie od korzenia, ale od ostatnio utworzonego liścia . Jeśli takiego węzła nie ma (jest wewnątrz krawędzi) to go tworzymy. Następnie tworzymy nowy liść odpowiadający sufiksowi , oraz krawędź etykietowaną .


Z tablicy odczytujemy długość .

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

Przechodząc drzewo posuwamy się po węzłach drzewa, przeskakując (w czasie stalym) 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. jest najdłuższym wspólnym prefiksem słów i . Kluczowe znaczenie w operacji ma znajomość wartości . Wiemy kiedy się zatrzymać idąc do góry od węzła w kierunku korzenia.

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

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

Zasd 2 4.jpg


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



Zasd 2 5.jpg
Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu .



Obliczanie tablicy lcp

Niech będzie pozycją w porządku leksykograficznym. W naszym przykładowym słowie mamy:

Niech .

Załóżmy, dla uproszczenia, że oraz że tekst kończy się specjalnym symbolem Obliczamy tablice następująco:


Algorytm Oblicz-lcp


1  for  to  do
2    oblicz  korzystając z faktu, że ; 
3    // koszt iteracji 
4  for  to  do
 5     

Można to zapisać w języku C++ następująco

Algorytm Oblicz-lcp1


for 

for ) 
  if 
      while ;
      
  



Pozostawiamy jako ćwiczenie dowód tego, że

.

Jeśli , to obliczamy sprawdzając symbol po symbolu (od lewej do prawej) zgodność prefiksów odpowiednich słów startując od pozycji . W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potem idziemy 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.

Słownik podsłów bazowych i konstrukcja tablicy sufiksowej w czasie O(n log n)

Opiszemy uproszczoną wersję algorytmu Karpa-Millera-Rosenberga (w skrócie algorytmu KMR) rozwiązywania problemów tekstowych metodą słownika podsłów bazowych. Ustalmy pewnie tekst długości .

Zakładamy w tej sekcji, że dodatkowym symbolem jest , leksykograficznie najmniejszy symbol. Przez segment -bazowy rozumiemy segment tekstu długości lub kończący się na .

Teoretycznie możemy założyć, że po symbolu mamy bardzo dużo takich symboli na prawo i każdy segment startujący w ma dokładnie długość .


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

, , ,.

Zakładamy, że jest pozycją słowa na posortowanej liście (bez powtórzeń) wszystkich podsłów długości słowa . Jeśli długość wystaje poza koniec to przyjmujemy że są tam (wirtualnie) same symbole . Poniżej przedstawiamy przykład słownika podsłów bazowych .

Zasd 2 4a.jpg

Algorytm liczenia tablic Nazwa jest bardzo prosty. Załóżmy od razu, że symbole są ponumerowane leksykograficznie. Wtedy jest zasadniczo równa tekstowi .

Zasd 2 6.jpg
Rysunek6: Słowo rozmiaru otrzymuje najpierw nazwę-kompozycję: kombinacją nazw (będących liczbami naturalnymi z przedziału ) dwóch podsłów długości .


Opis jednej iteracji )


Dla każdego tworzymy nazwę-kompozycję slowa jako

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). Wartością jest kod pary .


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

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

Opiszemy teraz błyskotliwy algorytm Karkkainena-Sandersa ( w skrócie KS) będący zoptymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR oblicza znacznie więcej niż tablica sufiksowa, ponieważ konstruuje słownik podsłów bazowych wielkości (mający liczne inne zastosowania, ale jako całość być może niepotrzebny przy liczeniu tablicy sufiksowej)

Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny. Rozbijmy zbiór pozycji [1..n] tekstu na dwa zbiory N, M :

Zbiór N składa się z co trzeciej pozycji, a M jest zbiorem pozostałych pozycji.

N = {3,6,9,12,15,....}, M = {1,2,4,5,7,8,10,11,...}

Przez , oznaczmy tablicę sufiksową dla pozycji ze zbioru , podobnie zdefiniujmy .

daje posortowany ciąg sufiksów zaczynających się na pozycjach ze zbioru .

Dla początkowego przykładowego tekstu mamy




Sprowadzenie obliczania do obliczania tablicy sufiksowej rozmiaru


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

Tworzymy nowe słowo w następujący sposób:

gdzie jest nowym maksymalnym symbolem



Przykład. Weźmy początkowy przykład , gdzie jest większe niże a,b. Mamy

,

Zatem kody tych trójek są kolejno .

Oznaczmy. Wtedy


,



Jeśli mamy tablicę sufiksową dla słowa , można łatwo obliczyć w czasie liniowym. Pozostawiamy to jako ćwiczenie.


Algorytm (Karkkainen-Sanders)


1. ;

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

3. obliczamy w czasie liniowym, znając tablicę sufiksową dla x';

4. obliczamy w czasie liniowym (bez rekursji), znając ;

5. scalamy posortowane ciągi w tablicę sufiksową dla całego słowa


Krok 1 algorytmu sprowadza się do radix-sortu, podobnie jak w algorytmie KMR. Kroki 3,4 są proste i ich implementację pozostawiamy czytelnikowi 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 lub oba są typu , 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ść jest równoważna temu, że zachodzi co najmniej jeden z warunków:

1.
2.
3.


Jednakże , zatem i , są typu M i można je porównać w czasie stałym.


Niech będzie czasem działania algorytmu KS. Zachodzi

Rozwiązaniem jest . Mamy więc 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, bez korzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena). W algorytmach tych współczynnik przy złożoności liniowej wynosi \log |A| , gdzie A jest alfabetem.