Fulltext Systems
Code | Completion | Credits | Range |
---|---|---|---|
XD36TIS | Z,ZK | 5 | 14+4s |
- The course is a substitute for:
- Textual Information Systems (D36TIS)
- Lecturer:
- Tutor:
- Supervisor:
- Department of Computer Science and Engineering
- Synopsis:
-
Classification of textual information systems, string searching methods, KMP algorithm, AC algorithm, finite automata (FA), BM and CW algorithms, two-way jumping automata, approximate string searching, index methods, text analysis, thesaurus, signature methods, data compression-models and coding, statistical methods, dictionary methods, spell-checkers, hypertext.
- Requirements:
- Syllabus of lectures:
-
1. Basic notions and a classification of information systems
2. Pattern matching, models of pattern matching algorithms
3. Simulation of non-deterministic FA, dynamic programming and bit-wise parallelism
4. Pattern matching engines, KMP and AC algorithms
5. Backward string matching, BM and CW algorithms
6. Two-way finite automata with jump
7. Factor automata
8. Indexing, text analysis, thesaurus
9. Signature methods
10. Data compression, modeling and coding
11. Statistical methods of data compression
12. Dictionary methods of data compression
13. Syntactical methods of data compression
14. Spell-checking
- Syllabus of tutorials:
-
1. Finite automata - recall
2. Finite automata for string matching
3. Finite automata for sequence matching
4. Simulation of finite automata, dynamic programming
5. Simulation of finite automata, bit parallelism
6. Boyer-Moore algorithm and its variants
7. Two-way automata with jump
8. Factor automata
9. Fulltext system with indexing
10. Index construction
11. Signature methods
12. Data compression, statistical methods
13. Data compression, dictionary methods
14. Models of data for data compression
- Study Objective:
- Study materials:
-
1. M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press,
New York, 1994.
- Note:
- Further information:
- No time-table has been prepared for this course
- The course is a part of the following study plans: