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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rytter (dyskusja | edycje)
830 edycji
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 27 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
<font size="7">Zaawansowane algorytmy tekstowe II</font>
<font size="6"> Zaawansowane algorytmy tekstowe II </font>


__TOC__
__TOC__  


W module tym zajmiemy się kodowaniem Huffmana. Zwiazane sa z nimi różne ciekawe problemy tekstowe.




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'').


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.
== Kodowanie prefiksowe: drzewa i kody Huffmana ==
Spośród wielu dobrych reprezentacji najbardziej znanymi są tablice sufiksowe (oznaczane przez<math>SUF</math>) i drzewa sufiksowe.


Niech <math>x=a_{1}a_{2}\dots a_{n}</math>, oraz niech <math>x_{n+1}=\#</math> będzie specjalnym znakiemleksykograficznie mniejszym od każdego innego symbolu.  
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:


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-tyleksykograficznie sufiks x. Sufiks zaczynający się na pozycji <math>(n+1)</math>-szej nie jest brany pod uwagę. Ciąg sufiksów posortowany leksykograficznie wygląda następująco:
===Optymalne kodowanie prefiksowe===
 
Dla danego słowa <math>x</math> znaleźć binarne kodowanie prefiksowe takie,
<center><math>sufix_{SUF[1]}< sufix_{SUF[2]}<sufix_{SUF[3]}<\ldots sufix_{SUF[n]}</math></center>
że <math>h(x)</math> ma minimalną długość.
 
 
[[Grafika:Zasd_2_1.jpg]]
 
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>
<br>
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>.
 
'''Drzewo sufiskowe''' jest drzewem, w którym każda ścieżka jest etykietowana kolejnymi symbolamipewnego 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 pewnepodsł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.
 
[[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 kolejnesymbole <math>z</math>, czasami posuwamy się po wewnętrznej etykiecie pewnej krawędzi. Zbiór wystąpie"n odpowiadazbiorowi liści w poddrzewie węzła do którego doszliśmy. Jeśli po drodze '' utknęliśmy'' i nie dało siędalej schodzić po drzewie to oznacza, że <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{\em binary search}, 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)|={\choose {n} 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).  




{{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>}}
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>
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>).
 
Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu liczącego tablicę <math>ROT</math>, zakładając, że mamy liniowy algorytm liczeniatablicy sufiksowej.
 
 
'''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.
 
 
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>
 
 
Pozostawiamy jako ćwiczenie policzenie wzoru na <math>|Subwords(F_n)|</math>.
 
== Drzewa sufiksowe =>tablice sufiksowe ==
 
W celu znalezenia początkowych pozycji sufiksów w porządku leksykograficznym przechodzimy drzewo sufiksowemetodą DFS, zakładając, że dla każdego węła lista jego synów jest w kolejności leksykograficznej etykietkrawędzi prowadzących do synów. Wystarczy sprawdzać piewsze symbole tych etykiet.
 
Załóżmy, że w liściach mamy początki sufiksów, które do nich prowadzą.Kolejność odwiedzania liści w naszym przejściu metodą DFS automatycznie generuje elementy tablicy sufiksowej.
 
== Tablice sufiksowe =>drzewa sufiksowe ==
Pokażemy konstruktywanie następujący istotny fakt:
 
jeśli znamy tablicę sufiksową i tablicę<math>lcp</math> to drzewo sufiksowe dla danego tekstu możemy ''łatwo'' skonstruować w czasie liniowym.
 
Przypuśćmy, że,
<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>
 
 
 
{{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>;
}}
}}




<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>
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.
 
 
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).
 
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>.


<center>[[Grafika:Huffnal.jpg]]<br><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ównież sumą wartości w
węzłach wewnętrznych:  <math>2+4+6+11= 23</math>


Z tablicy <math>lcp</math> odczytujemy długość <math>\gamma_1</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>. Przechodząc drzewo posuwamy się po węzłachdrzewa, przeskakując potencjalnie długie teksty na krawędziach. \myskipKoszt operacji wstawienia jest proporcjonalny do sumy: jeden plus zmniejszenie głębokości nowego liścia w stosunku do starego. Suma tychzmniejszeń jest liniowa. <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.
</center>


Lokalnie wykonana praca w jednej iteracjijest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego.
Długość tekstu <math>h(x)</math> jest równa ważonej sumie długości ścieżek, ważonej 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>.


Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.
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>. Algorytm ten był przedsatwiony na wykładach z ASD.  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.  


<center> [[Grafika:Zasd_2_4.jpg]] <br> Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu
{{algorytm| Huffmana (nieformalny opis)|algorytm_huffman_nieformalny|
<math>babaabababba\#</math>. </center>
Konfiguracje pośrednie algorytmu to zbiory drzew,


<center> [[Grafika:Zasd_2_5.jpg]] <br> Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu <math>babaabababba\#</math>. </center>
początkowo każdy pojedyńczy element <math>i</math> z wagą <math>w[i]</math> jest pojedyńczym drzewem.


== Oblicanie tablicy ''lcp'' ==
Korzeń każdego drzewa reprezentuje sklejenie jego wszystkich liści.  
 
Niech <math>rank(i)</math> będzie poycją <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>
 
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:
 
 
{{algorytm|Oblicz-lcp|algorytm_oblicz_lcp|
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
&nbsp;&nbsp;&nbsp;oblicz <math>lcp'[k]</math> korzystając z faktu, że <math>lcp'[k]\ge lcp'[k-1]-1</math>; <br>
&nbsp;&nbsp;&nbsp;&nbsp;koszt iteracji <math>O(lcp'[k]-lcp'[k-1]+const)</math><br>
'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''<br>
&nbsp;&nbsp;&nbsp;<math>lcp[rank[k]-1] := lcp'[k]</math>


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


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ść 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 doprzodu''. Liczba iteracji jest liniowa, więc liczba kroków do tyłu też.  Poniewaź odległość ''do celu'' jest liniowa, to suma kroków też jest liniowa.
Drzewo, które algorytm generuje, nazywamy drzewem Huffmana.
 
==Konstrukcja tablicy ''SUF'' w czasie ''O(n log n)'': algorytm KMR ==
 
Opiszemy uproszczoną wersję algorytmu  Karpa-Millera-Rosenberga (w skrócie algorytmu ''KMR'') rozwiązywania problemów tekstowych metodą ''słownika bazowego''. Ustalmy pewnie tekst <math>x</math> długości <math>n</math>.Załóżmy, że dodatkowym symbolem jest <math>x_{n+1}=\#</math>, leksykograficznie najmniejszy symbol. Przez <math>k</math>-bazowysegment rozumiemy segment <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>. Teoretyczniemożemy założyć, że po symbolu <math>\#</math> mamy bardzo dużo takich symboli na prawo i każde segment startujący w<math>x[1..n]</math> ma ''dokładnie '' długość <math>2^k</math>.
 
 
'''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>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ą ''radix-sort'' i  w tensposób otrzymujemy tablicę, która koduje (w porządku leksykograficznym) każdą parę liczbą naturalną(pozycją w porządku leksykograficznym). Warością <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:
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 optymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR liczy znacznie więcej niż tablica sufiksowa, ponieważliczy słownik podsłów bazowych wielkości <math>n \log n</math>, mający liczne zastosowania.
 
Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny.Rozważmy dwa zbiory pozycji tekstu <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>.  
Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i
drzew Huffmana.  


<math>SUF[M]</math> daje posortowany ciąg sufiskówzaczynających się na pozycjach ze zbioru <math>M</math>.
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.


===Kodowanie Huffmana słowami <math>k</math>-arnymi.===


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.


== Redukcja liczenia <math>SUF[M]</math> do liczenia tablicy sufiksowej rozmiaru <math>\frac{2}{3}n</math> ==
===Kodowanie prefiksowe 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łą (jest to problem tzw. lopsided trees). Inaczej mówiąc, szukamy takiego optymalnego drzewa, w którym 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ęścią wejścia) i dowolnych wag jest to zbyt trudne, nie znamy algorytmu wielomianowego. Dla
ustalonego <math>c</math> istnieje algorytm wielomianowy, którego stopień zależy od <math>c</math>.


