Vorlesungsskript 28

Bäume mit Klassen

Nachdem wir uns mit Klassendefinitionen vertraut gemacht haben, können wir uns daran machen, eine Klasse Tree für Bäume zu definieren. Klar ist: Ein Baum braucht zwei Attribute, nämlich ein Etikett und eine Liste von unmittelbaren Unterbäumen (was dann wiederum Tree-Objekte sind). Wir definieren den Konstruktor also so, dass er beides als Argumente nimmt und in entsprechenden Attributen speichert. Wir definieren das Argument für die Unterbäume als variadisches Argument (vgl. Vorlesungsskript 18), damit man beim Erzeugen eines Baums keine eckigen Klammern um die Unterbäume machen muss:

class Tree:

    def __init__(self, label, *subtrees):
        self.label = label
	self.subtrees = subtrees

Mit dieser Definition können wir bereits Bäume erzeugen und auf ihre Attribute zugreifen:

>>> ctree = Tree('S',
...             Tree('NP',
...                 Tree('D',
...                     Tree('the')),
...                 Tree('N',
...                     Tree('cat'))),
...             Tree('VP',
...                 Tree('V',
...                     Tree('chases')),
...                 Tree('NP',
...                     Tree('EN',
...                         Tree('peter')))))
>>> dtree = Tree('chases',
...             Tree('cat',
...                 Tree('the')),
...             Tree('Peter'))
>>> ctree.label
'S'
>>> ctree.subtrees[1].label
'VP'
>>> len(dtree.subtrees[0].subtrees)
1

Wir erweitern die Klasse um eine __repr__-Methode, die bei Ausgabe eines Baums seinen Inhalt sichtbar macht, etwa so:

>>> ctree
Tree('S', Tree('NP', Tree('D', Tree('the')), Tree('N', Tree('cat'))), Tree('VP', Tree('V', Tree('chases')), Tree('NP', Tree('EN', Tree('peter')))))
>>> dtree
Tree('chases', Tree('cat', Tree('the')), Tree('Peter'))

Da diese Repräsentationen aus ziemlich vielen Einzelteilen bestehen (Name der Klasse, öffnende Klammer, Etikett und Repräsentationen der Unterbäume und dazwischen jeweils Komma und Leerzeichen, schließende Klammern), sorgen wir für Übersicht, indem wir eine lokale Generatorfunktion definieren, die die Teile nach und nach yieldet. Wir fügen sie dann mit der join-Methode zu einem String zusammen:

    def __repr__(self):
        def parts():
            yield 'Tree('
            yield repr(self.label)
            for subtree in self.subtrees:
                yield ', '
                yield repr(subtree)
            yield ')'
        return ''.join(parts())

Wir können nun wieder verschiedene nützliche Operationen auf Bäumen definieren. In Vorlesungsskript 26 hatten wir das mit Funktionen gemacht, an die Bäume in Listenrepräsentation übergeben werden. Solche Funktionen müssen genau wissen, die die Baumbobjekte intern aufgebaut sind. Die objektorientierte Philosophie sagt: Wie ein Objekt intern aufgebaut ist, weiß es selbst (bzw. seine Klasse) am besten. Daher macht es Sinn, die Operationen innerhalb der Klasse zu definieren – als Methoden. Sollten wir den internen Aufbau der Baumklasse einmal ändern, können wir die Methoden gleich mit ändern und müssen uns keine Sorgen machen, dass irgendwo anders Funktionen existieren, die von der Änderung nichts mitbekommen haben.

Im Folgenden definieren wir z.B. leaf_labels – diesmal als Methode der Klasse Tree. Wir definieren auch eine Helfermethode is_leaf, die prüft, ob ein Baum ein Blatt ist. Dies in eine eigene Methode auszulagern verbessert die Lesbarkeit und Wartbarkeit von Code, der das prüfen muss.

    def leaf_labels(self):
        if self.is_leaf():
            yield self.label
        else:
            for subtree in self.subtrees:
                yield from subtree.leaf_labels()

    def is_leaf(self):
	return len(self.subtrees) == 0

Wir können die Methode nun so aufrufen:

>>> list(ctree.leaf_labels())
['the', 'cat', 'chases', 'peter']
>>> list(dtree.leaf_labels())
['the', 'Peter']