Efficient Text Pattern Matching

Přednášející:

Jan Holub (gar.)

Cvičící:

Jakub Jaroš

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Students get knowledge of efficient algorithms for text pattern matching. They learn to use so called succinct data structures that are efficient in both access time and memory complexity. They will be able to use the knowledge in design of applications that utilize pattern matching.

Požadavky:

Osnova přednášek:

1. Introduction, basic definitions.

2. Border array and exact pattern matching.

3. Exact pattern matching algorithms.

4. FFT in pattern matching.

5. Text full index: Suffix array.

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

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

8. Succinct data structure: rank & select.

9. Succinct data structure: wavelet tree.

10. FM-Index.

11. Dictionary representation, spell checking.

12. Approximate pattern matching.

13. Pattern matching in bioinformatcs and musicology.

Osnova cvičení:

Cíle studia:

The pattern matching is a key task in most applications. Its importance is increasing with enlargement of the mass of information collected. Efficient algorithms and data structures for pattern matching are therefore crucial in information processing, but also in other fields like security (e.g., intrusion detection, virus scans). This module provides an extensive overview of such algorithms and data structures.

Studijní materiály:

1. Crochemore, C., Rytter, W. ''Jewels of Stringology''. World Scientific Publishing Company, 2003. ISBN 9810248970.

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

Poznámka:

Rozsah=prednasky+proseminare+cviceni2p+1c, Prednasejici: doc. Ing. Jan Holub Ph.D.

Rozvrh na zimní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost T9:347 Holub J. 09:15–10:45 (přednášková par. 1) Dejvice NBFIT učebnamístnost T9:347 Jaroš J. 12:45–14:15 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna
Út
St
Čt
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• System Programming, in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět zaměření)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2010 (VO)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2011 (VO)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2012 (VO)
• System Programming, Presented in English - Version for Students who Enrolled in 2012 (povinný předmět zaměření)