Natomiast pozostawiamy jako
ćwiczenie przypadek, gdy <math>c</math> jest dowolne, a wszystkie wagi <math>w[i]</math> są równe. Istniej wtedy algorytm wielomianowy.


Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie <math>x</math> korzystając z rdix-sort. Każdemutakiemu słowu przyporządkujmy nazwę będącą jego pozycją w posortowanym leksykograficznie ciągu, oznaczmy<math>kod(z)</math> kod podsłowa długości 3. Zakładamy, że <math>x</math> ko"nczy się dodatkowo dwoma symbolami <math>\#</math> alerozważamy tylko podsłowa zaczynające się w <math>x</math>. Dla uproszczenia załóżmy, że 3 jest dzielnkiem n.
=== Kodowanie prefiksowe z kodami o ograniczonej długości===  
 
Innym ciekawym problemem jest
Tworzymy nowe słowo <math>compress(x)</math> w następujący sposób:
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.  Zakładamy teraz, że wagi krawędzi są takie same. Istnieją algorytmy
<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>
wielomianowe dla tego problemu, w których stopień wielomianu jest niezależny od <math>L</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></center>
 
 
Jeśli mamy tablicę sufiksową dla słowa <math>compress(x)</math> to można  łatwo policzyć <math>SUF[M]</math> w czasie liniowym.
 
{{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>
 
}}
 
Krok 1 algorytmu sprowadza się do ''radix-sort''u, podobnie jak w algorytmie KMR.Kroki 3,4 są proste i pozostawiamy cztelnikowi jako ćwiczenie.
 
Najważniejszy jest krok scalania. Mamy dwie posortowane listy sufiksów i trzeba je scalićw jedną posortowaną listę. Zasadniczym problemem jest implementacja operacji porównanialeksykograficznego dwóch sufiksów w czasie stałym. Jeśli  oba sufiksy są typu <math>M</math> luboba 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 jak porównać sufiks typu M z sufiksem typu N.
 
{{przyklad|||
Nierównośc<math>sufiks_2< sufiks_{12}</math> jest równoważna alternatywie:
 
<math> (a_2 < a_{12}) \ \textrm{lub}\ (a_2=a_{12}, a_3 < a_{13})  \ \textrm{lub}\\ (a_2=a_{12}, a_3=a_{13}, sufiks_4<sufiks_{14})  </math>
 
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. 
 
Niech <math>T(n)</math> będzie czasem działania algorytmu KS. Zachodzi <center><math>T(n) \ =\ T(\frac{2}{3}\cdot n + 1) + 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.
 
}}
 
Istnieje kilka interesujących algorytmów, które konstruują drzewo sufiksowe w czasie liniowym, bezkorzystania z tablicy sufiksowej (algorytm Weinera, McCreighta, Ukkonena).

Aktualna wersja na dzień 22:12, 11 wrz 2023

Zaawansowane algorytmy tekstowe II

W module tym zajmiemy się kodowaniem Huffmana. Zwiazane sa z nimi różne ciekawe problemy tekstowe.


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ównież 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żonej 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]). Algorytm ten był przedsatwiony na wykładach z ASD. 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 prefiksowe 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łą (jest to problem tzw. lopsided trees). Inaczej mówiąc, szukamy takiego optymalnego drzewa, w którym 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ęścią 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, a wszystkie wagi w[i] są równe. Istniej wtedy algorytm wielomianowy.

Kodowanie prefiksowe z kodami o ograniczonej długości

Innym ciekawym problemem jest 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. Zakładamy teraz, że wagi krawędzi są takie same. Istnieją algorytmy wielomianowe dla tego problemu, w których stopień wielomianu jest niezależny od L.

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