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

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 = a b r a c a d a b r a$ . Liczby wystąpień symboli w słowie $x$ są:

w_{a} = 5, w_{b} = 2, w_{c} = 1, w_{d} = 1, w_{r} = 2

Optymalnym kodowaniem jest $h (a) = 0, h (b) = 10, h (c) = 1100, h (d) = 1101, h (r) = 111$ $a b r a c a d a b r a$ 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], \dots 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 (n \log 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, \dots, 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$ .

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

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

Spis treści

Kodowanie prefiksowe: drzewa i kody Huffmana

Optymalne kodowanie prefiksowe

Kodowanie Huffmana słowami $k$ -arnymi.

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

Kodowanie prefiksowe z kodami o ograniczonej długości

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-<font size="6">Zaawansowane algorytmy tekstowe II</font>
+<font size="6"> Zaawansowane algorytmy tekstowe II </font>
 __TOC__
-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 wszsytkie 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''.
+W module tym zajmiemy się kodowaniem Huffmana. Zwiazane sa z nimi różne ciekawe problemy tekstowe.
-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. 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. 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:<center><math>sufix_{SUF[1]}< sufix_{SUF[2]}<sufix_{SUF[3]}<\ldots sufix_{SUF[n]}</math></center>
+== Kodowanie prefiksowe: drzewa i kody Huffmana ==
-<center>[[Grafika:Zasd_2_1.jpg]]
+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:
-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>.
+===Optymalne kodowanie prefiksowe===
+Dla danego słowa <math>x</math> znaleźć binarne kodowanie prefiksowe takie,
-Tablica sufiksowa ma następująca miłą własność: Niech
+że <math>h(x)</math> ma minimalną długość.
-<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.
-<center> [[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.</center>
-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|||
-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>
-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>.
-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.
-Lokalnie wykonana praca w jednej iteracjijest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego.
-Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.
-<center> [[Grafika:Zasd_2_4.jpg]] <br> Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu
-<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>
-== Oblicanie tablicy ''lcp'' ==
-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>
 }}
-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.
-==Konstrukcja tablicy ''SUF'' w czasie ''O(n log n)'': algorytm KMR ==
+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 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>.
+<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>
+</center>
-'''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>
+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>.
-<math>NAZWA_0</math>, <math>NAZWA_1</math>, <math>NAZWA_2</math>,<math> \ldots NAZWA_{\log n}</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>. 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.
-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>.
+{{algorytm| Huffmana (nieformalny opis)|algorytm_huffman_nieformalny|
+Konfiguracje pośrednie algorytmu to zbiory drzew,
-<center> [[Grafika:Zasd_2_4a.jpg]]</center>
+początkowo każdy pojedyńczy element <math>i</math> z wagą <math>w[i]</math> jest pojedyńczym drzewem.
-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>.
+Korzeń każdego drzewa reprezentuje sklejenie jego wszystkich liści.
-<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:
-. 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>
-. 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>.
-<math>SUF[M]</math> daje posortowany ciąg sufiskówzaczynających się na pozycjach ze zbioru <math>M</math>.
-=== Redukcja liczenia <math>SUF[M]</math> do liczenia tablicy sufiksowej rozmiaru <math>\frac{2}{3}n</math> ===
-Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie <math>x</math> korzystając z 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.
-Tworzymy nowe słowo <math>compress(x)</math> w następujący sposób:
-<center><math> y1\ =\ \ kod(a_1a_2a_3)\cdot kod(a_4a_5a_6) \ldots kod(a_{n-2}a_{n-1}a_n)</math>
-<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|
-. <math>x' := compress(x)</math>;
-. obliczamy tablicę sufiksową dla x' rekurencyjnie;
-. obliczamy <math>SUF[M]</math> wczasie liniowym, znając tablicę sufiksową dla x';
-. obliczamy <math>SUF[N]</math> w czasie liniowym (bez rekursji)znając <math>SUF[M]</math>;
-. 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ó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.
+Pozostawiamy jako ćwiczenie przerobienie algorytmu Optymalne-Sklejanie-Par na algorytm liczenia kodów i
+drzew Huffmana.
-Pokażemy na przykładzie jak porównać sufiks typu M z sufiksem typu N.
+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 alternatywie:
-<center><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></center>
+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.
-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 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>.
-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>
+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.
-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).
+=== 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ę <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, w których stopień wielomianu jest niezależny od <math>L</math>.

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

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

Kodowanie prefiksowe: drzewa i kody Huffmana

Optymalne kodowanie prefiksowe

Kodowanie Huffmana słowami k-arnymi.

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

Kodowanie prefiksowe z kodami o ograniczonej długości

Menu nawigacyjne

Szukaj

Kodowanie Huffmana słowami $k$ -arnymi.