Zaawansowane algorytmy i struktury danych/Wykład 2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Rytter (dyskusja | edycje)
830 edycji
Tprybick (dyskusja | edycje)
718 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
<font size="7">Zaawansowane algorytmy tekstowe II</font>
<font size="6"> Algorytmy tekstowe II </font>


__TOC__
__TOC__  


Poprzednie algorytmy dokonywały jedynie na tekstach wejściowych operacji sprawdzania symboli na równość.
Załóżmy teraz, że alfabet jest liniowo uporządkowany. Pokażemy, że  porównywanie symboli w sensie
porządku liniowego można istotnie wykorzystać w algorytmach tekstowych. Porządek liniowy na symbolach
implikuje {\em porządek  leksykograficzny} na słowach, na przykład:
<center><math> ab < ababab < abb < abbaa < abbaaaaaaaaaaa < abbaaaaaab</math></center>


== Równoważność cykliczna słó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'').
Pokażemy problem, który prawdopodobie najlepiej pokazuje użyteczność porządku liniowego na alfabecie.
Rotacją słowa <math>u=u[1..n]</math> jest kaz'rde słowo postaci <math>u^{(k)}\ =\ u[k+1.. n]u[1.. k]</math>. (w szczególności
<math>u^{(0)}=u^{(n)}=u)</math>. Niech <math>u,w</math> będą słowami długości <math>n</math>, mówimy, że są one cyklicznie równoważne
gdy  <math>u^{(i)}=w^{(j)}</math> dla pewnych  <math>i,j</math>.


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 problemytekstowe. Poza tym chcemy by rozmiar tej eprezentacji był liniowy, podczas gdy rozmiar <math>Subwords(x)</math> może być kwadratowy.
Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa <math>u</math> w słowie <math>ww</math>, ale podamy
Spośród wielu dobrych reprezentacji najbardziej znanymi są tablice sufiksowe (oznaczane przez<math>SUF</math>) i drzewa sufiksowe.
algorytm znacznie prostszy bazujący , który  będzie działal  w czasie liniowym i {\em w miejscu} (dodatkowa
pamięć jest stała).    W algorytmie roszerzamy tablicę <math>u,w</math> na <math>uu,\ ww</math> ale robimy to jedynie dla
uproszczenia, w rzeczywistości możemy poruszać się cyklicznie po <math>u</math> i po <math>w</math>, pozostawiamy modyfikację jako
ćwiczenie.  


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.
{{algorytm|Równoważność-Cykliczna|algorytm_rownowaznosc_cykliczna|
<math>x:=uu</math>; <math>y:=ww</math>;<br>
<math>i:=0</math>; <math>j:=0</math>;<br>
'''while''' <math>(i<n)</math> '''and''' <math>(j<n)</math> '''do'''<br>
&nbsp;&nbsp;&nbsp;<math>k:=1</math>;<br>
&nbsp;&nbsp;&nbsp;'''while'''<math>x[i+k]=y[j+k]</math> '''do''' <math>k:=k+1</math>;<br>
&nbsp;&nbsp;&nbsp;'''if''' <math>k>n</math> '''then return''' true;<br>
&nbsp;&nbsp;&nbsp;'''if''' <math>x[i+k]>y[i+k]</math> '''then'''<math>i:=i+k</math> '''else''' <math>j:=j+k</math>;<br>
'''return''' false;<br>
}}


Oznaczmy przez <math>sufiks_{i}=a_{i}a_{i+1}\dots a_{n}</math>sufiks tekstu x zaczynający się na pozycji i-tej.  
Zdefiniujmy:
<center>
<math>D(u)=\{k:1\leq k\leq n</math> oraz <math>u^{(k)}>w^{(j)}</math> dla pewnego <math>j\}</math>,<br>
<math>D(w)=\{k:1\leq k\leq n</math> oraz <math>w^{(k)}>u^{(j)}</math> dla pewnego <math>j\}</math>.
</center>


Niech <math>SUF[k]</math> będzie pozycją od której zaczyna się k-ty leksykograficznie sufiks x.  
Skorzystamy z prostego faktu:
Jeśli <math>D(u)=[1.. n]</math> lub <math>D(w)=[1.. n]</math>, to <math>u,w</math> nie są równoważne.  


Sufiks zaczynający się na pozycji <math>(n+1)</math>-szej nie jest brany pod uwagę.  
Uzasadnienie pozostawiamy jako ćwiczenie. Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:
<center>
<math>D(w)\supseteq [1.. i]</math>\ oraz \ <math>D(u)\supseteq [1.. j]</math>.</center>


Ciąg sufiksów posortowany leksykograficznie wygląda następująco:
Liczba porównań jest oczywiście liniowa. Pozostawiamy jako ćwiczenie policzenie dokładnego wzoru na maksymalną liczbę porównań symboli dla tekstów długości <math>n</math>.


<center><math>sufix_{SUF[1]}< sufix_{SUF[2]}<sufix_{SUF[3]}<\ldots sufix_{SUF[n]}</math></center>
== String-matching w pamięci stałej dla specjalnych wzorów ==




[[Grafika:Zasd_2_1.jpg]]
Oznaczmy przez <math>MaxSuf(w)</math> maksymalny leksykograficznie sufiks słowa <math>w</math>. Słowo <math>x</math> nazwiemy specjalnym gdy <math>MaxSuf(x)=x</math>.  


Rysunek 1: Tablicą sufiksową tekstu <math>x\ =\ babaabababba\#</math> jest ciąg  <math>SUF\ =\  [4,\ 2,\ 5,\ 7,\ 9,\ 12,\ 3,\ 1,\ 6,\6,\ 8,\ 11,\ 10]</math>
{{przyklad|||
<br>
'bajtocja' nie jest słowem specjalnym, ale rotacja tego słowa 'tocjabaj' jest.}}
Oznaczmy przez <math>lcp[k]</math> długść wspólnego prefisku <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 miłą własność: Niech


<math>min_{z}=\min\{k : z  \mbox{ jest prefiksem }  sufiks_{SUF[k]}\}</math>,
<math>max_{z}=\max\{k : z  \mbox{ jest prefiksem }  sufiks_{SUF[k]}\}</math>.


Wtedy <math>Occ(z,x)</math> jest przedziałem w tablicy sufiksowej od <math>min_{z}</math> do <math>max_{z}</math>.
Dlaczego słowa o tej własności  są interesujące ? Większość szybkich algorytmów szukania podsłów korzysta z okresów <math>p</math> prefiksów słowa. Liczenie tych okresów w ogólnym przypadku jest ''wąskim gardłem'' w projekcie algorytmu. Natomiast dla słow specjalnych  liczenie okresów jest trywialne.


'''Drzewo sufiskowe''' 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.
Jeśli <math>x</math> jest specjalny to okres każdego prefiksu słowa <math>x</math> można policzyć następującym naiwnym
 
algorytmem;
 
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.
 
[[Grafika: Zasd_2_2.jpg]] <br> Rysunek 2: Drzewo sufiksowe dla tekstu <math>x\ =\ babaabababba</math>. Na końcu jest dodany zank <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śći n. Z reguły <math>m << n</math>.
 
=== Szukanie podsłów===
 
Pokażemy jak sprawdzać, czy <math>z</math> występuje w <math>x</math>.
 
'''Używając drzewa sufiskowego''' (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"n 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>
 
'''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 przeciwym wypadku z nie jest podsłowem x.
 
Podobnie znajdujemy ostatni sufiks. Zbiór wystąpie"nodpowiada przedziałowi w tablicy <math>SUF</math> 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 <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>.
 
'''Używając drzewa sufiskowego''', czas <math>O(n)</math>
 
<br>Sumujemy wagi krawędzi drzewa.
 
'''Używając tablicy sufiksowej''', czas <math>O( n)</math>
 
Niech <math>SUMA(lcp)</math> będzie sumą elementów tablicy <math>lcp</math>. Liczbę podsłów obliczamy jako
 
 
<center><math>{n+1\choose{2}}-SUMA(lcp)</math></center>
 
 
Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona (korzystając z drzewa sufisowego lub z tablicy sufiksowej).


{{ algorytm| Funkcja Naiwne-Liczenie-Okresu (j)|funkcja_naiwne_liczenie_okresu|
<math>period:=1</math>;<br>
'''for''' <math>i:=2</math> to <math>j</math> '''do'''<br>
&nbsp;&nbsp;&nbsp;'''if''' <math>x[i] \ne x[i - period]</math> '''then''' <math>period := i</math>;<br>
'''return''' <math>period</math>;<br>
}}


{{przyklad|||
{{przyklad|||
Dla przykładowego <math>x\ =\babaabababba</math> mamy <math>|Subwords(x)|=55</math>. Proponujemy to wyliczyć z tablicy sufiksowej i drzewa sufiskowego 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>}}
Funkcja ''Naiwne-Liczenie-Okresu'' daje zły wynik dla tekstów które nie są specjalne, na przykład  załóżmy że <center>
 
<math>x= (aba)^6a = abaabaabaabaabaabaa</math>.} </center> Wtedy kolejne wartości okresów dla pozycji <math>j=1,2,..</math>
Podobnie jak tablicę sufiksową możemy zdefiniować tablicę <math>ROT</math> odpowiadającą posortowanemuciągowi wszystkich cyklicznych przesunięć słowa <math>x</math> (rotacji <math>x</math>).
są:
 
<center>
Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu liczącego tablicę <math>ROT</math>, zakładając, że mamy liniowy algorytm liczeniatablicy sufiksowej.
<table>
 
<tr>
 
<td>a</td>
'''Dysgresja.''' Ciekawą klasą słów dla których tablice <math>SUF,\ ROT</math> sąszczególnie interesujące są słowa Fibonacciego <math>F_n</math>. W tym szczególnym przypadku załóżmy, że pozycjenumerujemy 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.
<td>b</td>
 
<td>a</td>
 
<td>a</td>
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:
<td>b</td>
<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>
<td>a</td>
 
<td>a</td>
 
<td>b</td>
Pozostawiamy jako ćwiczenie policzenie wzoru na <math>|Subwords(F_n)|</math>.
<td>a</td>
 
<td>a</td>
== Drzewa sufiksowe =>tablice sufiksowe ==
<td>b</td>
 
<td>a</td>
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.
<td>a</td>
 
<td>b</td>
Załóżmy, że w liściach mamy początki sufiksów, które do nich prowadzą.
<td>a</td>
 
<td>a</td>
Kolejność odwiedzania liści w naszym przejściu metodą DFS automatycznie generuje elementy tablicy sufiksowej.
<td>b</td>
<td>a</td>
<td>a </td>
</tr>
<tr>
<td>
1</td>
<td>2</td>
<td>2</td>
<td>4</td>
<td>5</td>
<td>5</td>
<td>7</td>
<td>8</td>
<td>8</td>
<td>10</td>
<td>11</td>
<td>11</td>
<td>13</td>
<td>14</td>
<td>14</td>
<td>16</td>
<td>17</td>
<td>17</td>
<td>19
</td>
</tr>
</table>
</center>
}}


== Tablice sufiksowe =>drzewa sufiksowe ==
Zatem ''Naiwne-Liczenie-Okresu''<math>(19)\ =\ 19</math>, dla  <math>x\ = \ (aba)^6a</math>, wynik całkowicie niepoprawny. Poprawność algorytmu jest wyjaśniona na rysunku. Korzystamy z prostej własności, że prefiks specjalnego słowa jest też specjalny.
Pokażemy konstruktywanie 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.
<center>[[Grafika:Naiwneliczenieokresu.jpg]]<br>
Rysunek 1: Załóżmy, że w algorytmie  ''Naiwne-Liczenie-Okresu'' <math>x[i-period(i-1)] \ne x[i]</math>.  Niech
<math>a=x[i]</math>, <math>b=x[i-period]</math>. Ponieważ <math>uz</math> jest prefiksem  słowa specjalnego <math>x</math> zatem  <math>a <b</math>. Gdyby
<math>period(i)<i</math> to wtedy, ze względu na dwie okresowości,
<math>zb</math> jest właściwym podsłowem słowa  <math>x[1.. i-1]</math> oraz <math>zb>x</math>.
Zaprzecza to założeniu, że <math>x</math> jest specjalne. Zatem <math>period(i)=i</math>.
</center>


Przypuśćmy, że,  
Opiszemy teraz program szukania wzorca <math>x</math>  w slowie <math>y</math>i, zakładając że x jest sepcjalne.
<math>SUF\ =\ [i_1,i_2,\ldots,i_n]</math>, a więc:
Program wczytuje dwa teksty, pierwszy z nich jest specjalne:  <math>x</math> pamiętamy w tablicy <math>x[0..m-1]</math>, <math>y</math> w
<center><math> sufiks_{i_1}< sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.</math></center>
tablicy <math>y[0..n-1]</math>.
Program wypisuje wszystkie wystapienia <math>x</math> w <math>y</math>, tzn. wszystkie takie pozycje
<math>i</math>, ze <math>y[i\ldots i+m-1]\ =\ x</math>. Zapisujemy program w języku C++.
{{algorytm|Specjalny-String-Matching|algorytm_specjalny_string_matching|
#include <iostream.h><br>
#include string.h<br>
int i=0,j=0,p=1;<br>
void przesun();<br>
main() {<br>
char[] x,y; cin>>x>>y; m=strlen(x); n=strlen(y);<br>
while (i <= n-m-1)<br>
&nbsp;&nbsp;&nbsp;{ if (j==m) {cout<<i<<endl;  przesun();};<br>
&nbsp;&nbsp;&nbsp;&nbsp;else if (x[j)==y[i+j] {j=j+1; if (j==1)||(x[j-1]!=x[j-1-p]) p=j;};<br>
&nbsp;&nbsp;&nbsp;&nbsp;else  przesun();  }}<br>




void przesun()
{ if (j-1<2p) {i=i+p; j=0;} else {j=j-p; i=i+p;}}


{{algorytm|Drzewo-Susfiksowe|algorytm_drzewo_susfiksowe|
<math>T :=</math> drzewo reprezentujące <math>sufiks_{i_1}</math> (jedna krawędź);<br>
'''for''' <math>k:=2</math> '''to''' <math>n</math> '''do'''<br>
&nbsp;&nbsp;&nbsp;wstaw nową ścieżkę o sumarycznej etykiecie <math>sufiks_{i_k}</math> do <math>T</math>;
}}
}}


Program jest wstępem do programu szukajacego dowolne posłowo, niekoniecznie o wlasnosci bycia
specjalnym. Postawowym niezmiennikiem  w programie przed kazdym wykonaniem i po kazdym zakonczeniu pętli ''while' jest:
'''(A)\ ''' <math>x[0 \ldots j-1]\ =\ y[i \ldots i+j-1]</math>, .
'''(B)\ ''' Program wypisal wszsytkie wczesniejsze wystapienia <math>i' < i</math>,
'''(C)\ ''' <math>p</math> jest okresem slowa <math>x[0 \ldots j-1]</math>


<center> [[Grafika:Zasd_2_3.jpg]]<br> Rysunek 3: Wstawianie kolejnego sufiksu <math>sufiks_{i_k}</math> do drzewa sufiskowego, przed włożeniem wszystkie krawędzie ''ścieżki roboczej'' od <math>u</math> do korzenia  są skierowane w lewo. </center>
Algorytm  działa w czasie liniowym, można to udowodnić obserwując zmiany wartości <math>2i+j</math>, zauważmy, że wartość ta nie zmniejsza się, a w wypadku pozytywnego testu  <math> x[j)==y[i+j]</math>  zwiększa się co najmniej o 1. Jednocześnie <math>2i+j\le 3n</math>.


== String-matching w pamięci stałej dla dowolnych wzorców ==


Opiszemy w jaki sposób wstawiamy kolejny sufiks <math>\beta</math> 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).
Algorytym Specjalny-String-Matching  można  łatwo
zmodyfikować tak, aby znajdował on wystąpinia dowolnego słowa (niekoniecznie specjalnego) w czasie liniowym i
stałej pamięci.
Niech <math>x = uv</math>, gdzie <math>v</math> jest leksykograficzne maksymalnym sufiksem <math>x</math>. Oznaczmy <math>r=|u|</math>. Technicznie
informacja o rozkładzie <math>uv</math> sprowadza się do pamiętania <math>r</math>.


Niech <math>\alpha</math> będzie poprzednio wstawionym sufiksem, a <math>u</math> ostatniopoprzednio 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 gotworzymy. 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>.
'''Własność rozkładu. '''Niech <math>x=uv</math> będzie rozkładem jak wyżej opisany. Wtedy
Słowo <math>v</math> występuje tylko raz w słowie <math>uv</math>.
Jeśli <math>i'<i</math> są początkami wystąpień <math>v</math>, oraz <math>i-i'<r</math> to
na pozycji <math>i-1</math> nie kończy się wystąpienie <math>u</math>.




Z tablicy <math>lcp</math> odczytujemy długość <math>\gamma_1</math>.  
Z powyższego faktu wynika stosunkowo prosty algorytm szukania <math>x</math> w czasie loiniowym i pamięci
stałej. Algorytm ten jest modyfikacja agorytmu Specjalny-String-Matching , w ktorym rolę <math>x</math> pełni <math>v</math>.


W celu obliczenia <math>v</math> posuwamy się ścieżką od <math>u</math> w górę drzewa, aż znajdziemy węzeł oddalony od korzenia o <math>|\gamma|</math>.
{{algorytm |String-matching w pamięci stałej|algorytm_string_matching_pam_st|
Przechodząc drzewo posuwamy się po węzłach drzewa, przeskakując potencjalnie długie teksty na krawędziach.
Niech <math>v</math> będzie  leksykograficznie maksymalnym sufiksem <math>x</math>;


Liczymy  algorytmem Specjalny-String-Matching  kolejne wystąpienia <math>v</math> w <math>y</math>;


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.
Dla każdego wystąpienia <math>i</math> niech <math>i'</math> będzie wystąpieniem poprzednim;


Lokalnie wykonana praca w jednej iteracji jest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego. W sumie praca jest liniowa.
jeśli <math>i-i' \ge |v|</math> to sprawdź czy <math>u</math> występuje na lewo od pozycji <math>i</math>;


Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.
(sprawdzanie to wykonujemy w sposób naiwny)


<center> [[Grafika:Zasd_2_4.jpg]] <br> Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu
jeśli występuje to wypisz kolejne wystąpienie całego wzorca <math>x</math>.
<math>babaabababba\#</math>. </center>
}}


<center> [[Grafika:Zasd_2_5.jpg]] <br> Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu <math>babaabababba\#</math>. </center>
Pozostawiamy bardziej precyzyjny zapis algorytmu jako ćwiczenie.


== Oblicanie tablicy ''lcp'' ==
W ten sposób pokazaliśmy, że problem szukania słowa <math>x</math> w słowie <math>y</math> można rozwiązać
w czasie liniowym i pamięci (dodatkowej) stałej, jeśli znamy początkową pozycję <math>r</math>
leksykograficznie maksymalnego sufiksu <math>v</math> słowa <math>x</math>.


Niech <math>rank(i)</math> będzie poycją <math>sufiks_i</math> w porządku leksykograficznym. W naszym przykładowym słowie mamy:
== Liczenie maksymalnego sufiksu w pamięci stałej ==
<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>.
W algorytmie szukanie wzorca w pamięci stałej potrzebna jest pozycja <math>r</math> od której zaczyna się maksymalny
sufiks. Pokażemy teraz jak ją znajdować w czasie liniowym i w pamięci stałej. Kluczem do tego jest liczenie
czegoś więcej, dla każdego prefiksu liczymy maksymalny sufiks jak również dodatkowo jego okres. To własnie
liczenie okresu daje efektywność, chociaż na końcu nam ten okres jest  niepotrzebny.
Przekształcimy najpierw algorytm  ''Naiwne-Liczenie-Okresu'' na algorytm liczący długość najdłuższego
specjalnego prefiksu włącznie z jego okresem.


Załóżmy, dla uproszczenia, że  <math>lcp[0]=0</math>. Obliczamy tablice<math>lcp',\ lcp</math> następująco:
{algorytm| funkcja Najdłuższy-Specjalny-Prefiks(x)|fun_najdl_spec_pref|
<math>period := 1</math>;<br>
'''for''' <math>i:=2</math> to <math>|x|</math> '''do''' <br>
&nbsp;&nbsp;&nbsp;'''if''' <math>x[i] < x[i - period]</math> \textbf{then} <math>period := i</math><br>
&nbsp;&nbsp;&nbsp;'''else if''' <math>x[i] > x[i - period]</math> ''then'''<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''return''' <math>(i-1, period)</math>;<br>
'''return''' <math>(|x|, period)</math>;
}}


Skorzystamy z algorytmu ''Najdłuższy-Specjalny-Prefiks''. Funkcja ''Maksymalny-Sufiks'' liczy początkową pozycję i okres maksymalnego sufiksu.


{{algorytm|Oblicz-lcp|algorytm_oblicz_lcp|
{{algorytm|funkcja Maksymalny-Sufiks(x)|fun_max_suf|
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
<math>j := 1</math>;<br>
&nbsp;&nbsp;&nbsp;oblicz <math>lcp'[k]</math> korzystając z faktu, że <math>lcp'[k]\ge lcp'[k-1]-1</math>; <br>
'''repeat'''<br>
&nbsp;&nbsp;&nbsp;&nbsp;koszt iteracji <math>O(lcp'[k]-lcp'[k-1]+const)</math><br>
&nbsp;&nbsp;&nbsp;<math>(i,period) :=</math> ''Najdłuższy-Specjalny-Prefiks''<math>(x[j.. n])</math>;<br>
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
&nbsp;&nbsp;&nbsp;'''if''' <math>i=n</math> '''then return''' <math>(j, period)</math><br>
&nbsp;&nbsp;&nbsp;<math>lcp[rank[k]-1] := lcp'[k]</math>  
&nbsp;&nbsp;&nbsp;'''else''' <math>j := j+i - (i \mod period)</math>;<br>
 
'''forever''' <br>
}}
}}


Pozostawimay jako ćwiczenie dowód tego, że
Możemy przepisać algorytm Maksymalny-Sufiks tak aby nie wywoływał on funkcji Najdłuższy-Specjalny-Prefiks, wpisując tę funkcję do algorytmu. Arytmetyczna funkcja  <math>\mod</math> może być usunięta i zastąpiona przez operacje dodawania i odejmowania bez zmiany asymptotycznej złożoności.


<math>lcp'[k]\ge lcp'[k-1]-1</math>.  
Algorytm Maksymalny-Sufiks wykonuje co najwyżej <math>2.|x|</math> porównań symboli. Uzasadnienie pozostawiamy jako ćwiczenie.


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ść pefiksów odpowiednich słów startującod pozycji <math>t</math>. 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 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.
{{algorytm| funkcja} Maksymalny-Sufiks(x)|fun_max_suf2|
<math>s := 1</math>;  <math>i := 2</math>;  <math>p := 1</math>;<br>
'''while''' (<math>i \le n</math>) '''do'''<br>
&nbsp;&nbsp;&nbsp;<math>r := (i-s) \mod p</math>;<br>
&nbsp;&nbsp;&nbsp;'''if''' (<math>x[i] = x[s+r])</math> '''then''' <math>i := i+1</math><br>
&nbsp;&nbsp;&nbsp;'''else if''' (<math>x[i] < x[s+r])</math> '''then begin'''
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>i := i+1</math>; <math>p := i-s</math>;
&nbsp;&nbsp;&nbsp;'''else'''
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>s := i-r</math>; <math>i := s+1</math>; <math>p := 1</math>;<br>
'''return''' <math>s</math>;<br>
}}
== Kodowanie prefiksowe: drzewa i kody Huffmana ==


==Konstrukcja tablicy ''SUF'' w czasie ''O(n log n)'': algorytm KMR ==
Zbiór słów jest prefiksowy gdy żadne słowo nie jest prefiksem drugiego. Taki zbiór słów odpowiada drzewu,
którego ścieżki etykietowane są symbolami, w przypadku binarnym możemy przyjąć, że krawędź w lewo jest
etykietowana zerem, a w prawo jedynką.
Przez kodowanie rozumiemy funkcję <math>h</math> która każdemu symbolowi <math>s</math> przyporządkowuje niepusty ciąg binarny
<math>h(s)</math>, całe słowo <math>x</math> zostanie zakodowane na słowo <math>h(x)</math> (każda litera jest zakodowana niezależnie i kody
są ''skonkatenowane''. Kod jest prefiksowy gdy zbiór kodów symboli jest prefiksowy. Rozważamy
następujący problem.


Opiszemy uproszczoną wersję algorytmu  Karpa-Millera-Rosenberga (w skrócie algorytmu ''KMR'') rozwiązywania problemów tekstowych metodą ''słownika bazowego''. 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 segement <math>k</math>-bazowy  rozumiemy segement tekstu <math>x[i..i+2^k-1]</math>  długości <math>2^k</math> lub ko"nczący się na <math>x_{n+1}</math>.


Teoretycznie emoż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>.
===Optymalne kodowanie prefiksowe===
 
Dla danego słowa <math>x</math> znaleźć binarne kodowanie prefiksowe takie,
 
że <math>h(x)</math> ma minimalną długość.
'''Słownik podsłów bazowych''' (w skrócie DBF(x), od ang. ''dictionary of basic factors'')  składa sięz <math>\log n</math> tablic  <br>
 
<math>NAZWA_0</math>, <math>NAZWA_1</math>, <math>NAZWA_2</math>,<math> \ldots NAZWA_{\log n}</math>.
 
Zakładamy, że <math>NAZWA_k[i]</math> jest pozycją słowa <math>x[i..i+2^k-1]</math> na posortowanej liście (bez powtórzeń) wszystkich podsłów długości <math>2^k</math> słowa <math>x</math>. Jeśli długość ''wystaje'' poza koniec <math>x</math> to przyjmujemy że są tam (wirtualnie) same symbole <math>\#</math>. Poniżej przedstawiamy przykład słownika podsłów bazowych  <math>DBF(abaabbaa)</math>.
 
<center> [[Grafika:Zasd_2_4a.jpg]]</center>
 
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>
 
'''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>
 
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). Warością <math>NAZWA_{k+1}[i]</math> jest kod pary <math>(NAZWA_k[i],NAZWA_k[i+2^k])</math>.
 
 
Zauważmy, że tablica sufiksowa odpowiada tablicy <math>NAZWA_{\lceil \log n \rceil}</math>. Możemy to podsumować następująco:
<br>
1. słownik ''DBF(x)'' możemy skonstruować w czasie <math> O(n \log n) </math>i pamięci <math>O(n \log n)</math> (jest to również rozmiar słownika). <br>
2. Tablicę sufiksową możemy otrzymać,stosując algorytm KMR, w czasie <math>O(n \log n)</math> i pamięci <math>O(n)</math>. (Potrzebujemy pamiętać jedynie ostatnie dwie tablice w każdej iteracji.)
 
== 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ć mo¶e niepotrzbny przy
liczeniu tablicy sufisksowej)
 
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>:
 
<center><math> M\ =\ \{1\le i \le n:\ (i-1)\ \textrm{modulo}\ 3 \in \{0,1\}\}\ \ N\ =\ \{1,2,..,n\}-M</math></center>
 
Przez <math>SUF[M]</math>, oznaczmy tablicę sufiksowądla pozycji ze zbioru <math>M</math>, podobnie zdefiniujmy <math>SUF[N]</math>.
 
<math>SUF[M]</math> daje posortowany ciąg sufiskówzaczynających się na pozycjach ze zbioru <math>M</math>.




{{przyklad|||
Niech  <math>x=abracadabra</math>. Liczby wystąpień symboli w słowie <math>x</math> są:
<center><math>w_{a}=5, w_{b}=2, w_{c}=1, w_{d}=1, w_{r}=2.</math></center>
}}


''' Redukcja liczenia <math>SUF[M]</math> do liczenia tablicy sufiksowej rozmiaru <math>\frac{2}{3}n</math>'''


Optymalnym  kodowaniem jest <math>h(a)=0,h(b)=10,h(c)=1100,h(d)=1101,h(r)=111.</math>  <math>abracadabra</math> zostaje zakodowane na  <math>01011101100011010101110</math>, ciąg binarny długości <math>23</math>.  Optymalne drzewo binarne odpowiadające optymalnemu kodowi prefiksowemu jest pokazane na rysunku.


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.
<center>[[Grafika:Huffnal.jpg]]<br>
Rysunek 2:Drzewo Huffmana kodujące optymalnie symbole  <math>a,b,c,d,r</math> z wagami odpowiednio
<math>S\ =\ (5, 2, 1, 1, 2)</math>. Liczby w wewnętrznych węzłach są sumą wag w liściach odpowiadającego poddrzewa.
Koszt całkowity kodowania jest ważoną sumą długości ścieżek do liści, jest równeż sumą wartości w
węzłach wewnętrznych:  <math> 2+4+6+11\ =\ 23.</math>  


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


