Fulltextové systémy

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra softwarového inženýrství

Anotace:

Předmět se zabývá problematikou vyhledávání v nestrukturovaných datech, dále metodami komprese nad velkými objemy dat.

Požadavky:

Osnova přednášek:

Předmět Fulltextové systémy se zabývá problematikou počítačového zpracování volných textů, kde textem rozumíme posloupnost po sobě jdoucích symbolů z nějaké abecedy. Zabýváme se problematikou vyhledávání v textech. Kromě elementárního algoritmu projdeme algoritmy pro sousměrné i protisměrné vyhledávání, tedy algoritmy charakteristické předzpracováním vzorku. Ukážeme si také principy vyhledávání založené na předzpracování textu dokumentu, konkrétně indexové a signaturové metody. Druhou oblastí je komprese dat, principy kódování. Zabývat se budeme nejen Huffmanovým stromem či Shannon-Fanovo kódováním. Třetím blokem je problematika kontroly správnosti textu, kde si ukážeme řešení pomocí slovníků.

Osnova cvičení:

1. Úvod do textových informačních systémů, základní triviální algoritmus vyhledávání

2. Vyhledávací metody s použitím vzorku: KMP, AC,

3. Vyhledávací metody s použitím vzorku: BM, CW, konečný automat

4. Indexové metody vyhledávání

5. Využití metod signatur

6. Metody komprese dat, metody kódování dat: binární kódování, Fibonacciho kódování

7. Metody komprese dat, metody kódování dat: Eliasův kód, další metody pro kódování dat

8. Metody založené na k-arním stromu: kódování Shannon-Fano, kódování dle práce pana Huffmana

9. Metody založené na k-arním stromu: adaptivní dynamické Huffmanovo kódování

10. Metody komprese dat založené na užití adaptabilního slovníku: práce Lempel-Ziv-Welsch - skupina algoritmů LZ77, LZ78, LZW a jejich modifikace a rozšíření - principy

11. Metody komprese dat založené na užití adaptabilního slovníku: LZ77, LZ78, LZW aplikace metod a jejich modifikací

12. Principy získávání dat a jejich správa rozsáhlých indexech vhodných pro vyhledávání

13. Principy distribuovaného počítání pro správu a užití rozsáhlých indexů informací pro vyhledávání a vytěžování

Cíle studia:

Znalosti:

Studenti získají komplexní vhled do problematiky zpracování, správy a vytěžování velkých objemů nestrukturovaných dat.

Schopnosti:

Studenti budou umět využívat znalosti z teorie grafů - zejména pokud jde o stromy. Budou umět využít principy kódování dat.

Studijní materiály:

Povinná literatura:

[1] Melichar, B.: Textové informační systémy, Vydavatelství ČVUT, Praha, 1994.

Doporučená literatura:

[2] Kopecký, M., Pokorný, J., Snášel, V.: Dokumentografické informační systémy, Karolinum, 2005.

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ů: