Počkejte prosím...
Data pro 2018/2019

Efektivní vyhledávání v textech

Kredity 4
Rozsah 2 / 1 / 0
Examinace Z+Zk
Jazyk výuky čeština
Úroveň magisterský předmět
Garant prof. Ing. Jan Holub, Ph.D.

Anotace

Studenti získají znalosti efektivních algoritmů vyhledávání v textových informacích. Naučí se pracovat s tzv. zhuštěnými datovými strukturami, které vynikají jak rychlostí přístupu tak úsporou místa v paměti. Získané znalosti budou schopni uplatnit při návrhu aplikací zabývajících se vyhledáváním v textu.

Sylabus

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.

Literatura

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

VŠCHT Praha
Technická 5
166 28 Praha 6 – Dejvice
IČO: 60461373
DIČ: CZ60461373

Datová schránka: sp4j9ch

Copyright VŠCHT Praha 2014
Za informace odpovídá Oddělení komunikace, technický správce Výpočetní centrum
zobrazit plnou verzi