Schreiben Sie eine Klasse Parser mit den Left-Corner-Algorithmus und den Viterbi-Algorithmus, welcher einen Grammatiksatz von PCFG-Regeln und ein Lexikon einliest und damit Sätze parst.
Grammatikregeln:
1.0 S NP VP
0.2 VP VP PP
0.3 VP V NP
0.2 VP V
0.2 VP V PP
0.1 VP V NP PP
0.2 NP NP PP
0.5 NP DT N1
0.3 NP N1
0.3 N1 A N1
0.7 N1 N
1.0 PP P NPwobei die erste Spalte die Wahrscheinlichkeiten der jeweiligen Regeln, die zweite Spalte die linke Seite der Regel, und der Rest die rechte Seite der Regel enthält.
Lexikon:
0.6 DT the
0.4 DT a
0.2 A old
0.3 A young
0.2 A big
0.3 A small
0.2 N man
0.3 N hill
0.2 N telescope
0.2 N dog
0.1 N saw
0.4 V saw
0.6 V slept
0.6 P on
0.4 P withIn der ersten Spalte steht jeweils die Wahrscheinlichkeit, in der zweiten die linke Seite der Regel, und in der dritten das Wort.
# Importiere notwendige Bibliotheken
import sys
from math import log, inf
from collections import defaultdict
Item = tuple[str, tuple[str,...], int, int, int]
Parser und eine init-Methode¶init-Methode erhält die Namen einer Grammatikdatei und einer Lexikondatei als Argument.read_file() zweimals, um erst die Grammatik und dann das Lexikon in self.grammar_rules und self.lexicon_rules einzulesen.child items als Attribute.class Parser:
def __init__(self, grammarfile: str, lexiconfile: str):
self.grammar_rules = self.read_file(grammarfile)
self.lexicon_rules = self.read_file(lexiconfile)
self.logvitprob: list[dict[Item,float]]
self.childitem: list[dict[Item, Item]]
def init_chart(self, N) -> None:
''' Datenstrukturen initialisieren '''
self.logvitprob = [{} for _ in range(N+1)]
self.childitem = {}
def parse(self, tokens: list[str, ...]) -> str|None:
''' parst einen einzelnen Satz '''
self.init_chart(len(tokens))
# Scan-Operation für jedes Token aufrufen
for i, token in enumerate(tokens):
self.scan(token, i)
# Analyse des Gesamtsatzes suchen
root_item = self.find_root_item()
if root_item is None:
return None # keine Analyse
# Parsebaum ausgeben
return self.build_tree(root_item)
@staticmethod
def read_file(filename: str) -> dict[str,list[tuple[str, tuple[str,...], float]]]:
pass
@staticmethod
def next_cat(item: Item) -> str:
pass
def add(self, item: Item, logprob: float, child: Item) -> None:
# Viterbi-Maximierung
pass
def scan(self, token: str, pos: int) -> None:
pass
def predict(self, child: Item, logprob: float) -> None:
pass
def complete(self, child: Item, logprob: float) -> None:
pass
def find_root_item(self):
pass
def build_tree(self, item: Item) -> str:
pass
read_file() .¶read_file()-Methode liest Grammatik bzw. das Lexikon ein.0.5 NP DT N1 wird durch grammar_rules['DT'].append(('NP', ('DT','N1'), log(0.2))) gespeichert.
Ausgabe: Ein Dictionary@staticmethod
def read_file(filename: str) -> dict[str,list[tuple[str, tuple[str,...], float]]]:
''' liest Grammatik- oder Lexikonregeln aus einer Datei und
speichert sie in einem Dictionary von Listen.
Das erste Element auf der rechte Seite der Regel ist der Key,
mit dem das Dictionary indiziert wird.
Für jede Regel wird ein Tripel bestehend aus
- der linken Seite der Regel,
- der rechten Seite der Regel (als Tupel) und
- der logarithmierten Regelwahrscheinlichkeit
generiert und zur Liste, die den Value des Keys repräsentiert, hinzugefügt.
Hier ist ein defaultdict(list) nützlich.
'''
rules = defaultdict(list)
with open(filename) as file:
for line in file:
p, lhs, *rhs = line.split()
rules[rhs[0]].append((lhs, tuple(rhs), log(float(p))))
return rules
Schreibe die Methoden scan()
Eingaben: das Wort token und seine Satzposition pos
self.lexicon_rules nach und die add-Methode aufruft, um die Regeln in die Chart einzutragendef scan(self, token: str, pos: int) -> None:
''' schlägt die Regeln für das Argument-Token im Lexikon nach
und trägt jede Regel mit der add-Funktion in die Chart ein.
Als child-Argument wird der add-Funktion der Wert None übergeben.
Punkt-, Start- und End-Position sind geeignet zu definieren.
'''
if token not in self.lexicon_rules:
# Das Wort ist nicht im Lexikon
print('unknown word:', token, file=sys.stderr)
else:
for lhs, rhs, logp in self.lexicon_rules[token]:
# Alle möglichen Wortarten aus dem Lexikon eintragen
self.add((lhs, rhs, 1, pos, pos+1), logp, None)
predict()-Methode.¶Eingaben: das child Item und die logarithmierten Viterbi-Wahrscheinlichkeit logprob.
def predict(self, child: Item, logprob: float) -> None:
''' Schlägt die Regeln für die linke Seite der übergebenen Punktregel
in der Grammatik nach und trägt jede Regel mit der add-Funktion
in die Chart ein.
'''
cat, _, _, startpos, endpos = child
for lhs, rhs, logp in self.grammar_rules[cat]:
self.add((lhs, rhs, 1, startpos, endpos), logprob+logp, child)
complete()-Methode.¶Eingaben: das child Item und die logarithmierten Viterbi-Wahrscheinlichkeit logprob.
child-Konstituente als Nächstes erwarten.def complete(self, child: Item, logprob: float) -> None:
''' findet alle Regeln in self.logvitprob[i],
wobei i die Startposition der übergebenen Regel ist.
Jede gefundene Regel, welche die Kategorie auf der linken Seite
der übergebenen Regel als Nächstes erwartet, wird vervollständigt,
d.h. Punktposition, Endposition und log-Wahrscheinlichkeit der
gefundenen Regel werden angepasst und die resultierende Regel wird mit
der add-Funktion in die Chart eingetragen.
'''
cat, _, _, splitpos, endpos = child
# Alle Punktregeln durchlaufen, die an splitpos enden
for item, logp in self.logvitprob[splitpos].items():
lhs, rhs, dotpos, startpos, _ = item
# Test, ob die Punktregel mit der als Argument
# übergebenen Punktregel vervollständigt werden kann
if self.next_cat(item) == cat:
self.add((lhs, rhs, dotpos+1, startpos, endpos), logp+logprob, child)
add()-Methode.¶Eingaben: eine Punktregel item und die logarithmierten Viterbi-Wahrscheinlichkeit logprob.
predict und complete auf. Schreibe dabei auch eine statische Methode next_cat(), welche eine Punktregel als Argument erhält und das Element auf der rechten Seite nach dem Punkt liefert bzw. None falls der Punkt sich am Ende befindet.
def add(self, item: Item, logprob: float, child: Item) -> None:
''' trägt die übergebene Punktregel item als Key mit Value logprob
in die Chart (self.logvitprob) ein,
falls sie noch nicht darin enthalten war oder
falls die alte Wahrscheinlichkeit kleiner war.
Wenn die Regel eingetragen wurde, werden noch predict und complete aufgerufen,
falls der Punkt am Ende der rechten Seite steht.
Außerdem wird die übergebene Punktregel child in self.childitem
als beste Kindkonstituente der neuen Konstituente gespeichert.
'''
lhs, rhs, dotpos, startpos, endpos = item
# Viterbi-Maximierung
if self.logvitprob[endpos].get(item, -inf) < logprob:
self.logvitprob[endpos][item] = logprob
self.childitem[item] = child # Verweis auf Tochterkonstituente
if self.next_cat(item) is None:
# Konstituente vollständig erkannt
self.predict(item, logprob)
self.complete(item, logprob)
@staticmethod
def next_cat(item: Item) -> str:
''' erhält eine Punktregel als Argument und
liefert das Element auf der rechten Seite nach dem Punkt
bzw. None falls der Punkt sich am Ende befindet.
Eine Punktregel ist ein 5-Tupel bestehend aus
- der linken Seite der Regel
- der rechten Seite der Regel (ein Tupel)
- der Position des Punktes auf der rechten Seite der Regel (int)
- der Startposition der Konstituente
- der Endposition der Konstituente
Beispiel: ('VP', ('V', 'NP'), 1, 2, 3)
Das ist eine VP-Regel. Der Punkt befindet sich nach dem 'V' und
die partiell erkannte Konstituente beginnt nach dem 2. Wort und
endet nach dem 3. Wort.
'''
rhs, dotpos = item[1:3]
try:
cat = rhs[dotpos]
except IndexError:
cat = None
return cat
find_root_item()-Methode für das Parsing.¶Die Methode sucht die wahrscheinlichste vollständige S-Konstituente, die den ganzen Satz abdeckt.
def find_root_item(self):
''' sucht die wahrscheinlichste vollständige S-Konstituente,
die den ganzen Satz abdeckt.
'''
bestscore, bestitem = -inf, None
for item, score in self.logvitprob[-1].items():
lhs, rhs, dotpos, startpos, _ = item
# Hat die Punktregel alle gewünschten Eigenschaften?
if lhs == 'S' and self.next_cat(item) is None and startpos == 0:
# Ist die neue Analyse besser als alle bisherigen?
if bestscore < score:
bestscore = score
bestitem = item
return bestitem
build_tree()-Methode.¶Eingaben: eine Punktregel item.
Ausgabe: Teilbaum für die Punktregel
def build_tree(self, item: Item) -> str:
''' gibt den Teilbaum für die übergebene Punktregel rekursiv
in Klammernotation aus. Leerzeichen sollten nur vor Wörtern
ausgegeben werden.
self.childitem[item] liefert Ihnen die Kind-Konstituente.
Wenn die Punktposition größer als 1 ist,
müssen Sie mit der Startposition der Kindkonstituente
die Punktregel rekonstruieren, die mit der Kindkonstituente
vervollständigt wurde.
Durch rekursiven Aufruf von build_tree erzeugen Sie die Teilbäume
für die Kindkonstituente und die rekonstruierte Punktregel.
'''
lhs, rhs, dotpos, startpos, endpos = item
# Punktregel für den letzten Tochterknoten
child = self.childitem[item]
if child is None: # Punktregel der Form A --> w .
# präterminalen Knoten ausgeben
return f"({lhs} {rhs[0]})"
# Die Punktregel hat die Form A --> x B . y
# letzten Tochterknoten B ausgeben
parse = self.build_tree(child)
if dotpos > 1:
# Punktregel der Form A --> x . B y ausgeben
startpos_last_child = child[-2]
parse = self.build_tree((lhs, rhs, dotpos-1, startpos, startpos_last_child)) + parse
# aktuellen Knoten ausgeben, falls die Konstituente komplett ist
if self.next_cat(item) is None: # Punktregel der Form A --> x B .
parse = f"({lhs}{parse})"
return parse