<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>
Długość tekstu <math>h(x)</math> jest równa ważonej sumie długości ścieżek, ważoenj w tym sensie, że
długość ścieżki do danego liścia jest przemnożona przez wagę tego liścia. W przykładzie jest to suma:
<math>5 *1+2*2+1*4+1*4+2*3\ =\ 23</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>
Niech <math>n</math> będzie liczbą różnych symboli w <math>x</math>, <math>w[i]</math> będzie liczbą wystąpień <math>i</math>-tego symbolu. Problem możemy rozwiązać stosując algorytm dla problemu ''Optymalne Sklejanie Par'' dla ciągu <math>w[1],w[2],\ldots
w[n])</math>. Musimy algorytm zmodyfikować tak, aby nie tylko sklejał pary ale również tworzył lokalnie drzewo.
Inaczej mówiąc algorytm w momencie sklejania elementów <math>a</math>, <math>b</math> w element <math>c</math> tworzy równieź dowiązania,
<math>a</math> staje się lewym synem <math>c</math>, natomiast  <math>b</math> staje się prawym synem.


<math>compress(x)\ =\ y1\ \#\ y2</math></center>
{{algorytm| Huffmana (nieformalny opis)|algorytm_huffman_nieformalny|
Konfiguracje pośrednie algorytmu to zbiory drzew,


początkowo każdy pojedyńczy element <math>i</math> z wagą <math>w[i]</math> jest pojedyńczym drzewem.


Symbol # jest tutsj (jak poprzednio) leksykograficznie najmniejszy.  
Korzeń każdego drzewa reprezentuje sklejenie jego wszystkich liści.  
<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.
Pozostawiamy to jako ćwiczenie.
 
{{algorytm|KS|algorytm_KS|
1. <math>x' := compress(x)</math>;
 
2. obliczamy tablicę sufiksową dla x' rekurencyjnie;
 
3. obliczamy <math>SUF[M]</math> wczasie liniowym, znając tablicę sufiksową dla x';
 
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>


Za każdym razem sklejamy dwa korzenie drzew o minimalnej wadze.
}}
}}


Krok 1 algorytmu sprowadza się do ''radix-sort''u, podobnie jak w algorytmie KMR.Kroki 3,4 są proste i pozostawiamy cztelnikowi jako ćwiczenie.
Drzewo które algorytm generuje nazywamy drzewem Huffmana.


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.
Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i
drzew Huffmana.  


Pokażemy na przykładzie kluczową operację porównania  sufiksu typu M z sufiksem typu N w czasie stałym.
Z analizy algorytmu ''Optymalne Sklejanie Par'' wynika, że problem optymalnych binarnych kodów prefiksowych można rozwiązać w czasie <math>O(n \log n)</math>, a jeśli wagi <math>w[i]</math> są posortowane to w czasie liniowym.


{{przyklad|||
===Kodowanie Huffmana słowami <math>k</math>-arnymi.===
Nierównośc <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>
Pozostawiamy jako ćwiczenie podobny problem, ale gdy kodujemy w alfabecie <math>k</math>-arnym, mamy teraz symbole <math>0,1,\ldots, k-1</math>. W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy.
2. <math> \ (a_2=a_{12}, a_3 < a_{13}) </math> <br>
3. <math> (a_2=a_{12}, a_3=a_{13}, sufiks_4<sufiks_{14})  </math>


===Kodowanie prefiskowe z symbolami kodowymi nierównej długości===
Problem robi się skomplikowany,gdy długość symbolu 0 jest 1 a długość symbolu 1 jest <math>c</math>, gdzie <math>c</math> jest pewną stała (jest to po
angielsku problem tzw. lopsided trees). Inaczej mówiąc szukamy takiego optymalnego drzewa, że ważona suma
ścieżek jest minimalna, ale długość krawędzi na lewo wynosi 1 a długość krawędzi na prawo wynosi <math>c</math>.
Pozostawiamy jako ćwiczenie znalezienie efektywnego algorytmu dla małych <math>c</math> (<math>c=2</math> lub <math>c=3</math>). Dla dowolnego
<math>c</math> (będącego częścia wejścia) i dowolnych wag jest to zbyt trudne, nie znamy algorytmu wielomianowego. Dla
ustalonego c istnieje algorytm wielomianowy którego stopień zależy od c. Natomiast pozostawiamy jako
ćwiczenie przypadek gdy <math>c</math> jest dowolne ale wszystkie wagi <math>w[i]</math> są równe.


Jednakże <math>4,14\in M</math>, zatem <math>sufiks_4</math> i <math>sufiks_{14}</math>, są typu M i można je porównać w czasie stałym. 
=== Kodowanie prefiskowe z kodami o ograniczonej długości===
 
Innym ciekawym problemem jest
 
też skonstruowanie optymalnego kodu prefiksowego, w którym wszystkie słowa kodowe są ograniczone przez pewną
 
zadaną liczbę <math>L</math>. Inaczej mówiąc ograniczamy z góry wysokość drzewa Huffmana. Istnieją algorytmy
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>
wielomianowe dla tego problemu, stopień wielomianu niezależny od <math>L</math>.
 
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.
 
}}
 
Istnieje kilka interesujących algorytmów, które konstruują drzewo sufiksowe w czasie liniowym, bezkorzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena).

Wersja z 06:40, 24 sie 2006

Algorytmy tekstowe II

Poprzednie algorytmy dokonywały jedynie na tekstach wejściowych operacji sprawdzania symboli na równość. Załóżmy teraz, że alfabet jest liniowo uporządkowany. Pokażemy, że porównywanie symboli w sensie porządku liniowego można istotnie wykorzystać w algorytmach tekstowych. Porządek liniowy na symbolach implikuje {\em porządek leksykograficzny} na słowach, na przykład:

ab<ababab<abb<abbaa<abbaaaaaaaaaaa<abbaaaaaab

Równoważność cykliczna słów

Pokażemy problem, który prawdopodobie najlepiej pokazuje użyteczność porządku liniowego na alfabecie. Rotacją słowa u=u[1..n] jest kaz'rde słowo postaci u(k) = u[k+1..n]u[1..k]. (w szczególności u(0)=u(n)=u). Niech u,w będą słowami długości n, mówimy, że są one cyklicznie równoważne gdy u(i)=w(j) dla pewnych i,j.

Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa u w słowie ww, ale podamy algorytm znacznie prostszy bazujący , który będzie działal w czasie liniowym i {\em w miejscu} (dodatkowa pamięć jest stała). W algorytmie roszerzamy tablicę u,w na uu, ww ale robimy to jedynie dla uproszczenia, w rzeczywistości możemy poruszać się cyklicznie po u i po w, pozostawiamy modyfikację jako ćwiczenie.

Algorytm Równoważność-Cykliczna

x:=uu; y:=ww;
i:=0; j:=0;
while (i<n) and (j<n) do
   k:=1;
   whilex[i+k]=y[j+k] do k:=k+1;
   if k>n then return true;
   if x[i+k]>y[i+k] theni:=i+k else j:=j+k;
return false;

Zdefiniujmy:

D(u)={k:1≤k≤n oraz u(k)>w(j) dla pewnego j},
D(w)={k:1≤k≤n oraz w(k)>u(j) dla pewnego j}.

Skorzystamy z prostego faktu: Jeśli D(u)=[1..n] lub D(w)=[1..n], to u,w nie są równoważne.

Uzasadnienie pozostawiamy jako ćwiczenie. Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:

D(w)⊇[1..i]\ oraz \ D(u)⊇[1..j].

Liczba porównań jest oczywiście liniowa. Pozostawiamy jako ćwiczenie policzenie dokładnego wzoru na maksymalną liczbę porównań symboli dla tekstów długości n.

String-matching w pamięci stałej dla specjalnych wzorów

Oznaczmy przez MaxSuf(w) maksymalny leksykograficznie sufiks słowa w. Słowo x nazwiemy specjalnym gdy MaxSuf(x)=x.

Przykład

'bajtocja' nie jest słowem specjalnym, ale rotacja tego słowa 'tocjabaj' jest.


Dlaczego słowa o tej własności są interesujące ? Większość szybkich algorytmów szukania podsłów korzysta z okresów p prefiksów słowa. Liczenie tych okresów w ogólnym przypadku jest wąskim gardłem w projekcie algorytmu. Natomiast dla słow specjalnych liczenie okresów jest trywialne.

Jeśli x jest specjalny to okres każdego prefiksu słowa x można policzyć następującym naiwnym algorytmem;

Algorytm Funkcja Naiwne-Liczenie-Okresu (j)

period:=1;
for i:=2 to j do
   if x[i]≠x[i−period] then period:=i;
return period;

Przykład

Funkcja Naiwne-Liczenie-Okresu daje zły wynik dla tekstów które nie są specjalne, na przykład załóżmy że
x=(aba)6a=abaabaabaabaabaabaa.}
Wtedy kolejne wartości okresów dla pozycji j=1,2,..

są:

a b a a b a a b a a b a a b a a b a a
1 2 2 4 5 5 7 8 8 10 11 11 13 14 14 16 17 17 19

Zatem Naiwne-Liczenie-Okresu(19) = 19, dla x = (aba)6a, wynik całkowicie niepoprawny. Poprawność algorytmu jest wyjaśniona na rysunku. Korzystamy z prostej własności, że prefiks specjalnego słowa jest też specjalny.


Rysunek 1: Załóżmy, że w algorytmie Naiwne-Liczenie-Okresu x[i−period(i−1)]≠x[i]. Niech a=x[i], b=x[i−period]. Ponieważ uz jest prefiksem słowa specjalnego x zatem a<b. Gdyby period(i)<i to wtedy, ze względu na dwie okresowości, zb jest właściwym podsłowem słowa x[1..i−1] oraz zb>x. Zaprzecza to założeniu, że x jest specjalne. Zatem period(i)=i.

Opiszemy teraz program szukania wzorca x w slowie yi, zakładając że x jest sepcjalne. Program wczytuje dwa teksty, pierwszy z nich jest specjalne: x pamiętamy w tablicy x[0..m−1], y w tablicy y[0..n−1]. Program wypisuje wszystkie wystapienia x w y, tzn. wszystkie takie pozycje i, ze y[i…i+m−1] = x. Zapisujemy program w języku C++.

Algorytm Specjalny-String-Matching



void przesun() { if (j-1<2p) {i=i+p; j=0;} else {j=j-p; i=i+p;}}

}}

Program jest wstępem do programu szukajacego dowolne posłowo, niekoniecznie o wlasnosci bycia specjalnym. Postawowym niezmiennikiem w programie przed kazdym wykonaniem i po kazdym zakonczeniu pętli while' jest: (A)\ x[0…j−1] = y[i…i+j−1], . (B)\ Program wypisal wszsytkie wczesniejsze wystapienia i′<i, (C)\ p jest okresem slowa x[0…j−1]

Algorytm działa w czasie liniowym, można to udowodnić obserwując zmiany wartości 2i+j, zauważmy, że wartość ta nie zmniejsza się, a w wypadku pozytywnego testu x[j)==y[i+j] zwiększa się co najmniej o 1. Jednocześnie 2i+j≤3n.

String-matching w pamięci stałej dla dowolnych wzorców

Algorytym Specjalny-String-Matching można łatwo zmodyfikować tak, aby znajdował on wystąpinia dowolnego słowa (niekoniecznie specjalnego) w czasie liniowym i stałej pamięci. Niech x=uv, gdzie v jest leksykograficzne maksymalnym sufiksem x. Oznaczmy r=|u|. Technicznie informacja o rozkładzie uv sprowadza się do pamiętania r.


Własność rozkładu. Niech x=uv będzie rozkładem jak wyżej opisany. Wtedy Słowo v występuje tylko raz w słowie uv. Jeśli i′<i są początkami wystąpień v, oraz i−i′<r to na pozycji i−1 nie kończy się wystąpienie u.


Z powyższego faktu wynika stosunkowo prosty algorytm szukania x w czasie loiniowym i pamięci stałej. Algorytm ten jest modyfikacja agorytmu Specjalny-String-Matching , w ktorym rolę x pełni v.

Algorytm String-matching w pamięci stałej

Niech v będzie leksykograficznie maksymalnym sufiksem x;

Liczymy algorytmem Specjalny-String-Matching kolejne wystąpienia v w y;

Dla każdego wystąpienia i niech i′ będzie wystąpieniem poprzednim;

jeśli i−i′≥|v| to sprawdź czy u występuje na lewo od pozycji i;

(sprawdzanie to wykonujemy w sposób naiwny)

jeśli występuje to wypisz kolejne wystąpienie całego wzorca x.

Pozostawiamy bardziej precyzyjny zapis algorytmu jako ćwiczenie.

W ten sposób pokazaliśmy, że problem szukania słowa x w słowie y można rozwiązać w czasie liniowym i pamięci (dodatkowej) stałej, jeśli znamy początkową pozycję r leksykograficznie maksymalnego sufiksu v słowa x.

Liczenie maksymalnego sufiksu w pamięci stałej

W algorytmie szukanie wzorca w pamięci stałej potrzebna jest pozycja r od której zaczyna się maksymalny sufiks. Pokażemy teraz jak ją znajdować w czasie liniowym i w pamięci stałej. Kluczem do tego jest liczenie czegoś więcej, dla każdego prefiksu liczymy maksymalny sufiks jak również dodatkowo jego okres. To własnie liczenie okresu daje efektywność, chociaż na końcu nam ten okres jest niepotrzebny. Przekształcimy najpierw algorytm Naiwne-Liczenie-Okresu na algorytm liczący długość najdłuższego specjalnego prefiksu włącznie z jego okresem.

{algorytm| funkcja Najdłuższy-Specjalny-Prefiks(x)|fun_najdl_spec_pref| period:=1;
for i:=2 to |x| do
   if x[i]<x[i−period] \textbf{then} period:=i
   'else if x[i]>x[i−period] then
      return (i−1,period);
return (|x|,period); }}

