Reguläre Ausdrücke und endliche Automaten

Praktische Techniken, die auf regulären Sprachen basieren – Musterabgleich mit regulären Ausdrücken und String-zu-String-Abbildung mit endlichen Transducern – die Tokenisierung, Normalisierung und morphologische Analyse effizient handhaben.

Definition

Endliche Automaten sind sprachverarbeitende Techniken, bei denen Muster und Abbildungen als reguläre Ausdrücke oder endliche Automaten und Transducer ausgedrückt werden, was eine effiziente Erkennung in linearer Zeit gewährleistet.

Scope

Behandelt reguläre Ausdrücke als Mustersprache über Strings, endliche Automaten und Transducer als deren rechnerische Realisierung sowie deren Anwendung auf Textnormalisierung, Tokenisierung, Rechtschreibung und Computerlinguistik. Es umfasst gewichtete endliche Automaten, die in der Sprachverarbeitung und flachen Verarbeitung verwendet werden. Eine vollständige phonologische Theorie und tiefgehende syntaktische Analyse sind nicht Gegenstand dieses Bereichs.

Core questions

• Wie können reguläre Ausdrücke Textmuster präzise spezifizieren und extrahieren?
• Wie bilden endliche Transducer Oberflächenformen auf lexikalische Analysen ab, wie in der Morphologie?
• Warum werden endliche Automaten für die Tokenisierung und Normalisierung bevorzugt?

Key concepts

• regulärer Ausdruck
• endlicher Transducer
• Tokenisierung
• Textnormalisierung
• morphologische Analyse
• Zwei-Ebenen-Morphologie
• gewichtete Automaten
• Editierdistanz

Key theories

Reguläre Modelle der Morphologie und Phonologie

Das Ergebnis, dass phonologische Umschreibregeln und morphologische Alternationen in endliche Transducer kompiliert werden können, wodurch Analyse und Generierung zu einem einzigen effizienten Rahmenwerk werden.

Äquivalenz von regulären Ausdrücken und endlichen Automaten

Reguläre Ausdrücke, reguläre Grammatiken und endliche Automaten beschreiben alle exakt die regulären Sprachen, sodass ein deklaratives Muster in einen effizienten Erkennungsmechanismus kompiliert werden kann.

History

Reguläre Ausdrücke fanden ihren Weg in die Informatik durch Kleenes Arbeit und wurden in Textwerkzeugen allgegenwärtig. In den 1980er Jahren etablierten Koskenniemis Zwei-Ebenen-Morphologie und Kaplans und Kays Kompilierung phonologischer Regeln in Transducer die Finite-State-Technologie als das „Arbeitspferd“ der morphologischen Verarbeitung, ein Ansatz, der in Beesley und Karttunens Handbuch gefestigt wurde.

Debates

Wie weit können endliche Automaten skaliert werden?

Endliche Automaten sind äußerst effizient, aber auf reguläre Phänomene beschränkt; die Debatte betrifft, welche sprachverarbeitenden Aufgaben am besten durch sie im Vergleich zu reichhaltigeren statistischen oder neuronalen Modellen bedient werden.

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

Warum sollte man einen endlichen Transducer anstelle einer einfachen Nachschlagetabelle für die Morphologie verwenden?

Ein Transducer kodiert systematische Alternationen kompakt und kann Wortformen analysieren oder generieren, die er noch nie gesehen hat, während eine Tabelle nur explizit darin aufgeführte Formen speichert.