Finite-State-Maschinen für die Vokalwiederherstellung: Ein praktischer Leitfaden für CS539

Einführung in Finite-State-Maschinen und Vokalwiederherstellung

Stell dir vor, du bekommst einen englischen Satz, aus dem alle Vokale entfernt wurden – wie 'THS S A TST'. Kannst du ihn lesen? Für Menschen ist das oft knifflig, aber für Computer ist es eine klassische Aufgabe der Computerlinguistik. In diesem Tutorial lernst du, wie du mit endlichen Automaten (FSA) und endlichen Transduktoren (FST) solche Texte automatisch mit Vokalen versehen kannst. Dieses Thema ist nicht nur für Studierende der CS539 relevant, sondern auch für alle, die sich für Natural Language Processing (NLP), automatische Rechtschreibkorrektur oder Textvorhersage interessieren. Besonders spannend: Ähnliche Techniken werden in modernen KI-Apps wie ChatGPT oder Google Translate verwendet, um fehlende Buchstaben zu ergänzen oder Sprache zu verstehen.

Grundlagen: Was ist ein endlicher Automat?

Ein endlicher Automat (FSA) ist wie ein einfacher Schaltplan, der entscheidet, ob eine Zeichenkette zu einer bestimmten Sprache gehört. Stell dir vor, du baust einen Automaten, der nur englische Wörter akzeptiert, getrennt durch Unterstriche. Jeder Buchstabe ist ein Schritt von einem Zustand zum nächsten. Wenn du am Ende in einem Endzustand landest, ist die Zeichenkette gültig. In unserem Fall wollen wir einen Automaten, der alle möglichen englischen Sätze aus einem gegebenen Vokabular akzeptiert – ähnlich wie ein Spiel-Turnierbaum, bei dem nur bestimmte Spielzüge zum Sieg führen. Dieses Konzept ist auch die Basis für automatische Vervollständigung in Suchmaschinen oder Textvorhersage auf dem Smartphone.

Warum ist das nützlich? Ein Trend-Beispiel aus der Finanzwelt

Im Jahr 2026 nutzen viele Finanz-Apps wie Robinhood oder Trade Republic ähnliche Algorithmen, um Aktienkurse vorherzusagen oder Handelsstrategien zu optimieren. Auch wenn es hier um Buchstaben geht, ist die Logik dieselbe: Aus einer Sequenz von Symbolen (Buchstaben oder Kursdaten) soll eine sinnvolle Struktur erkannt werden. Genau das machst du mit deinem FSA für englische Wörter.

Schritt 1: Erstellen eines FSA für englische Wörter

Deine erste Aufgabe ist es, einen FSA zu bauen, der alle Zeichenketten akzeptiert, die aus Wörtern eines gegebenen Vokabulars bestehen, getrennt durch Unterstriche. Das machst du mit einem Python-Programm, das die Wörter aus einer Datei liest und einen Automaten im Carmel-Format ausgibt. Carmel ist ein Tool, das mit endlichen Automaten arbeitet – perfekt für diese Aufgabe. Dein Programm sollte etwa 25 Zeilen lang sein und einen Automaten mit etwa 250.000 Zuständen erzeugen.

# Beispiel für make.py (Auszug)
import sys
words = [line.strip() for line in sys.stdin]
print('F')
# ... Zustände und Transitionen erzeugen

Teste deinen Automaten mit den mitgelieferten Testdateien: strings (korrekte Sätze) und strings.bad (fehlerhafte). Dein Automat sollte alle korrekten Sätze akzeptieren und alle fehlerhaften zurückweisen. Das ist wie ein Virenscanner, der nur sichere Dateien durchlässt.

Schritt 2: Finite-State-Transduktor für Vokalentfernung

