Wyszukiwanie wzorca w tekście (algorytmy w Pythonie; projekt)

Wariant podstawy (na ocenę 4 z algorytmów)

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

Rozszerzenia, na wyższe oceny z algorytmów

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.

Wymagania dotyczące programowania

Kod programu powinien być możliwie przejrzysty i czytelny.

Mile widziana jest obsługa całego alfabetu unicode w algorytmie Sunday’a, którą można uzyskać implementując używaną przez algorytm tablicę pomocniczą za pomocą słownika (dict).

Program powinien rysować wykresy umożliwiające empiryczne porównanie oczekiwanej złożoności czasowej zaimplementowanych algorytmów.

Do narysowania wykresów można użyć zewnętrznych bibliotek. Polecam bibliotekę matplotlib i samouczek dostępny na jej stronie domowej.

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.

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 (jako A można użyć kilku pierwszych liter spośród a, …, z):

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

• 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ść?

Przykładowe pytania sprawdzające z programowania

• Wyjaśnić jak działa użyta w programie składnia Pythona albo funkcja.
• Za co odpowiedzialna jest w programie wskazana linia?