informatyka algorytmy struktury danych i techniki programowania wydanie iv piotr wroblewski ebook

Algorytmy, struktury danych
i techniki programowania.
Wydanie IV

Autor:

Piotr Wróblewski

ISBN: 978-83-246-2306-8
Format: 158

u235, stron: 452

Podstawowy podrêcznik do nauki algorytmiki

• Przystêpne wprowadzenie do algorytmiki
• Bez zbêdnej teorii
• Gotowe rozwi¹zania w C++

Oto kolejne wydanie sprawdzonej i cenionej przez programistów, wyk³adowców
oraz studentów ksi¹¿ki, bêd¹cej podstawowym podrêcznikiem do nauki algorytmiki.
W pierwszej kolejnoœci autor zapozna Ciê z elementarnymi zagadnieniami z tej
dziedziny oraz wyjaœni, sk¹d bierze siê tak szybki postêp w tej dyscyplinie nauki.
Podczas dalszej lektury poznasz takie pojêcia, jak rekurencja, analiza z³o¿onoœci oraz
algorytmy sortowania i przeszukiwania czy algorytmy numeryczne. Szybko opanujesz
metody optymalizacji algorytmów, sposoby kodowania i kompresji danych oraz elementy
algorytmiki grafów. Przedstawione w ksi¹¿ce algorytmy zilustrowane zosta³y przyk³adowymi
kodami Ÿród³owymi w C++ , u³atwiaj¹cymi zrozumienie poznawanych zagadnieñ.
Przejrzysta forma, praktyczne przyk³ady oraz przystêpny jêzyk sprawiaj¹, ¿e ksi¹¿ka
ta pozwala szybko, a tak¿e bezboleœnie opanowaæ zarówno algorytmy, jak i struktury
danych oraz najlepsze techniki programowania.

• Historia algorytmiki
• Wykorzystanie rekurencji
• Analiza z³o¿onoœci algorytmów
• Algorytmy sortowania
• Algorytmy przeszukiwania
• Przeszukiwanie tekstów
• Struktury danych i ich implementacja
• Optymalizacja algorytmów
• Zaawansowane techniki programowania
• Wykorzystanie grafów
• Wprowadzenie do sztucznej inteligencji
• Kodowanie i kompresja danych
• Algorytmy numeryczne
• Poradnik kompilacji i uruchamiania programów (GCC, DevC++, Microsoft Visual

C++ Express Edition).

Szybko i bezboleœnie opanuj wszystkie zagadnienia algorytmiki!

Spis tre

Ĉci

Przedmowa ...................................................................................... 9

Rozdzia

ä 1. Zanim wystartujemy ....................................................................... 17

Jak to wcze

Ğniej bywaáo, czyli wyjątki z historii maszyn algorytmicznych ................... 18

Jak to si

Ċ niedawno odbyáo,

czyli o tym, kto „wymy

Ğliá” metodologiĊ programowania ........................................... 21

Proces koncepcji programów .......................................................................................... 22
Poziomy abstrakcji opisu i wybór j

Ċzyka ....................................................................... 23

Poprawno

Ğü algorytmów ................................................................................................ 24

Rozdzia

ä 2. Rekurencja .................................................................................... 27

Definicja rekurencji ........................................................................................................ 27
Ilustracja poj

Ċcia rekurencji ............................................................................................ 28

Jak wykonuj

ą siĊ programy rekurencyjne? ..................................................................... 30

Niebezpiecze

Ĕstwa rekurencji ........................................................................................ 31

ąg Fibonacciego .................................................................................................... 31

Stack overflow! ........................................................................................................ 33

áapek ciąg dalszy ........................................................................................................ 34

ąd do wiecznoĞci ................................................................................................... 34

Definicja poprawna, ale... ......................................................................................... 35

Typy programów rekurencyjnych ................................................................................... 36
My

Ğlenie rekurencyjne ................................................................................................... 38

Przyk

áad 1.: Spirala .................................................................................................. 38

Przyk

áad 2.: Kwadraty „parzyste” ............................................................................ 40

Uwagi praktyczne na temat technik rekurencyjnych ...................................................... 41
Zadania ........................................................................................................................... 42
Rozwi

ązania i wskazówki do zadaĔ ............................................................................... 44

Rozdzia

ä 3. Analiza zäoĔonoĈci algorytmów ........................................................ 49

Definicje i przyk

áady ...................................................................................................... 50

Jeszcze raz funkcja silnia ......................................................................................... 53
Zerowanie fragmentu tablicy .................................................................................... 57
Wpadamy w pu

áapkĊ ................................................................................................ 58

Ró

Īne typy záoĪonoĞci obliczeniowej ...................................................................... 59

Nowe zadanie: upro

Ğciü obliczenia! ............................................................................... 61

Algorytmy, struktury danych i techniki programowania

Analiza programów rekurencyjnych ............................................................................... 62

Terminologia i definicje ........................................................................................... 62
Ilustracja metody na przyk

áadzie .............................................................................. 63

Rozk

áad logarytmiczny ............................................................................................. 64

Zamiana dziedziny równania rekurencyjnego .......................................................... 66
Funkcja Ackermanna, czyli co

Ğ dla smakoszy ......................................................... 66

áoĪonoĞü obliczeniowa to nie religia! ........................................................................... 68

Techniki optymalizacji programów ................................................................................ 68
Zadania ........................................................................................................................... 69
Rozwi

ązania i wskazówki do zadaĔ ............................................................................... 70

Rozdzia

ä 4. Algorytmy sortowania ..................................................................... 73

Sortowanie przez wstawianie, algorytm klasy O(N

) ..................................................... 74

Sortowanie b

ąbelkowe, algorytm klasy O(N

) ............................................................... 75

Quicksort, algorytm klasy O(N log N) ........................................................................... 77
Heap Sort — sortowanie przez kopcowanie ................................................................... 80
Scalanie zbiorów posortowanych ................................................................................... 82
Sortowanie przez scalanie ............................................................................................... 83
Sortowanie zewn

Ċtrzne ................................................................................................... 84

Uwagi praktyczne ........................................................................................................... 87

Rozdzia

ä 5. Typy i struktury danych .................................................................. 89

Typy podstawowe i z

áoĪone ........................................................................................... 89

ągi znaków i napisy w C++ ......................................................................................... 90

Abstrakcyjne struktury danych ....................................................................................... 92

Listy jednokierunkowe ............................................................................................. 93
Tablicowa implementacja list ................................................................................. 115
Stos ......................................................................................................................... 119
Kolejki FIFO .......................................................................................................... 123
Sterty i kolejki priorytetowe ................................................................................... 125
Drzewa i ich reprezentacje ..................................................................................... 131
Zbiory ..................................................................................................................... 143
Zadania ................................................................................................................... 145
Rozwi

ązania zadaĔ ................................................................................................. 146

Rozdzia

ä 6. Derekursywacja i optymalizacja algorytmów .................................. 147

Jak pracuje kompilator? ................................................................................................ 148
Odrobina formalizmu nie zaszkodzi! ............................................................................ 150
Kilka przyk

áadów derekursywacji algorytmów ............................................................ 151

Derekursywacja z wykorzystaniem stosu ..................................................................... 154

Eliminacja zmiennych lokalnych ............................................................................ 154

Metoda funkcji przeciwnych ........................................................................................ 156
Klasyczne schematy derekursywacji ............................................................................ 158

Schemat typu while ................................................................................................ 159
Schemat typu if-else ............................................................................................... 160
Schemat z podwójnym wywo

áaniem rekurencyjnym ............................................. 162

Podsumowanie .............................................................................................................. 163

Rozdzia

ä 7. Algorytmy przeszukiwania ............................................................. 165

Przeszukiwanie liniowe ................................................................................................ 165
Przeszukiwanie binarne ................................................................................................ 166
Transformacja kluczowa (hashing) ............................................................................... 167

W poszukiwaniu funkcji H ..................................................................................... 169
Najbardziej znane funkcje H .................................................................................. 169
Obs

áuga konfliktów dostĊpu ................................................................................... 171

Spis tre

Ĉci

Powrót do

Ĩródeá .................................................................................................... 172

Jeszcze raz tablice! ................................................................................................. 173
Próbkowanie liniowe .............................................................................................. 173
Podwójne kluczowanie ........................................................................................... 175
Zastosowania transformacji kluczowej ................................................................... 176
Podsumowanie metod transformacji kluczowej ..................................................... 176

Rozdzia

ä 8. Przeszukiwanie tekstów ............................................................... 179

Algorytm typu brute-force ............................................................................................ 179
Nowe algorytmy poszukiwa

Ĕ ....................................................................................... 181

Algorytm K-M-P .................................................................................................... 182
Algorytm Boyera i Moore’a ................................................................................... 185
Algorytm Rabina i Karpa ....................................................................................... 187

Rozdzia

ä 9. Zaawansowane techniki programowania ....................................... 191

Programowanie typu „dziel i zwyci

ĊĪaj” ...................................................................... 192

Odszukiwanie minimum i maksimum w tablicy liczb ............................................ 193
Mno

