Eesti keeles: Tekstialgoritmid I
Inglise keeles: Text algorithms I
Kood: MTAT.03.165

Maht: 2 ap
Loengud ja praktikumid - Jaak Vilo -  vilo at egeen.ee
Toimumine: 2003 kevadsemester
Kolmapäeviti, kell 14-16 ja praktikumid kell 16-18. Liivi tn. L206.


Eksam toimub esmaspäeval, 2. juunil kell 14:00 A405
Eksam on kirjalik, kestab 3 tundi

Eksamiküsimused



Osalenud üliõpilaste kommentaare kursusele.




Loeng: 18 t
Praktikum: 16 t
Iseseisev töö 46 t.

Kursuse käigus tutvustatakse sõnede täpse ja ligikaudse otsimise algoritme, tekstide indekseerimise meetodeid, andmete pakkimise meetodeid, andmetes mustrite tuvastamist, tekstide kaevandamist ja tekstinfo otsinguid.

Hindamine toimub kolme komponendi järgi:

• Iganädalased praktikumid - osalemine ja ülesannete lahendamine
• Programmeerimistöö ja praktiline algoritmivõrdlus
• Eksam

Praktikumid             - 30p  - miinimum 50% kohaleolekut ja 50% lahendatud ülesandeid
Programmeerimistöö      - 20p  - (Teemad)
Eksam                   - 50p
Boonusülesanded		- vastavalt välja pakutud punktide arvule
------------------------------
                         100+ p 

Hindevahemikud nagu ette nähtud - % maksimum 100 punktst.

Loengute ja praktikumide ajad (2003 kevad)

1. 12.2. Täpne otsimine - jõu-, KMP, BM meetodid
2. 5.3. Täpne otsimine - Rabin-Karp, Shift-OR, Aho-Corasick
   19.2. ja 26.2 loengut/praktikumi EI TOIMU
3. 16.3. Regulaaravaldistega otsimine
   19.3 ja 26.3. loengut/praksi EI TOIMU.
4. 2.4. 2-D otsimine ja sõnede teisenduskaugus
5. 9.4. Ligikaudne otsimine
6. 16.4. Staatilistest tekstidest otsimine (sufiksipuud)
7. 23.4. Pakkimismeetodid
   30.4 loengut/praksi EI TOIMU (Volbriöö).
8. 7.5. Information Retrieval, bioinformaatika jmt.
   • Kodused projektid
   • Information Retrieval
   • PWM, HMM, SCFG
9. 14.5. Pattern discovery

Loengukonspekt teemade järgi

• Ainekava
• Praktikumide ülesanded
• Programmeerimisprojekti ülesandepüstitused
• Tarkvara lähtekoodid
• Kirjanduse loetelu
• Veebist saadavad materjalid
• Artiklite kogu(d)

• Teema 1: Täpne otsimine
  • Triviaalne algoritm O(nm)
  • Knuth-Morris-Pratt O(m+n)
  • Boyer-Moore
  • Rabin-Karp
  • Shift-OR
  • Aho-Corasick (mitme sõne otsimine)
  
  
• Teema 2: Regulaaravaldiste otsimine
  • Regulaaravaldised ja lõplikud automaadid
  • Regulaaravaldistest automaatide tegemine (mittedeterministlike ja deterministlike)
  • Deterministlike automaatide sobitamine
  • Mittedeterministlike automaatide sobitamine
  
  
• Teema 2.5: 2-D otsimine
  • 2-D otsimise ülesanne
  
  
• Teema 3: * Sõnede sarnasus ja teisenduskaugus
  • Teisenduskaugus
  • Dünaamiline programmeerimine
  • Diagonaali meetod
  • Aja painutamine - time warping
  • DNA- ja valkude kauguse mõõdud - Smith Waterman jt.
  
  
• Teema 4: Ligikaudne otsimine pikast tekstist
  • Otsimine pikast tekstist
  • q-gram meetodid - "filtreeri ja otsi"
  • Bitiparalleelsus - Shift/OR meetod (ja SHIFT-ADD)
  
  
• Teema 5: * Staatiliste tekstide indekseerimine
  • Sufiksipuu ja -trie
  • Sufiksipuu rakendusi
  • Sufiksiautomaat
  • Sufiksitabel
  • PAT-indeks ja OED projekt
  • Modernsed andmestruktuurid
  
  
• Teema 6: Info-otsimine (Information Retrieval)
  • Tekstinfo otsimine (information retrieval)
  • Tekstide kaevandamine (otsi seoseid tekstidokumentides)
  
  
• Teema 7: * Tekstide pakkimine (vt. datacompression.info)
  • Shannon-Fano ja Huffmani kodeering
  • Aritmeetiline kodeerimine
  • Lempel-Ziv perekond
  • jne.
  
  
• Teema 8: Probabilistlikud motiivid ja grammatikad (PWM, SCFG, HMM)
  • Probabilistlikud motiivid (Position Weight Matrices)
  • Informatsiooni sisaldus
  • Sequence logo
  • PWM otsimine
  • Stohhastilised grammatikad
  • HMM - Hidden Markov Models
  • SCFG - Stochastic Context Free Grammars
  
  
• Teema 9: * Mustrite tuvastamine (Pattern Discovery)
  • Mustrite tuvastamise põhimõisted
  • Erinevad mustrite klassid
  • Gibbs Sampling
  • Expectation Maximization
  
  
• Palindroomid: A Man, a Plan, a Pointless(?) Program

Terminoloogia/sõnastik

String

Sõne, string

Stringology

Stringoloogia (huhhh...)

Edit distance

Teisenduskaugus

Brute-force

Jõumeetod

• Gusfield, Dan: Algorithms on Strings, Trees, and Sequences (Cambridge University Press, 1997)
• A. Aho: Algorithms for finding patterns in strings. In Handbook of Theoretical Computer Science, Vol. A, Elsevier, 1990, 255-300.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L. Introduction to Algorithms (MIT Press 1990), Chapter 34 (String Matching).
• Pevzner, P.A. Computational Molecular Biology - An Algorithmic Approach (MIT Press, 2000)
• Baldi, Pierre, and Brunak, Soren, Bioinformatics - the Machine Learning Approach 2nd edition, (MIT Press, 2001)
• Durbin, R., Eddy, S., Krogh, A., Mitchison - Biological sequence analysis - Probabilistic models of proteins and nucleic acids (Cambridge University Press, 1998)
• Jorma Tarhio, Merkkijonomenetelmät (luentomoniste) ~ 1995 University of Helsinki
• Ricardo Baeza-Yates, Berthier Ribeiro-Neto: Modern Information Retrieval, Addison Wesley

• jt.

• String Search, TR-92-gas-01, by Graham A. Stephen ja kohalikud: [DVI] [Postscript]
• Exact String Matching Algorithms - animations in Java (Christian Charras - Thierry Lecroq)
• HANDBOOK OF COMPUTER SCIENCE AND ENGINEERING Chapter 6 Pattern matching and text compression algorithms [local PDF]
• Text Searching and Processing Maxime Crochemore, Department of Computer Science King's College London. (A lecture course and materials)
• Jesper Larsson - thesis and research on suffix trees [PDF]
• Stefan Kurtz - Foundations of Sequence Analysis [gzipped Postscript]
• Computational Biology - Martin Tompa
• The Algorithm Design Manual The CD-ROM (Steven S. Skiena)
• Finite state automata utilities
• datacompression.info - informatsioon andmete pakkimise kohta

Abiks materjalide kirjutamisel

• Character entity references in HTML 4 (local) (local with entities)
• MathZilla; itex2mathml