(zadanie nieobowiązkowe)
Zadanie to jest dedykowane osobom pragnącym szczegółowo zapoznać się z zagadnieniem przeszukiwania tekstów (string searching), istniejącymi podejściami, opublikowanymi algorytmami realizującymi te podejścia, ich wymaganiami (wymagania czasowe i pamięciowe pracy algorytmu, dodatkowe wymagania przetwarzania wstępnego wzorca lub tekstu), oraz praktycznymi aspektami ich implementacji oraz wykorzystania w zastosowaniach praktycznych. Zadanie wymaga podejścia badawczego, i połączenia zdolności analizy teoretycznej i syntetycznego przedstawienia pozyskanej wiedzy, z umiejętnościami programistycznymi, oraz umiejętnością przeprowadzenia eksperymentalnych badań praktycznych.
Zadaniem jest teoretyczne oraz praktyczne zapoznanie się z algorytmami wyszukiwania tekstów [1]. Należy uwzględnić co najmniej algorytmy: naiwny, Rabin-Karp, oraz co najmniej jeden z algorytmów opartych na wstępnym przetwarzaniu wzorca, takich jak: Knuth-Morris-Pratt i/lub Boyer-Moore, a także co najmniej jeden z algorytmów opartych na indeksowaniu tekstu, takich jak: budowa drzewa końcówek lub tablicy końcówek (np. BDM lub jego warianty).
Dodatkowo należy uwzględnić następujące rozszerzenia/ograniczenia podstawowego algorytmu:
Należy rozważyć modyfikacje poszczególnych algorytmów konieczne dla uwzględnienia tych rozszerzeń.
Zadanie projektowe obejmuje:
Wynikiem projektu powinien być raport zawierający opis wszystkich uzyskanych wyników teoretycznych i praktycznych, oraz pakiet uruchomieniowy, pozwalający odtworzyć opisane w raporcie wyniki i pomiary.
Uwaga: nie jest wymagane samodzielne zaimplementowanie wszystkich algorytmów od podstaw. Można korzystać z opublikowanych implementacji wzorcowych, oraz/lub dostępnych bibliotek, pod warunkiem pełnej znajomości zawartej w danej bibliotece implementacji danego algorytmu i jej własności.
Podobnie, można wykorzystać istniejące i dostępne zbiory danych (tekstów). Jednak co najmniej część przedstawionych eksperymentów należy obmyśleć samodzielnie, a nie tylko powielać przykłady opublikowane w literaturze.
Oczywiście, w raporcie należy podać kompletne źródła wszystkich wykorzystanych zasobów. Linki do zasobów internetowych proszę podać w raporcie w pełnym brzmieniu, np: https://kcir.pwr.edu.pl/~witold/pamsi/Proj4_wymagania.html, a nie tylko jako aktywny link, np: Tutaj, aby przy czytaniu raportu (np. wydrukowanego na papierze) link był w pełni czytelny.
To zadanie nie stanowi możliwości zyskania dodatkowych punktów dla poprawienia oceny z przedmiotu. Akceptowane będą tylko projekty najwyższej klasy, wyróżniające się głębokością ujęcia, dojrzałością analizy, i starannością opracowania całości, wykraczające poza standardowy program i wymagania przedmiotu. Tak ocenione zadanie nr 4 pozwoli na otrzymanie końcowej oceny z projektu 5.5 (celującej), pod warunkiem uzyskania sumarycznej oceny z wszystkich obowiązkowych zadań projektowych oceny 4.5 lub wyższej.
W ocenie tego zadania liczyć się będzie zarówno ocena raportu: jego poprawności, głębokości merytorycznego ujęcia, kompletności przedstawionych wyników, oraz staranności opracowania, jak i ocena przeprowadzonych badań praktycznych: wykorzystanych algorytmów/programów, oraz ocena opracowanego zestawu eksperymentów porównawczych, dokonanych pomiarów i przygotowanych zbiorów danych. Obie części przedstawionych wyników zadania muszą być ocenione jako celujące.
Th.H.Cormen, Ch.E.Leiserson, R.L.Rivest, C.Stein: Introduction to Algorithms, (4th ed.), MIT Press and McGraw-Hill, 2020