Wie rekonstruiere ich den Wald von Syntaxbäumen aus dem Earley-Vektor?

Die Verwendung des Earley-Vektors als Erkenner ist recht einfach: Wenn das Ende der Zeichenfolge erreicht ist, müssen Sie nur noch nach einer abgeschlossenen axiomatischen Produktion suchen, die an Position 0 gestartet wurde. Wenn Sie mindestens eine haben, wird die Zeichenfolge akzeptiert.

Die Verwendung des Earley-Vektors zur Rekonstruktion der Analysebäume ist weniger offensichtlich. Eigentlich kann ich nicht herausfinden, wie ein algorithmisches Verfahren funktionieren würde, außerdem waren die einzigen Referenzen, die ich fand, entweder vage oder supertechnisch. Könnte jemand etwas Licht ins Dunkel bringen?

Ich verwende Terminologie und Notationen aus Earleys Artikel . Möglicherweise ist die von Ihnen gelesene Beschreibung unterschiedlich.

Es scheint häufig, dass allgemeine CF-Parsing-Algorithmen zuerst in Form eines Erkenners dargestellt werden, und dann wird das Informationsmanagement, das zum tatsächlichen Erstellen von Analysebäumen und Analysewäldern erforderlich ist, nachträglich hinzugefügt. Ein Grund kann sein, dass das Beibehalten der zum Erstellen der gemeinsam genutzten Gesamtstruktur erforderlichen Informationen einen kubischen Raum erfordert, wobei n die Länge der zu analysierenden Eingabezeichenfolge ist, der Platzbedarf jedoch nur das Quadrat O ( n 2 ) für die Erkennung ist, wenn Diese Informationen bleiben nicht erhalten. Der Grund für diese Zunahme der Raumkomplexität ist recht einfach: Die Größe des Analysewaldes kann kubisch sein.$O(n^3)$$n$$O(n^2)$

Die Zeitkomplexität im ungünstigsten Fall ist bekanntlich .$O(n^3)$

Die beste Referenz für Earleys Algorithmus ist natürlich Earleys Artikel , aber es geht nicht sehr explizit um das Erstellen des Analysewaldes. Dies kann tatsächlich ein chaotisches Geschäft sein, viel mehr als das schnelle Gerede von Abschnitt 7 Seite 101 erscheinen lässt. Um wahr zu sein, spricht Earley nicht von Analysewald oder von Wald, sondern von " einer faktorisierten Darstellung aller möglichen Analysebäume ". Und es gibt einen guten Grund dafür: wenn er versuchte , einen Wald zu produzieren nach seiner Grammatik, sein Raum (daher Zeit) Komplexität gebunden klettern würde , wo $O(n^{s+1})$$s$ist die Größe der längsten Regel auf der rechten Seite. Aus diesem Grund verwenden andere Algorithmen Grammatiken in binärer Form (nicht unbedingt Chomsky Normal Form (CNF)).

Tatsächlich verwendet Earley implizit die binäre Form , da dies für die Komplexität der kubischen Zeit erforderlich ist. Dies ist eine der Hauptrollen des Regelpunkts in Staaten. Aber diese implizite binäre Form erzeugt Parsen und Wälder gemäß der binärisierten Grammatik, nicht nach der ursprünglichen, die, wie ich befürchte, eine Hauptquelle der Dunkelheit ist. Dies wird weiter unten detailliert beschrieben.

Ein guter Weg, um zu verstehen, wie der Wald erhalten wird, besteht wahrscheinlich darin, ihn in einem einfacheren Fall, dem CYK-Algorithmus, zu betrachten . Es wird auch oft als Erkenner beschrieben, und der Parser-Aspekt wird am Ende hinzugefügt. Sie können die Beschreibung in Wikipedia ansehen. Die Informationen, die zum Erstellen der Gesamtstruktur benötigt werden, werden in der Tabelle der "Backpointers" gespeichert. Backpointers sind im Wesentlichen Zeiger auf Teilzeichenfolgen (ein zugehöriges Symbol), die nach einer bestimmten Regel die Bestandteile einer Zeichenfolge bilden. Sie bieten alle Möglichkeiten zum Parsen eines Teilstrings. Denken Sie daran, dass CYK eine binäre Form verwendet, normalerweise CNF, damit die Dinge einfacher werden. Der CYK-Parser hat grundsätzlich die gleiche dynamische Programmierstruktur wie Earley, ist jedoch viel einfacher. Ein gutes Verständnis kann daher eine wichtige Hilfe sein.

