Wyszukiwanie wzorca w tekście (projekt)

Spis treści

Wariant podstawy (na ocenę 3)

Należy zaimplementować dwa algorytmy wyszukiwania wzorca w tekście: naiwny oraz Sunday’a.

Dodatkowo należy opanować (ze zrozumieniem) teorię dotyczącą tych algorytmów (zasady działania, złożoności obliczeniowe czasowe i pamięciowe).

Ocena może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.

Rozszerzenia, na wyższe oceny

Każde z poniższych rozszerzeń umożliwia podwyższenie maksymalnej oceny:

Dodatkowy algorytm wyszukiwania (+1 do oceny)

Zaimplementować dodatkowy algorytm wyszukiwania wzorca (i ze zrozumieniem opanować dotyczącą go teorię), np. (Knutha-)Morisa-Pratta, Karpa-Rabina, Boyera-Moore’a.

Wersja algorytmu Sunday’a używająca par liter (+1 do oceny)

Zaimplementować zmodyfikowaną wersję algorytmu Sunday’a używającą par sąsiednich liter z tekstu do obliczania przesunięć. Także używana przez algorytm tablica pomocnicza powinna być zbudowana dla par sąsiednich liter ze wzorca. Szczegóły modyfikacji należy opracować samodzielnie.

Wykresy: porównanie oczekiwanej złożoności czasowej (+1,5 do oceny)

Empiryczne porównać oczekiwaną złożoności czasową zaimplementowanych algorytmów.

Złożoność należy zmierzyć jako liczbę porównań znaków, wykonanych przez algorytm wyszukujący wszystkich wystąpień wzorca W w tekście T (t.j. algorytmy nie kończą pracy po znalezieniu pierwszego wystąpienia W w T).

Zarówno wzorzec W jak i tekst T powinien być wylosowany przy użyciu alfabetu A o zadanej wielkości |A|, np. A = {a, b, c} i |A|=3. Losowanie powinno odbywać się poprzez dołączenie kolejnych liter wybieranych z równym prawdopodobieństwem z A, aż do uzyskania żądanej długości.

Należy sporządzić (co najmniej) 3 wykresy, ilustrujące liczbę porównań znaków w zależności od:

  • długości tekstu |T|,
  • długości wzorca |W|,
  • wielkości alfabetu |A|.

Przy czym zawsze zakładamy, że pozostałe parametry są stałe, np. jak zmienia się |T|, to |W| i |A| są stałe (można narysować po kilka wykresów, dla kilku zestawów stałych dla parametrów).

Na każdym wykresie, na osi X mamy badany, zmienny parametr, zaś na osi Y liczbę porównań znaków. Na każdym wykresie mamy tyle krzywych ile badamy algorytmów, po jednej dla każdego z nich.

Wykresy można narysować zarówno bezpośrednio za pomocą programu (korzystając z bibliotek takich jak np. matplotlib dla języka Python), jak i za pomocą zewnętrznego narzędzia, np. arkusza kalkulacyjnego. W tym drugim przypadku najłatwiej jest zapisać dane pomiarowe do pliku CSV, który następnie można otworzyć w arkuszu.

Dane do wykresu przedstawiającego zależność od |T| można spreparować następującym algorytmem:

  1. Używając alfabetu A (np. A={a, …, z}), wylosuj wzorzec W o zadanej długości (np. 5 znaków).
  2. Utwórz pusty tekst T.
  3. Dodaj na koniec T jeden znak wylosowany z A.
  4. Zmierz liczbę porównań znaków wykonanych przy wyszukiwaniu wszystkich wystąpień W w T przez algorytm naiwny. Zapisz długość T (x=|T|) oraz zmierzoną liczbę porównań (y). Te dwie liczby (x, y) stanowią pojedynczy punkt do wykresu dla algorytmu naiwnego.

    To samo wykonaj dla algorytmu Sunday’a i innych (jeśli zaimplementowano) by otrzymać po jednym punkcie pomiarowym dla każdego z tych algorytmów.

  5. Wrócić do punktu 3, chyba że tekst T jest zbyt długi (np. |T| > 10000).

Dane do wykresu przedstawiającego zależność od |W| można spreparować następującym algorytmem:

  1. Używając alfabetu A (np. A={a, …, z}), wylosuj tekst T o zadanej długości (np. 10000 znaków).
  2. Utwórz pusty wzorzec W.
  3. Dodaj na koniec W jeden znak wylosowany z A.
  4. Zmierz liczbę porównań znaków wykonanych przy wyszukiwaniu wszystkich wystąpień W w T przez algorytm naiwny. Zapisz długość W (x=|W|) oraz zmierzoną liczbę porównań (y). Te dwie liczby (x, y) stanowią pojedynczy punkt do wykresu dla algorytmu naiwnego.

    To samo wykonaj dla algorytmu Sunday’a i innych (jeśli zaimplementowano) by otrzymać po jednym punkcie pomiarowym dla każdego z tych algorytmów.

  5. Wrócić do punktu 3, chyba że wzorzec W jest zbyt długi (np. |W| > 40).

Dane do wykresu przedstawiającego zależność od |A| można spreparować następującym algorytmem: Dla kolejnych wielkości alfabetu |A| od 1 do 20:

  1. Używając alfabetu A o wielkości |A|, wylosuj tekst T (np. o długości 10000) i wzorzec W (np. o długości 10).
  2. Zmierz liczbę porównań znaków wykonanych przy wyszukiwaniu wszystkich wystąpień W w T przez algorytm naiwny. Zapisz wielkość A (x=|A|) oraz zmierzoną liczbę porównań (y). Te dwie liczby (x, y) stanowią pojedynczy punkt do wykresu dla algorytmu naiwnego.

    To samo wykonaj dla algorytmu Sunday’a i innych (jeśli zaimplementowano) by otrzymać po jednym punkcie pomiarowym dla każdego z tych algorytmów.

Przykładowe pytania sprawdzające

  • Zilustrować działanie wskazanego algorytmu (zaimplementowanego w programie) na zadanym przykładzie, np. jak będzie przebiegał algorytm Sunday’a wyszukując wzorca W=“aba” w tekście T=“aabcbcbababa”?
  • Co zawiera pomocnicza tablica algorytmu Sunday’a (lub innego zaimplementowanego)? Jak jest wypełniana? (zilustrować na przykładowych danych)
  • Jaka jest złożoność czasowa wskazanego algorytmu? Wskazać miejsca w kodzie (pętle, rekurencje), które za to opowiadają.
  • Jaka jest złożoność pamięciowa wskazanego algorytmu? Wskazać miejsca w kodzie gdzie alokowana jest pamięć (w jakiej ilości?).
  • (w przypadku wykonania modyfikacji algorytmu Sunday’a używającej par liter) Jakie zalety i wady ma zmodyfikowana wersja algorytmu Sunday’a w stosunku do oryginalnej?
  • (w przypadku sporządzenia wykresów) Jakie wnioski można wyciągnąć ze wskazanego wykresu, np. jak zmienia się liczba porównań znaków wykonanych przez algorytm Sunday’a w zależności od wielkości alfabetu? Postawić hipotezę, dlaczego uzyskano taką zależność?

Powiązane