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

@@ Linia 1: / Linia 1: @@
-Moduł ZASD:\ zaawansowane algorytmy tekstowe II''' \myskip<!--%--------+---------+---------+---------+---------+---------+---------+---------+-->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. {\em Occurrences})
+<font size="6"> Zaawansowane algorytmy tekstowe II </font>
-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ę. \noindentCią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>
-<!--%**********************************************************-->\begin{figure}[hbt]\begin{center}\includegraphics[width=7cm]{teksty_fig20.eps} \caption{Tablicą sufiksową tekstu <math>x\ =\ babaabababba\#</math> jest ciąg  <center><math>SUF\ =\  [4,\ 2,\ 5,\ 7,\ 9,\ 12,\ 3,\ 1,\ 6,\6,\ 8,\ 11,\ 10]</math></center> Wartości najdłuższego wspólnego prefiksu między kolejnymi słowami są przedstawione jakozacienione segmenty. Odpowiadają one tablicy <math>lcp\ =\ [1,\ 3,\ 4,\ 2,\ 1,\ 0,\ 2,\ 4,\ 3,\ 2,\ 1]</math>. }\end{center}\end{figure}
-<!--%--------+---------+---------+---------+---------+---------+---------+---------+-->\noindentOznaczmy przez <math>lcp[k]</math> długść wspólnego prefisku <math>k</math>-tego i następnego sufiksuw kolejności leksykograficznej.\myskip<!--%--><!--%\noindent '''Przykład'''\ Niech <math>x\ =\ babaabababba\#</math>, wtedy (patrz rysunek)--><!--%<center><math>SUF\ =\ [4,\ 2,\ 5,\ 7,\ 9,\ 12,\ 3,\ 1,\ 6,\ 6,\ 8,\ 11,\ 10]</math></center>--><!--%<center><math>lcp = [1,\ 3,\ 4,\ 2,\ 1,\ 0,\ 2,\ 4,\ 3,\ 2,\ 1]</math></center>-->
-\noindent Tablica sufiksowa ma następująca miłą własność: Niech
-\begin{center}<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>.\end{center}Wtedy <math>Occ(z,x)</math> jest przedziałem w tablicy sufiksowej od <math>min_{z}</math> do <math>max_{z}</math>.<!--%-->\myskip '''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ę {\em 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 jestdługość odpowiadającego jej słowa. \myskip<!--%**********************************************************-->\begin{figure}[bh]\begin{center}\includegraphics[width=15cm]{teksty_fig15.eps} \caption{Drzewo sufiksowe dla tekstu <math>x\ =\ babaabababba</math>. Na ko"ncu jest dodany zank <math>\#</math>. Ko"ncowe węzły zawierająinformację gdzie zaczyna się sufiks, którym  dochodzimy do danego węzła.}\end{center}\end{figure}\myskip Obie reprezentacje rozwiązują szybko problem string-matchingu, oraz mają rozmiar liniowy.
-\noindent 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>.\subsection*{Szukanie podsłów}Pokażemy jak sprawdzać, czy <math>z</math> występuje w <math>x</math>.\begin{description}\item{'''Używając drzewa sufiskowego}, czas <math>O(m)</math>}\mbox{ \ '''\\{\em 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 {\em utknęliśmy} i nie dało siędalej schodzić po drzewie to oznacza, że <math>z \notin Subwords(x)</math>.<!--%-->\item{'''Używając tablicy sufiksowej}, czas <math>O(m \log n)</math>}\mbox{ \ '''\\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ę odz.\end{description}<!--%--><!--%-->\subsection*{Liczenie liczby podsłów}Pokażemy jak liczyć liczbę podsłów słowa <math>x</math> mając tablicę sufiksową lub drzewo sufiksowe. Ko"ncowymarker <math>\#</math> nie traktujemy jako części słowa <math>x</math>. Liczba podsłów  jest równa <math>|Subwords(x)|</math>. Jeśliwszsytkie symbole słowa są różne to <math>|Subwords(x)|={\choose {n} 2}</math>.\begin{description}\item{'''Używając drzewa sufiskowego}, czas <math>O(n)</math>}\mbox{ \ '''\\Sumujemy wagi krawędzi drzewa.<!--%-->\item{'''Używając tablicy sufiksowej}, czas <math>O( n)</math>}\mbox{ \ '''\\Niech <math>SUMA(lcp)</math> będzie sumą elementówtablicy <math>lcp</math>. Liczbę podsłów obliczamy jako <center><math>{n+1\choose{2}}-SUMA(lcp)</math></center><!--% \frac{n\cdot (n+1)}{2}-SUMA.<center><math>-->\end{description}
-\noindent Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona(korzystając z drzewa sufisowego lub z tablicy sufiksowej). \myskip '''Przykład.'''\ 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>\myskip<!--%-->\noindent 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>). \myskip Pozostawiamy jako ćwiczenieznalezienie liniowego algorytmu liczącego tablicę <math>ROT</math>, zakładając, że mamy liniowy algorytm liczeniatablicy sufiksowej. \myskip '''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.<!--%-->\myskipSł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:<!--%    </math></center>SUF_1\ =\ [0\;1],\ SUF_2\ =\ [2\;0\;1], \ SUF_3\ =\ [2\;3\;0\;4\;1],<center><math>--></math></center>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].<center><math>\noindent Pozostawiamy jako ćwiczenie policzenie wzoru na <math>|Subwords(F_n)|</math>.<!--%--------+---------+---------+---------+---------+---------+---------+---------+-->
-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.%%===================================================================================
-Pokażemy konstruktywanie następujący istotny fakt: \vskip 0.1cm jeśli znamy tablicę sufiksową i tablicę<math>lcp</math> to drzewo sufiksowe dla danego tekstu możemy {\em łatwo} skonstruować w czasie liniowym.\myskipPrzypuśćmy, że, <math>SUF\ =\ [i_1,i_2,\ldots,i_n]</math>, a więc:</math></center>sufiks_{i_1}< sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.<center><math>\begin{center}\begin{minipage}{12cm}\noindent '''Algorytm''' Drzewo-Susfiksowe;
-<math>T</math> := drzewo reprezentujące <math>sufiks_{i_1}</math> (jedna krawędź);
-'''for''' <math>k:=2</math> '''to''' <math>n</math> '''do'''\\\hspace*{1cm} wstaw nową ścieżkę o sumarycznej etykiecie <math>sufiks_{i_k}</math> do <math>T</math>; \myskip\end{minipage}\end{center}<!--%-->
-<!--%**********************************************************-->
-\begin{figure}[ht]\begin{center}\includegraphics[width=4.7cm]{teksty_fig16.eps}\caption{ Wstawianie kolejnego sufiksu <math>sufiks_{i_k}</math> do drzewa sufiskowego, przed włożeniem wszystkiekrawędzie{\em ścieżki roboczej} od <math>u</math> do korzenia   {są skierowane } w lewo.  }  <span id="suffix1" \> \end{center}\end{figure}<!--%**********************************************************-->
-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łnaetykieta 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żceod korzenia etykietowanej <math>\gamma_1</math>. Podstawowym {\em 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 jestproporcjonalny do sumy: jeden plus zmniejszenie głębokości nowego liścia w stosunku do starego. Suma tychzmniejsze"n 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. \myskipLokalnie wykonana praca w jednej iteracjijest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do porzedniego.\myskipHistoria algorytmu jest pokazana dla przykładowego tekstu na rysunkach.
-<!--%**********************************************************-->\begin{figure}[ht]\begin{center}\includegraphics[width=10cm]{teksty_fig17.eps}\caption{Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu <math>babaabababba\#</math>. }  <span id="suffix1" \> \end{center}\end{figure}<!--%**********************************************************-->
-<!--%**********************************************************-->\begin{figure}[htb]\begin{center}\includegraphics[width=14.4cm]{teksty_fig18.eps}\caption{Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu <math>babaabababba\#</math>. }  <span id="suffix2" \> \end{center}\end{figure}<!--%**********************************************************-->
+__TOC__
-Niech <math>rank(i)</math> b"dzie poycją <math>sufiks_i</math> w porządkuleksykograficznym. W naszym przykładowym słowie mamy: </math></center>rank\ =\ [8,\ 2,\ 7,\ 1,\ 3,\ 9,\ 4,\ 10,\ 5,\ 12,\11,\ 6]<center><math>
-Niech \  <math>lcp'[k]\ =\ lcp[rank[k]-1]</math>.\ \myskip Załóżmy, dla uproszczenia, że  <math>lcp[0]=0</math>. Obliczamy tablice<math>lcp',\ lcp</math> następująco: \vskip 0.5 cm<!--%-->\begin{center}\begin{minipage}{12cm}\noindent '''Algorytm''' Oblicz-lcp;
+W module tym zajmiemy się kodowaniem Huffmana. Zwiazane sa z nimi różne ciekawe problemy tekstowe.
-'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''\\\hspace*{0.5cm} oblicz <math>lcp'[k]</math> korzystając z faktu, że<!--%\hspace*{0.5cm}--><math>lcp'[k]\ge lcp'[k-1]-1</math>; \\\hspace*{0.7cm}  koszt iteracji <math>O(lcp'[k]-lcp'[k-1]+const)</math>
-'''for''' <math>k:=1</math> '''to''' <math>n</math> '''do'''\\\hspace*{0.5cm} <math>lcp[rank[k]-1]</math> := <math>lcp'[k]</math> \myskip\end{minipage}\end{center}<!--%-->
-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  {\em do przodu} (sprawdzając kolejne symbole). Jest to analiza typu {\em jeden krok do tyłu i kilka doprzodu}. Liczba iteracji jest liniowa, więc liczba kroków do tyłu też.  Poniewaź odległość {\em do celu}jest liniowa, to suma kroków też jest liniowa.
-<!--%----------------------------------------------------------------------->
+== Kodowanie prefiksowe: drzewa i kody Huffmana ==
-Opiszemy uproszczoną wersję algorytmu  Karpa-Millera-Rosenberga (w skrócie algorytmu {\em KMR})rozwiązywania problemów tekstowych metodą {em 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 {\em dokładnie } długość <math>2^k</math>.
-<!--%\myskip '''Obserwacja'''.\ W sekcji tej przez podsłowa/segmenty rozumiemy podsłowa łącznie  z ich pozycją w--><!--%tekście. Jest to istotnie rórne od poprzednich sekcji. \myskip-->
+Zbiór słów jest prefiksowy, gdy żadne słowo nie jest prefiksem drugiego. Taki zbiór słów odpowiada drzewu,
-'''Słowanik podsłów bazowych} (w skrócie <math>DBF(x)</math>, od ang. {\em dictionary of basic factors''') składa sięz <math>\log n</math> tablic  <math>\textsl{NAZWA}_0</math>,\ <math>\textsl{NAZWA}_1</math>,\ <math>\textsl{NAZWA}_2</math>,\ldots <math>\textsl{NAZWA}_{\log n}</math>.
+którego ścieżki etykietowane są symbolami. W przypadku binarnym możemy przyjąć, że krawędź w lewo jest
-Zakładamy, że <math>\textsl{NAZWA}_k[i]</math> jest pozycją słowa <math>x[i..i+2^k-1]</math> na posortowanej liście (bezpowtórze"n) wszystkich podsłów długości <math>2^k</math> słowa <math>x</math>. Jeśli długość {\em wystaje} poza koniec <math>x</math> toprzyjmujemy że są tam (wirtualnie) same symbole <math>\#</math>. Poniżej przedsatwiamy przykład słownika podsłówbazowych  <math>DBF(abaabbaa)</math>. \vskip 0.5cm
+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:
+===Optymalne kodowanie prefiksowe===
+Dla danego słowa <math>x</math> znaleźć binarne kodowanie prefiksowe takie,
+że <math>h(x)</math> ma minimalną długość.
+{{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>
+}}
+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><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>
+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>.
+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.
+{{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.
+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 <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.
+===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.
+=== 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

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

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.