Hauptseminar Automaten und Transduktoren
WS 1998/99

Dozent: H.Leiß

TERMIN:	Di 13-15 Uhr, Raum Z11
Achtung:	Der Termin weicht wegen Überschneidungen vom Termin im grünen Vorlesungsverzeichnis ab!
VORBESPRECHUNG:	in der ersten Semesterwoche, DI, 3.11.98, 13.15 Uhr, Z11

Vorträge

1. Implementierung endlicher Automaten in einer funktionalen Sprache

2. Minimierung deterministischer endlicher Automaten in O(|Sigma|*|Q|*log|Q|)

   J.E.Hopcroft: An n log n algorithm for minimizing states in a finite automaton. In Z.Kohavi and A.Paz (eds) Theory of Machines and Computation, p. 189-196. Academic Press, 1971

   N.Blum: Minimization of finite automata in O(n * log n) ... Information Processing Letters, 1996

3. Aufbau eines kreisfreien Graphen aller Wörter einer sortierten Wortliste:

   B.Alexandrov, S.Mihov: On-line algorithm for building minimal automaton presenting finite language. Preprint, LPDP, Bulgarian Acad.Sci. 1998

4. Konstruktion von Suffix-Tries und Suffix-Bäumen eines Texts in O(|Text|):

   R.Giegerich, S.Kurtz: Suffix trees in the functional programming paradigm. In: D.Sanella (ed): Programming Languages and Systems. ESOP'94 Proceedings. Springer LNCS 788, p. 225-240.

   G.A.Stephen: String searching algorithms. Lecture Notes Series on Computing, Vol 3. World Scientific, London 1994. (Chapter 4, pp.87-110)

   D.Breslauer: The suffix tree of a tree and minimizing sequential transducers. Tech.Report BRICS RS-95-47, Sept. 1995

5. Aufbau des Indexes aller Wörter eines Textes w in O(|w|) Schritten

   A.Blumer, J.Blumer, D.Haussler, A.Ehrenfeucht, M.T.Chen, J.Seiferas: The smallest automaton recognizing the subwords of a text. Theoretical Computer Science 40, p. 31-55., 1985.

6. Minimierung kreisfreier deterministischer Automaten in O(|Q|):

   D.Revuz: Minimization of acyclic deterministic automata in linear time. Theoretical Computer Science 92, p. 181-189. 1992.

7. Minimierung sequentieller Transduktoren:

   M.Mohri: Compact natural language representations by finite state transducers. Proceedings ACL'94.

   M.Mohri: Minimization of sequential transducers. Proc. 5th Symposium on Combinbatorial Pattern Matching. LNCS 807, p. 151-163. Springer 1994.

   D.Breslauer: The suffix tree of a tree and minimizing sequential transducers. Tech.Report BRICS RS-95-47, Univ.Aarhus, Sept. 1995

   D.Maurel, L.Chauvier: Pseudo-minimal transducers: a transducer with proper elements.

   E.Roche: Factorization of finite-state transducers. Mitsubishi Electric Research Labs, Cambridge, Mass. 1995.

8. Anwendungen von Suffix-Baümen auf die Suche in Strings. (Approximate string matching)

9. Darstellung regulärer Sprachen durch umgegekehrte alternierende endliche Automaten.

   K.Salomaa, X.Wu, S.Yu: Efficient Implementation of regular languages using r-AFA. D.Woods, S.Yu (Eds): Automata Implementation. WIA'97 Revised Papers. LNCS 1436, p.176-183. Springer, 1998.

10. Implementierung von Baum-Lexika durch Baum-Tries (statt String-Tries).

    Muss man weitgehend selbst machen.

Begriffe

Trie

Baum, in dem die von einem Knoten ausgehenden Kanten durch paarweise verschiedene Buchstaben markiert sind.

z.B. benutzt in der Suche mit mehreren Mustern zur kompakten Darstellung der Suchmuster. Knoten des Tries entsprechen Zustände des Suchautomaten, Kanten die Übergänge. (Fehlerfunktion für Rücksprünge, wenn im Text ein Symbol auftritt, zu dem der geg.Zustand keinen Übergang hat.)

Suffix-Trie

(oder position tree, non-compact suffix-tree): Die Blätter entsprechen genau den Suffixen eines gegebenen Worts. Dazu darf es keine eingebetteten Suffixe geben, die in einem internen Knoten des Baums enden würden; dazu hängt man ein Endsymbol an das Wort.)

Eingebettetes Suffix: ein Suffix von wa, das Teilwort von w ist.

Beachte: Ein Teilwort v von w ist ein Präfix eines Suffixes von w, wird also durch den Knoten des Suffix-Tries repräsentiert, den man von der Wurzel aus durch Lesen von v erreicht.

Suffix-Tree

kompaktere Darstellung, bei der an den Kanten nicht Buchstaben, sondern Wörter stehen, wobei bei einer Verzweigung die Anfangsbuchstaben der Kantenmarkierungen paarweise verschieden sind. Damit spart man sich nicht-verzweigende Knoten im Baum. Wenn man die Kantenmarkierungen durch Positionen (i,j) im Text darstellt, ist die Darstellung kompakter als ein Suffix-Trie.

Patricia-Baum

Vorform der Suffix-Trees.

Anwendung von Suffix-Bäumen: (Stephen, p.197 ff.)

1. Längstes wiederholtes Teilwort von y in O(|y|):
2. Lägstes gemeinsame Teilwort von zweier Wörter x und y in O(|x|+|y|)
3. Maximale wiederholte Teilswörter
4. Nicht-überlappende wiederholte Teilwörter
5. String-Matching
6. Approximatives String-Matching (z.B. gegen Tippfehler tolerante Suche)

Historie und Eigenschaften von Suffix-Trees

• Morrison (1968): Practical Algorithm To Retrieve Information Coded In Alphanumeric führt PATRICIA-Baüme ein, eine implizite Form der Suffix-Baume
• Weiner (1973): führt die Suffix-Baume als Index ein. Aufbau des Suffix-Baums durch Einfügen von Suffixen; zwischendurch kein Suffix-Baum, aber in Linearzeit. (Naives Verfahren: quadratisch, praktisch oft n*log n)
• Varianten von Suffix-Baumen: Fredkin (1959,1960): Trie-Datenstruktur: Suffix-Tries sind weniger kompakt als Suffix-baume. Aho,Hopcroft,Ullman (1974): Positions-Bäme. Blumer e.a (1984) Complete Inverted File.
• Chen, Seiferas (1985): Vereinfachung von Weiners Aufbau des Suffix-Baums
• McCreight (1976): funktional ähnlich wie Weiner, aber platzsparender
• Majster, Reiser (1980): On-line Aufbau des Suffix-Baums, nicht-linear.
• Ukkonen (1992,1993): On-line Aufbau des Suffix-Baums in Linearzeit und Platz, Umweg über einen Suffix-Trie.
• Giegerich,Kurtz: einfacher funktionaler Algorithmus aus der induktiven Definition eines Suffix-Baums; ergibt effizienteren imperativen Algorithmus als Ukkonens bisher bestes Verfahren.