|
|
| (Nie pokazano 12 wersji utworzonych przez 4 użytkowników) |
| Linia 3: |
Linia 3: |
| __TOC__ | | __TOC__ |
|
| |
|
| Poprzednie algorytmy dokonywały jedynie na tekstach wejściowych operacji sprawdzania symboli na równość.
| | W module tym zajmiemy się kodowaniem Huffmana. Zwiazane sa z nimi różne ciekawe problemy tekstowe. |
| 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 ==
| |
|
| |
|
| 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>.
| |
|
| |
|
| Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa <math>u</math> w słowie <math>ww</math>, 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ę <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.
| |
|
| |
| {{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>
| |
| <math>k:=1</math>;<br>
| |
| '''while'''<math>x[i+k]=y[j+k]</math> '''do''' <math>k:=k+1</math>;<br>
| |
| '''if''' <math>k>n</math> '''then return''' true;<br>
| |
| '''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>
| |
| }}
| |
|
| |
| 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>
| |
|
| |
| 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.
| |
|
| |
| 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>
| |
|
| |
| 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>.
| |
|
| |
| == String-matching w pamięci stałej dla specjalnych wzorów ==
| |
|
| |
|
| |
| 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>.
| |
|
| |
| {{przyklad|||
| |
| '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 <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.
| |
|
| |
| 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;
| |
|
| |
| {{ 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>
| |
| '''if''' <math>x[i] \ne x[i - period]</math> '''then''' <math>period := i</math>;<br>
| |
| '''return''' <math>period</math>;<br>
| |
| }}
| |
|
| |
| {{przyklad|||
| |
| 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>
| |
| są:
| |
| <center>
| |
| <table>
| |
| <tr>
| |
| <td>a</td>
| |
| <td>b</td>
| |
| <td>a</td>
| |
| <td>a</td>
| |
| <td>b</td>
| |
| <td>a</td>
| |
| <td>a</td>
| |
| <td>b</td>
| |
| <td>a</td>
| |
| <td>a</td>
| |
| <td>b</td>
| |
| <td>a</td>
| |
| <td>a</td>
| |
| <td>b</td>
| |
| <td>a</td>
| |
| <td>a</td>
| |
| <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>
| |
| }}
| |
|
| |
| 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.
| |
|
| |
| <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>
| |
|
| |
| Opiszemy teraz program szukania wzorca <math>x</math> w slowie <math>y</math>i, zakładając że x jest sepcjalne.
| |
| 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
| |
| 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>
| |
| { if (j==m) {cout<<i<<endl; przesun();};<br>
| |
| else if (x[j)==y[i+j] {j=j+1; if (j==1)||(x[j-1]!=x[j-1-p]) p=j;};<br>
| |
| else przesun(); }}<br>
| |
|
| |
|
| |
| 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)\ ''' <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>
| |
|
| |
| 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 ==
| |
|
| |
| 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>.
| |
|
| |
|
| |
| '''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 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>.
| |
|
| |
| {{algorytm |String-matching w pamięci stałej|algorytm_string_matching_pam_st|
| |
| 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>;
| |
|
| |
| Dla każdego wystąpienia <math>i</math> niech <math>i'</math> będzie wystąpieniem poprzednim;
| |
|
| |
| jeśli <math>i-i' \ge |v|</math> to sprawdź czy <math>u</math> występuje na lewo od pozycji <math>i</math>;
| |
|
| |
| (sprawdzanie to wykonujemy w sposób naiwny)
| |
|
| |
| jeśli występuje to wypisz kolejne wystąpienie całego wzorca <math>x</math>.
| |
| }}
| |
|
| |
| Pozostawiamy bardziej precyzyjny zapis algorytmu jako ćwiczenie.
| |
|
| |
| 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>.
| |
|
| |
| == Liczenie maksymalnego sufiksu w pamięci stałej ==
| |
|
| |
| 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.
| |
|
| |
| {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>
| |
| '''if''' <math>x[i] < x[i - period]</math> \textbf{then} <math>period := i</math><br>
| |
| '''else if''' <math>x[i] > x[i - period]</math> ''then'''<br>
| |
| '''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|funkcja Maksymalny-Sufiks(x)|fun_max_suf|
| |
| <math>j := 1</math>;<br>
| |
| '''repeat'''<br>
| |
| <math>(i,period) :=</math> ''Najdłuższy-Specjalny-Prefiks''<math>(x[j.. n])</math>;<br>
| |
| '''if''' <math>i=n</math> '''then return''' <math>(j, period)</math><br>
| |
| '''else''' <math>j := j+i - (i \mod period)</math>;<br>
| |
| '''forever''' <br>
| |
| }}
| |
|
| |
| 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.
| |
|
| |
| Algorytm Maksymalny-Sufiks wykonuje co najwyżej <math>2.|x|</math> porównań symboli. Uzasadnienie pozostawiamy jako ćwiczenie.
| |
|
| |
| {{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>
| |
| <math>r := (i-s) \mod p</math>;<br>
| |
| '''if''' (<math>x[i] = x[s+r])</math> '''then''' <math>i := i+1</math><br>
| |
| '''else if''' (<math>x[i] < x[s+r])</math> '''then begin'''
| |
| <math>i := i+1</math>; <math>p := i-s</math>;
| |
| '''else'''
| |
| <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 == | | == 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, | | 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 | | 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ą. | | 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 | | 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 | | <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 | | są ''skonkatenowane''). Kod jest prefiksowy gdy zbiór kodów symboli jest prefiksowy. Rozważamy |
| następujący problem. | | następujący problem: |
|
| |
|
|
| |
|
| Linia 264: |
Linia 25: |
| {{przyklad||| | | {{przyklad||| |
| Niech <math>x=abracadabra</math>. Liczby wystąpień symboli w słowie <math>x</math> są: | | 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> | | <center><math>w_{a}=5, w_{b}=2, w_{c}=1, w_{d}=1, w_{r}=2</math></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. | | 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. |
|
| |
|
| <center>[[Grafika:Huffnal.jpg]]<br> | | <center>[[Grafika:Huffnal.jpg]]<br><br> |
| Rysunek 2:Drzewo Huffmana kodujące optymalnie symbole <math>a,b,c,d,r</math> z wagami odpowiednio | | 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. | | <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 | | 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> | | węzłach wewnętrznych: <math>2+4+6+11= 23</math> |
|
| |
|
| </center> | | </center> |
|
| |
|
| 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ść 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: | | 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>5 *1+2*2+1*4+1*4+2*3= 23</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 | | 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. | | 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, | | 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>a</math> staje się lewym synem <math>c</math>, natomiast <math>b</math> staje się prawym synem. |
|
| |
|
| {{algorytm| Huffmana (nieformalny opis)|algorytm_huffman_nieformalny| | | {{algorytm| Huffmana (nieformalny opis)|algorytm_huffman_nieformalny| |
| Linia 297: |
Linia 58: |
| }} | | }} |
|
| |
|
| Drzewo które algorytm generuje nazywamy drzewem Huffmana. | | Drzewo, które algorytm generuje, nazywamy drzewem Huffmana. |
|
| |
|
| Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i | | Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i |
| drzew Huffmana. | | drzew Huffmana. |
|
| |
|
| 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. | | 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.=== | | ===Kodowanie Huffmana słowami <math>k</math>-arnymi.=== |
| Linia 308: |
Linia 69: |
| 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. | | 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. |
|
| |
|
| ===Kodowanie prefiskowe z symbolami kodowymi nierównej długości=== | | ===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ła (jest to po | | 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 |
| 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>. |
| ś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 | | 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 | | <math>c</math> (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 | | ustalonego <math>c</math> istnieje algorytm wielomianowy, którego stopień zależy od <math>c</math>. |
| ćwiczenie przypadek gdy <math>c</math> jest dowolne ale wszystkie wagi <math>w[i]</math> są równe. | | |
| | 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. |
|
| |
|
| === Kodowanie prefiskowe z kodami o ograniczonej długości=== | | === Kodowanie prefiksowe z kodami o ograniczonej długości=== |
| Innym ciekawym problemem jest | | Innym ciekawym problemem jest |
| też skonstruowanie optymalnego kodu prefiksowego, w którym wszystkie słowa kodowe są ograniczone przez pewną
| | 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 | | 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 |
| wielomianowe dla tego problemu, stopień wielomianu niezależny od <math>L</math>. | | wielomianowe dla tego problemu, w których stopień wielomianu jest niezależny od <math>L</math>. |
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ę , która każdemu symbolowi przyporządkowuje niepusty ciąg binarny
. Całe słowo zostanie zakodowane na słowo (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 znaleźć binarne kodowanie prefiksowe takie,
że ma minimalną długość.
Przykład
Niech . Liczby wystąpień symboli w słowie są:
Optymalnym kodowaniem jest zostaje zakodowane na , ciąg binarny długości . Optymalne drzewo binarne odpowiadające optymalnemu kodowi prefiksowemu jest pokazane na rysunku.
Rysunek 2:Drzewo Huffmana kodujące optymalnie symbole z wagami odpowiednio
. 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:
Długość tekstu 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:
.
Niech będzie liczbą różnych symboli w , będzie liczbą wystąpień -tego symbolu. Problem możemy rozwiązać, stosując algorytm dla problemu Optymalne Sklejanie Par dla ciągu . 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 , w element tworzy również dowiązania,
staje się lewym synem , natomiast staje się prawym synem.
Algorytm Huffmana (nieformalny opis)
Konfiguracje pośrednie algorytmu to zbiory drzew,
początkowo każdy pojedyńczy element z wagą 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 , a jeśli wagi są posortowane, to w czasie liniowym.
Kodowanie Huffmana słowami -arnymi.
Pozostawiamy jako ćwiczenie podobny problem, ale gdy kodujemy w alfabecie -arnym, mamy teraz symbole . 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 , gdzie 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 .
Pozostawiamy jako ćwiczenie znalezienie efektywnego algorytmu dla małych ( lub ). Dla dowolnego
(będącego częścią wejścia) i dowolnych wag jest to zbyt trudne, nie znamy algorytmu wielomianowego. Dla
ustalonego istnieje algorytm wielomianowy, którego stopień zależy od .
Natomiast pozostawiamy jako
ćwiczenie przypadek, gdy jest dowolne, a wszystkie wagi 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ę . 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 .