Īenie macierzy o rozmiarze N×N .................................................................... 195

Mno

Īenie liczb caákowitych ................................................................................... 197

Inne znane algorytmy „dziel i zwyci

ĊĪaj” .............................................................. 198

Algorytmy „

Īaráoczne”, czyli przekąsiü coĞ nadszedá juĪ czas... .................................. 199

Problem plecakowy, czyli nie

áatwe jest Īycie turysty piechura .............................. 200

Programowanie dynamiczne ......................................................................................... 202

ąg Fibonacciego .................................................................................................. 203

Równania z wieloma zmiennymi ........................................................................... 204
Najd

áuĪsza wspólna podsekwencja ........................................................................ 205

Inne techniki programowania ....................................................................................... 208
Uwagi bibliograficzne .................................................................................................. 210

Rozdzia

ä 10. Elementy algorytmiki grafów ......................................................... 211

Definicje i poj

Ċcia podstawowe .................................................................................... 212

Cykle w grafach ............................................................................................................ 214
Sposoby reprezentacji grafów ....................................................................................... 217

Reprezentacja tablicowa ......................................................................................... 217
S

áowniki wĊzáów .................................................................................................... 218

Listy kontra zbiory ................................................................................................. 219

Podstawowe operacje na grafach .................................................................................. 220

Suma grafów .......................................................................................................... 220
Kompozycja grafów ............................................................................................... 220
Pot

Ċga grafu ........................................................................................................... 220

Algorytm Roy-Warshalla ............................................................................................. 221
Algorytm Floyda-Warshalla ......................................................................................... 224
Algorytm Dijkstry ........................................................................................................ 227
Algorytm Bellmana-Forda ............................................................................................ 228
Drzewo rozpinaj

ące minimalne .................................................................................... 228

Algorytm Kruskala ................................................................................................. 229
Algorytm Prima ...................................................................................................... 230

Przeszukiwanie grafów ................................................................................................. 230

Strategia „w g

áąb” (przeszukiwanie zstĊpujące) ..................................................... 231

Strategia „wszerz” .................................................................................................. 232
Inne strategie przeszukiwania ................................................................................. 234

Problem w

áaĞciwego doboru ......................................................................................... 235

Podsumowanie .............................................................................................................. 239
Zadania ......................................................................................................................... 239

Algorytmy, struktury danych i techniki programowania

Rozdzia

ä 11. Algorytmy numeryczne ................................................................. 241

Poszukiwanie miejsc zerowych funkcji ........................................................................ 241
Iteracyjne obliczanie warto

Ğci funkcji .......................................................................... 243

Interpolacja funkcji metod

ą Lagrange’a ....................................................................... 244

Ró

Īniczkowanie funkcji ............................................................................................... 245

ákowanie funkcji metodą Simpsona .......................................................................... 247

Rozwi

ązywanie ukáadów równaĔ liniowych metodą Gaussa ....................................... 248

Uwagi ko

Ĕcowe ............................................................................................................ 251

Rozdzia

ä 12. Czy komputery mogñ myĈleè? ....................................................... 253

Przegl

ąd obszarów zainteresowaĔ Sztucznej Inteligencji ............................................. 254

Systemy eksperckie ................................................................................................ 255
Sieci neuronowe ..................................................................................................... 256

Reprezentacja problemów ............................................................................................ 257

ûwiczenie 1. ........................................................................................................... 258

Gry dwuosobowe i drzewa gier .................................................................................... 259
Algorytm mini-max ...................................................................................................... 260

Rozdzia

ä 13. Kodowanie i kompresja danych .................................................... 265

Kodowanie danych i arytmetyka du

Īych liczb ............................................................. 267

Kodowanie symetryczne ........................................................................................ 267
Kodowanie asymetryczne ....................................................................................... 268
Metody prymitywne ............................................................................................... 274

àamanie szyfrów .................................................................................................... 275

Techniki kompresji danych ........................................................................................... 275

Kompresja poprzez modelowanie matematyczne ................................................... 277
Kompresja metod

ą RLE ......................................................................................... 278

Kompresja danych metod

ą Huffmana .................................................................... 279

Kodowanie LZW .................................................................................................... 283
Idea kodowania s

áownikowego na przykáadach ..................................................... 284

Opis formatu GIF ................................................................................................... 286

Rozdzia

ä 14. Zadania róĔne .............................................................................. 289

Teksty zada

Ĕ ................................................................................................................. 289

Rozwi

ązania ................................................................................................................. 291

Dodatek A Poznaj C++ w pi

öè minut! ............................................................. 295

Elementy j

Ċzyka C++ na przykáadach .......................................................................... 295

Pierwszy program ................................................................................................... 295
Dyrektywa #include ............................................................................................... 296

Podprogramy ................................................................................................................ 296

Procedury ............................................................................................................... 296
Funkcje ................................................................................................................... 297

Operacje arytmetyczne ................................................................................................. 298

Operacje logiczne ................................................................................................... 298
Wska

Ĩniki i zmienne dynamiczne .......................................................................... 299

Referencje ..................................................................................................................... 300
Typy z

áoĪone ................................................................................................................ 300

Tablice .................................................................................................................... 300
Rekordy .................................................................................................................. 301
Instrukcja switch .................................................................................................... 301

Iteracje .......................................................................................................................... 302
Struktury rekurencyjne ................................................................................................. 303
Parametry programu main() .......................................................................................... 303
Operacje na plikach w C++ .......................................................................................... 303

Spis tre

Ĉci

Programowanie obiektowe w C++ ............................................................................... 304

Terminologia .......................................................................................................... 304
Obiekty na przyk

áadzie ........................................................................................... 305

áadowe statyczne klas ......................................................................................... 308

Metody sta

áe klas .................................................................................................... 308

Dziedziczenie w

áasnoĞci ......................................................................................... 308

Kod warunkowy w C++ ............................................................................................... 311

Dodatek B Systemy obliczeniowe w pigu

äce ................................................... 313

Kilka definicji ............................................................................................................... 313
System dwójkowy ........................................................................................................ 313

Operacje arytmetyczne na liczbach dwójkowych ................................................... 315
Operacje logiczne na liczbach dwójkowych ........................................................... 315

System ósemkowy ........................................................................................................ 317
System szesnastkowy ................................................................................................... 317
Zmienne w pami

Ċci komputera .................................................................................... 317

Kodowanie znaków ...................................................................................................... 318

Dodatek C Kompilowanie programów przyk

äadowych ...................................... 321

Zawarto

Ğü archiwum ZIP na ftp .................................................................................... 321

Darmowe kompilatory C++ .......................................................................................... 321
Kompilacja i uruchamianie ........................................................................................... 322

GCC ....................................................................................................................... 322
Visual C++ Express Edition ................................................................................... 323
Dev C++ ................................................................................................................. 327

Literatura ..................................................................................... 329

Spis tabel ................................................................................... 331

Spis ilustracji .............................................................................. 333

Skorowidz ................................................................................... 339

Rozdzia

ä 8.

Przeszukiwanie tekstów

Zanim na dobre zanurzymy si

Ċ w lekturĊ nowego rozdziaáu, naleĪy wyjaĞniü pewne nieporozumie-

nie, które mo

Īe towarzyszyü jego tytuáowi. OtóĪ za tekst bĊdziemy uwaĪali ciąg znaków w sen-

sie informatycznym. Nie zawsze b

Ċdzie to miaáo cokolwiek wspólnego z ludzką „pisaniną”! Tek-

stem b

Ċdzie na przykáad równieĪ ciąg bitów

, który tylko przez umowno

Ğü moĪe byü podzielony

na równej wielko

Ğci porcje, którym przyporządkowano pewien kod liczbowy

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

Algorytm typu brute-force

Zadaniem, które b

Ċdziemy usiáowali wspólnie rozwiązaü, jest poszukiwanie wzorca

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 symbolicznie przedstawionych na rysunku 8.1.

Rysunek 8.1.
Algorytm typu
brute-force
przeszukiwania tekstu

Zarezerwujmy indeksy

do poruszania si

Ċ odpowiednio we wzorcu i tekĞcie podczas opera-

cji porównywania znak po znaku zgodno

Ğci wzorca z tekstem. ZaáóĪmy, Īe w trakcie poszuki-

Ĕ 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 (

i++; j++)

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

j-1

Reprezentuj

ący np. pamiĊü ekranu.

Np. ASCII lub dowolny inny.

Ang. pattern matching.

180

Algorytmy, struktury danych i techniki programowania

znaków, wyzerowuj

ąc przy okazji

. Omówmy jeszcze moment 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

i-M

áumacząc powyĪsze sytuacje na C++, moĪemy áatwo dojĞü do nastĊpującej procedury:

txt-1.cpp

int

szukaj(char *w, char *t)

{
int

i=0,j=0, M=strlen(w), N=strlen(t);

while

( (j<M) && (i<N) )

{
if(t[i]!=w[j])
{
i-=j-1;
j=-1;
}
i++;
j++;
}
if

(j==M)

return i-M;
else
return -1;
}

Sposób korzystania z funkcji

szukaj

jest przedstawiony na przyk

áadzie nastĊpującej funkcji

main

int

main()

{
char

*b="abrakadabra",*a="rak";

cout << szukaj(a,b) << endl;
}

Jako wynik funkcji zwracana jest pozycja w tek

Ğcie, od której zaczyna siĊ wzorzec, lub

-1

w przypadku, gdy poszukiwany tekst nie zosta

á odnaleziony — jest to znana nam juĪ dosko-

nale konwencja. Przypatrzmy si

Ċ dokáadniej przykáadowi poszukiwania wzorca

10100

w pewnym

tek

Ğcie binarnym (patrz rysunek 8.2).

Rysunek 8.2.
„Fa

ászywe starty”

podczas poszukiwania

Rozdzia

ä 8.

i Przeszukiwanie tekstów

181

Rysunek jest nieco uproszczony: w istocie poziome przesuwanie si

Ċ wzorca oznacza instrukcje

zaznaczone na listingu jako (*), natomiast ca

áa szara strefa o dáugoĞci k oznacza k-krotne wyko-

nanie (**).

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. Chodzi oczywiĞcie zarówno

o tekst, jak i wzorzec z

áoĪone z samych zer i zakoĔczone jedynką

Spróbujmy obliczy

ü klasĊ tego algorytmu dla opisanego przed chwilą ekstremalnego najgor-

szego przypadku. Obliczenie nie nale

Īy do skomplikowanych czynnoĞci: zakáadając, Īe restart al-

gorytmu b

Ċdzie konieczny

(N-1)-(M-2)=N-M+1

razy, i wiedz

ąc, Īe podczas kaĪdego cyklu jest ko-

nieczne wykonanie

porówna

Ĕ, otrzymujemy natychmiast

M(N-M+1)

, czyli oko

áo

Zaprezentowany w tym paragrafie algorytm wykorzystuje komputer jako bezmy

Ğlne, ale

sprawne liczyd

áo

. Jego z

áoĪonoĞü obliczeniowa eliminuje go w praktyce z przeszukiwania tek-

stów binarnych, w których mo

Īe wystąpiü wiele niekorzystnych konfiguracji danych. Jedyną zaletą

algorytmu jest jego prostota, co i tak nie czyni go na tyle atrakcyjnym, by da

ü siĊ zamĊczyü jego

powolnym dzia

áaniem.

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á teoretyczny rezultat doty-

ący pewnej abstrakcyjnej maszyny. Wynikaáo z niego, Īe istniaá algorytm poszukiwania

wzorca w tek

Ğcie, który dziaáaá w czasie proporcjonalnym do

M+N

w najgorszym przypadku.

Rezultat pracy Cooka wcale nie by

á przewidziany do praktycznych celów, niemniej D. E.

Knuth i V. R. Pratt otrzymali na jego podstawie algorytm, który mo

Īna juĪ byáo zaimplementowaü

w komputerze — 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 odkry

á dokáadnie ten sam algorytm jako rozwiązanie problemu, który na-

potka

á 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 jakichĞ nie-

wiadomych powodów nagle kilku pracuj

ących osobno ludzi dochodzi do tego samego dobrego re-

zultatu. Prawda,

Īe jest w tym coĞ niesamowitego i aĪ siĊ prosi o jakieĞ metafizyczne hipotezy?

Knuth, Morris i Pratt opublikowali swój algorytm dopiero w 1976 roku. W mi

Ċdzyczasie pojawiá

Ċ kolejny „cudowny” algorytm, tym razem autorstwa R. S. Boyera i J. S. Moore’a, który okazaá

Ċ w pewnych zastosowaniach znacznie szybszy od algorytmu K-M-P. Zostaá on równieĪ rów-

nolegle wynaleziony (odkryty?) przez R. W. Gospera. Oba te algorytmy s

ą jednak doĞü trud-

ne 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 wynale

Ĩli algorytm, który — dziaáając

ągle w czasie proporcjonalnym do

M+N

— 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ól-

ü na przypadek poszukiwania w tablicach 2-wymiarowych, co czyni go potencjalnie uĪytecznym

w obróbce obrazów.

W nast

Ċpnych trzech sekcjach szczegóáowo omówimy sobie wspomniane w tym przeglądzie hi-

storycznym algorytmy.

Zera i jedynki symbolizuj

ą tu dwa róĪne od siebie znaki.

Zwykle

Ċdzie znacznie mniejsze niĪ

Termin brute-force jeden z moich znajomych

Ğlicznie przetáumaczyá jako „metodĊ mastodonta”.

182

Algorytmy, struktury danych i techniki programowania

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, zapominając po drodze

