Wykład 18. Algorytmów tekstowych cd.

 Na wykładzie omówiłem następujące zagadnienia:

  • Hasze dla podsłów.
  • KMR i słownik słów bazowych.
  • Struktura danych dla dynamicznych słów z porównywaniem.
  • Proste własności drzew sufiksowych.
  • Zastosowania drzew sufiksowych oraz haszy i KMR-a, tj. problem najdłuższego wspólnego podsłowa oraz tablice SA, revsuf, LCP i LPF.

Na wykładzie nie opowiedziałem o algorytmie konstrukcji drzewa sufiksowego, gdyż i tak nie byłbym w stanie zrobić tego lepiej, niż Esko Ukkonen opisał w swojej pracy (jest ona naprawdę bardzo czytelna), lecz skupiłem się na zastosowaniach drzew sufiksowych i pozostałych struktur danych (hasze, KMR).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3130. Termin: 07.04.2009, 16:15-18:00.

Dostępne materiały: Nagrania.