Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00077 006030 19007263 na godz. na dobę w sumie
Algorytmy, struktury danych i techniki programowania dla programistów Java - książka
Algorytmy, struktury danych i techniki programowania dla programistów Java - książka
Autor: Liczba stron: 456
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-5465-4 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> java - programowanie
Porównaj ceny (książka, ebook (-35%), audiobook).

Opanuj Javę jak prawdziwy profesjonalista!

Java jest obecnie jednym z najpopularniejszych języków programowania, co zawdzięcza przede wszystkim swojej prostocie, nowoczesności, dużym możliwościom oraz niezależności od architektury platform sprzętowych i systemowych, na których mają pracować napisane w tym języku programy. Java znalazła zastosowanie w wielu różnych branżach - zdecydowanie dominuje w rozwiązaniach działających w sieci, stanowiących obecnie dużą część oprogramowania tworzonego komercyjnie. Mimo to dotychczas trudno było znaleźć rzetelne źródło wiedzy o algorytmach, które byłoby przeznaczone dla użytkowników Javy, wyjaśniało zasady modelowania danych w tym języku i pozwalało szybko testować gotowe programy.

Na szczęście to już przeszłość! Książka Algorytmy, struktury danych i techniki programowania dla programistów Java jest pierwszą poważną pozycją przybliżającą tematykę algorytmów osobom posługującym się tym językiem. W prosty i praktyczny sposób przedstawia najważniejsze zagadnienia algorytmiki, pozwala poznać struktury danych i ich zastosowania, prezentuje popularne algorytmy oraz problemy, które można za ich pomocą rozwiązać, omawia także techniki programowania wykorzystywane przez miliony specjalistów w ich codziennej pracy. Jeśli chcesz być profesjonalnym programistą Javy, nie mogłeś trafić lepiej!

Rozwiązuj problemy programistyczne w Javie!

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

