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 do oceny za 3 typy wykresów; albo +0,5 za 2 typy)

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 (tj. 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:

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