Efficient Text Pattern Matching

Garant předmětu:

Jan Holub

Přednášející:

Jan Holub

Cvičící:

Jan Holub

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:

Knowledge of basic data structures, fundamentals of computer programming, and theory of finite automata.

Osnova přednášek:

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. (2) Pattern matching in bioinformatics.

Osnova cvičení:

1. Basic definitions.

2. Text full index

3. Exact pattern matching algorithms.

4. FFT in pattern matching.

5. Succinct data structure

6. FM-Index, approximate pattern matching.

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. Smyth, W. F. : Computing Patterns in Strings. Addison Wesley, 2003. ISBN 0201398397.

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

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

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

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/NI-EVY/

Rozvrh na zimní semestr 2023/2024:

	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 TH:A-s135 Holub J. 09:15–10:45 (přednášková par. 1) Thákurova 7 (budova FSv) As135
Út	místnost TH:A-1242 Holub J. 09:15–10:45 SUDÝ TÝDEN (přednášková par. 1 paralelka 102) Thákurova 7 (budova FSv)
St
Čt
Pá

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

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

• Master specialization Software Engineering, in English, 2021 (volitelný předmět)
• Master specialization Computer Security, in English, 2021 (volitelný předmět)
• Master specialization Computer Systems and Networks, in English, 2021 (volitelný předmět)
• Master specialization Design and Programming of Embedded Systems, in English, 2021 (volitelný předmět)
• Master specialization Computer Science, in English, 2021 (PS, volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Master Specialization Digital Business Engineering, 2023 (volitelný předmět)