Textové algoritmy

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

Anotace:

Text je nejjednodušší a přirozená reprezentace informací v různých oblastech. Text je lineární posloupnost symbolů z nějaké abecedy. Manipulace s textem se používá v mnoha aplikačních oblastech: zpracování textu v přirozených a formálních jazycích, studium posloupností v molekulární biologii, analýza hudby atd. Hlavními problémy, kterými se zabývá tento předmět, je vyhledávání vzorků a opakujících se částí textu. V obou případech se jedná jak o přesné vyhledávání, tak o přibližné vyhledávání. Těmto problémům je věnována hlavní pozornost v přednáškách i cvičeních. Hlavním formálním systémem, který je pro popis algoritmů použit, jsou konečné automaty. Ty se ukázaly jako vynikající nástroj nejen pro pochopení, ale i pro řešení mnoha problémů zpracování textu.

Požadavky:

Osnova přednášek:

1. Textové systémy, základní pojmy, klasifikace vyhledávacích problémů.

2. Sousměrné vyhledávání, modely vyhledávacích algoritmů.

3. Nedeterministické vyhledávací automaty.

4. Simulace nedeterministických vyhledávacích automatů, bitový paralelismus, dynamické programování.

5. Prefixové a suffixové automaty.

6. Faktorové automaty, faktor oracle, sufix oracle.

7. Hranice a periody v textu.

8. Repetice v textu, přesné a přibližné.

9. Simulace nedeterministických vyhledávacích automatů, fail funkce, MP a KMP algoritmy.

10. Simulace nedeterministických vyhledávacích algoritmů, fail funkce, AC algoritmus.

11. Protisměrné vyhledávání jednoho vzorku, BM algoritmus.

12. Protisměrné vyhledávání množiny vzorků, CW algoritmus.

13. Aktuální výsledky v oblasti vyhledávání v textu (např. vyhledávání ve vícerozměrném textu).

14. Aktuální výsledky v oblasti vyhledávání v textu (např. vyhledávání v komprimovaném textu).

Osnova cvičení:

1. Konečné automaty, základní operace s konečnými automaty.

2. Formulace základních vyhledávacích problémů pro přesné a přibližné vyhledávání.

3. Nedeterministické konečné automaty jako modely pro vyhledávání v textu.

4. Deterministické vyhledávací automaty a jejich složitost.

5. Simulace vyhledávacích automatů, bitový paralelismus, dynamické programování.

6. Konstrukce prefixových a sufixových automatů.

7. Konstrukce faktorových automatů, faktor a sufix oracle automatů.

8. Hledání hranic a period v textu.

9. Hledání přesných a přibližných repetic v textu.

10. Simulace vyhledávacích automatů, MP a KMP algoritmy.

11. Simulace vyhledávacích algoritmů, AC algoritmus.

12. Protisměrné vyhledávání, BM algoritmus.

13. Protisměrné vyhledávání, CW algoritmus.

14. Zápočet.

Cíle studia:

Studijní materiály:

1. Melichar, B., Holub, J., Polcar, T.: Text searching algorithms. Volume I, II. Učební text pro přednášky.

2. Melichar, B. a kol.: Text searching algorithms. Seminars. Sbírka příkladů pro cvičení.

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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

• Výpočetní technika - systémové programování- strukturované studium (povinný předmět zaměření)