Students will be able to:

Understand pattern matching as a key task in most applications.

Understand efficient algorithms and data structures for pattern matching (not only in information processing, but also in other fields like security - intrusion detection, virus scans).

Have an extensive overview of such algorithms and data structures.

Studenti budou umět:

budou mít znalosti efektivních algoritmů vyhledávání v textových informacích.

pracovat s tzv. zhuštěnými datovými strukturami, které vynikají jak rychlostí přístupu tak úsporou místa v paměti.

uplatnit získané znalosti při návrhu aplikací zabývajících se vyhledáváním v textu.

Pro zı́skánı́ zápočtu je potřeba dostatek bodů ze zápočtových testů. Zkouška se skládá z povinné pı́semné a povinné ústnı́ části.

R: Pokorný J., Dokumentografické informační systémy, Karolinum, 2005, ISBN 80-246-1148-1

R: M.Crochemore, C. Hancart, T. Lecroq: Algorithms on Strings. Cambridge University Press, 2014. ISBN 1107670993

A: Melichar B., Textové informační systémy, Praha, 1994, ISBN 8001012069, 9788001012062

A: W.F. Smyth: Computing Patterns in Strings, Pearson Addison Wesley (UK), 2003, 423 pp. ISBN 0201398397

A: M.Crochemore, W. Rytter: Jewels of Stringology. World Scientific Publishing Company, 2003. ISBN 9810248970

A: G.Navarro, M. Raffinot: Flexible Pattern Matching in Strings. Cambridge University Press, 2008. ISBN 0521039932

Z: Pokorný J., Dokumentografické informační systémy, Karolinum, 2005, ISBN 80-246-1148-1

Z: M.Crochemore, C. Hancart, T. Lecroq: Algorithms on Strings. Cambridge University Press, 2014. ISBN-10: 1107670993

D: Melichar B., Textové informační systémy, Praha, 1994, ISBN 8001012069, 9788001012062

D: W.F. Smyth: Computing Patterns in Strings, Pearson Addison Wesley (UK), 2003, 423 pp. ISBN-10: 0201398397

D: M.Crochemore, W. Rytter: Jewels of Stringology. World Scientific Publishing Company, 2003. ISBN-10: 9810248970

D: G.Navarro, M. Raffinot: Flexible Pattern Matching in Strings. Cambridge University Press, 2008. ISBN-10: 0521039932

1. Introduction, basic definitions, border array.

2. Text full index: Suffix array.

3. Text full index: Suffix tree, LCP construction.

4. Text full index: Factor, suffix automata, on-line construction.

5. Exact pattern matching algorithms.

6. FFT in pattern matching.

7. Succinct data structure: rank & select.

8. Succinct data structure: wavelet tree.

9. FM-Index.

10. Dictionary representation, spell checking.

11. Approximate pattern matching.

12. Pattern matching in bioinformatics and musicology.

13. Pattern matching in bioinformatics and musicology.

1. Úvod, základní definice, border array.

2. Úplné indexování textu: Suffix array.

3. Úplné indexování textu: Suffix tree, konstrukce LCP.

4. Úplné indexování textu: factor, suffix automata, on-line konstrukce.

5. Algoritmy přesného vyhledávání.

6. FFT ve vyhledávání.

7. Succinct data structure: metody rank & select.

8. Succinct data structure: wavelet tree.

9. FM-Index.

10. Reprezentace slovníku, kontrola pravopisu.

11. Přibližné vyhledávání.

12. Vyhledávání v bioinformatice a v muzikologii.

13. Vyhledávání v bioinformatice a v muzikologii.

https://edux.fit.cvut.cz/courses/MI-EVY/

(login necessary)

https://edux.fit.cvut.cz/courses/MI-EVY/

(nutné přihlášení)

Automata and grammars

Automaty a gramatiky