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
Nie podano opisu zmian
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 6 wersji utworzonych przez 2 użytkowników)
Linia 3: Linia 3:
__TOC__  
__TOC__  


W module tym zajmiemy się przedw wszystkim dwoma niezależnymi problemami: ‘’string-matching’’ w czasie liniowym i pamięci stałej, oraz kodowaniem Huffmana. Zwiazane sa z nimi róne inne ciekawe problemy tekstowe.
W module tym zajmiemy się kodowaniem Huffmana. Zwiazane sa z nimi różne ciekawe problemy tekstowe.






== String-matching w pamięci stałej dla specjalnych wzorów ==
Załóżmy, ż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>
Oznaczmy przez <math>MaxSuf(w)</math>  leksykograficznie  maksymalny 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>
&nbsp;&nbsp;&nbsp;'''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> daje wynik całkowicie niepoprawny. Poprawność algorytmu jest wyjaśniona na rysunku. Korzystamy z następującej prostej własności:
<br>
<center> prefiks specjalnego słowa jest też specjalny. <center>
<center>[[Grafika:Naiwneliczenieokresu.jpg]]<br><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 <math>x</math> jest specjalne.
Program wczytuje dwa teksty, pierwszy z nich jest specjalny:  <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>, że <math>y[i\ldots i+m-1]\ =\ x</math>. Zapisujemy program w języku C++.
{{algorytm|Specjalny-String-Matching|algorytm_specjalny_string_matching|
&nbsp;#include <iostream.h><br>
&nbsp;#include string.h<br>
&nbsp;int <math>i=0</math>, <math>j = 0</math>, <math>p = 1</math>;<br>
&nbsp;void przesun();<br>
&nbsp;main() {<br>
&nbsp;char[] x,y; cin>>x>>y; m<math>=</math>strlen(x); n<math>=</math>strlen(y);<br>
&nbsp;while (i <math><=</math> n-m-1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;{ if (j<math>==</math>m) {cout<<i<<endl;  przesun();};<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if (x[j]<math>==</math>y[i+j]) {j<math>=</math>j+1; if (j<math>==</math>1)  <math>||</math> (x[j-1]<math>!=</math>x[j-1-p]) p<math>=</math>j;};<br>
&nbsp;&nbsp;&nbsp;&nbsp; else przesun(); } }<br> 
void przesun()<br>
&nbsp;&nbsp;&nbsp;{ if (j-1<2p) {i<math>=</math>i+p; j<math>=</math>0;} else {j<math>=</math>j-p; i<math>=</math>i+p;}
}
}}
Program jest wstępem do programu szukającego dowolne podsłowo, niekoniecznie specjalne. Podstawowym niezmiennikiem  w programie przed każdym wykonaniem i po każdym zakończeniu pętli ''while'' jest:
'''(A)\ ''' <math>x[0 \ldots j-1]\ =\ y[i \ldots i+j-1]</math>,
'''(B)\ ''' Program wypisał wszystkie wcześniejsze wystąpienia <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ąpienia 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 liniowym i pamięci
stałej. Algorytm ten jest modyfikacją algorytmu Specjalny-String-Matching, w którym 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>, 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, 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 szukania 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: <br>
dla każdego prefiksu liczymy jego maksymalny sufiks, jak również dodatkowo jego okres.
<br>
To właśnie
liczenie okresu daje efektywność, chociaż na końcu ten okres nie jest nam potrzebny.
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>
&nbsp;&nbsp;&nbsp;'''if''' <math>x[i] < x[i - period]</math> \textbf{then} <math>period := i</math><br>
&nbsp;&nbsp;&nbsp;'''else if''' <math>x[i] > x[i - period]</math> ''then'''<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''return''' <math>(i-1, period)</math>;<br>
'''return''' <math>(|x|, period)</math>;
}}
Skorzystamy z algorytmu ''Najdłuższy-Specjalny-Prefiks''. Funkcja ''Maksymalny-Sufiks'' liczy początkową pozycję i okres maksymalnego sufiksu.
{{algorytm|funkcja Maksymalny-Sufiks(x)|fun_max_suf|
<math>j := 1</math>;<br>
'''repeat'''<br>
&nbsp;&nbsp;&nbsp;<math>(i,period) :=</math> ''Najdłuższy-Specjalny-Prefiks''<math>(x[j.. n])</math>;<br>
&nbsp;&nbsp;&nbsp;'''if''' <math>i=n</math> '''then return''' <math>(j, period)</math><br>
&nbsp;&nbsp;&nbsp;'''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>
&nbsp;&nbsp;&nbsp;<math>r := (i-s) \mod p</math>;<br>
&nbsp;&nbsp;&nbsp;'''if''' (<math>x[i] = x[s+r])</math> '''then''' <math>i := i+1</math><br>
&nbsp;&nbsp;&nbsp;'''else if''' (<math>x[i] < x[s+r])</math> '''then begin'''
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>i := i+1</math>; <math>p := i-s</math>;
&nbsp;&nbsp;&nbsp;'''else'''
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>s := i-r</math>; <math>i := s+1</math>; <math>p := 1</math>;<br>
'''return''' <math>s</math>;<br>
}}
== Kodowanie prefiksowe: drzewa i kody Huffmana ==
== Kodowanie prefiksowe: drzewa i kody Huffmana ==


Linia 242: 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><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ównież 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>
Linia 258: Linia 41:
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ść 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

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”