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.

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.

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

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

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

Z:M.Crochemore, C. Hancart, T. Lecroq: ''Algorithms on Strings''. Cambridge University Press, 2007. ISBN-10: 0521848997

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

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

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

R:M.Crochemore, C. Hancart, T. Lecroq: ''Algorithms on Strings''. Cambridge University Press, 2007. ISBN-10: 0521848997

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.

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.

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

(nutné přihlášení)

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

(login necessary)

Znalosti konečných automatů a složitosti.

Knowledge of finite automata and complexity.