wszystko, co przetestowali

Ğmy do tej pory. Narzuca siĊ tu niejako chĊü skorzystania z informa-

cji, które ju

Ī w pewien sposób posiadamy — przecieĪ w nastĊpnym etapie bĊdą wykonywane

ĊĞciowo te same porównania, co poprzednio!

W pewnych szczególnych przypadkach przy znajomo

Ğci struktury analizowanego tekstu moĪliwe

jest ulepszenie algorytmu. Przyk

áadowo: jeĞli wiemy na pewno, iĪ w poszukiwanym wzorcu je-

go pierwszy znak nie pojawia si

Ċ juĪ w nim w ogóle

, to w razie restartu nie musimy cofa

wska

Ĩnika

j-1

pozycji, jak to by

áo poprzednio (patrz listing txt-1.cpp). W tym przypadku

Ī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 wyspecja-

lizowane teksty zdarzaj

ą siĊ relatywnie rzadko, jednak powyĪszy przykáad ukazuje, iĪ ewentu-

alne manipulacje algorytmami poszukiwa

Ĕ są ciągle moĪliwe — wystarczy siĊ tylko rozejrzeü.

Idea algorytmu K-M-P polega na wst

Ċpnym zbadaniu wzorca w celu obliczenia liczby pozycji,

o które nale

Īy cofnąü wskaĨnik

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 algo-
rytmie. W przypadku zauwa

Īenia niezgodnoĞci na pewnej pozycji

wzorca

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ó

Ī wyobraĨmy sobie, Īe przesuwamy teraz wzorzec bardzo wolno w prawo, patrząc jedno-

cze

Ğ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 nastĊpuje pokrycie obu tych czĊĞci. Zatrzymu-

jemy 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Ğü para-

doksalnie 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 „

j-1

znaków by

áo zgodnych” — w tym sensie

Īna zupeánie o badanym tekĞcie zapomnieü i analizując wyáącznie sam wzorzec, odkryü po-

szukiwane 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 dostrzec, iĪ na siódmej po-

zycji wzorca

(którym jest do

Ğü abstrakcyjny ciąg

12341234

) zosta

áa stwierdzona niezgodnoĞü.

Przyk

áad: „ABBBBBBB” — znak ‘A’ wystąpiá tylko jeden raz.

Lub i w przypadku badanego tekstu.

Licz

ąc indeksy tablicy tradycyjnie od zera.

Rozdzia

ä 8.

i Przeszukiwanie tekstów

183

Rysunek 8.4.
Przesuwanie si

Ċ wzorca

w algorytmie K-M-P (1)

Ğli zostawimy indeks

w spokoju, to — modyfikuj

ąc wyáącznie

— mo

Īemy bez proble-

mu kontynuowa

ü przeszukiwanie. Jakie jest optymalne przesuniĊcie wzorca? ĝlizgając go

wolno w prawo (patrz rysunek 8.4), doprowadzamy w pewnym momencie do na

áoĪenia siĊ cią-

gów

123

przed kresk

ą — caáa strefa niezgodnoĞci zostaáa wyprowadzona na prawo i ewentualne

dalsze testowanie mo

Īe byü kontynuowane!

Analogiczny przyk

áad znajduje siĊ na rysunku 8.5.

Rysunek 8.5.
Przesuwanie si

Ċ wzorca

w algorytmie K-M-P (2)

Tym razem niezgodno

Ğü wystąpiáa na pozycji

j=3

. Dokonuj

ąc — podobnie jak poprzednio —

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

j=1

. Dodatkowo 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Ċü

int shift[M]

. Sposób jej zastosowania b

Ċdzie nastĊpujący: jeĞli na pozycji

wyst

ąpiáa nie-

zgodno

Ğü znaków, to kolejną wartoĞcią

Ċdzie

shift[j]

. Nie wnikaj

ąc chwilowo w sposób ini-

cjalizacji tej tablicy (odmiennej oczywi

Ğcie dla kaĪdego wzorca), moĪemy natychmiast podaü

algorytm K-M-P, który w konstrukcji jest niemal dok

áadną kopią algorytmu typu brute-force:

kmp.cpp

int

kmp(char *w, char *t)

{
int

i,j, N=strlen(t);

for

(i=0,j=0; (i<N) && (j<M); i++,j++)

while( (j>=0) && (t[i]!=w[j]) )
j=shift[j];
if

(j==M)

return i-M;
else
return -1;
}

Szczególnym przypadkiem jest wyst

ąpienie niezgodnoĞci na pozycji zerowej: z zaáoĪenia nie-