Darmowy fragment publikacji:

Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Redaktor prowadzący: Małgorzata Kulik Projekt okładki: Studio Gravite / Olsztyn Obarek, Pokoński, Pazdrijowski, Zaprucki Grafika na okładce została wykorzystana za zgodą Shutterstock.com Wydawnictwo HELION ul. Kościuszki 1c, 44-100 GLIWICE tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie/algoja Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. ISBN: 978-83-283-5465-4 Copyright © Helion 2019 Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Czym powinien się charakteryzować algorytm? ........................................................................ 18 Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych .................. 20 — 1804 — ................................................................................................................ 20 — 1830 i później — ................................................................................................. 21 — 1890 — ................................................................................................................ 21 — lata 30. XX w. — ................................................................................................. 21 — lata 40. XX w. — ................................................................................................. 22 — okres powojenny — ............................................................................................. 22 — 1969 — ................................................................................................................ 23 — teraz — ................................................................................................................ 23 Jak to się niedawno odbyło, czyli o tym, kto „wymyślił” metodologię programowania ....................................................................................................................................... 24 Proces koncepcji programów .............................................................................................................. 25 Poziomy abstrakcji opisu i wybór języka ...................................................................................... 26 Modelowanie działania algorytmów (maszyna Turinga) ...................................................... 28 Poprawność algorytmów ....................................................................................................................... 29 Zadania ........................................................................................................................................................... 31 Rozwiązania i wskazówki do zadań ................................................................................................. 31 System dziesiętny i kilka definicji ..................................................................................................... 36 System dwójkowy ..................................................................................................................................... 36 Operacje arytmetyczne na liczbach dwójkowych ..................................................... 37 Operacje logiczne na liczbach dwójkowych ............................................................. 38 Kod BCD ......................................................................................................................................................... 40 System ósemkowy .................................................................................................................................... 41 System szesnastkowy .............................................................................................................................. 41 Kodowanie liczb ze znakiem ................................................................................................................ 42 Kod znak-moduł (ZM) ............................................................................................. 42 Kod U2 (system uzupełnienia dwójkowego) ............................................................ 42 Zmienne w pamięci komputera .......................................................................................................... 43 Kodowanie znaków .................................................................................................................................. 44 Kodowanie obrazów ................................................................................................................................ 46 Mapy bitowe na przykładzie formatu BMP .............................................................. 47 Kup książkęPoleć książkę Definicja rekurencji .................................................................................................................................. 51 Ilustracja pojęcia rekurencji ................................................................................................................ 53 Jak wykonują się programy rekurencyjne? .................................................................................. 55 Niebezpieczeństwa rekurencji ............................................................................................................ 56 Ciąg Fibonacciego .................................................................................................... 56 Stack overflow! ........................................................................................................ 58 Pułapek ciąg dalszy .................................................................................................................................. 61 Stąd do wieczności ................................................................................................... 61 Definicja poprawna, ale… ........................................................................................ 62 Typy programów rekurencyjnych .................................................................................................... 63 Myślenie rekurencyjne ........................................................................................................................... 65 Przykład 1. Spirala ................................................................................................... 66 Przykład 2. Kwadraty „parzyste” ............................................................................. 67 Uwagi praktyczne na temat technik rekurencyjnych .............................................................. 69 Zadania ........................................................................................................................................................... 70 Rozwiązania i wskazówki do zadań ................................................................................................. 73 Definicje i przykłady ................................................................................................................................ 80 Jeszcze raz funkcja silnia .......................................................................................... 83 Zerowanie fragmentu tablicy .................................................................................... 87 Wpadamy w pułapkę ................................................................................................ 89 Różne typy złożoności obliczeniowej ...................................................................... 90 Nowe zadanie: uprościć obliczenia! ................................................................................................. 92 Analiza programów rekurencyjnych ............................................................................................... 92 Terminologia i definicje ........................................................................................... 92 Ilustracja metody na przykładzie .............................................................................. 94 Rozkład logarytmiczny ............................................................................................. 95 Przeszukiwanie binarne… tym razem bez matematyki wyższej! ............................. 96 Zamiana dziedziny równania rekurencyjnego .......................................................... 97 Funkcja Ackermanna, czyli coś dla smakoszy ......................................................... 97 Złożoność obliczeniowa to nie religia! ............................................................................................ 99 Techniki optymalizacji programów ............................................................................................... 100 Zadania ........................................................................................................................................................ 101 Rozwiązania i wskazówki do zadań .............................................................................................. 102 Typy proste i złożone ........................................................................................................................... 104 Operatory i zmienne ............................................................................................... 105 Obiektowe typy proste, czyli klasy osłonowe ........................................................ 107 Ciągi znaków i napisy ............................................................................................ 107 Tablice .................................................................................................................... 110 Pojęcie referencji, czyli gdzie te wskaźniki z dawnych lat… ................................. 113 Programowanie obiektowe jako narzędzie modelowania danych i algorytmów ........ 116 Terminologia .......................................................................................................... 117 Modelowanie danych na przykładzie liczb zespolonych ........................................ 119 Pola i metody statyczne klas ................................................................................... 122 Dziedziczenie własności ......................................................................................... 123 Struktury rekurencyjne w Javie ...................................................................................................... 126 Kup książkęPoleć książkę Abstrakcyjne typy danych .................................................................................................................. 130 Listy jednokierunkowe ........................................................................................... 131 Tablicowa implementacja list ................................................................................. 154 Listy innych typów ................................................................................................. 160 Listy z iteratorem ................................................................................................... 164 Podsumowanie ........................................................................................................................................ 169 Stos ................................................................................................................................................................ 171 Zasada działania stosu ............................................................................................ 171 Realizacja programowa stosu ................................................................................. 173 Kolejki FIFO ............................................................................................................................................... 176 Sterty i kolejki priorytetowe ............................................................................................................. 179 Zadania ........................................................................................................................................................ 186 Rozwiązania i wskazówki do zadań .............................................................................................. 186 Drzewa i ich reprezentacje ................................................................................................................ 189 Binarne drzewa poszukiwań (BST) ........................................................................ 193 Drzewa binarne i wyrażenia arytmetyczne ............................................................. 199 Uniwersalna struktura słownikowa ......................................................................... 205 Drzewa „egzotyczne” ............................................................................................. 210 Zbiory ........................................................................................................................................................... 211 Zadania ........................................................................................................................................................ 213 Rozwiązania zadań ................................................................................................................................ 214 Java i interfejsy ........................................................................................................................................ 216 Klasa Arrays, operacje na tablicach ............................................................................................... 217 Klasa Vector, czyli tablice dynamiczne ........................................................................................ 218 Listy ............................................................................................................................................................... 221 Iteratory, czyli wygodne indeksowanie kolekcji ..................................................................... 222 Stos ................................................................................................................................................................ 223 Sortowanie kolekcji ............................................................................................................................... 224 Klasa HashSet, czyli szybko do celu ............................................................................................... 225 Przeszukiwanie liniowe ...................................................................................................................... 227 Przeszukiwanie binarne ...................................................................................................................... 228 Transformacja kluczowa (hashing) ............................................................................................... 230 W poszukiwaniu funkcji H ..................................................................................... 232 Najbardziej znane funkcje H .................................................................................. 233 Obsługa konfliktów dostępu ................................................................................... 235 Powrót do źródeł .................................................................................................... 235 Jeszcze raz tablice! ................................................................................................. 236 Próbkowanie liniowe .............................................................................................. 237 Podwójne kluczowanie ........................................................................................... 238 Zastosowania transformacji kluczowej ................................................................... 240 Klasyczne funkcje C/C++ oraz Java ....................................................................... 240 Funkcje hashujące a klasy Javy ........................................................................................................ 241 Podsumowanie metod transformacji kluczowej ..................................................................... 243 Kup książkęPoleć książkę Sortowanie przez wstawianie, algorytm klasy O(N2) ........................................................... 246 Sortowanie bąbelkowe, algorytm klasy O(N2) ......................................................................... 248 Sortowanie szybkie (Quicksort) — algorytm klasy O(N log N) ....................................... 250 Heapsort — sortowanie przez kopcowanie .............................................................................. 253 Scalanie zbiorów posortowanych .................................................................................................. 256 Sortowanie przez scalanie, algorytm klasy O(N log N) ........................................................ 257 Sortowanie zewnętrzne ...................................................................................................................... 258 Uwagi praktyczne ................................................................................................................................... 262 Jak pracuje kompilator? ...................................................................................................................... 264 Odrobina formalizmu nie zaszkodzi! ............................................................................................ 266 Kilka przykładów derekursywacji algorytmów ...................................................................... 267 Derekursywacja z wykorzystaniem stosu .................................................................................. 271 Eliminacja zmiennych lokalnych ............................................................................ 271 Metoda funkcji przeciwnych ............................................................................................................. 273 Klasyczne schematy derekursywacji ............................................................................................ 275 Schemat typu while ................................................................................................ 276 Schemat typu if-else ............................................................................................... 277 Schemat z podwójnym wywołaniem rekurencyjnym ............................................. 279 Podsumowanie ........................................................................................................................................ 281 Algorytm typu brute force ................................................................................................................. 283 Nowe algorytmy poszukiwań ........................................................................................................... 286 Algorytm KMP ....................................................................................................... 286 Algorytm Boyera-Moore’a ..................................................................................... 290 Algorytm Rabina-Karpa ......................................................................................... 292 Programowanie typu „dziel i zwyciężaj” ..................................................................................... 296 Odszukiwanie minimum i maksimum w tablicy liczb ............................................ 297 Mnożenie macierzy o rozmiarze N×N .................................................................... 300 Mnożenie liczb całkowitych ................................................................................... 302 Inne znane algorytmy „dziel i zwyciężaj” .............................................................. 303 Algorytmy „żarłoczne”, czyli przekąsić coś nadszedł już czas… ...................................... 303 Problem plecakowy, czyli niełatwe jest życie turysty piechura .............................. 304 Wydawanie reszty, czyli „A nie ma pan drobnych?” w praktyce ........................... 307 Programowanie dynamiczne ............................................................................................................ 308 Ciąg Fibonacciego .................................................................................................. 309 Równania z wieloma zmiennymi ........................................................................... 311 Najdłuższa wspólna podsekwencja ......................................................................... 312 Najdłuższy wspólny podłańcuch ............................................................................ 315 Heurystyczne techniki programowania ...................................................................................... 317 Uwagi bibliograficzne ........................................................................................................................... 319 Definicje i pojęcia podstawowe ....................................................................................................... 323 Etykiety i wartości .................................................................................................. 323 Cykle w grafach ....................................................................................................................................... 325 Sposoby reprezentacji grafów .......................................................................................................... 328 Reprezentacja tablicowa ......................................................................................... 328 Słowniki węzłów .................................................................................................... 330 Kup książkęPoleć książkę Listy kontra zbiory ................................................................................................. 331 Podstawowe operacje na grafach ................................................................................................... 332 Suma grafów .......................................................................................................... 332 Kompozycja grafów ............................................................................................... 332 Graf do potęgi ......................................................................................................... 333 Algorytm Roya-Warshalla .................................................................................................................. 334 Algorytm Floyda-Warshalla .............................................................................................................. 339 Algorytm Dijkstry ................................................................................................................................... 342 Algorytm Bellmana-Forda .................................................................................................................. 343 Drzewo rozpinające minimalne ....................................................................................................... 344 Algorytm Kruskala ................................................................................................. 344 Algorytm Prima ...................................................................................................... 345 Przeszukiwanie grafów ....................................................................................................................... 346 Strategia „w głąb” (przeszukiwanie zstępujące) ..................................................... 346 Strategia „wszerz” .................................................................................................. 348 Inne strategie przeszukiwania ................................................................................. 350 Problem właściwego doboru ............................................................................................................ 351 Podsumowanie ........................................................................................................................................ 355 Zadania ........................................................................................................................................................ 355 Poszukiwanie miejsc zerowych funkcji ....................................................................................... 358 Iteracyjne obliczanie wartości funkcji ......................................................................................... 359 Interpolacja funkcji metodą Lagrange’a ...................................................................................... 360 Różniczkowanie funkcji ...................................................................................................................... 362 Całkowanie funkcji metodą Simpsona ......................................................................................... 363 Rozwiązywanie układów równań liniowych metodą Gaussa .............................................. 364 Biblioteki naukowe dla Javy .............................................................................................................. 367 Uwagi końcowe ....................................................................................................................................... 367 Kodowanie danych i arytmetyka dużych liczb ......................................................................... 371 Metody prymitywne ............................................................................................... 372 Kodowanie symetryczne ........................................................................................ 373 Kodowanie asymetryczne ....................................................................................... 374 Obliczenia na bardzo dużych liczbach całkowitych ............................................... 376 Klasa BigInteger ..................................................................................................... 380 Łamanie kodów ....................................................................................................................................... 381 Jakość klucza szyfrującego ..................................................................................... 381 Metody łamania szyfrów ........................................................................................ 381 Techniki kompresji danych ............................................................................................................... 382 Kompresja za pomocą modelowania matematycznego .......................................... 383 Kompresja metodą RLE ......................................................................................... 384 Kompresja danych metodą Huffmana .................................................................... 385 Kodowanie LZW .................................................................................................... 390 Przegląd obszarów zainteresowań sztucznej inteligencji (SI) ......................................... 398 Systemy eksperckie ................................................................................................ 399 Sieci neuronowe ..................................................................................................... 401 Reprezentacja problemów ................................................................................................................. 402 Gry dwuosobowe i drzewa gier ....................................................................................................... 405 Algorytm min-max ................................................................................................. 407 Kup książkęPoleć książkę Teksty zadań ............................................................................................................................................. 415 Rozwiązania .............................................................................................................................................. 417 Instalacja środowiska Java ................................................................................................................. 422 Środowiska IDE do Javy ...................................................................................................................... 423 Konfiguracja środowiska Java .......................................................................................................... 425 Systemy pochodne UNIX (np. Linux) .................................................................... 425 System Windows .................................................................................................... 425 Kompilujemy program w Javie ........................................................................................................ 426 Pakiety w Javie ......................................................................................................................................... 427 Poznaj Javę w 5 minut! ......................................................................................................................... 430 Elementy języka Java na przykładach .................................................................... 431 Sterowanie przebiegiem programu ......................................................................... 432 Konwersje typów i wprowadzanie danych ............................................................. 433 Operacje na plikach w Javie ................................................................................... 435 Funkcje matematyczne w Javie .............................................................................. 437 Kup książkęPoleć książkę Przeszukiwanie tekstów traktuje się jako odrębną dziedzinę z uwagi na szeroką gamę zasto- sowań praktycznych. Tekst jest tutaj definiowany jako ciąg znaków w sensie informatycznym (nie zawsze będzie to miało cokolwiek wspólnego z ludzką „pisaniną”!) i może być ciągiem bitów, który oczywiście można interpretować za pomocą umownych kodów (np. ASCII , Unicode) jako jednostki leksykalne mające określone znaczenie dla czytelnika. Wszystko jest zresztą kwestią umowy, w szczególności ciąg bitów może reprezentować… pamięć ekranu (patrz rozdział 2.). Okazuje się wszelako, że przyjęcie konwencji dotyczących interpretowania informacji uła- twia wiele operacji na niej. Dlatego też pozostańmy przy ogólnikowym stwierdzeniu „tekst”, wiedząc, że za tym określeniem może się kryć sporo znaczeń. Określenie brute force w przypadku algorytmów zazwyczaj tłumaczymy: „na siłę” lub „siłowy”, a jeden z moich znajomych pomysłowo przełożył całość jako „metodę mastodonta”, co dosko- nale odzwierciedla jej nieco „bezmyślny” charakter. Zadaniem, które będziemy usiłowali wspólnie rozwiązać, jest poszukiwanie wzorca w o dłu- gości M znaków w tekście t o długości N (ang. pattern matching). Z łatwością możemy zapro- ponować dość oczywisty algorytm rozwiązujący to zadanie, a bazować będziemy na pomy- słach symbolicznie przedstawionych na rysunku 13.1. Algorytm typu brute force przeszukiwania tekstu Zarezerwujmy indeksy j i i do poruszania się odpowiednio we wzorcu i w tekście podczas 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 stwier- dzeniu tego faktu przesuwamy się zarówno we wzorcu, jak i w tekście o jedną pozycję do przodu (i++; j++). Kup książkęPoleć książkę Cóż jednak powinno się stać z indeksami i oraz j podczas stwierdzenia niezgodności zna- ków? W takiej sytuacji całe poszukiwanie kończy się porażką, co zmusza do anulowania „sza- rej strefy” zgodności. Czynimy to poprzez cofnięcie się w tekście o to, co było zgodne, czyli o j-1 znaków, wyzerowując przy okazji j. Omówię jeszcze moment stwierdzenia całkowi- tej zgodności wzorca z tekstem. Kiedy to nastąpi? Otóż nietrudno zauważyć, że podczas stwierdzenia zgodności ostatniego znaku j powinno się zrównać z M. Możemy wówczas łatwo odtworzyć pozycję, od której wzorzec startuje w badanym tekście: będzie to oczywiście i-M. Tłumacząc powyższe sytuacje na instrukcje Javy, możemy łatwo dojść do nas tępującej procedury: class SzukajTxt{ public static int szukaj(char t[], char w[]) { // szukaj wzorca w w tablicy znaków t int i=0,j=0; int M=w.length, N=t.length; 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; // nie znaleziono wzorca } public static void main(String[] args) { char t[]= { a , b , r , a , k , a , d , a , b , r , a }; // jawna tablica // znaków String tS = new String(t); // tablica znaków skonwertowana na String char w1[]= { r , a , k , i }; // wzorzec 1 char w2[]= { r , a , k }; String w1S = new String(w1); // wzorzec 1 jako String String w2S = new String(w2); System.out.printf( Szukam [ s] w [ s], wynik (pozycja): d\n , w1S, tS, szukaj (t, w1) ); System.out.printf( Szukam [ s] w [ s], wynik (pozycja): d\n , w2S, tS, szukaj (t, w2) ); } } Wynik uruchomienia programu jest następujący: Szukam [raki] w [abrakadabra], wynik (pozycja): -1 Szukam [rak] w [abrakadabra], wynik (pozycja): 2 Jako wynik funkcji zwracana jest pozycja w tekście, od której zaczyna się wzorzec, lub -1, gdy poszukiwany tekst nie został odnaleziony — to znana już doskonale konwencja. Program można też nieznacznie zmodyfikować, aby wyszukiwał wszystkie wystąpienia wzo rca w tekście — wystarczy w takim przypadku wypisać odnaleziony indeks i kontynuować pętlę aż do osiągnięcia końca tekstu. Kup książkęPoleć książkę  szukaj (t, w2)! String t.charAt(i) t[i] String tS.indexOf(w2S) i t Przypatrzmy się teraz dokładniej przykładowi poszukiwania wzorca 10100 w pewnym tek- ście binarnym (rysunek 13.2). Rysunek jest nieco uproszczony: w istocie poziome przesuwanie się wzorca oznacza instruk- cje zaznaczone na listingu SzukajTxt.java jako (*), natomiast cała szara strefa o długości k oznacza k-krotne wykonanie (**). Na podstawie zobrazowanego przykładu możemy podjąć próbę wymyślenia takiego naj- gorszego tekstu i wzorca, 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ą (umawiamy się, że zera i jedynki symbolizują tu dwa różne znaki). „Fałszywe starty” podczas poszukiwania Spróbujmy obliczyć klasę tego algorytmu dla opisanego przed chwilą ekstremalnego naj- gorszego przypadku. Obliczenie nie należy do skomplikowanych czynności: przy założeniu, że restart algorytmu będzie konieczny (N-1)-(M-2)=N-M+1 razy i że podczas każdego cyklu konieczne jest wykonanie M porównań, otrzymujemy natychmiast M(N-M+1), czyli ok.1 MN. 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 tekstó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 wystarczająco atrakcyjnym, by dać się zamęczyć jego powolnym działaniem. 1 Zwykle M będzie znacznie mniejsze niż N. Kup książkęPoleć książkę Algorytm, o którym będzie mowa w tym rozdziale, posiada ciekawą historię, którą w formie anegdoty warto przytoczyć. Otóż w roku 1970 Stephen Arthur Cook udowodnił teoretyczny rezultat dotyczą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 najgor- szym przypadku. Rezultat pracy Cooka wcale nie był przewidziany do praktycznych celów, niemniej Donald Knuth i Vaughan Ronald Pratt otrzymali na jego podstawie algorytm, który można już było zaimplementować w komputerze — ukazując przy okazji, że pomiędzy praktycznymi realizacjami a rozważaniami teoretycznymi nie istnieje wcale aż tak ogromna przepaść, jak by się mogło wydawać. W tym samym czasie James Morris odkrył dokładnie ten sam algorytm jako rozwiązanie problemu, który napotkał podczas praktycznej imple- mentacji edytora tekstu. Algorytm KMP — bo tak będziemy go dalej zwali — jest jednym z przykładów dość częstych w nauce odkryć równoległych: z jakichś niewiadomych powo- dó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 jakieś metafizyczne hipotezy? Knuth, Morris i Pratt opublikowali swój algorytm dopiero w 1976 r. Tymczasem pojawił się kolejny „cudowny” algorytm, tym razem autorstwa Roberta Boyera i J Strothera Moore’a, który okazał się w pewnych zastosowaniach znacznie szybszy od algorytmu KMP. Został on także równolegle wynaleziony (odkryty?) przez Billa Gospera. Oba te algorytmy są jednak dość trudne do zrozumienia bez pogłębionej analizy, co utrudniło ich rozpropagowanie. W roku 1980 Richard Karp i Michael 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 M+N — jest ideowo zbliżony do poznanego już algorytmu typu brute force. Na dodatek jest to algorytm, który można względnie łatwo uogólnić na przypadek poszukiwania w tablicach dwuwymiarowych, co sprawia, że jest potencjalnie użyteczny w obróbce obrazów. W następnych trzech punktach szczegółowo omówię algorytmy wspomniane w tym histo- rycznym przeglądzie. Wadą algorytmu brute force jest jego uwrażliwienie na konfigurację danych: fałszywe restarty są tu bardzo kosztowne; w analizie tekstu cofamy się o całą długość wzorca, zapominając po drodze o wszystkim, co przetestowaliśmy do tej pory. Narzuca się tu niejako chęć sko- rzystania 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 tekstu możliwe jest ulepszenie algorytmu. Jeśli przykładowo wiemy na pewno, że w poszukiwa- nym wzorcu pierwszy znak w ogóle się nie pojawia2, to w razie restartu nie musimy cofać wskaźnika i o j-1 pozycji, jak to było poprzednio (patrz listing SzukajTxt.java). W tym przy- padku możemy po prostu inkrementować i, wiedząc, że ewentualne powtórzenie poszu- kiwań na pewno nic by nie dało. Owszem, można się łatwo zgodzić z twierdzeniem, że tak wyspecjalizowane teksty zdarzają się relatywnie rzadko, jednak powyższy przykład ukazuje, iż ewentualne manipulacje algorytmami poszukiwań są ciągle możliwe — wystarczy się tylko rozejrzeć. Idea algorytmu KMP polega na wstępnym zbadaniu wzorca w celu oblicze- nia liczby pozycji, o które należy cofnąć wskaźnik i w przypadku stwierdzenia niezgodności 2 Przykład: „ABBBBBBB” — znak „A” wystąpił tylko jeden raz. Kup książkęPoleć książkę  badanego tekstu ze wzorcem. Oczywiście można również rozumować w kategoriach przesu- wania 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 inteli- gentniej niż w poprzednim algorytmie. W przypadku zauważenia niezgodności na pewnej pozycji j wzorca3 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 13.3. Wyszukiwanie optymalnego przesunięcia w algorytmie KMP Moment niezgodności został zaznaczony poprzez narysowanie przerywanej pionowej kre- ski. 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 jest umieszczony powyżej wzorca. W pewnym momencie może się okazać, że następuje pokrycie obu tych części. Zatrzymujemy wówczas przesuwanie i kontynuujemy testowanie (znak po znaku) zgodności obu części znajdujących się za pionową kreską. 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 był, jest ukryta w stwierdzeniu „j-1 znaków było zgodnych” — w tym sensie można zupełnie o badanym tekście zapomnieć i analizując wyłącznie wzorzec, odkryć poszukiwane optymalne przesunięcie. Na tym właśnie spostrzeżeniu opiera się idea algo- rytmu KMP. Okazuje się, że badając samą strukturę wzorca, można obliczyć, jak powinniśmy zmodyfikować indeks j w razie stwierdzenia niezgodności tekstu ze wzorcem na j-tej pozycji. Zanim zagłębimy się w wyjaśnienia na temat obliczania tych przesunięć, popatrzmy na efekt ich działania na kilku kolejnych przykładach. Na rysunku 13.4 możemy dostrzec, że na siódmej pozycji wzorca4 (którym jest dość abstrakcyjny ciąg 12341234) została stwierdzona niezgodność. Przesuwanie się wzorca w algorytmie KMP (1) Jeśli zostawimy indeks i w spokoju, to modyfikując wyłącznie j, możemy bez problemu kontynuować przeszukiwanie. Jakie jest optymalne przesunięcie wzorca? Przesuwając go wolno w prawo (rysunek 13.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 13.5. 3 Lub i w przypadku badanego tekstu. 4 Licząc indeksy tablicy tradycyjnie od zera. Kup książkęPoleć książkę Przesuwanie się wzorca w algorytmie KMP (2) Tym razem niezgodność wystąpiła na pozycji j=3. Wykonując podobnie jak poprzednio przesuwanie wzorca w prawo, zauważamy, że 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 i. Dla algorytmu KMP konieczne okazuje się wprowadzenie tablicy przesunięć int shift[M], gdzie M jest długością wzorca. Sposób jej zastosowania będzie następujący: jeśli na pozycji j wystąpiła niezgodność znaków, kolejną wartością j będzie shift[j]. Nie wnikając chwi- lowo w sposób inicjowania tej tablicy (odmiennej oczywiście dla każdego wzorca), możemy natychmiast podać algorytm KMP, który w konstrukcji jest niemal dokładną kopią algo- rytmu typu brute force: class KMP{ public static int kmp(String w, String t, int shift[]) { int i,j; int N = t.length(); int M = shift.length; for(i=0,j=0; (i N) (j M); i++,j++) while( (j =0) (t.charAt(i)!=w.charAt(j)) ) j=shift[j]; if (j==M) return i-M; else return -1; } public static void main(String[] args) { String t = new String( abcd1010efg ); String w1 = new String( 1010 ); String w2 = new String( 1011 ); int shift1[]= new int[ w1.length() ]; init_shifts(w1, shift1); System.out.printf( Szukam [ s] w [ s], wynik (pozycja): d\n , w1, t, kmp (w1,t,shift1) ); int shift2[]= new int[ w2.length() ]; init_shifts(w2, shift2); System.out.printf( Szukam [ s] w [ s], wynik (pozycja): d\n , w2, t, kmp (w2,t,shift2) ); } } Wynik uruchomienia programu jest następujący: Szukam [1010] w [abcd1010efg], wynik (pozycja): 4 Szukam [1011] w [abcd1010efg], wynik (pozycja): -1 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 Kup książkęPoleć książkę  powodu chcemy, aby indeks j pozostał niezmieniony, przy jednoczesnej progresji indeksu i. Jest to możliwe do uzyskania, jeśli umówimy się, że shift[0] zostanie zainicjowany war- tością -1. Wówczas podczas kolejnej iteracji pętli for nastąpi inkrementacja i oraz j, co wyzeruje j. Pozostaje do omówienia sposób konstrukcji tablicy shift[M]. Jej obliczenie powinno nastą- pić przed wywołaniem funkcji kmp, co sugeruje, że w przypadku wielokrotnego poszuki- wania tego samego wzorca nie musimy już powtarzać inicjacji tej tablicy. Funkcja inicjująca tablicę jest przewrotna — jest ona niemal identyczna z kmp, z tą tylko różnicą, że algorytm sprawdza zgodność wzorca… z nim samym! public static void init_shifts(String w, int shift[]) { int i,j; int M = shift.length; shift[0]=-1; for(i=0,j=-1; i M-1; i++, j++, shift[i]=j ) while( (j =0) ( w.charAt(i)!=w.charAt(j) ) ) j=shift[j]; } Sens tego algorytmu jest następujący: tuż po inkrementacji i oraz j wiemy, że pierwsze j znaków wzorca jest zgodne ze znakami na pozycjach p[i-j-1] ... p[i-1] (ostatnie j pozycji w pierwszych i znakach wzorca). Ponieważ jest to największe j spełniające powyższy waru- nek, zatem aby nie ominąć potencjalnego miejsca wykrycia wzorca w tekście, należy usta- wić shift[i] na j. Popatrzmy, jaki będzie efekt zadziałania funkcji init_shifts na słowie ananas (rysunek 13.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 z rysunkiem 13.5). Przypomnijmy jeszcze, że tablica shift zawiera nową wartość dla indeksu j, który prze- mieszcza się po wzorcu. Optymalne przesunięcia wzorca „ananas” w algorytmie KMP Algorytm KMP działa w czasie proporcjonalnym do M+N w najgorszym przypadku. Naj- wię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 KMP będzie zatem słabo zauważ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 i w funkcji kmp nigdy nie jest dekrementowany, co oznacza, że plik można przeglądać od początku do końca bez Kup książkęPoleć książkę 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 wykony- wanych operacji nie pozwala na cofnięcie się w tej czynności (i w odczytywanym na bie- żąco pliku). Kolejny algorytm, który omówię, jest ideowo znacznie prostszy do zrozumienia niż algo- rytm KMP. W przeciwieństwie do metody KMP porównywaniu ulega ostatni znak wzorca. To niekonwencjonalne podejście ma kilka istotnych zalet:  Jeśli podczas porównywania okaże się, że rozpatrywany aktualnie znak nie wchodzi w ogóle w skład wzorca, możemy „skoczyć” w analizie tekstu o całą długość wzorca do przodu! Ciężar algorytmu przesunął się zatem 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 1 — porównaj z metodą KMP! Zanim przejdę do szczegółowej prezentacji kodu, omówię na przykładzie jego działanie. Spójrzmy w tym celu na rysunek 13.7, gdzie przedstawione zostało poszukiwanie ciągu zna- ków „lek” w tekście „Z pamiętnika młodej lekarki”5. Przeszukiwanie tekstu metodą Boyera-Moore a Pierwsze pięć porównań trafia na litery p, i, n, a i ł, które we wzorcu nie występują! Za każdym razem możemy zatem przeskoczyć w tekście o trzy znaki do przodu (długość wzorca). Porównanie szóste trafia jednak na literę e, która w słowie „lek” występuje. Algorytm wów- czas przesuwa wzorzec o tyle pozycji do przodu, aby litery e nałożyły się na siebie, i porów- nywanie jest kontynuowane. Następnie okazuje się, że litera j nie występuje we wzorcu — mamy zatem prawo przesunąć się o kolejne trzy znaki do przodu. W tym momencie trafiamy już na poszukiwane słowo, co następuje po jednokrotnym przesunięciu wzorca, tak aby pokryły się litery k. Algorytm jest — jak widać — klarowny, prosty i szybki. Jego realizacja także nie jest zbyt skomplikowana. Podobnie jak w metodzie poprzedniej, także tu musimy dysponować tablicą pomocniczą zapisującą stan bieżących niezgodności. Tablica ta powinna mieć tyle pozycji, ile jest znaków w alfabecie. 5 Tytuł kultowego cyklu skeczy radiowych autorstwa Ewy Szumańskiej (1921 – 2011). Kup książkęPoleć książkę  Jedną z możliwych wersji algorytmu przedstawiam poniżej (nazwy parametrów i kluczo- wych zmiennych są identyczne jak w KMP, co powinno ułatwić analizę kodu). Zacznijmy od tablicy inicjalizacji przesunięć: class BM{ static int MAX = 256; // liczba znaków alfabetu (pomijamy polskie znaki) static void init_shifts(String w, int shift[]) { int i; for (i = 0; i MAX; i++) // inicjalizacja shift[i] = -1; // zapiszmy ostatnie wystąpienie każdego możliwego znaku wzorca w tablicy o rozmiarze równym // rozmiarowi alfabetu. Przy braku znaku w tablicy umożliwi nam to przesunięcie o całą długość // wzorca! for (i = 0; i w.length(); i++) shift[ (int) w.charAt(i) ] = i; } char int Teraz przejdziemy do prezentacji listingu algorytmu z przykładem wywołania: static void bm(String t, String w) { int N = t.length(); int M = w.length(); int shift[] = new int[MAX]; init_shifts(w, shift); // inicjalizacja tablicy przesunięć dla wzorca w int przes = 0; // aktualne przesunięcie wzorca w względem tekstu while(przes = (N -M)) { // sytuacja, gdy wzorzec będzie znajdował się na samym końcu int j = M-1; // przesuwanie indeksu j (pozycja dopasowania), gdy porównywane znaki są równe: while(j = 0 w.charAt(j) == t.charAt(przes+j)) j--; // przesuwanie wzorca tak, aby kolejny znak zrównał się z ostatnim swoim wystąpieniem we wzorcu: if (j 0) { System.out.println( Znalazłem dopasowanie na pozycji: + przes); przes += (przes+M N)? M-shift[t.charAt(przes+M)] : 1; } else // przesuwanie do ostatniej niezgodności z uwzględnieniem możliwego końca tekstu przes += max(1, j - shift[t.charAt(przes+j)]); } } public static void main(String []args) { String t = Z pamietnika mlodej lekarki podajacej w tym momencie pacjentowi nowe  lekarstwo ; String w = lek ; System.out.println(t); bm(t, w); // program znajdzie dopasowanie na pozycjach: 20 i 69 } } Kup książkęPoleć książkę Algorytm Boyera-Moore’a, podobnie jak KMP, jest klasy M+N, jednak jest o tyle od niego lepszy, że w przypadku krótkich wzorców i długiego alfabetu kończy się po ok. M/N porów- naniach. W celu obliczenia optymalnych przesunięć6 autorzy algorytmu proponują połą- czenie powyższego algorytmu z zaproponowanym przez Knutha, Morrisa i Pratta. Celo- wość tego zabiegu wydaje się jednak wątpliwa, gdyż optymalizując sam algorytm, można bardzo łatwo sprawić, że proces prekompilacji wzorca stanie się zbyt czasochłonny. Ostatni algorytm do przeszukiwania tekstów, który przeanalizuję, wymaga znajomości rozdziału 10. i terminologii transformacji kluczowej, która została w nim przedstawiona. Algorytm Rabina-Karpa polega na dość przewrotnej idei:  Wzorzec w (do odszukania) jest kluczem o długości M znaków, charakteryzującym się pewną wartością wybranej przez nas funkcji H. Możemy zatem obliczyć jednokrotnie Hw=H(w) i korzystać z tego wyliczenia w sposób ciągły.  Tekst wejściowy t (do przeszukania) może być odczytywany w taki sposób, aby na bieżąco znać M ostatnich znaków7. Z tych M znaków wyliczamy na bieżąco Ht=H(t). Gdy założymy jednoznaczność wybranej funkcji H, sprawdzenie zgodności wzorca z aktu- alnie badanym fragmentem tekstu sprowadza się do odpowiedzi na pytanie: czy Hw jest równe Ht? Jeśli jesteś spostrzegawczy, masz prawo pokręcić w tym miejscu z powątpiewa- niem głową i stwierdzić, że przecież to nie ma prawa działać szybko! Istotnie pomysł wyli- czenia dodatkowo funkcji H dla każdego słowa wejściowego o długości M wydaje się tak samo kosztowny — jeśli nie bardziej — jak zwykłe sprawdzanie tekstu znak po znaku (np. stosując algorytm siłowy typu brute force). Tym bardziej, że do tej pory nie powiedziałem ani słowa na temat funkcji H! W rozdziale 10. mogliśmy się przekonać, że jej wybór wcale nie jest taki oczywisty. Omawiany algorytm jednak istnieje i na dodatek działa szybko! Aby zatem to wszystko, co poprzednio zostało napisane, logicznie się łączyło, potrzebny będzie jakiś trik. Sztuka polega na właściwym wyborze funkcji H. Robin i Karp wybrali taką funkcję, która dzięki swym szczególnym właściwościom umożliwia dynamiczne wykorzystywanie wyników obliczeń wykonanych krok wcześniej, co znacząco może 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 liczbę wszystkich możliwych znaków, otrzymamy:
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Algorytmy, struktury danych i techniki programowania dla programistów Java
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ą: