Programmierprojekt "Reimplementation des Brill-Taggers in PROLOG: Teil I"
Bearbeiterin: Sonja Brodersen
Betreuer: Simon Clematide
Einführung
Der Brilltagger ist ein Part-of-Speech-Tagger, der regelbasiert arbeitet, wobei die Regeln statistisch aus einem vorgegebenen Trainingskorpus induziert werden. Der Tagger besteht aus 4 Komponenten:
- Training
- Erstellen der morphographematischen und positionsbezogenen lexikalischen Regeln für das Taggen von unbekannten Wortformen
- Erstellen der kontextuellen Regeln, die nach dem ersten provisorischen Tagging angewendet werden
- Tagging
- Provisorisches Taggen der bekannten Wörter durch Tags aus Lexikon und der unbekannten Wörter durch Anwenden der lexikalischen Regeln
- Anwenden der kontextuellen Regeln auf die provisorische getaggte Eingabe
Ziel und Zweck
Im Rahmen dieser Arbeit sollen die Teile A.a sowie B.a in PROLOG reimplementiert werden. Die Reimplementation bezweckt zwei Dinge:
- Didaktik: Die Studierenden der CL in Zürich lernen als Programmiersprache nur PROLOG. Damit sie Einblick in Implementation und Algorithmus dieses statistisch/regelbasierten Systems bekommen können, ist eine PROLOG-Version hilfreich. Das Ziel wäre demnach eine konzeptuell möglichst klare und einfache Implementation.
- Effizienz: Das Programm von Brill, das A.a berechnet (unknown-lexical-learn.prl), ist momentan in PERL geschrieben und zeigt ein sehr schlechtes Laufzeitverhalten, wenn die Grösse des Corpus zunimmt (für Corpus von ca. 800 kb auf neueren SUN-Stations fast 24h). Die Implementation soll einerseits zeigen, ob die Umsetzung in PROLG gegenüber PERL Effiziensvorteile bringt oder nicht, andererseits das Effizienzverhalten unter Berücksichtigung des didaktischen Ziels verbessern.
Arbeitsschritte
- Zusammenfassung und genaue Beschreibung des Algorithmus' von Brill für die Komponente A.a. aus Abschnitt 6.2 der Dissertation und dem Programmkode
- Alle Datenstrukturen, Prozeduren kurz beschreiben; Kontrollverhalten darstellen in Pseudokode
- Implementierungsentwurf in PROLOG
- Sinnvolle Repräsentationen der Datenstrukturen und Prozeduren in PROLOG (Sprachumfang ISO-Prolog)
- Insbesondere: Wo Listen? Wie Arrays repräsentieren? Dynamische Programmierung?...
- Implementierung des Entwurfs
- Überprüfung der Korrektheit (vs. PERL-Programm) und vs. Spezifikation
- Beurteilungs des Laufzeitverhaltens (Vergleich mit PERL), Benennen von Flaschenhälsen, Profiling der Prädikate, die am meisten aufgerufen werden
- Vorschläge (bzw. Implementationen) zur Verbesserung des Laufzeitverhaltens
Literatur/ Links:
Simon Clematide