Īliwe jest tu przesuwanie wzorca w celu uzyskania naáoĪenia siĊ znaków. Z tego powodu

chcemy, aby indeks

pozosta

á niezmieniony przy jednoczesnej progresji indeksu

. Jest to

Īliwe do uzyskania, jeĞli umówimy siĊ, Īe

shift[0]

zostanie zainicjowany warto

Ğcią

-1

Wówczas podczas kolejnej iteracji p

Ċtli

for

nast

ąpi inkrementacja

oraz

, co wyzeruje nam

Pozostaje do omówienia sposób konstrukcji tablicy

shift[M]

. Jej obliczenie powinno nast

ąpiü

przed wywo

áaniem funkcji

kmp

, co sugeruje, i

Ī w przypadku wielokrotnego poszukiwania tego

samego wzorca nie musimy ju

Ī powtarzaü inicjacji tej tablicy. Funkcja inicjująca tablicĊ jest

przewrotna — jest ona praktycznie identyczna z

kmp

z t

ą tylko róĪnicą, iĪ algorytm sprawdza

zgodno

Ğü wzorca... z nim samym!

184

Algorytmy, struktury danych i techniki programowania

int

shift[M];

void

init_shifts(char *w)

{
int

i,j;

shift[0]=-1;
for

(i=0,j=-1;i<M-1;i++,j++,shift[i]=j)

while((j>=0)&&(w[i]!=w[j]))
j=shift[j];
}

Sens tego algorytmu jest nast

Ċpujący: tuĪ po inkrementacji

wiemy,

Īe pierwsze

znaków wzor-

ca jest zgodne ze znakami na pozycjach:

p[i-j-1]... p[i-1]

(ostatnie

pozycji w pierwszych

znakach wzorca). Poniewa

Ī jest to najwiĊksze

spe

ániające powyĪszy warunek, zatem aby nie

omin

ąü potencjalnego miejsca wykrycia wzorca w tekĞcie, naleĪy ustawiü

shift[i]

Popatrzmy, jaki b

Ċdzie efekt zadziaáania funkcji

init_shifts

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ü wyraĨnie,

które strefy pokrywaj

ą siĊ przed strefą zacieniowaną (porównaj rysunek 8.5).

Rysunek 8.6.
Optymalne przesuni

Ċcia

wzorca „ananas”
w algorytmie K-M-P

Przypomnijmy jeszcze,

Īe tablica

shift

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 poszuki-

ü. Przykáadowo: jeĞli bardzo czĊsto zdarza nam siĊ szukaü w tekstach sáowa ananas, to

w funkcj

kmp

Īna wbudowaü tablicĊ przesuniĊü:

ananas.cpp

int

kmp_ananas(char *t)

{
int

i=-1;

start: i++;
et0: if (t[i]!='a')
goto start;
i++;
et1: if (t[i]!='n')
goto et0;
i++;
et2: if (t[i]!='a')
goto et0;
i++;
et3: if (t[i]!='n')
goto et1; i++;
if (t[i]!='a')
goto et2; i++;
if (t[i]!='s')
goto et3; i++;
return

i-6;

}

Rozdzia

ä 8.

i Przeszukiwanie tekstów

185

W celu w

áaĞciwego odtworzenia etykiet naleĪy oczywiĞcie co najmniej raz wykonaü funkcjĊ

init_shifts

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 asemblero-
wym, jest zatem bardzo szybka. Posiadacze kompilatorów, które umo

Īliwiają generacjĊ kodu

wynikowego jako tzw. „assembly output”

, mog

ą z áatwoĞcią sprawdziü róĪnice pomiĊdzy

wersjami

kmp

kmp_ananas

! Dla przyk

áadu mogĊ podaü, Īe w przypadku wspomnianego kom-

pilatora GNU klasyczna wersja procedury

kmp

(wraz z

init_shifts

) mia

áa objĊtoĞü okoáo 170 linii

kodu asemblerowego, natomiast

kmp_ananas

zmie

Ğciáa siĊ w ok. 100 liniach. (Patrz: pliki z rozsze-

rzeniem s na dyskietce dla kompilatora GNU lub asm dla kompilatora Borland C++ 5.5).

Algorytm K-M-P dzia

áa w czasie proporcjonalnym do

M+N

w najgorszym przypadku. Naj-

Ċ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 zauwaĪalny.

Ī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ü, wskaĨnik

w funkcji

kmp

nigdy nie

jest dekrementowany, co oznacza,

Īe plik moĪna przeglądaü od początku do koĔca bez cofania

Ċ 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 po-

zwala na cofni

Ċcie siĊ w tej czynnoĞci (i w odczytywanym na bieĪąco pliku).

