|
|
| Linia 9: |
Linia 9: |
|
| |
|
|
| |
|
| == 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>
| |
| '''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 == |
|
| |
|
Zaawansowane algorytmy tekstowe II
W module tym zajmiemy się przedw wszystkim dwoma niezależnymi problemami: string-matchingiem w czasie liniowym i pamięci stałej, oraz kodowaniem Huffmana. Zwiazane sa z nimi róne inne 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 .