Jetzt baust du einen Transduktor (FST), der aus einem normalen Satz einen Satz ohne Vokale macht. Das ist die Umkehrung dessen, was wir später brauchen. Der Transduktor liest Buchstaben und gibt sie entweder unverändert aus (wenn sie Konsonanten sind) oder löscht sie (wenn sie Vokale sind). So wird aus 'YOU ARE HERE' → 'Y R HR'.

In der Praxis wird so etwas in Spracherkennungssystemen verwendet, um aus Audiosignalen Buchstaben zu extrahieren. Auch bei automatischen Untertiteln auf YouTube kommen ähnliche Techniken zum Einsatz.

Schritt 3: Vokalwiederherstellung durch Rückwärtsanwendung

Der spannende Teil: Du wendest den Transduktor rückwärts an, um aus einem Text ohne Vokale den ursprünglichen Text zu rekonstruieren. Das Problem: Es gibt viele Möglichkeiten – aus 'Y R HR' könnte 'YOUR HERE' oder 'YOU ARE HERE' werden. Dein Transduktor allein liefert nur eine zufällige Auswahl. Die Genauigkeit liegt daher bei etwa 1,3% – das ist wie ein Wetterbericht, der nur rät.

Schritt 4: Kombination von FSA und FST für bessere Ergebnisse

Um die Genauigkeit zu verbessern, kombinierst du deinen FSA (der nur gültige englische Sätze akzeptiert) mit dem Transduktor. Das machst du, indem du die Ausgabe des Transduktors durch den FSA filterst. So werden nur sinnvolle Sätze zugelassen. Die Genauigkeit steigt auf etwa 30% – besser, aber noch nicht perfekt. Das liegt daran, dass der FSA nur die Wortreihenfolge prüft, nicht die Wahrscheinlichkeit einzelner Wörter. Ein Mensch würde sofort erkennen, dass 'THS S A TST' wahrscheinlich 'THIS IS A TEST' ist, weil 'THIS' häufiger vorkommt als 'THUS'. Unser Modell hat noch kein Sprachmodell für Wahrscheinlichkeiten.

Schritt 5: Verbesserung mit n-Gramm-Modellen

Der nächste Schritt: Du ersetzt den einfachen FSA durch ein n-Gramm-Modell, das die Wahrscheinlichkeit von Wortsequenzen berücksichtigt. In der Praxis wird oft ein Trigramm-Modell verwendet, das die letzten zwei Wörter betrachtet. Damit kannst du die Genauigkeit auf über 90% steigern. Das ist ähnlich wie bei der Texteingabe auf dem Smartphone, die das nächste Wort vorhersagt. Auch ChatGPT nutzt solche Wahrscheinlichkeitsmodelle, um kohärente Texte zu erzeugen.

Du kannst auch ein Wörterbuch mit Wortfrequenzen einbauen oder ein phonetisches Modell, das die Aussprache berücksichtigt. In der Hausaufgabe wird das mit dem Katakana-Beispiel aus dem Japanischen illustriert, wo englische Wörter in japanische Silben übersetzt werden. Auch da helfen endliche Transduktoren.

Fazit und Ausblick

Endliche Automaten und Transduktoren sind mächtige Werkzeuge in der Computerlinguistik und KI. Sie werden nicht nur für die Vokalwiederherstellung verwendet, sondern auch in der Rechtschreibkorrektur, maschinellen Übersetzung und Spracherkennung. Mit den heutigen Large Language Models wie GPT-4 sind sie zwar oft unsichtbar, aber sie bilden das Fundament vieler Algorithmen. Wenn du dieses Tutorial durcharbeitest, hast du einen wichtigen Schritt in Richtung NLP-Entwicklung gemacht – und vielleicht fällt dir beim nächsten E-Sport-Turnier ein, dass die Spielzüge der Profis auch wie Zustandsübergänge in einem Automaten sind.

Weiterführende Ressourcen

• Carmel-Tutorial: Primer on Finite-State Software for NLP
• Wikipedia: Finite-State Machine
• Open-Source-Tools: NLTK für Python