A. Aho: Algorithms for finding patterns in strings. In: Handbook of Theoretical Computer Science, Vol. A, Elsevier Science Publishers, 1990, s. 255-300
G. Stephen: String Searching Algorithms. World Scientific Publishing Comp., 1994
M. Crochemore, W. Rytter: Text Algorithms. Oxford University Press, 1994
2-INF-147 Vyhľadávanie v texte
| Odporúčaný ročník: | 1. |
| Semester: | letný |
| Rozsah: | K4 |
| Hodnotenie: | 40/60 |
| Počet kreditov: | 6 |
| Vyučujúci: | prednáša doc. Mgr. Bronislava Brejová PhD. |
| www stránka: | http://compbio.fmph.uniba.sk/vyuka/vvt/ |
| Predmet je v tomto akademickom roku suspendovaný. | |
Cieľ:
Oboznámiť so základnými algoritmami pre vyhľadávanie vzorky (slova) v texte: nájdenie presných a približných výskytov, vyhľadávanie v statickom texte.
Sylabus:
Algoritmy pre nájdenie presných výskytov vzorky:
Knuth-Morris-Pratt, Boyer-Moore-(Horspool), Karp-Rabin, Shift-or, Vishkin, Aho-Corasick, algoritmy založené na DFA/NFA, Baker-Bird.
Približné výskyty vzorky:
editačná vzdialenosť medzi slovami a jej výpočet, približné výskyty vzorky, najdlhšia spoločná podpostupnosť slov (dynamické programovanie, Hunt-Szymanski).
Nájdenie výskytov vzorky v statickom texte:
suffixové stromy, suffixové tabuľky.
Literatúra: