IDZ DO
IDZ DO
PRZYKŁADOWY ROZDZIAŁ
PRZYKŁADOWY ROZDZIAŁ
Algorytmy, struktury danych
SPIS TRE CI
SPIS TRE CI
i techniki programowania.
KATALOG KSIĄŻEK
KATALOG KSIĄŻEK
Wydanie III
KATALOG ONLINE
KATALOG ONLINE
Autor: Piotr Wróblewski
ISBN: 83-7361-101-0
ZAMÓW DRUKOWANY KATALOG
ZAMÓW DRUKOWANY KATALOG
Format: B5, stron: 360
TWÓJ KOSZYK
TWÓJ KOSZYK
Algorytmika stanowi gałą wiedzy, która w ciągu ostatnich kilkudziesięciu lat
dostarczyła wielu efektywnych narzędzi wspomagających rozwiązywanie różnorodnych
DODAJ DO KOSZYKA
DODAJ DO KOSZYKA
problemów za pomocą komputera. Teoria algorytmów i struktur danych jest jednym
z podstawowych przedmiotów wykładanych na studiach informatycznych i pokrewnych.
Książka, której trzecie i poprawione wydanie trzymasz w ręku, od wielu lat stanowi
CENNIK I INFORMACJE
CENNIK I INFORMACJE
podstawowy podręcznik z dziedziny algorytmiki. Różni się od klasycznych
podręczników akademickich: skierowana jest nie tylko do adeptów informatyki.
ZAMÓW INFORMACJE
ZAMÓW INFORMACJE
Dzięki naciskowi na praktyczną stronę prezentowanych zagadnień powinna
O NOWO CIACH
O NOWO CIACH
zainteresować także osoby programujące hobbystycznie, jak również tych wszystkich,
dla których programowanie jest działalno cią ważną, lecz nie podstawową w pracy
ZAMÓW CENNIK
ZAMÓW CENNIK
zawodowej. Jest to nowoczesny podręcznik dla wszystkich, którzy w codziennej pracy
programistycznej odczuwają potrzebę szybkiego odszukania pewnych informacji
z dziedziny algorytmiki w celu zastosowania ich w swoich programach.
CZYTELNIA
CZYTELNIA
W książce opisano m.in.:
" Techniki rekurencyjne: co to jest rekurencja i jak ją stosować w praktyce?
FRAGMENTY KSIĄŻEK ONLINE
FRAGMENTY KSIĄŻEK ONLINE
" Sortowanie danych: najpopularniejsze procedury sortujące.
" Struktury danych: listy, kolejki, zbiory i drzewa w ujęciu praktycznym.
" Derekursywacja: jak zmienić program rekurencyjny (czasami bardzo
czasochłonny) na wersję iteracyjną?
" Algorytmy przeszukiwania: przeszukiwanie liniowe, binarne i transformacja
liniowa (ang. hashing).
" Przeszukiwanie tekstów: opis najbardziej znanych metod przeszukiwania tekstów
(Boyera i Moore'a, Rabina i Karpa, brute-force, K-M-P).
" Zaawansowane techniki programowania: dziel i rząd , programowanie
dynamiczne, algorytmy żarłoczne (ang. greedy).
" Algorytmika grafów: opis jednej z najciekawszych struktur danych
Wydawnictwo Helion
występujących w informatyce.
ul. Chopina 6
" Sztuczna inteligencja: czy komputery mogą my leć?
44-100 Gliwice
" Kodowanie i kompresja danych: opis najpopularniejszych metod kodowania
tel. (32)230-98-63
i kompresji danych systemu kryptograficznego z kluczem publicznym
e-mail: helion@helion.pl
i metody Huffmana
W książce znajdziesz również liczne przykłady i zadania, które pomogą Ci sprawdzić
swoją wiedzę. Kod ródłowy znajdziesz na dołączonej dyskietce.
Spis treści
Przedmowa......................................................................................11
Rozdział 1. Zanim wystartujemy ........................................................................19
1.1. Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych..............21
1.2. Jak to sią niedawno odbyło, czyli o tym, kto wymyślił
metodologią programowania .....................................................................................23
1.3. Proces koncepcji programów .....................................................................................24
1.4. Poziomy abstrakcji opisu i wybór ją zyka...................................................................25
1.5. Poprawność algorytmów............................................................................................27
Rozdział 2. Rekurencja......................................................................................29
2.1. Definicja rekurencji....................................................................................................29
2.2. Ilustracja poją cia rekurencji .......................................................................................31
2.3. Jak wykonują sią programy rekurencyjne?...................................................................32
2.4. Niebezpieczeństwa rekurencji....................................................................................34
2.4.1. Ciąg Fibonacciego ............................................................................................34
2.4.2. Stack overflow!.................................................................................................36
2.5. Pułapek ciąg dalszy ....................................................................................................37
2.5.1. Stąd do wieczności............................................................................................37
2.5.2. Definicja poprawna, ale... .................................................................................38
2.6. Typy programów rekurencyjnych ..............................................................................39
2.7. Myślenie rekurencyjne ...............................................................................................41
2.7.1. Przykład 1.: Spirala...........................................................................................42
2.7.2. Przykład 2.: Kwadraty parzyste .....................................................................44
2.8. Uwagi praktyczne na temat technik rekurencyjnych .................................................45
2.9. Zadania.......................................................................................................................46
2.9.1. Zadanie 2.1........................................................................................................46
2.9.2. Zadanie 2.2........................................................................................................46
2.9.3. Zadanie 2.3........................................................................................................48
2.9.4. Zadanie 2.4........................................................................................................48
2.9.5. Zadanie 2.5........................................................................................................49
2.10. Rozwiązania i wskazówki do zadań.........................................................................49
2.10.1. Zadanie 2.1......................................................................................................49
2.10.2. Zadanie 2.2......................................................................................................50
2.10.3. Zadanie 2.3......................................................................................................50
2.10.4. Zadanie 2.4......................................................................................................51
2.10.5. Zadanie 2.5......................................................................................................52
6 Algorytmy, struktury danych i techniki programowania
Rozdział 3. Analiza sprawności algorytmów........................................................53
3.1. Dobre samopoczucie użytkownika programu ............................................................54
3.2. Przykład 1: Jeszcze raz funkcja silnia........................................................................56
3.3. Przykład 2: Zerowanie fragmentu tablicy ..................................................................60
3.4. Przykład 3: Wpadamy w pułapką ...............................................................................62
3.5. Przykład 4: Różne typy złożoności obliczeniowej.....................................................63
3.6. Nowe zadanie: uprościć obliczenia! ............................................................................66
3.7. Analiza programów rekurencyjnych ...........................................................................66
3.7.1. Terminologia.....................................................................................................67
3.7.2. Ilustracja metody na przykładzie ......................................................................68
3.7.3. Rozkład logarytmiczny .....................................................................................70
3.7.4. Zamiana dziedziny równania rekurencyjnego ..................................................71
3.7.5. Funkcja Ackermanna, czyli coś dla smakoszy .................................................72
3.8. Zadania.......................................................................................................................73
3.8.1. Zadanie 3.1........................................................................................................73
3.8.2. Zadanie 3.2........................................................................................................74
3.8.3. Zadanie 3.3........................................................................................................74
3.8.4. Zadanie 3.4........................................................................................................74
3.9. Rozwiązania i wskazówki do zadań...........................................................................75
3.9.1 Zadanie 3.2.........................................................................................................75
3.9.2. Zadanie 3.4........................................................................................................76
Rozdział 4. Algorytmy sortowania ......................................................................77
4.1. Sortowanie przez wstawianie, algorytm klasy O(N2) ................................................78
4.2. Sortowanie bąbelkowe, algorytm klasy O(N2)...........................................................80
4.3. Quicksort, algorytm klasy O(N log N).......................................................................82
4.4. Heap Sort sortowanie przez kopcowanie ..............................................................85
4.5. Sortowanie przez scalanie ..........................................................................................88
4.6. Uwagi praktyczne.......................................................................................................90
Rozdział 5. Struktury danych .............................................................................93
5.1. Listy jednokierunkowe...............................................................................................94
5.1.1. Realizacja struktur danych listy jednokierunkowej ..........................................96
5.1.2. Tworzenie listy jednokierunkowej....................................................................97
5.1.3. Listy jednokierunkowe teoria i rzeczywistość................................................106
5.2. Tablicowa implementacja list...................................................................................119
5.2.1. Klasyczna reprezentacja tablicowa .................................................................119
5.2.2. Metoda tablic równoległych ...........................................................................121
5.2.3. Listy innych typów .........................................................................................123
5.3. Stos...........................................................................................................................125
5.3.1. Zasada działania stosu.....................................................................................125
5.4. Kolejki FIFO ............................................................................................................129
5.5. Sterty i kolejki priorytetowe.....................................................................................132
5.6. Drzewa i ich reprezentacje .......................................................................................139
5.6.1. Drzewa binarne i wyrażenia arytmetyczne .....................................................142
5.7. Uniwersalna struktura słownikowa ..........................................................................147
5.8. Zbiory.......................................................................................................................152
5.9. Zadania.....................................................................................................................155
5.9.1. Zadanie 5.1......................................................................................................155
5.9.2. Zadanie 5.2......................................................................................................155
5.9.3. Zadanie 5.3......................................................................................................155
5.10. Rozwiązania zadań.................................................................................................155
5.10.1. Zadanie 5.1....................................................................................................155
5.10.2. Zadanie 5.3....................................................................................................156
Spis treści 7
Rozdział 6. Derekursywacja i optymalizacja algorytmów ...................................157
6.1. Jak pracuje kompilator? ...........................................................................................158
6.2. Odrobina formalizmu nie zaszkodzi!..........................................................................160
6.3. Kilka przykładów derekursywacji algorytmów ...........................................................162
6.4. Derekursywacja z wykorzystaniem stosu ................................................................165
6.4.1. Eliminacja zmiennych lokalnych....................................................................166
6.5. Metoda funkcji przeciwnych....................................................................................168
6.6. Klasyczne schematy derekursywacji........................................................................170
6.6.1. Schemat typu while.........................................................................................171
6.6.2. Schemat typu if-else........................................................................................173
6.6.3. Schemat z podwójnym wywołaniem rekurencyjnym .....................................175
6.7. Podsumowanie .........................................................................................................177
Rozdział 7. Algorytmy przeszukiwania ..............................................................179
7.1. Przeszukiwanie liniowe............................................................................................179
7.2. Przeszukiwanie binarne............................................................................................180
7.3. Transformacja kluczowa (hashing) ..........................................................................181
7.3.1. W poszukiwaniu funkcji H .............................................................................183
7.3.2. Najbardziej znane funkcje H...........................................................................184
7.3.3. Obsługa konfliktów dostą pu ...........................................................................187
7.3.4. Powrót do zródeł .............................................................................................187
7.3.5. Jeszcze raz tablice!..........................................................................................188
7.3.6. Próbkowanie liniowe ......................................................................................189
7.3.7. Podwójne kluczowanie ...................................................................................191
7.3.8. Zastosowania transformacji kluczowej...........................................................193
7.3.9. Podsumowanie metod transformacji kluczowej ...............................................193
Rozdział 8. Przeszukiwanie tekstów.................................................................195
8.1. Algorytm typu brute-force .......................................................................................195
8.2. Nowe algorytmy poszukiwań...................................................................................197
8.2.1. Algorytm K-M-P.............................................................................................198
8.2.2.Algorytm Boyera i Moore a.............................................................................203
8.2.3. Algorytm Rabina i Karpa................................................................................205
Rozdział 9. Zaawansowane techniki programowania.........................................209
9.1. Programowanie typu dziel i zwycią żaj .................................................................210
9.1.1. Odszukiwanie minimum i maksimum w tablicy liczb....................................211
9.1.2. Mnożenie macierzy o rozmiarze NN............................................................214
9.1.3. Mnożenie liczb całkowitych ...........................................................................217
9.1.4. Inne znane algorytmy dziel i zwycią żaj ......................................................218
9.2. Algorytmy żarłoczne , czyli przekąsić coś nadszedł już czas... ............................219
9.2.1. Problem plecakowy, czyli niełatwe jest życie turysty-piechura ...........................220
9.3. Programowanie dynamiczne ....................................................................................223
9.4. Uwagi bibliograficzne..............................................................................................227
Rozdział 10. Elementy algorytmiki grafów ..........................................................229
10.1. Definicje i poją cia podstawowe .............................................................................230
10.2. Sposoby reprezentacji grafów ................................................................................232
10.3. Podstawowe operacje na grafach ...........................................................................234
10.3.1. Suma grafów .................................................................................................234
10.3.2. Kompozycja grafów......................................................................................234
10.3.3. Potą ga grafu ..................................................................................................235
10.4. Algorytm Roy-Warshalla .......................................................................................236
10.5. Algorytm Floyda-Warshalla...................................................................................239
10.6. Algorytm Dijkstry ..................................................................................................243
8 Algorytmy, struktury danych i techniki programowania
10.7. Drzewo rozpinające minimalne..............................................................................244
10.8. Przeszukiwanie grafów ..........................................................................................245
10.8.1. Strategia w głąb .........................................................................................246
10.8.2. Strategia wszerz .........................................................................................247
10.9. Problem właściwego doboru ..................................................................................249
10.10. Podsumowanie .....................................................................................................254
Rozdział 11.Algorytmy numeryczne....................................................................255
11.1. Poszukiwanie miejsc zerowych funkcji .................................................................255
11.2. Iteracyjne obliczanie wartości funkcji....................................................................257
11.3. Interpolacja funkcji metodą Lagrange a ................................................................258
11.4. Różniczkowanie funkcji.........................................................................................260
11.5. Całkowanie funkcji metodą Simpsona...................................................................262
11.6. Rozwiązywanie układów równań liniowych metodą Gaussa ................................263
11.7. Uwagi końcowe......................................................................................................266
Rozdział 12. Czy komputery mogą myśleć? ........................................................267
12.1. Przegląd obszarów zainteresowań Sztucznej Inteligencji......................................268
12.1.1. Systemy eksperckie.......................................................................................269
12.1.2. Sieci neuronowe............................................................................................271
12.2. Reprezentacja problemów......................................................................................272
12.2.1. Ćwiczenie 12.1..............................................................................................274
12.3. Gry dwuosobowe i drzewa gier..............................................................................274
12.4. Algorytm mini-max................................................................................................276
Rozdział 13. Kodowanie i kompresja danych ......................................................281
13.1. Kodowanie danych i arytmetyka dużych liczb...........................................................283
13.1.1. Kodowanie symetryczne...............................................................................284
13.1.2. Kodowanie asymetryczne .............................................................................285
13.1.3. Metody prymitywne......................................................................................292
13.1.4. Aamanie szyfrów...........................................................................................293
13.2. Techniki kompresji danych ....................................................................................294
13.2.1. Kompresja poprzez modelowanie matematyczne.........................................296
13.2.2. Kompresja metodą RLE................................................................................297
13.2.3. Kompresja danych metodą Huffmana ..........................................................298
13.2.4. Kodowanie LZW ..........................................................................................304
13.2.5. Idea kodowania słownikowego na przykładach ...........................................304
13.2.6. Opis formatu GIF..........................................................................................307
Rozdział 14. Zadania różne................................................................................311
14.1. Teksty zadań...........................................................................................................311
14.1.1. Zadanie 14.1..................................................................................................311
14.1.2. Zadanie 14.2..................................................................................................312
14.1.3. Zadanie 14.3..................................................................................................312
14.1.4. Zadanie 14.4..................................................................................................312
14.1.5. Zadanie 14.5..................................................................................................312
14.1.6. Zadanie 14.6..................................................................................................312
14.1.7. Zadanie 14.7..................................................................................................312
14.1.8. Zadanie 14.8..................................................................................................313
14.1.9. Zadanie 14.9..................................................................................................313
14.1.10. Zadanie 14.10..............................................................................................313
14.1.11. Zadanie 14.11..............................................................................................313
14.1.12. Zadanie 14.12..............................................................................................313
Spis treści 9
14.2. Rozwiązania ...........................................................................................................313
14.2.1. Zadanie 14.1..................................................................................................313
14.2.2. Zadanie 14.3..................................................................................................314
14.2.3. Zadanie 14.4..................................................................................................315
14.2.4. Zadanie 14.10................................................................................................315
14.2.5. Zadanie 14.12................................................................................................316
Dodatek A Poznaj C++ w pięć minut! ..............................................................319
Dodatek B Systemy obliczeniowe w pigułce.....................................................337
Literatura ......................................................................................343
Spis ilustracji ................................................................................345
Spis tablic.....................................................................................349
Skorowidz......................................................................................351
Rozdział 8.
Przeszukiwanie tekstów
Zanim na dobre zanurzymy sią w lekturą nowego rozdziału, należy wyjaśnić pewne nie-
porozumienie, które może towarzyszyć jego tytułowi. Otóż za tekst bą dziemy uważali
ciąg znaków w sensie informatycznym. Nie zawsze bą dzie to miało cokolwiek wspólnego
z ludzką pisaniną ! Tekstem bą dzie na przykład również ciąg bitów1, który tylko przez
umowność może być podzielony na równej wielkości porcje, którym przyporządkowano
pewien kod liczbowy2.
Okazuje sią wszelako, że przyją cie konwencji dotyczących interpretacji informacji ułatwia
wiele operacji na niej. Dlatego też pozostańmy przy ogólnikowym stwierdzeniu tekst
wiedząc, że za tym określeniem może sią kryć dość sporo znaczeń.
8.1. Algorytm typu brute-force
Zadaniem, które bą dziemy usiłowali wspólnie rozwiązać, jest poszukiwanie wzorca3 w
o długości M znaków w tekście t o długości N. Z łatwością możemy zaproponować
dość oczywisty algorytm rozwiązujący to zadanie, bazując na pomysłach symbolicz-
nie przedstawionych na rysunku 8.1.
Rysunek 8.1.
Fragmenty (jeszcze) zgodne
Algorytm typu brute-
-force przeszukiwania
tekstu
T E L E F O N K O T E L E E K S O R A Z
N-1
0 j M-1 0 i
wzorzec w Badany tekst t
1
Reprezentujący np. pamią ć ekranu.
2
Np. ASCII lub dowolny inny.
3
Ang. pattern matching.
196 Algorytmy, struktury danych i techniki programowania
Zarezerwujmy indeksy i do poruszania sią odpowiednio we wzorcu i tekście pod-
czas operacji porównywania znak po znaku zgodności wzorca z tekstem. Załóżmy, że
w trakcie poszukiwań obszary obją te szarym kolorem na rysunku okazały sią zgodne.
Po stwierdzeniu tego faktu przesuwamy sią zarówno we wzorcu, jak i w tekście o jedną
pozycją do przodu ( ; ).
Cóż sią jednak powinno stać z indeksami oraz podczas stwierdzenia niezgodności
znaków? W takiej sytuacji całe poszukiwanie kończy sią porażką, co zmusza nas do
anulowania szarej strefy zgodności. Czynimy to poprzez cofnią cie sią w tekście o to,
co było zgodne, czyli o znaków, wyzerowując przy okazji . Omówmy jeszcze mo-
ment stwierdzenia całkowitej zgodności wzorca z tekstem. Kiedy to nastąpi? Otóż
nietrudno zauważyć, że podczas stwierdzenia zgodności ostatniego znaku powinno
zrównać sią z . Możemy wówczas łatwo odtworzyć pozycją , od której wzorzec startuje
w badanym tekście: bą dzie to oczywiście .
Tłumacząc powyższe sytuacje na C++, możemy łatwo dojść do nastą pującej procedury:
txt-1.cpp
Sposób korzystania z funkcji jest przedstawiony na przykładzie nastą pującej
funkcji :
Jako wynik funkcji zwracana jest pozycja w tekście, od której zaczyna sią wzorzec, lub
w przypadku, gdy poszukiwany tekst nie został odnaleziony jest to znana nam już
doskonale konwencja. Przypatrzmy sią dokładniej przykładowi poszukiwania wzorca
w pewnym tekście binarnym (patrz rysunek 8.2).
Rozdział 8. f& Przeszukiwanie tekstów 197
Rysunek 8.2.
` 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1
Fałszywe starty
1 0 1 0 0
podczas poszukiwania
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
1 0 1 0 0
Rysunek jest nieco uproszczony: w istocie poziome przesuwanie sią wzorca oznacza in-
strukcje zaznaczone na listingu jako (*), natomiast cała szara strefa o długości k oznacza
k-krotne wykonanie (**).
Na podstawie zobrazowanego przykładu możemy spróbować wymyślić taki najgorszy
tekst i wzorzec, dla których proces poszukiwania bą dzie trwał możliwie najdłużej. Cho-
dzi oczywiście o zarówno tekst, jak i wzorzec złożone z samych zer i zakończone je-
dynką4.
Spróbujmy obliczyć klasą tego algorytmu dla opisanego przed chwilą ekstremalnego naj-
gorszego przypadku. Obliczenie nie należy do skomplikowanych czynności: zakłada-
jąc, że restart algorytmu bą dzie konieczny razy, i wiedząc, że pod-
czas każdego cyklu jest konieczne wykonanie porównań, otrzymujemy natychmiast
, czyli około5 .
Zaprezentowany w tym paragrafie algorytm wykorzystuje komputer jako bezmyślne,
ale sprawne liczydło6. Jego złożoność obliczeniowa eliminuje go w praktyce z przeszu-
kiwania tekstów binarnych, w których może wystąpić wiele niekorzystnych konfigura-
cji danych. Jedyną zaletą algorytmu jest jego prostota, co i tak nie czyni go na tyle atrak-
cyjnym, by dać sią zamą czyć jego powolnym działaniem.
8.2. Nowe algorytmy poszukiwań
Algorytm, o którym bą dzie mowa w tym rozdziale, posiada ciekawą historią , którą
w formie anegdoty warto przytoczyć. Otóż w 1970 roku S. A. Cook udowodnił teore-
tyczny rezultat dotyczący pewnej abstrakcyjnej maszyny. Wynikało z niego, że istniał
4
Zera i jedynki symbolizują tu dwa różne od siebie znaki.
5
Zwykle bą dzie znacznie mniejsze niż .
6
Termin brute-force jeden z moich znajomych ślicznie przetłumaczył jako metodą mastodonta .
198 Algorytmy, struktury danych i techniki programowania
algorytm poszukiwania wzorca w tekście, który działał w czasie proporcjonalnym do
w najgorszym przypadku. Rezultat pracy Cooka wcale nie był przewidziany do prak-
tycznych celów, niemniej D. E. Knuth i V. R. Pratt otrzymali na jego podstawie algo-
rytm, który był łatwo implementowalny praktycznie ukazując przy okazji, iż pomią -
dzy praktycznymi realizacjami a rozważaniami teoretycznymi nie istnieje wcale aż tak
ogromna przepaść, jakby sią to mogło wydawać. W tym samym czasie J. H. Morris od-
krył dokładnie ten sam algorytm jako rozwiązanie problemu, który napotkał podczas
praktycznej implementacji edytora tekstu. Algorytm K-M-P bo tak bą dziemy go dalej
zwali jest jednym z przykładów dość czą stych w nauce odkryć równoległych: z ja-
kichś niewiadomych powodów nagle kilku pracujących osobno ludzi dochodzi do tego
samego dobrego rezultatu. Prawda, że jest w tym coś niesamowitego i aż sią prosi o ja-
kieś metafizyczne hipotezy?
Knuth, Morris i Pratt opublikowali swój algorytm dopiero w 1976 roku. W mią dzyczasie
pojawił sią kolejny cudowny algorytm, tym razem autorstwa R. S. Boyera i J. S.
Moore a, który okazał sią w pewnych zastosowaniach znacznie szybszy od algorytmu
K-M-P. Został on również równolegle wynaleziony (odkryty?) przez R. W. Gospera.
Oba te algorytmy są jednak dość trudne do zrozumienia bez pogłą bionej analizy, co
utrudniło ich rozpropagowanie.
W roku 1980 R. M. Karp i M. O. Rabin doszli do wniosku, że przeszukiwanie tekstów
nie jest aż tak dalekie od standardowych metod przeszukiwania i wynalezli algorytm,
który działając ciągle w czasie proporcjonalnym do jest ideowo zbliżony do
poznanego już przez nas algorytmu typu brute-force. Na dodatek, jest to algorytm, który
można wzglą dnie łatwo uogólnić na przypadek poszukiwania w tablicach 2-wymiaro-
wych, co czyni go potencjalnie użytecznym w obróbce obrazów.
W nastą pnych trzech sekcjach szczegółowo omówimy sobie wspomniane w tym prze-
glądzie historycznym algorytmy.
8.2.1. Algorytm K-M-P
Wadą algorytmu brute-force jest jego czułość na konfiguracją danych: fałszywe restarty
są tu bardzo kosztowne; w analizie tekstu cofamy sią o całą długość wzorca, zapomi-
nając po drodze wszystko, co przetestowaliśmy do tej pory. Narzuca sią tu niejako
chą ć skorzystania z informacji, które już w pewien sposób posiadamy przecież
w nastą pnym etapie bą dą wykonywane czą ściowo te same porównania, co poprzednio!
W pewnych szczególnych przypadkach przy znajomości struktury analizowanego tek-
stu możliwe jest ulepszenie algorytmu. Przykładowo: jeśli wiemy na pewno, iż w po-
szukiwanym wzorcu jego pierwszy znak nie pojawia sią już w nim w ogóle7, to
w razie restartu nie musimy cofać wskaznika o pozycji, jak to było poprzednio
(patrz listing txt-1.cpp). W tym przypadku możemy po prostu zinkrementować wiedząc,
że ewentualne powtórzenie poszukiwań na pewno nic by już nie dało. Owszem, moż-
na sią łatwo zgodzić z twierdzeniem, iż tak wyspecjalizowane teksty zdarzają sią re-
latywnie rzadko, jednak powyższy przykład ukazuje, iż ewentualne manipulacje algo-
7
Przykład: ABBBBBBB znak A wystąpił tylko jeden raz.
Rozdział 8. f& Przeszukiwanie tekstów 199
rytmami poszukiwań są ciągle możliwe wystarczy sią tylko rozejrzeć. Idea algorytmu
K-M-P. polega na wstą pnym zbadaniu wzorca w celu obliczenia ilości pozycji, o które
należy cofnąć wskaznik w przypadku stwierdzenia niezgodności badanego tekstu ze
wzorcem. Oczywiście, można również rozumować w kategoriach przesuwania wzorca
do przodu rezultat bą dzie ten sam. To właśnie tą drugą konwencją bą dziemy stosować
dalej. Wiemy już, że powinniśmy przesuwać sią po badanym tekście nieco inteligentniej
niż w poprzednim algorytmie. W przypadku zauważenia niezgodności na pewnej pozy-
cji wzorca8 należy zmodyfikować ten indeks, wykorzystując informacją zawartą w już
zbadanej szarej strefie zgodności.
Brzmi to wszystko (zapewne) niesłychanie tajemniczo, pora wią c jak najszybciej wyjaśnić
tą sprawą , aby uniknąć możliwych nieporozumień. Popatrzmy w tym celu na rysunek 8.3.
Rysunek 8.3.
Wyszukiwanie optymalnego
przesunięcia w algorytmie
K-M-P
Moment niezgodności został zaznaczony poprzez narysowanie przerywanej pionowej
kreski. Otóż wyobrazmy sobie, że przesuwamy teraz wzorzec bardzo wolno w prawo,
patrząc jednocześnie na już zbadany tekst tak, aby obserwować ewentualne pokrycie
sią tej czą ści wzorca, która znajduje sią po lewej stronie przerywanej kreski, z tekstem,
który umieszczony jest powyżej wzorca. W pewnym momencie może okazać sią , że na-
stą puje pokrycie obu tych czą ści. Zatrzymujemy wówczas przesuwanie i kontynuujemy
testowanie (znak po znaku) zgodności obu czą ści znajdujących sią za kreską pionową.
Od czego zależy ewentualne pokrycie sią oglądanych fragmentów tekstu i wzorca? Otóż,
dość paradoksalnie badany tekst nie ma tu nic do powiedzenia jeśli można to tak
określić. Informacja o tym, jaki on był, jest ukryta w stwierdzeniu znaków było
zgodnych w tym sensie można zupełnie o badanym tekście zapomnieć i analizując
wyłącznie sam wzorzec, odkryć poszukiwane optymalne przesunią cie. Na tym właśnie
spostrzeżeniu opiera sią idea algorytmu K-M-P. Okazuje sią , że badając samą strukturą
wzorca, można obliczyć, jak powinniśmy zmodyfikować indeks w razie stwierdzenia
niezgodności tekstu ze wzorcem na j-tej pozycji.
Zanim zagłą bimy sią w wyjaśnienia na temat obliczania owych przesunią ć, popatrzmy
na efekt ich działania na kilku kolejnych przykładach. Na rysunku 8.4 możemy do-
strzec, iż na siódmej pozycji wzorca9 (którym jest dość abstrakcyjny ciąg ) zo-
stała stwierdzona niezgodność.
Jeśli zostawimy indeks w spokoju, to modyfikując wyłącznie możemy bez
problemu kontynuować przeszukiwanie. Jakie jest optymalne przesunią cie wzorca? Śli-
zgając go wolno w prawo (patrz rysunek 8.4) doprowadzamy w pewnym momencie
do nałożenia sią ciągów przed kreską cała strefa niezgodności została wyprowa-
dzona na prawo i ewentualne dalsze testowanie może być kontynuowane!
8
Lub i w przypadku badanego tekstu.
9
Licząc indeksy tablicy tradycyjnie od zera.
200 Algorytmy, struktury danych i techniki programowania
Rysunek 8.4.
i=const
i=const
Przesuwanie się wzorca
w algorytmie K-M-P (1)
1 2 3 4 1 2 3 5 1 2 3 4 1 2 3 5
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
j=7 j=3
Analogiczny przykład znajduje sią na rysunku 8.5.
Rysunek 8.5.
i=const
i=const
Przesuwanie się wzorca
w algorytmie K-M-P (2)
1 0 1 1 0 1 0 1 0 1 1 0 1 0
1 0 1 1 1 1 0 1 0 1 1 1 1 0
j=3 j=1
Tym razem niezgodność wystąpiła na pozycji . Dokonując podobnie jak poprzed-
nio przesuwania wzorca w prawo, zauważamy, iż jedyne możliwe nałożenie sią
znaków wystąpi po przesunią ciu o dwie pozycje w prawo czyli dla . Dodatko-
wo okazuje sią , że znaki za kreską też sią pokryły, ale o tym algorytm dowie sią dopiero
podczas kolejnego testu zgodności na pozycji .
Dla potrzeb algorytmu K-M-P konieczne okazuje sią wprowadzenie tablicy przesunią ć
. Sposób jej zastosowania bą dzie nastą pujący: jeśli na pozycji wystąpiła
niezgodność znaków, to kolejną wartością bą dzie . Nie wnikając chwilowo
w sposób inicjalizacji tej tablicy (odmiennej oczywiście dla każdego wzorca), może-
my natychmiast podać algorytm K-M-P, który w konstrukcji jest niemal dokładną kopią
algorytmu typu brute-force:
kmp.cpp
Szczególnym przypadkiem jest wystąpienie niezgodności na pozycji zerowej: z za-
łożenia niemożliwe jest tu przesuwanie wzorca w celu uzyskania nałożenia sią znaków.
Z tego powodu chcemy, aby indeks pozostał niezmieniony przy jednoczesnej progre-
sji indeksu . Jest to możliwe do uzyskania, jeśli umówimy sią , że zostanie
zainicjowany wartością . Wówczas podczas kolejnej iteracji pą tli nastąpi in-
krementacja oraz , co wyzeruje nam .
Rozdział 8. f& Przeszukiwanie tekstów 201
Pozostaje do omówienia sposób konstrukcji tablicy . Jej obliczenie powinno
nastąpić przed wywołaniem funkcji , co sugeruje, iż w przypadku wielokrotnego po-
szukiwania tego samego wzorca nie musimy już powtarzać inicjacji tej tablicy. Funk-
cja inicjująca tablicą jest przewrotna jest ona praktycznie identyczna z z tą tylko
różnicą, iż algorytm sprawdza zgodność wzorca... z nim samym!
Sens tego algorytmu jest nastą pujący: tuż po inkrementacji i wiemy, że pierwsze
znaków wzorca jest zgodne ze znakami na pozycjach: (ostatnie
pozycji w pierwszych znakach wzorca). Ponieważ jest to najwią ksze spełniające po-
wyższy warunek, zatem, aby nie ominąć potencjalnego miejsca wykrycia wzorca w tek-
ście, należy ustawić na .
Popatrzmy, jaki bą dzie efekt zadziałania funkcji na słowie ananas (patrz
rysunek 8.6). Zacieniowane litery oznaczają miejsca, w których wystąpiła niezgodność
wzorca z tekstem. W każdym przypadku graficznie przedstawiono efekt przesunią cia
wzorca widać wyraznie, które strefy pokrywają sią przed strefą zacieniowaną (po-
równaj rysunek 8.5).
Rysunek 8.6.
a) b)
Optymalne przesunięcia
wzorca ananas
a n a n a s a n a n a s
a n a n a s a n a n a s
c) d)
a n a n a s a n a n a s
a n a n a s a n a n a s
e)
a n a n a s
a n a n a s
Przypomnijmy jeszcze, że tablica zawiera nową wartość dla indeksu , który
przemieszcza sią po wzorcu.
Algorytm K-M-P można zoptymalizować, jeśli znamy z góry wzorce, których bą dziemy
poszukiwać. Przykładowo: jeśli bardzo czą sto zdarza nam sią szukać w tekstach sło-
wa ananas, to w funkcją można wbudować tablicą przesunią ć:
202 Algorytmy, struktury danych i techniki programowania
ananas.cpp
W celu właściwego odtworzenia etykiet należy oczywiście co najmniej raz wykonać
funkcją lub obliczyć samemu odpowiednie wartości. W każdym razie gra
jest warta świeczki: powyższa funkcja charakteryzuje sią bardzo zwią złym kodem
wynikowym asemblerowym, jest zatem bardzo szybka. Posiadacze kompilatorów,
które umożliwiają generacją kodu wynikowego jako tzw. assembly output 10, mogą
z łatwością sprawdzić różnice pomią dzy wersjami i ! Dla przykładu
mogą podać, że w przypadku wspomnianego kompilatora GNU klasyczna wersja pro-
cedury (wraz z ) miała obją tość około 170 linii kodu asemblerowego,
natomiast zmieściła sią w ok. 100 liniach. (Patrz: pliki z rozszerzeniem s na
dyskietce dla kompilatora GNU lub asm dla kompilatora Borland C++ 5.5).
Algorytm K-M-P działa w czasie proporcjonalnym do w najgorszym przypadku.
Najwią kszy zauważalny zysk związany z jego użyciem dotyczy przypadku tekstów
o wysokim stopniu samopowtarzalności dość rzadko wystą pujących w praktyce.
Dla typowych tekstów zysk związany z wyborem metody K-M-P bą dzie zatem słabo za-
uważalny.
Użycie tego algorytmu jest jednak niezbą dne w tych aplikacjach, w których nastą puje
liniowe przeglądanie tekstu bez buforowania. Jak łatwo zauważyć, wskaznik w funk-
cji nigdy nie jest dekrementowany, co oznacza, że plik można przeglądać od po-
czątku do końca bez cofania sią w nim. W niektórych systemach może to mieć istotne
znaczenie praktyczne przykładowo: mamy zamiar analizować bardzo długi plik
tekstowy i charakter wykonywanych operacji nie pozwala na cofnią cie sią w tej czynno-
ści (i w odczytywanym na bieżąco pliku).
10
W przypadku kompilatorów popularnej serii Borland C++ należy skompilować program rą cznie poprzez
polecenie bcc32 -S -Ixxx plik.cpp, gdzie xxx oznacza katalog z plikami typu H; identyczna opcja istnieje
w kompilatorze GNU C++, należy wystukać: c++ -S plik.cpp.
Rozdział 8. f& Przeszukiwanie tekstów 203
8.2.2.Algorytm Boyera i Moore a
Kolejny algorytm, który bą dziemy omawiali, jest ideowo znacznie prostszy do zrozu-
mienia niż algorytm K-M-P. W przeciwieństwie do metody K-M-P porównywaniu
ulega ostatni znak wzorca. To niekonwencjonalne podejście niesie ze sobą kilka istot-
nych zalet:
jeśli podczas porównywania okaże sią , że rozpatrywany aktualnie znak nie
wchodzi w ogóle w skład wzorca, wówczas możemy skoczyć w analizie
tekstu o całą długość wzorca do przodu! Cią żar algorytmu przesunął sią wią c
z analizy ewentualnych zgodności na badanie niezgodności a te ostatnie są
statystycznie znacznie czą ściej spotykane;
skoki wzorca są zazwyczaj znacznie wią ksze od porównaj z metodą K-M-P!
Zanim przejdziemy do szczegółowej prezentacji kodu, omówimy sobie na przykładzie je-
go działanie. Spójrzmy w tym celu na rysunek 8.7, gdzie przedstawione jest poszukiwa-
nie ciągu znaków lek w tekście Z pamiętnika młodej lekarki 11.
Rysunek 8.7.
Z p a m i ą t n i k a m ł o d e j l e k a r k i
Przeszukiwanie tekstu
metodą Boyera
l e k
i Moore'a
l e k
l e k
l e k
l e k
l e k
l e k
l e k
l e k
Pierwsze pią ć porównań trafia na litery: , , , i , które we wzorcu nie wystą pują!
Za każdym razem możemy zatem przeskoczyć w tekście o trzy znaki do przodu (dłu-
gość wzorca). Porównanie szóste trafia jednak na literą , która w słowie lek wy-
stą puje. Algorytm wówczas przesuwa wzorzec o tyle pozycji do przodu, aby litery
nałożyły sią na siebie, i porównywanie jest kontynuowane.
Nastą pnie okazuje sią , że litera nie wystą puje we wzorcu mamy zatem prawo prze-
sunąć sią o kolejne 3 znaki do przodu. W tym momencie trafiamy już na poszukiwane
słowo, co nastą puje po jednokrotnym przesunią ciu wzorca, tak aby pokryły sią litery .
Algorytm jest jak widać klarowny, prosty i szybki. Jego realizacja także nie jest zbyt
skomplikowana. Podobnie jak w przypadku metody poprzedniej, także i tu musimy wy-
konać pewną prekompilacją w celu stworzenia tablicy przesunią ć. Tym razem jednak
tablica ta bą dzie miała tyle pozycji, ile jest znaków w alfabecie wszystkie znaki,
które mogą wystąpić w tekście plus spacja. Bą dziemy również potrzebowali prostej
11
Tytuł znakomitego cyklu autorstwa Ewy Szumańskiej.
204 Algorytmy, struktury danych i techniki programowania
funkcji , która zwraca w przypadku spacji liczbą zero w pozostałych przypad-
kach numer litery w alfabecie. Poniższy przykład uwzglą dnia jedynie kilka polskich
liter Czytelnik uzupełni go z łatwością o brakujące znaki. Numer litery jest oczywi-
ście zupełnie arbitralny i zależy od programisty. Ważne jest tylko, aby nie pominąć w ta-
blicy żadnej litery, która może wystąpić w tekście. Jedna z możliwych wersji funkcji
jest przedstawiona poniżej:
Funkcja ma jedynie charakter usługowy. Służy ona m.in. do właściwej inicjali-
zacji tablicy przesunią ć. Mając za sobą analizą przykładu z rysunku 8.7, Czytelnik nie
powinien być zbytnio zdziwiony sposobem inicjalizacji:
Przejdzmy wreszcie do prezentacji samego listingu algorytmu, z przykładem wywołania:
Rozdział 8. f& Przeszukiwanie tekstów 205
Algorytm Boyera i Moore a, podobnie jak i K-M-P, jest klasy jednak jest on
o tyle od niego lepszy, iż w przypadku krótkich wzorców i długiego alfabetu kończy
sią po około M/N porównaniach. W celu obliczenia optymalnych przesunią ć12 autorzy al-
gorytmu proponują skombinowanie powyższego algorytmu z tym zaproponowanym
przez Knutha, Morrisa i Pratta. Celowość tego zabiegu wydaje sią jednak wątpliwa,
gdyż, optymalizując sam algorytm, można w bardzo łatwy sposób uczynić zbyt czaso-
chłonnym sam proces prekompilacji wzorca.
8.2.3. Algorytm Rabina i Karpa
Ostatni algorytm do przeszukiwania tekstów, który bą dziemy analizowali, wymaga zna-
jomości rozdziału 7. i terminologii, która została w nim przedstawiona. Algorytm Rabina
i Karpa polega bowiem na dość przewrotnej idei:
wzorzec (do odszukania) jest kluczem (patrz terminologia transformacji
kluczowej w rozdziale 7.) o długości znaków, charakteryzującym sią pewną
wartością wybranej przez nas funkcji . Możemy zatem obliczyć jednokrotnie
i korzystać z tego wyliczenia w sposób ciągły.
tekst wejściowy (do przeszukania) może być w taki sposób odczytywany,
aby na bieżąco znać ostatnich znaków13. Z tych znaków wyliczamy
na bieżąco .
Gdy założymy jednoznaczność wybranej funkcji , sprawdzenie zgodności wzorca
z aktualnie badanym fragmentem tekstu sprowadza sią do odpowiedzi na pytanie: czy
jest równe ? Spostrzegawczy Czytelnik ma jednak prawo pokrą cić w tym miejscu
z powątpiewaniem głową: przecież to nie ma prawa działać szybko! Istotnie, pomysł
wyliczenia dodatkowo funkcji dla każdego słowa wejściowego o długości wydaje
sią tak samo kosztowny jak nie bardziej! jak zwykłe sprawdzanie tekstu znak po
znaku (patrz algorytm brute-force, ż8.1). Tym bardziej że jak do tej pory nie powie-
dzieliśmy ani słowa na temat funkcji ! Z poprzedniego rozdziału pamią tamy zapewne,
iż jej wybór wcale nie był taki oczywisty.
Omawiany algorytm jednak istnieje i na dodatek działa szybko! Zatem, aby to wszyst-
ko, co poprzednio zostało napisane, logicznie sią ze sobą łączyło, potrzebny nam bą dzie
zapewne jakiś trik. Sztuka polega na właściwym wyborze funkcji . Robin i Karp wybrali
12
Rozważ np. wielokrotne wystą powanie takich samych liter we wzorcu.
13
Na samym początku bą dzie to oczywiście pierwszych znaków tekstu.
206 Algorytmy, struktury danych i techniki programowania
taką funkcją , która dzią ki swym szczególnym właściwościom umożliwia dynamiczne
wykorzystywanie wyników obliczeń dokonanych krok wcześniej, co znacząco potrafi
uprościć obliczenia wykonywane w kroku bieżącym.
Załóżmy, że ciąg M znaków bą dziemy interpretować jako pewną liczbą całkowitą.
Przyjmując za b jako podstawą systemu ilość wszystkich możliwych znaków,
otrzymamy:
x = t[i]bM-1 + t[i +1]bM-2+& t[i + M -1].
Przesuńmy sią teraz w tekście o jedną pozycją do przodu i zobaczmy, jak zmieni sią
wartość x:
x'= t[i +1]bM-1 + t[i + 2]bM-2+... t[i + M].
Jeśli dobrze przyjrzymy sią x i x', to okaże sią , że wartość x' jest w dużej czą ści zbudo-
wana z elementów tworzących x pomnożonych przez b z uwagi na przesunią cie.
Nietrudno jest wówczas wywnioskować, że:
x'= x - t[i]bM-1 + t[i + M].
()
Jako funkcji użyjemy dobrze nam znanej z poprzedniego rozdziału , gdzie
jest dużą liczbą pierwszą. Załóżmy, że dla danej pozycji wartość jest nam
znana. Po przesunią ciu sią w tekście o jedną pozycją w prawo pojawia sią konieczność
wyliczenia wartości funkcji dla tego nowego słowa. Czy istotnie zachodzi po-
trzeba powtarzania całego wyliczenia? Być może istnieje pewne ułatwienie bazujące na
zależności, jaka istnieje pomią dzy i ?
Na pomoc przychodzi nam tu własność funkcji użytej w wyrażeniu arytmetycz-
nym. Można oczywiście obliczyć z wyniku końcowego, lecz to bywa czasami
niewygodne z uwagi na przykład wielkość liczby, z którą mamy do czynienia a po-
za tym, gdzie tu byłby zysk szybkości?! Jednak identyczny wynik otrzymuje sią , apliku-
jąc funkcją po każdej operacji cząstkowej i przenosząc otrzymaną wartość do
nastą pnego wyrażenia cząstkowego! Dla przykładu wezmy obliczenie:
(5*100 + 6*10 + 8)%7 = 568%7 = 1.
Wynik ten jest oczywiście prawdziwy, co można łatwo sprawdzić z kalkulatorem. Iden-
tyczny rezultat da nam jednak nastą pująca sekwencja obliczeń:
5*100%7 = 3 (3+ 6*10)%7 = 0 (0 + 8)%7 = 1
co jest też łatwe do weryfikacji.
Implementacja algorytmu jest prosta, lecz zawiera kilka instrukcji wartych omówienia.
Popatrzmy na listing:
Rozdział 8. f& Przeszukiwanie tekstów 207
rk.cpp
Na pierwszym etapie nastą puje wyliczenie początkowych wartości i . Ponieważ
ciągi znaków trzeba interpretować jako liczby, konieczne bą dzie zastosowanie znanej
już nam doskonale funkcji (patrz strona 204.). Wartość jest niezmienna i nie
wymaga uaktualniania. Nie dotyczy to jednak aktualnie badanego fragmentu tekstu
tutaj wartość ulega zmianie podczas każdej inkrementacji zmiennej . Do obliczenia
możemy wykorzystać omówioną wcześniej własność funkcji co jest do-
konywane w trzeciej pą tli . Dodatkowego wyjaśnienia wymaga być może linia ozna-
czona (*). Otóż dodawanie wartości do pozwala nam uniknąć przypadkowego
wskoczenia w liczby ujemne. Gdyby istotnie tak sią stało, przeniesiona do nastą pnego
wyrażenia arytmetycznego wartość byłaby nieprawidłowa i sfałszowałaby koń-
cowy wynik!
Kolejne uwagi należą sią parametrom i . Zaleca sią , aby było dużą liczbą pierw-
szą14, jednakże nie można tu przesadzać z uwagi na możliwe przekroczenie zakresu
pojemności użytych zmiennych. W przypadku wyboru dużego zmniejszamy praw-
dopodobieństwo wystąpienia kolizji spowodowanej niejednoznacznością funkcji . Ta
możliwość mimo iż mało prawdopodobna ciągle istnieje i ostrożny programista
powinien wykonać dodatkowy test zgodności i po zwróceniu
przez funkcją pewnego indeksu .
Co zaś sią tyczy wyboru podstawy systemu (oznaczonej w programie jako b), to warto
jest wybrać liczbą nawet nieco za dużą, zawsze jednak bą dącą potą gą liczby 2. Moż-
liwe jest wówczas zaimplementowanie operacji mnożenia przez b jako przesunią cia
bitowego wykonywanego przez komputer znacznie szybciej niż zwykłe mnożenie.
Przykładowo: dla b=64 możemy zapisać mnożenie jako .
Gwoli formalności jeszcze można dodać, że gdy nie wystą puje kolizja (typowy przy-
padek!), algorytm Robina i Karpa wykonuje sią w czasie proporcjonalnym do .
14
W naszym przypadku jest to liczba 33554393.
Wyszukiwarka
Podobne podstrony:
algo3 hufalgo3 READMEalgo3 LZWwięcej podobnych podstron