Skorzystamy z algorytmu Najdłuższy-Specjalny-Prefiks. Funkcja Maksymalny-Sufiks liczy początkową pozycję i okres maksymalnego sufiksu.

Algorytm funkcja Maksymalny-Sufiks(x)

j:=1;
repeat
   (i,period):= Najdłuższy-Specjalny-Prefiks(x[j..n]);
   if i=n then return (j,period)
   else j:=j+i−(imodperiod);
forever

Możemy przepisać algorytm Maksymalny-Sufiks tak aby nie wywoływał on funkcji Najdłuższy-Specjalny-Prefiks, wpisując tę funkcję do algorytmu. Arytmetyczna funkcja mod może być usunięta i zastąpiona przez operacje dodawania i odejmowania bez zmiany asymptotycznej złożoności.

Algorytm Maksymalny-Sufiks wykonuje co najwyżej 2.|x| porównań symboli. Uzasadnienie pozostawiamy jako ćwiczenie.

Algorytm funkcja} Maksymalny-Sufiks(x)

s:=1; i:=2; p:=1;
while (i≤n) do
   r:=(i−s)modp;
   if (x[i]=x[s+r]) then i:=i+1
   else if (x[i]<x[s+r]) then begin       i:=i+1; p:=i−s;    else       s:=i−r; i:=s+1; p:=1;
return s;

Kodowanie prefiksowe: drzewa i kody Huffmana

Zbiór słów jest prefiksowy gdy żadne słowo nie jest prefiksem drugiego. Taki zbiór słów odpowiada drzewu, którego ścieżki etykietowane są symbolami, w przypadku binarnym możemy przyjąć, że krawędź w lewo jest etykietowana zerem, a w prawo jedynką. Przez kodowanie rozumiemy funkcję h która każdemu symbolowi s przyporządkowuje niepusty ciąg binarny h(s), całe słowo x zostanie zakodowane na słowo h(x) (każda litera jest zakodowana niezależnie i kody są skonkatenowane. Kod jest prefiksowy gdy zbiór kodów symboli jest prefiksowy. Rozważamy następujący problem.


Optymalne kodowanie prefiksowe

Dla danego słowa x znaleźć binarne kodowanie prefiksowe takie, że h(x) ma minimalną długość.


Przykład

Niech x=abracadabra. Liczby wystąpień symboli w słowie x są:

wa=5,wb=2,wc=1,wd=1,wr=2.


Optymalnym kodowaniem jest h(a)=0,h(b)=10,h(c)=1100,h(d)=1101,h(r)=111. abracadabra zostaje zakodowane na 01011101100011010101110, ciąg binarny długości 23. Optymalne drzewo binarne odpowiadające optymalnemu kodowi prefiksowemu jest pokazane na rysunku.


Rysunek 2:Drzewo Huffmana kodujące optymalnie symbole a,b,c,d,r z wagami odpowiednio S = (5,2,1,1,2). Liczby w wewnętrznych węzłach są sumą wag w liściach odpowiadającego poddrzewa. Koszt całkowity kodowania jest ważoną sumą długości ścieżek do liści, jest równeż sumą wartości w węzłach wewnętrznych: 2+4+6+11 = 23.

Długość tekstu h(x) jest równa ważonej sumie długości ścieżek, ważoenj w tym sensie, że długość ścieżki do danego liścia jest przemnożona przez wagę tego liścia. W przykładzie jest to suma: 5*1+2*2+1*4+1*4+2*3 = 23.

Niech n będzie liczbą różnych symboli w x, w[i] będzie liczbą wystąpień i-tego symbolu. Problem możemy rozwiązać stosując algorytm dla problemu Optymalne Sklejanie Par dla ciągu w[1],w[2],…w[n]). Musimy algorytm zmodyfikować tak, aby nie tylko sklejał pary ale również tworzył lokalnie drzewo. Inaczej mówiąc algorytm w momencie sklejania elementów a, b w element c tworzy równieź dowiązania, a staje się lewym synem c, natomiast b staje się prawym synem.

Algorytm Huffmana (nieformalny opis)

Konfiguracje pośrednie algorytmu to zbiory drzew,

początkowo każdy pojedyńczy element i z wagą w[i] jest pojedyńczym drzewem.

Korzeń każdego drzewa reprezentuje sklejenie jego wszystkich liści.

Za każdym razem sklejamy dwa korzenie drzew o minimalnej wadze.

Drzewo które algorytm generuje nazywamy drzewem Huffmana.

Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i drzew Huffmana.

Z analizy algorytmu Optymalne Sklejanie Par wynika, że problem optymalnych binarnych kodów prefiksowych można rozwiązać w czasie O(nlog⁡n), a jeśli wagi w[i] są posortowane to w czasie liniowym.

Kodowanie Huffmana słowami k-arnymi.

Pozostawiamy jako ćwiczenie podobny problem, ale gdy kodujemy w alfabecie k-arnym, mamy teraz symbole 0,1,…,k−1. W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy.

Kodowanie prefiskowe z symbolami kodowymi nierównej długości

Problem robi się skomplikowany,gdy długość symbolu 0 jest 1 a długość symbolu 1 jest c, gdzie c jest pewną stała (jest to po angielsku problem tzw. lopsided trees). Inaczej mówiąc szukamy takiego optymalnego drzewa, że ważona suma ścieżek jest minimalna, ale długość krawędzi na lewo wynosi 1 a długość krawędzi na prawo wynosi c. Pozostawiamy jako ćwiczenie znalezienie efektywnego algorytmu dla małych c (c=2 lub c=3). Dla dowolnego c (będącego częścia wejścia) i dowolnych wag jest to zbyt trudne, nie znamy algorytmu wielomianowego. Dla ustalonego c istnieje algorytm wielomianowy którego stopień zależy od c. Natomiast pozostawiamy jako ćwiczenie przypadek gdy c jest dowolne ale wszystkie wagi w[i] są równe.

Kodowanie prefiskowe z kodami o ograniczonej długości

Innym ciekawym problemem jest też skonstruowanie optymalnego kodu prefiksowego, w którym wszystkie słowa kodowe są ograniczone przez pewną zadaną liczbę L. Inaczej mówiąc ograniczamy z góry wysokość drzewa Huffmana. Istnieją algorytmy wielomianowe dla tego problemu, stopień wielomianu niezależny od L.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wykład_2&oldid=26053”