Zurück zu Earleys Algorithmus: Ich glaube nicht, dass Sie einen Earley-Vektor benötigen, um über die Akzeptanz zu entscheiden oder um Bäume und Wälder zu analysieren. Was Earley in seinem Artikel als Vektor bezeichnet, erscheint nur auf Seite 97 im dritten Absatz der Implementierung. Es ist nur ein Gerät, um die Suche nach Zuständen zu beschleunigen, die auf eine bestimmte Zeichenfolgenposition k zurückweisen, um eine bessere Komplexität zu erzielen. Alle Informationen befinden sich jedoch in den Statussätzen, die als Statuslisten implementiert sind. Diese Informationen reichen jedoch nicht aus, um den Wald von Analysebäumen zu erstellen, da der Algorithmus nicht verfolgt, wie ein Zustand erhalten werden kann. In der Tat wird der Vektor sogar verwendet, um einen bereits gefundenen Zustand effizient zu verwerfen, unabhängig davon, wie er gefunden wurde.

In Abschnitt 7 von Earleys Artikel erklärt er, dass es notwendig ist, die Art und Weise zu verfolgen, wie Vervollständigungen durchgeführt werden, um "den Erkenner in einen Parser zu verwandeln", dh um Analysebäume wiederherstellen zu können.

$E\rightarrow \alpha D.\beta \; g$$D$$D\rightarrow \gamma. \; f$$D$$\gamma$$E\rightarrow \alpha D.\beta \; g$$\gamma$$D$

$f$$g$$f$$D\rightarrow \gamma$$g$

$D$$E\rightarrow \alpha D.\beta \; g$$w$$f+1$$g$$w_{f+1:g}$$D$$D\rightarrow \gamma$$D\rightarrow \gamma. \; f$$D$

Angenommen, Sie haben alle erforderlichen Zeiger wie im Artikel angegeben beibehalten, können Sie alle gemeinsam genutzten Baumdarstellungen ab dem letzten vom Parser erkannten Symbol abrufen, das natürlich das Anfangssymbol der Grammatik ist.

$U\rightarrow XYZ$$W\rightarrow UV$

$w_{f+1:g}$$X$$w_{g+1:h}$$Y$$w_{h+1:i}$$w_{h+1:j}$$Z$$U\rightarrow XYZ$$w_{f+1:i}$$w_{f+1:j}$$U$

$w_{i+1:k}$$w_{j+1:k}$$V$$W\rightarrow UV$$w_{f+1:k}$$W$

$w_{f+1:g}$$w_{g+1:h}$$X$$Y$$U$$U\rightarrow XYZ$$U\rightarrow XY.Z \; f$$S_h$$Z$$W\rightarrow UV. \; f$$S_k$

Der Wald der Syntaxbäume kann also sehr seltsam sein, mit siamesischen Zwillingsunterbäumen, die die ersten beiden Kanten eines Knotens teilen, aber nicht die dritte Kante. Mit anderen Worten, es kann eine sehr unangenehme Struktur sein. Dies könnte erklären, warum Earley es " eine faktorisierte Darstellung aller möglichen Analysebäume " nennt , ohne genauer zu sein.

Jeder Versuch, die siamesischen Zwillinge chirurgisch zu trennen, ohne die Grammatik zu ändern, führt zu einer erhöhten Komplexität. Der richtige Weg, dies zu tun, besteht darin, die Grammatik zu binarisieren.

Ich hoffe, dies wird dir helfen. Gib mir Bescheid. Aber ich bestehe darauf, dass ein gutes Verständnis der CYK-Analyse helfen kann. Es gibt andere Algorithmen, die einfacher als die von Earley sind und alle CF-Sprachen effizient analysieren können.

Weitere allgemeine Informationen zu diesem Parse Forest-Problem finden Sie in zwei weiteren Antworten, die ich gegeben habe: /cstheory/7374#18006 und https://linguistics.stackexchange.com/questions/4619#6120 . Sie gehen jedoch nicht auf bestimmte Details des Earley-Algorithmus ein.