Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00556 008660 10441438 na godz. na dobę w sumie
Algorytmy, struktury danych i techniki programowania. Wydanie III - książka
Algorytmy, struktury danych i techniki programowania. Wydanie III - książka
Autor: Liczba stron: 360
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-101-0 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> algorytmy - programowanie
Porównaj ceny (książka, ebook, audiobook).

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 problemów za pomocą komputera. Teoria algorytmów i struktur danych jest jednym z podstawowych przedmiotów wykładanych na studiach informatycznych i pokrewnych.

To już trzecie, poprawione wydanie książki, która od wielu lat stanowi podstawowy podręcznik z dziedziny algorytmiki. Różni się od klasycznych podręczników akademickich: skierowana jest nie tylko do adeptów informatyki. Dzięki naciskowi na praktyczną stronę prezentowanych zagadnień powinna 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 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.

W książce opisano m.in.: 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.

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Algorytmy, struktury danych i techniki programowania. Wydanie III Autor: Piotr Wróblewski ISBN: 83-7361-101-0 Format: B5, stron: 360 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 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 podstawowy podrêcznik z dziedziny algorytmiki. Ró¿ni siê od klasycznych podrêczników akademickich: skierowana jest nie tylko do adeptów informatyki. Dziêki naciskowi na praktyczn¹ stronê prezentowanych zagadnieñ powinna 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 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. W ksi¹¿ce opisano m.in.: • Techniki rekurencyjne: co to jest rekurencja i jak j¹ stosowaæ w praktyce? • 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 wystêpuj¹cych w informatyce. • Sztuczna inteligencja: czy komputery mog¹ myġleæ? • Kodowanie i kompresja danych: opis najpopularniejszych metod kodowania i kompresji danych — systemu kryptograficznego z kluczem publicznym 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 „cwymyślił” metodologię programowania ...................................................c..................................23 1.3. Proces koncepcji programów ...................................................c..................................24 1.4. Poziomy abstrakcji opisu i wybór języka...................................................c................25 1.5. Poprawność algorytmów ...................................................c.........................................27 Rozdział 2. Rekurencja ....................................................................................... 29 2.1. Definicja rekurencji...................................................c.................................................29 2.2. Ilustracja pojęcia rekurencji ...................................................c....................................31 2.3. Jak wykonują się programy rekurencyjne?...................................................c................32 2.4. Niebezpieczeństwa rekurencji...................................................c.................................34 2.4.1. Ciąg Fibonacciego ...................................................c.........................................34 2.4.2. Stack overflow!...................................................c..............................................36 2.5. Pułapek ciąg dalszy ...................................................c.................................................37 2.5.1. Stąd do wieczności...................................................c.........................................37 2.5.2. Definicja poprawna, ale... ...................................................c..............................38 2.6. Typy programów rekurencyjnych ...................................................c...........................39 2.7. Myślenie rekurencyjne ...................................................c............................................41 2.7.1. Przykład 1.: Spirala...................................................c........................................42 2.7.2. Przykład 2.: Kwadraty „parzyste”...................................................c..................44 2.8. Uwagi praktyczne na temat technik rekurencyjnych .................................................45 2.9. Zadania ...................................................c...................................................c.................46 2.9.1. Zadanie 2.1....................................................c...................................................c.46 2.9.2. Zadanie 2.2....................................................c...................................................c.46 2.9.3. Zadanie 2.3....................................................c...................................................c.48 2.9.4. Zadanie 2.4....................................................c...................................................c.48 2.9.5. Zadanie 2.5....................................................c...................................................c.49 2.10. Rozwiązania i wskazówki do zadań...................................................c......................49 2.10.1. Zadanie 2.1....................................................c..................................................49 2.10.2. Zadanie 2.2....................................................c..................................................50 2.10.3. Zadanie 2.3....................................................c..................................................50 2.10.4. Zadanie 2.4....................................................c..................................................51 2.10.5. Zadanie 2.5....................................................c..................................................52 6 Algorytmy, struktury danych i techniki programowania Rozdział 3. Analiza sprawności algorytmów ......................................................... 53 3.1. Dobre samopoczucie użytkownika programu ...................................................c.........54 3.2. Przykład 1: Jeszcze raz funkcja silnia... ...................................................c..................56 3.3. Przykład 2: Zerowanie fragmentu tablicy ...................................................c...............60 3.4. Przykład 3: Wpadamy w pułapkę...................................................c............................62 3.5. Przykład 4: Różne typy złożoności obliczeniowej...................................................c..63 3.6. Nowe zadanie: uprościć obliczenia! ...................................................c.........................66 3.7. Analiza programów rekurencyjnych ...................................................c........................66 3.7.1. Terminologia...................................................c..................................................67 3.7.2. Ilustracja metody na przykładzie ...................................................c...................68 3.7.3. Rozkład logarytmiczny ...................................................c..................................70 3.7.4. Zamiana dziedziny równania rekurencyjnego ..................................................71 3.7.5. Funkcja Ackermanna, czyli coś dla smakoszy .................................................72 3.8. Zadania ...................................................c...................................................c.................73 3.8.1. Zadanie 3.1....................................................c...................................................c.73 3.8.2. Zadanie 3.2....................................................c...................................................c.74 3.8.3. Zadanie 3.3....................................................c...................................................c.74 3.8.4. Zadanie 3.4....................................................c...................................................c.74 3.9. Rozwiązania i wskazówki do zadań...................................................c........................75 3.9.1 Zadanie 3.2....................................................c...................................................c..75 3.9.2. Zadanie 3.4....................................................c...................................................c.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)...................................................c........80 4.3. Quicksort, algorytm klasy O(N log N)...................................................c....................82 4.4. Heap Sort — sortowanie przez kopcowanie ...................................................c...........85 4.5. Sortowanie przez scalanie ...................................................c.......................................88 4.6. Uwagi praktyczne...................................................c...................................................c.90 Rozdział 5. Struktury danych .............................................................................. 93 5.1. Listy jednokierunkowe...................................................c............................................94 5.1.1. Realizacja struktur danych listy jednokierunkowej ..........................................96 5.1.2. Tworzenie listy jednokierunkowej...................................................c.................97 5.1.3. Listy jednokierunkowe — teoria i rzeczywistość................................................106 5.2. Tablicowa implementacja list...................................................c................................119 5.2.1. Klasyczna reprezentacja tablicowa ...................................................c..............119 5.2.2. Metoda tablic równoległych ...................................................c........................121 5.2.3. Listy innych typów ...................................................c......................................123 5.3. Stos...................................................c...................................................c.....................125 5.3.1. Zasada działania stosu...................................................c..................................125 5.4. Kolejki FIFO ...................................................c...................................................c......129 5.5. Sterty i kolejki priorytetowe...................................................c..................................132 5.6. Drzewa i ich reprezentacje ...................................................c....................................139 5.6.1. Drzewa binarne i wyrażenia arytmetyczne ...................................................c..142 5.7. Uniwersalna struktura słownikowa ...................................................c.......................147 5.8. Zbiory ...................................................c...................................................c.................152 5.9. Zadania ...................................................c...................................................c...............155 5.9.1. Zadanie 5.1....................................................c..................................................155 5.9.2. Zadanie 5.2....................................................c..................................................155 5.9.3. Zadanie 5.3....................................................c..................................................155 5.10. Rozwiązania zadań...................................................c..............................................155 5.10.1. Zadanie 5.1....................................................c................................................155 5.10.2. Zadanie 5.3....................................................c................................................156 Spis treści 7 Rozdział 6. Derekursywacja i optymalizacja algorytmów ................................... 157 6.1. Jak pracuje kompilator? ...................................................c........................................158 6.2. Odrobina formalizmu nie zaszkodzi!...................................................c.......................160 6.3. Kilka przykładów derekursywacji algorytmów ...................................................c........162 6.4. Derekursywacja z wykorzystaniem stosu ...................................................c.............165 6.4.1. Eliminacja zmiennych lokalnych...................................................c.................166 6.5. Metoda funkcji przeciwnych...................................................c.................................168 6.6. Klasyczne schematy derekursywacji...................................................c.....................170 6.6.1. Schemat typu while...................................................c......................................171 6.6.2. Schemat typu if-else...................................................c.....................................173 6.6.3. Schemat z podwójnym wywołaniem rekurencyjnym .....................................175 6.7. Podsumowanie ...................................................c...................................................c...177 Rozdział 7. Algorytmy przeszukiwania ............................................................... 179 7.1. Przeszukiwanie liniowe...................................................c.........................................179 7.2. Przeszukiwanie binarne...................................................c.........................................180 7.3. Transformacja kluczowa (hashing) ...................................................c.......................181 7.3.1. W poszukiwaniu funkcji H ...................................................c..........................183 7.3.2. Najbardziej znane funkcje H...................................................c........................184 7.3.3. Obsługa konfliktów dostępu ...................................................c........................187 7.3.4. Powrót do źródeł ...................................................c..........................................187 7.3.5. Jeszcze raz tablice!...................................................c.......................................188 7.3.6. Próbkowanie liniowe ...................................................c...................................189 7.3.7. Podwójne kluczowanie ...................................................c................................191 7.3.8. Zastosowania transformacji kluczowej...................................................c........193 7.3.9. Podsumowanie metod transformacji kluczowej ...............................................193 Rozdział 8. Przeszukiwanie tekstów .................................................................. 195 8.1. Algorytm typu brute-force ...................................................c....................................195 8.2. Nowe algorytmy poszukiwań...................................................c................................197 8.2.1. Algorytm K-M-P...................................................c..........................................198 8.2.2.Algorytm Boyera i Moore’a...................................................c..........................203 8.2.3. Algorytm Rabina i Karpa...................................................c.............................205 Rozdział 9. Zaawansowane techniki programowania......................................... 209 9.1. Programowanie typu „dziel i zwyciężaj” ...................................................c..............210 9.1.1. Odszukiwanie minimum i maksimum w tablicy liczb....................................211 9.1.2. Mnożenie macierzy o rozmiarze N×N...................................................c.........214 9.1.3. Mnożenie liczb całkowitych ...................................................c........................217 9.1.4. Inne znane algorytmy „dziel i zwyciężaj” ...................................................c...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 ...................................................c.................................223 9.4. Uwagi bibliograficzne ...................................................c...........................................227 Rozdział 10. Elementy algorytmiki grafów ........................................................... 229 10.1. Definicje i pojęcia podstawowe ...................................................c..........................230 10.2. Sposoby reprezentacji grafów ...................................................c.............................232 10.3. Podstawowe operacje na grafach ...................................................c........................234 10.3.1. Suma grafów ...................................................c..............................................234 10.3.2. Kompozycja grafów...................................................c...................................234 10.3.3. Potęga grafu ...................................................c...............................................235 10.4. Algorytm Roy-Warshalla ...................................................c....................................236 10.5. Algorytm Floyda-Warshalla...................................................c................................239 10.6. Algorytm Dijkstry ...................................................c...............................................243 8 Algorytmy, struktury danych i techniki programowania 10.7. Drzewo rozpinające minimalne...................................................c...........................244 10.8. Przeszukiwanie grafów ...................................................c.......................................245 10.8.1. Strategia „w głąb” ...................................................c......................................246 10.8.2. Strategia „wszerz”...................................................c......................................247 10.9. Problem właściwego doboru ...................................................c...............................249 10.10. Podsumowanie ...................................................c..................................................254 Rozdział 11.Algorytmy numeryczne..................................................................... 255 11.1. Poszukiwanie miejsc zerowych funkcji ...................................................c..............255 11.2. Iteracyjne obliczanie wartości funkcji...................................................c.................257 11.3. Interpolacja funkcji metodą Lagrange’a ...................................................c.............258 11.4. Różniczkowanie funkcji...................................................c......................................260 11.5. Całkowanie funkcji metodą Simpsona...................................................c................262 11.6. Rozwiązywanie układów równań liniowych metodą Gaussa ................................263 11.7. Uwagi końcowe...................................................c...................................................c266 Rozdział 12. Czy komputery mogą myśleć? ......................................................... 267 12.1. Przegląd obszarów zainteresowań Sztucznej Inteligencji......................................268 12.1.1. Systemy eksperckie...................................................c....................................269 12.1.2. Sieci neuronowe...................................................c.........................................271 12.2. Reprezentacja problemów ...................................................c...................................272 12.2.1. Ćwiczenie 12.1....................................................c..........................................274 12.3. Gry dwuosobowe i drzewa gier...................................................c...........................274 12.4. Algorytm mini-max...................................................c.............................................276 Rozdział 13. Kodowanie i kompresja danych ....................................................... 281 13.1. Kodowanie danych i arytmetyka dużych liczb...................................................c........283 13.1.1. Kodowanie symetryczne...................................................c............................284 13.1.2. Kodowanie asymetryczne ...................................................c..........................285 13.1.3. Metody prymitywne...................................................c...................................292 13.1.4. Łamanie szyfrów...................................................c........................................293 13.2. Techniki kompresji danych ...................................................c.................................294 13.2.1. Kompresja poprzez modelowanie matematyczne.........................................296 13.2.2. Kompresja metodą RLE...................................................c.............................297 13.2.3. Kompresja danych metodą Huffmana ...................................................c.......298 13.2.4. Kodowanie LZW ...................................................c.......................................304 13.2.5. Idea kodowania słownikowego na przykładach ...........................................304 13.2.6. Opis formatu GIF...................................................c.......................................307 Rozdział 14. Zadania różne................................................................................. 311 14.1. Teksty zadań...................................................c...................................................c.....311 14.1.1. Zadanie 14.1....................................................c..............................................311 14.1.2. Zadanie 14.2....................................................c..............................................312 14.1.3. Zadanie 14.3....................................................c..............................................312 14.1.4. Zadanie 14.4....................................................c..............................................312 14.1.5. Zadanie 14.5....................................................c..............................................312 14.1.6. Zadanie 14.6....................................................c..............................................312 14.1.7. Zadanie 14.7....................................................c..............................................312 14.1.8. Zadanie 14.8....................................................c..............................................313 14.1.9. Zadanie 14.9....................................................c..............................................313 14.1.10. Zadanie 14.10....................................................c..........................................313 14.1.11. Zadanie 14.11....................................................c..........................................313 14.1.12. Zadanie 14.12....................................................c..........................................313 Spis treści 9 14.2. Rozwiązania ...................................................c...................................................c.....313 14.2.1. Zadanie 14.1....................................................c..............................................313 14.2.2. Zadanie 14.3....................................................c..............................................314 14.2.3. Zadanie 14.4....................................................c..............................................315 14.2.4. Zadanie 14.10....................................................c............................................315 14.2.5. Zadanie 14.12....................................................c............................................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. Algorytm typu brute- -force przeszukiwania tekstu Fragmenty (jeszcze) zgodne T E L E F NO K O T E L E E SK O R ZA 0 j M-1 0 i N-1 wzorzec w Badany tekst t 1 2 3 Reprezentujący np. pamięć ekranu. Np. ASCII lub dowolny inny. Ang. pattern matching. 196 Algorytmy, struktury danych i techniki programowania Zarezerwujmy indeksy L i K 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 (K ;L ). Cóż się jednak powinno stać z indeksami K oraz L 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 L znaków, wyzerowując przy okazji L. 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 L 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 K/. Tłumacząc powyższe sytuacje na C++, możemy łatwo dojść dro następującej procedury: txt-1.cpp KPVUWMCL EJCT YEJCT V ] KPVKL/0 /UVTNGP Y FđWIQħèYQTEC 0UVTNGP V FđWIQħèVGMUVW YJKNG L/K0 ] KH V=K?Y=L? ] KL L _ K L  _ KH L/ TGVWTPK/ GNUG TGVWTP _ Sposób korzystania z funkcji UWMCL jest przedstawiony na przykładzie następującej funkcji OCKP: KPVOCKP ] EJCT DCDTCMCFCDTC CTCM EQWVUWMCL CD GPFNYTCEC _ 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. ♦ Przeszukiwanie tekstów 197 Rysunek 8.2. „Fałszywe starty” podczas poszukiwania 0 ` 1 0 0 1 1 1 0 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 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 0 0 1 1 0 0 0 1 0 0 0 Rysunek jest nieco uproszczony: w istocie poziome przesuwanie się wzorca oznacza in- strukcje zaznaczone na listingu jako (*), natomiast całra 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 0  / 0/  razy, i wiedząc, że pod- czas każdego cyklu jest konieczne wykonanie / porównań, otrzymujemy natychmiast / 0/  , czyli około5 /Ŗ0. 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łaniemr. 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 5 6 Zera i jedynki symbolizują tu dwa różne od siebie znakąi. Zwykle / będzie znacznie mniejsze niż 0. Termin brute-force jeden z moich znajomych ślicznie przetłumaczył jako „mąetodę mastodonta”. 198 Algorytmy, struktury danych i techniki programowania algorytm poszukiwania wzorca w tekście, który działał w czasie proporcjonalnym do / 0 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 wynaleźli algorytm, który — działając ciągle w czasie proporcjonalnym do / 0 — 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ć wskaźnika K o L pozycji, jak to było poprzednio (patrz listing txt-1.cpp). W tym przypadku możemy po prostu zinkrementować K 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. ♦ 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ąć wskaźnik K 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 bardanym tekście nieco inteligentniej niż w poprzednim algorytmie. W przypadku zauważenia niezgodności na pewnej pozy- cji L 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óż wyobraźmy 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 znajdurją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 „L 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 L 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 K w spokoju, to — modyfikując wyłącznie L — 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! Lub i w przypadku badanego tekstu. 8 9 Licząc indeksy tablicy tradycyjnie od zera. 200 Algorytmy, struktury danych i techniki programowania Rysunek 8.4. Przesuwanie się wzorca w algorytmie K-M-P (1) i=const i=const 1 1 2 2 3 3 4 4 1 1 2 2 3 3 5 4 1 2 3 4 1 1 2 2 3 3 5 4 1 2 3 4 j=7 j=3 Analogiczny przykład znajduje się na rysunku 8.5. Rysunek 8.5. Przesuwanie się wzorca w algorytmie K-M-P (2) i=const i=const 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 j=3 j=1 Tym razem niezgodność wystąpiła na pozycji L. 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 L. 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 K. Dla potrzeb algorytmu K-M-P konieczne okazuje się wprowadzenie tablicy przesunięć KPVUJKHV=/?. Sposób jej zastosowania będzie następujący: jeśli na pozycji L wystąpiła niezgodność znaków, to kolejną wartością L będzie UJKHV=L?. 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 KPVMOR EJCT YEJCT V ] KPVKL0UVTNGP V  HQT KLK0L/K L YJKNG L   V=K?Y=L? LUJKHV=L? KH L/ TGVWTPK/ GNUG TGVWTP _ 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 L pozostał niezmieniony przy jednoczesnej progre- sji indeksu K. Jest to możliwe do uzyskania, jeśli umówimy się, że UJKHV=? zostanie zainicjowany wartością . Wówczas podczas kolejnej iteracji pętli HQT nastąpi in- krementacja K oraz L, co wyzeruje nam L. Rozdział 8. ♦ Przeszukiwanie tekstów 201 Pozostaje do omówienia sposób konstrukcji tablicy UJKHV=/?. Jej obliczenie powinno nastąpić przed wywołaniem funkcji MOR, 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 MOR z tą tylko różnicą, iż algorytm sprawdza zgodność wzorca... z nim samym! KPVUJKHV=/? XQKFKPKVAUJKHVU EJCT Y ] KPVKL UJKHV=? HQT KLK/K L UJKHV=K?L YJKNG  L   Y=K?Y=L?  LUJKHV=L? _ Sens tego algorytmu jest następujący: tuż po inkrementacji K i L wiemy, że pierwsze L znaków wzorca jest zgodne ze znakami na pozycjach: R=KL?R=K? (ostatnie L pozycji w pierwszych K znakach wzorca). Ponieważ jest to największe L spełniające po- wyższy warunek, zatem, aby nie ominąć potencjalnego miejsca wykrycia wzorca w tek- ście, należy ustawić UJKHV=K? na L. Popatrzmy, jaki będzie efekt zadziałania funkcji KPKVAUJKHVU 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ą (po- równaj rysunek 8.5). Rysunek 8.6. Optymalne przesunięcia wzorca „ananas” a) b) a n a n a s a n a n s a s d) a n a a n n a a s n a s s a s a n a n a a n a n c) a n e) a n a a a a n n n n a a a a n a s s n a s Przypomnijmy jeszcze, że tablica UJKHV zawiera nową wartość dla indeksu L, 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ę MOR można wbudować tablicę przesunięć: 202 Algorytmy, struktury danych i techniki programowania ananas.cpp KPVMORACPCPCU EJCT V ] KPVK UVCTV K  GVKH V=K? C IQVQUVCTV K  GVKH V=K? P IQVQGV K  GVKH V=K? C IQVQGV K  GVKH V=K? P IQVQGV K  KH V=K? C IQVQGV K  KH V=K? U IQVQGV K  TGVWTPK _ W celu właściwego odtworzenia etykiet należy oczywiście co najmniej raz wykonać funkcję KPKVAUJKHVU lub obliczyć samemu odpowiednie wartości. W każdym rrazie 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 MOR i MORACPCPCU! Dla przykładu mogę podać, że w przypadku wspomnianego kompilatora GNU klasyczna wersja pro- cedury MOR (wraz z KPKVAUJKHVU) miała objętość około 170 linii kodu asemblerowego, natomiast MORACPCPCU 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 / 0 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ć, wskaźnik K w funk- cji MOR 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. ♦ 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 rozpatrywarny 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 algorytrmu 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. Przeszukiwanie tekstu metodą Boyera i Moore a Z p a m i ę t n i k a m ł o d e j l e k a r k i l e k l e k l e k l e k l e k l e l k e k l e l k e k Pierwsze pięć porównań trafia na litery: R, K, P, Ci đ, 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ę G, która w słowie „lek” wy- stępuje. Algorytm wówczas przesuwa wzorzec o tyle pozycji do przodu, aby litery G nałożyły się na siebie, i porównywanie jest kontynurowane. Następnie okazuje się, że litera L 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 wzorrca, tak aby pokryły się litery M. 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 KPFGMU, 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 KPFGMU jest przedstawiona poniżej: EQPUV-    PCMK#5 ++ RQNUMKGNKVGT[ URCELC KPVUJKHV=-? KPVKPFGMU EJCTE ] UYKVEJ E ] ECUG  TGVWTPURCELC ECUG ú TGVWTP ECUG ù TGVWTPRQNUMKGNKVGT[ ECUG đ TGVWTP ECUG Đ TGVWTPKVFFNCRQQUVCđ[EJ FGHCWNVRQNUMKEJNKVGT KH KUNQYGT E ŎEŏLGUVOCđæNKVGTæ! TGVWTPE C  GNUG TGVWTPE #  _ _ Funkcja KPFGMU 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: XQKFKPKVAUJKHVU EJCT Y ] KPVK/UVTNGP Y  HQT KK-K UJKHV=K?/ HQT KK/K UJKHV=KPFGMU Y=K? ?/K _ Przejdźmy wreszcie do prezentacji samego listingu algorrytmu, z przykładem wywołania: KPVDO EJCT YEJCT V ] KPKVAUJKHVU Y  KPVKL0UVTNGP V /UVTNGP Y  HQT K/L/L KL YJKNG V=K?Y=L? ] KPVZUJKHV=KPFGMU V=K? ? KH /L Z K /L GNUG K Z KH K 0 TGVWTP L/ _ Rozdział 8. ♦ Przeszukiwanie tekstów 205 TGVWTPK _ KPVOCKP ] EJCT V RCOKúVPKMCOđQFGLNGMCTMK EQWV9[PKMRQUWMKYCēDO NGMV GPFN _ Algorytm Boyera i Moore’a, podobnie jak i K-M-P, jest klasy / 0 — 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 Y(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 *Y* Y i korzystać z tego wyliczenia w sposób ciągły.  tekst wejściowy V (do przeszukania) może być w taki sposób odczytywanyr, aby na bieżąco znać / ostatnich znaków13. Z tych / znaków wyliczamy na bieżąco *V* V . Gdy założymy jednoznaczność wybranej funkcji *, sprawdzenie zgodności wzorca z aktualnie badanym fragmentem tekstu sprowadza się do odpowiedzi na pytanie: czy *Y jest równe *V? 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 13 Rozważ np. wielokrotne występowanie takich samych liteąr we wzorcu. 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]b M-1 + t[i + 1]b M-2 + t[i + M -1]. K Przesuńmy się teraz w tekście o jedną pozycję do przodu i zobaczmy, jak zmieni się wartość x: x = t[i + 1]b M-1 + t[i + 2]b M-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]b ( M -1 ) + t[i + M]. Jako funkcji * użyjemy dobrze nam znanej z poprzedniego rozdziału * Z Z R, gdzie R jest dużą liczbą pierwszą. Załóżmy, że dla danej pozycji K wartość * Z jest nam znana. Po przesunięciu się w tekście o jedną pozycję w prawo pojawia się konieczność wyliczenia wartości funkcji * Z 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 Z i Z ? Na pomoc przychodzi nam tu własność funkcji OQFWNQ użytej w wyrażeniu arytmetycz- nym. Można oczywiście obliczyć OQFWNQ 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ę OQFWNQ po każdej operacji cząstkowej i przenosząc otrzymaną wartość do następnego wyrażenia cząstkowego! Dla przykładu weźmy robliczenie: (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. ♦ Przeszukiwanie tekstów 207 rk.cpp KPVTM EJCTY=?EJCTV=? ] WPUKIPGFNQPIKD/A*Y*V/0 /UVTNGP Y 0UVTNGP V  HQT KK/K ] *Y *Y D KPFGMU Y=K? RKPKELCELCHWPMELK*FNCYQTECY *V *V D KPFGMU V=K? RKPKELCELCHWPMELK*FNCVGMUVW _ HQT KK/K D/A D D/A R HQT K*Y*VK RTGUWYCPKGUKúYVGMħEKG ] *V *V D RKPFGMU V=K? D/A R *V *V D KPFGMU V=K /? R KH K 0/ TGVWTPRQTCľMCRQUWMKYCē _ TGVWTPK _ Na pierwszym etapie następuje wyliczenie początkowych wartości *V i *Y. Ponieważ ciągi znaków trzeba interpretować jako liczby, konieczne będzie zastosowanie znanej już nam doskonale funkcji KPFGMU (patrz strona 204.). Wartość *Y jest niezmienna i nie wymaga uaktualniania. Nie dotyczy to jednak aktualnie badanego fragmentu tekstu — tutaj wartość *V ulega zmianie podczas każdej inkrementacji zmiennej K. Do obliczenia * Z możemy wykorzystać omówioną wcześniej własność funkcji OQFWNQ — co jest do- konywane w trzeciej pętli HQT. Dodatkowego wyjaśnienia wymaga być może linia ozna- czona (*). Otóż dodawanie wartości D R do *V pozwala nam uniknąć przypadkowego wskoczenia w liczby ujemne. Gdyby istotnie tak się stało, przeniesiona do następnego wyrażenia arytmetycznego wartość OQFWNQ byłaby nieprawidłowa i sfałszowałaby koń- cowy wynik! Kolejne uwagi należą się parametrom R i D. Zaleca się, aby R 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 R 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 Y i V=K? V=K /? po zwróceniu przez funkcję TM pewnego indeksu K. 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 D R jako R. 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 / 0. 14 W naszym przypadku jest to liczba 33554393.
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Algorytmy, struktury danych i techniki programowania. Wydanie III
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: