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

9

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?

Stefano Sanfilippo
quelle
2
Es wäre hilfreich, wenn Sie die gefundenen Referenzen auflisten würden, die Sie für vage und für übermäßig technisch hielten. Andernfalls ist die Antwort wahrscheinlich ein Zeiger auf die Referenzen, die Sie bereits gefunden haben.
Wandering Logic
1
Es kann sein, dass das, was Sie als Vektor bezeichnen, nicht das ist, was Earley in seinem Originalpapier als Vektor bezeichnet. Oder es kann sein, dass es nicht genau die gleiche Rolle spielt. Autoren führen Variationen in Algorithmen ein. Es gibt keine Möglichkeit, dies zu wissen, da Sie keinen Verweis auf die von Ihnen verwendeten Dokumente geben ... und wir möglicherweise ohnehin keinen Zugriff darauf haben. Was helfen kann, ist, Definitionen genauer zu definieren. Bei der Beantwortung habe ich nur angenommen, dass Sie dieselben Definitionen wie bei Earley verwendet haben.
Babou
@babou, was ich "Earley-Vektor" nannte, ist die tabellarische Darstellung der vom Parser erstellten Datenstruktur. Es war der Begriff, den mein Professor für formale Sprachen verwendete, während er sich darauf bezog. Es sollte beachtet werden, dass meine Hauptsprache nicht Englisch ist, daher könnte dies nur ein schlechter Versuch sein, die Terminologie zu übersetzen. Die technische Referenz, die ich erwähnte, ist Earleys Papier selbst. Ich näherte mich ihm, aber es war ein wenig einschüchternd für einen echten Anfänger wie mich.
Stefano Sanfilippo
Vielleicht möchten Sie überprüfen, ob "Earley-Vektor" von Ihrem Professor verwendet wird, um dieselbe Struktur zu bedeuten, die Earley in seiner Arbeit als "Vektor" bezeichnet. Kann für die Kommunikation nützlich sein. Wie Sie sehen, müssen Sie im Übrigen zusätzliche Informationen aufbewahren, um Analysebäume wiederherstellen zu können, aber Earley geht nicht wirklich auf Details ein. Es gibt jetzt andere Algorithmen, und ich befürchte, dass die Komplexität von Earleys Algorithmus die Schlüsselideen dieser Art von Techniken etwas verbirgt. Viel Glück.
Babou
War meine Erklärung hilfreich oder benötigen Sie eine detailliertere Beschreibung des technischen Teils?
Babou

Antworten:

9

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(n3)nO(n2)

Die Zeitkomplexität im ungünstigsten Fall ist bekanntlich .O(n3)

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 sO(ns+1)sist 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αD.βgDDγ.fDγEαD.βgγD

fgfDγg

DEαD.βgwf+1gwf+1:gDDγDγ.fD

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.

UXYZWUV

wf+1:gXwg+1:hYwh+1:iwh+1:jZUXYZwf+1:iwf+1:jU

wi+1:kwj+1:kVWUVwf+1:kW

wf+1:gwg+1:hXYUUXYZUXY.ZfShZWUV.fSk

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.

babou
quelle
Neben der CYK-Analyse lohnt es sich auch, sich mit der GLR-Analyse zu befassen.
Pseudonym
1
@Pseudonym Das Wissen und Verstehen verschiedener Formen der allgemeinen CF-Analyse tut sicherlich nicht weh, und ich schlage dies mit den beiden Referenzen am Ende der Antwort vor. Meine Wahl von CYK war jedoch nicht zufällig. Es teilt mit Earleys Algorithmus die Eigenschaft, interpretativ zu sein und die Grammatik direkt zu verwenden, anstatt Tabellen zu verwenden, die durch Kompilieren der Grammatik zu einem Push-Down-Automaten (wie in GLR, GLL, GPrec) erstellt wurden. Daher ist die Beziehung zwischen dem Erkennungsprozess und der Baum- / Waldgenerierung deutlicher sichtbar. CKY ist mit einer Ausnahme auch der einfachste Algorithmus.
Babou