Algorytm Boyera i Moore’a

Kolejny algorytm, który b

Ċdziemy omawiali, jest ideowo znacznie prostszy do zrozumienia niĪ algo-

rytm 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 istotnych 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 jego dzia-

áanie. Spójrzmy w tym celu na rysunek 8.7, gdzie przedstawione jest poszukiwanie ciągu zna-
ków „lek” w tek

Ğcie „Z pamiĊtnika máodej lekarki”

Pierwsze pi

Ċü porównaĔ trafia na litery:

, które we wzorcu nie wyst

Ċpują! Za kaĪ-

dym razem mo

Īemy zatem przeskoczyü w tekĞcie o trzy znaki do przodu (dáugoĞü wzorca). Porów-

nanie szóste trafia jednak na liter

, która w s

áowie „lek” wystĊpuje. Algorytm wówczas prze-

suwa wzorzec o tyle pozycji do przodu, aby litery

á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 przesunąü

Ċ o kolejne 3 znaki do przodu. W tym momencie trafiamy juĪ na poszukiwane sáowo, co na-

Ċ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 skompli-

kowana. Podobnie jak w przypadku metody poprzedniej, tak

Īe i tu musimy wykonaü pewną pre-

kompilacj

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

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.

Tytu

á znakomitego cyklu autorstwa Ewy SzumaĔskiej.

186

Algorytmy, struktury danych i techniki programowania

Rysunek 8.7. Przeszukiwanie tekstu metod

ą Boyera i Moore'a

Ċdziemy równieĪ potrzebowali prostej funkcji

indeks

, która zwraca w przypadku spacji licz-

Ċ zero — w pozostaáych przypadkach 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

indeks

jest

przedstawiona poni

Īej:

bm.cpp

const

int K=26*2+2*2+1;// znaki ASCII + polskie litery + odst

Ċp

int

shift[K];

int

indeks(char c)

{
switch

(c)

{
case ' ':return 0; // odst

Ċp = 0

case 'ú':return 53;
case 'ù':return 54; // polskie litery
case 'đ':return 55;
case 'Đ':return 56; // itd. dla pozosta

áych polskich liter

default:
if(islower(c))
return c-'a'+1;
else
return c-'A'+27;
• •
• •

Funkcja

indeks

ma jedynie charakter us

áugowy. SáuĪy ona m.in. do wáaĞciwej inicjalizacji tablicy

przesuni

Ċü. Mając za sobą analizĊ przykáadu z rysunku 8.7, Czytelnik nie powinien byü zbyt-

nio zdziwiony sposobem inicjalizacji:

void

init_shifts(char *w)

{
int

M=strlen(w);

for

(int i=0; i<K; i++)

shift[i]=M;

Czytaj dalej...

Rozdzia

ä 8.

i Przeszukiwanie tekstów

187

for

(int i=0; i<M; i++)

shift[indeks(w[i])]=M-i-1;
}

Przejd

Ĩmy wreszcie do prezentacji samego listingu algorytmu, z przykáadem wywoáania:

int

bm(char *w, char *t)

{
init_shifts(w);
int

i, j,N=strlen(t),M=strlen(w);

for

(i=M-1,j=M-1; j>0; i--,j--)

while(t[i]!=w[j])
{
int x=shift[indeks(t[i])];
if(M-j>x)
i+=M-j;
else
i+=x;
if (i>=N)
return -1;
j=M-1;
}
return

}

int

main()

{
char

*t="Z pamiútnika mđodej lekarki";

cout << "Wynik poszukiwaē="<<bm("lek",t)<<endl;
}

Algorytm Boyera i Moore’a, podobnie jak i K-M-P, jest klasy

M+N

— 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

Ċü

autorzy algorytmu 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 czasocháonnym sam proces prekompilacji wzorca.

Algorytm Rabina i Karpa

Ostatni algorytm do przeszukiwania tekstów, który b

Ċdziemy analizowali, wymaga znajomoĞci roz-

dzia

á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

=H(w)

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ów

. Z tych

znaków wyliczamy na bie

Īąco

=H(t)

Gdy za

áoĪymy jednoznacznoĞü wybranej funkcji

, sprawdzenie zgodno

Ğci wzorca z aktualnie ba-

danym fragmentem tekstu sprowadza si

Ċ do odpowiedzi na pytanie: czy

jest równe

? Spo-

strzegawczy 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

Rozwa

Ī np. wielokrotne wystĊpowanie takich samych liter we wzorcu.

Na samym pocz

ątku bĊdzie to oczywiĞcie

pierwszych znaków tekstu.