DE69715525T2

DE69715525T2 - Verfahren und System um Datenstrukturen zu vereinigen

Info

Publication number: DE69715525T2
Application number: DE69715525T
Authority: DE
Inventors: Ronald M. Kaplan; Maxwell
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1996-06-21
Filing date: 1997-06-19
Publication date: 2003-01-16
Anticipated expiration: 2017-06-20
Also published as: EP0814417A1; US5903860A; EP0814417B1; DE69715525D1; JPH10105551A

Description

Die vorliegende Erfindung betrifft Verfahren zur Vereinigung von Datenstrukturen.
Die extreme Zunahme von Informationen hat zu einer bisher nicht befriedigten Nachfrage für automatisches Verarbeiten natürlich- bzw. umgangssprachlichen Dokumenten geführt. Eine derartige Bearbeitungsmöglichkeit würde Schnittstellen von der Umgangssprache zu Datenbanken, automatische Erzeugung von Auszügen und Zusammenfassungen von Texten in der Umgangssprache und einer automatischen Übersetzung und Interpretation der Umgangssprache ermöglichen. Eine Entwicklung dieser Technologie wird behindert durch die zur Bearbeitung moderner grammatikalischer Formalismen erforderliche Zeit.
Viele moderne grammatikalische Formalismen gebrauchen rekursive Merkmalsstrukturen, um die syntaktische Struktur von Umgangssprache zu beschreiben. Merkmalsstrukturen besitzen den Vorteil, dass diese leicht zu verstehen und leicht zu implementieren sind, sofern auf Vereinigung basierende Programmiersprachen wie etwa Prolog vorgegeben sind. Diese haben jedoch den Nachteil, dass sie die resultierenden grammatikalischen Formalismen nur unter Schwierigkeiten effizient umsetzen, sowohl in der Theorie als auch in der Praxis. In der Theorie können grammatikalische Formalismen, die willkürliche rekursive Merkmalsstrukturen verwenden, im schlimmsten Falle nicht unterscheidbar sein. Selbst mit geeigneten Einschränkungen, etwa der Randbedingungen hinsichtlich der nicht interaktiven Untersuchbarkeit von LFG können die Formalismen im schlimmsten Falle exponentiell sein. Obwohl in der Praxis die Arten von Erscheinungen, die einen Formalismus zu einem exponentiellen Zeitverhalten führen, selten sind, benötigen unabgestimmte auf Vereinigung basierende Analysealgorithmen für gewöhnlich Minuten, um einen mehr oder minder komplexen Satz zu analysieren.
Kontextbezogene Vereinigung, die manchmal auch als disjunkte Vereinigung bezeichnet wird, ist ein weiteres Verfahren zum Reduzieren der für die Vereinigung erforderlichen Verarbeitungszeit. Kontextbezogene Vereinigung vermischt alternative Merkmalsstrukturen, in denen die diversen Alternativen mit Aussagevariablen bezeichnet werden, die die Alternativen kennzeichnen, von denen sie abstammen. Die folgenden Regeln geben formal die grundlegende Idee der kontextbezogenen Vereinigung wider:
1. φ&sub1;vφ&sub2; ist erfüllbar nur dann, wenn (p → φ) A ( p → φ&sub2;) erfüllbar ist, wobei p eine neue Aussagevariable ist;
2. wenn φ&sub1; φ&sub2; → φ&sub3; eine Deduktionsregel ist, dann ist (P → φ&sub1;) (Q →52) → (P Q → φ&sub3;) eine kontextbezogene Version dieser Regel, wobei P und Q Boolsche Kombinationen von Aussagevariablen sind;
3. wenn P→FALSCH ist, dann ist P richtig. (In der ATMS-Sprache wird P als Nogood bezeichnet.)
Wenn wir die Vereinheitlichung als ein Verfahren betrachten, um das Umschreiben von Termen effizienter zu gestalten, indem Gleichheitsbeziehungen in einem Merkmalsbaum gekennzeichnet werden, dann kann kontextbezogene Vereinigung in gleicher Weise betrachtet werden, wobei die Aussagevariablen durch die Gleichheitsrelationen gekennzeichnet sind und die Vereinigung dann im Hinblick auf die obigen Regeln ausgeführt wird. Kontextbezogene Vereinigung wird in drei Schritten durchgeführt. Zuerst werden Disjunktionen in Konjunktionen unter Anwendung der Regel 1 von oben umgewandelt und als ein Beispiel einer Merkmalsstruktur betrachtet. Anschließend werden Merkmalsstrukturen vereinigt und Nogoods werden erzeugt. Schließlich können die Nogoods ermittelt und gelöst werden, um zu bestimmen, welche Kombinationen der Aussagevariablen gültig sind. Dieser Prozess wurde in US-A-5,438,511 beschrieben.
Fig. 1 zeigt ein einfaches Beispiel, wie kontextbezogene Vereinigung funktioniert. Die erste Merkmalsstruktur 20 ergibt sich aus der Umsetzung der Bedingungen ([A+]v[B- ]) ([C +]v[C-]). Die zweite Merkmalsstruktur 22 ergibt sich aus der Umsetzung der Bedingungen ([A+]v[A-]) ([D+]v[D-]). Es wurden Aussagevariablen p, q, r und s eingeführt, um die vier Disjunktionen in den beiden Bedingungen zu repräsentieren. Die Vereinigung der Merkmalsstrukturen 20 und 22 ergibt eine Merkmalsstruktur 24 und das Nogood (p r). Um Lösungen für die Merkmalsstruktur 24 zu finden, werden alle möglichen Kombinationen der Aussagevariablen berechnet, die mit dem bekannten Nogood konsistent sind. In diesem Falle gibt es zwölf mögliche Lösungen:
Der Hauptvorteil der kontextbezogenen Vereinigung ist das Verschieben des Bildens von Kreuzprodukten von Alternativen bis die Nogoods ermittelt worden sind. Dies ist zumindest aus zwei Gründen hilfreich. Erstens, das Ermitteln des Kreuzproduktes von Aussagevariablen ist rechentechnisch billiger als Ermitteln des Kreuzprodukts der Merkmalsstrukturen. Zweitens, kontextbezogene Vereinigung vermeidet das Verwenden unnötiger Kreuzprodukte, da diese nicht ermittelt werden, bis festgestellt ist, ob die Vereinigung gültig ist. Wenn die Vereinigung nicht zulässig ist, werden keine Kreuzprodukte genommen.
Die konventionelle kontextbezogene Vereinigung sowie andere konventionelle Verfahren können allerdings manchmal eine exponentielle Zeitdauer erfordern; wenn diese Verfahren zur Analyse eines Satzes oder einer Zeichensequenz durch Analysieren, um die zugrunde liegende Bedeutung zu bestimmen oder zur anderweitigen Verarbeitung landessprachlicher Sätze verwendet werden, können diese eine Zeitdauer erfordern, die exponential zur Anzahl der Wörter in einem Satz oder einer Zeichenkette ist. Insbesondere kann eine exponentielle Zeitdauer erforderlich sein, um Lösungen in gewissen Fällen zu finden, wenn Nogoods in einer Datenbank in naiver Weise kombiniert werden, um eine Lösung zu erhalten. Wenn ferner Aussagevariablen innerhalb einer Hierarchie aus Merkmalsstrukturen aufwärts kopiert werden, kann die Struktur des Baumes codiert werden, wodurch die Kontextfreiheit verletzt und eine exponentielle Zeitdauer erforderlich wird. Die exponentielle Zeitdauer kann daher diese Verfahren für einige Verarbeitungsanwendungen der Umgangssprache als nicht praktikabel erscheinen lassen.
Die Erfindung stellt Verfahren bereit, die dieses Problem umgehen, indem das Risiko verringert wird, dass eine exponentielle Zeitdauer erforderlich sein wird. Die Verfahren nutzen Datenwerte, die als "undurchsichtige bzw. verborgene Sätze" bezeichnet werden, um spezielle Zusammenhänge bzw. Kontexte darzustellen, die als "verborgene Zusammenhänge" bezeichnet werden, da deren innere Struktur nicht zum Kopieren in eine höhere Ebene der Hierarchie verfügbar ist. Wenn die Grammatik kontextfrei oder dazu äquivalent ist, wird die Anzahl der verborgenen Kontexte beschränkt. Folglich kann eine Nogood-Datenbank lokal in Begriffen des verborgenen Kontexts gelöst werden. Tatsächlich lassen verborgene Sätze zu, dass eine Nogood-Datenbank als eine Sammlung kleiner Datenbanken gelöst wird.
Verborgene Sätze helfen somit sicherzustellen, dass die für die Vereinigung erforderliche Zeit mit der dritten Potenz der Anzahl der Wörter in einem Satz oder in einer Zeichenkette variiert. Insbesondere kann eine Vereinigung in der dritten Potenz der Zeit stattfinden für Teile einer Grammatik, die kontextfrei oder dazu äquivalent ist, was bedeutet, dass die beiden Konstituenten ohne Bezug zu der inneren Struktur der kombinierten Konstituenten miteinander kombiniert werden können; im hierin verwendeten Sinne kann ein Konstituent eine beliebige Wortgruppe innerhalb einer Zeichenkette sein, zusammenhängend oder nicht, so dass eine Zeichenkette Konstituenten enthalten kann, unabhängig ob die verwendete Grammatik Konstituenten definiert, sei es explizit oder implizit.
Undurchsichtige Sätze sind, wenn sie zusammen mit kontextbezogenen einfachen Kopierverknüpfungen verwendet werden, noch wirksamer beim Vermeiden des Risikos, dass eine exponentielle Zeitdauer erforderlich sein wird.
Die folgenden Begriffe sind zum Verständnis der Erfindung hilfreich;
die Begriffe "Verknüpfung" und "Struktur" sind miteinander verwandt und beziehen sich beide auf Datenpunkte innerhalb einer Datenstruktur. Eine Verknüpfung ist ein Datenpunkt, der zwei oder mehr Strukturen miteinander in Beziehung setzt, und eine Struktur ist ein Datenpunkt, der mit anderen Strukturen mittels einer Verknüpfung in Beziehung stehen könnte.
Die Begriffe "Attribut" und "Wert" stehen ebenfalls in Beziehung zueinander: Ein Attribut ist immer ein Symbol oder ein einzelnes Element und ein Attribut kann einen Wert annehmen. Ein "Attributwertepaar" ist ein geordnetes Paar, das ein Attribut und einen der Werte, den dieses annehmen kann, enthält. Der Wert eines Attributs könnte selbst ein Symbol oder ein einzelnes bzw. atomares Element sein, oder es könnte ein Satz mit Attributwertepaaren sein. Bei der Verarbeitung von Umgangssprache gehören zu Beispielen von Attributen grammatikalische Funktionen, etwa Subjekt, Objekt, Anzahl, etc., die jeweils einen Wert für einen Teil eines umgangssprachlichen Texts annehmen können. Der generische Begriff "Faktum" beschreibt sowohl Attribute als auch Werte.
Eine "Merkmalsstruktur" ist eine Struktur, die ein oder mehrere Attributwertepaare enthält. Bei der Verarbeitung von Umgangssprache können Merkmalsstrukturen verwendet werden, um grammatikalische Funktionen an der Oberfläche von Teilen von Zeichenketten darzustellen. Eine Merkmalsstruktur wird herkömmlicherweise als eine Anordnung aus Attributwertepaaren innerhalb von eckigen Klammern dargestellt, wobei jedes einfache Attributwertepaar eine horizontale Linie ist. Da der Wert eines Attributs ein Satz an Attributwertepaaren sein kann, kann eine Merkmalsstruktur eine Hierarchie von Attributwertepaaren beinhalten; eine derartige Merkmalsstruktur kann als "hierarchisch" oder "nichtfinit" bezeichnet werden.
Ein "Kontext" ist eine von mehreren Alternativen.
Ein "Kontextidentifizierer" ist ein Datenpunkt, der einen Kontext kennzeichnet. Eine "kontextbezogene Verknüpfung" ist eine Verknüpfung, die einen Kontextidentifizierer aufweist, der einen Kontext bezeichnet, der nicht durch den Wert WAHR gekennzeichnet ist.
"Vereinigung" oder "Vereinheitlichung" ist eine Operation an Datenstrukturen, die eine vereinigte Datenstruktur liefert, mit der die Datenstrukturen verträglich sind. Im Allgemeinen beinhaltet die vereinigte Datenstruktur mehr Informationen als die Datenstrukturen, die vereinigt sind. Wenn die Datenstrukturen nicht konsistent sind, zeigt die vereinigte Datenstruktur eine Inkonsistenz. Zu den Datenstrukturen, an denen eine Vereinigung ausgeführt werden kann, gehören beispielsweise Merkmalsstrukturen oder andere Strukturen, die Attributwertepaare und Positionswertformen von Datenbanken, etwa von Wissensbanken, beinhalten. Eine Vereinigung, die an Merkmalsstrukturen ausgeführt wird, die Kontextidentifizierer enthalten, kann als eine "kontextbezogene Vereinigung" bezeichnet werden. Eine kontextbezogene Vereinigung kann angewendet werden, um Merkmalsstrukturen zu vereinigen, die Disjunktionen enthalten und kontextkennzeichnende Daten erzeugen können, in denen die Merkmalsstrukturen nicht konsistent sind, und auch als "Nogoods" bezeichnet werden.
Eine "Vorwärtskopierverknüpfung" ist eine Verknüpfung, auf die von einer Struktur zugegriffen werden kann, und die verwendet werden kann, um auf eine Kopie der Struktur zuzugreifen.
Eine "einfache Kopieverknüpfung" ist eine Verknüpfung, auf die von einer Kopie einer Struktur zugreifbar ist, und die verwendet werden kann, um auf die Struktur, die der Ursprung der Kopie ist, zuzugreifen. Eine Merkmalsstruktur, die einfache Kopieverknüpfungen enthält, ist ein Beispiel einer "unspezifizierten Merkmalsstruktur", da diese nicht alle notwendigen Informationen enthält, um deren Attribute zu beschreiben, sondern die vielmehr einfache Kopieverknüpfungen zu anderen Merkmalsstrukturen enthält, um fehlende Informationen kennzuzeichnen. Eine unspezifizierte Merkmalsstruktur ist "unspezifiziert", wenn die einzigen Datenpunkte eine oder mehrere einfache Kopieverknüpfungen zu anderen Merkmalsstrukturen sind.
"Einfaches Kopieren" bedeutet Kopieren einer hierarchischen Datenstruktur, etwa einer hierarchischen Merkmalsstruktur, durch Kopieren der Hierarchie von der obersten Ebene nach unten unter Verwendung von einfachen Kopieverknüpfungen, um Informationen in Ebenen kennzuzeichnen, die noch nicht kopiert sind.
Eine einfache Kopieverknüpfung "wechselwirkt" oder "ist aktiviert", wenn ein Ereignis auftritt, das ein weiteres Kopieren von der Struktur zu der Kopie erfordert. "Erweitern" ist die Operation, die das weitere Kopieren ausführt, wodurch zuvor weggelassene Informationen, die durch eine oder mehrere einfache Kopierverknüpfungen gekennzeichnet sind, hinzugefügt werden. Das Erweitern muss nicht alle einfachen Kopierverknüpfungen entfernen, da diese einfache Kopieverknüpfungen in Ebenen erhalten oder hinzufügen kann, die noch nicht vollständig erweitert sind.
Eine "kontextbezogene einfache Kopieverknüpfung" ist eine einfache Kopieverknüpfung, die einen Kontextidentifizierer aufweist, der einen Kontext bezeichnet, der nicht der NULL-Kontext ist. Eine kontextbezogene einfache Kopieverknüpfung kann durch Vereinigung mit einem weiteren Datenpunkt, der einen überlappenden Kontext aufweist, aktiviert werden; der andere Datenpunkt kann eine weitere einfache Verknüpfung sein.
Eine "Aussagevariable" ist eine Variable, die einen von zwei Werten, die typischerweise als WAHR und FALSCH bezeichnet werden, aufweisen kann.
Ein "verborgener Kontext" ist ein Kontext, dessen Komplexität aus seiner Darstellung nicht ersichtlich ist; beispielsweise kann ein verborgener Kontext durch eine Aussagevariable dargestellt sein, obwohl der verborgene Kontext eine Kombination anderer Kontexte ist. Anders ausgedrückt, ein verborgener Kontext, der eine Kombination anderer Kontexte ist, kann unabhängig von den anderen Kontexten, die in der Kombination enthalten sind, behandelt werden.
Ein "Satz" ist ein Datenpunkt, der eine Kombination aus Kontexten repräsentiert. Ein "verborgener Satz" ist ein Satz, der einen verborgenen Kontext darstellt. Es wird detailliert ein Verfahren zur Verwendung eines Prozessors beschrieben, um einen ersten Satz und einen zweiten Satz während der Vereinigung einer ersten grafischen Datenstruktur mit einer weiteren grafischen Datenstruktur zu verbinden. Zunächst bestimmt der Prozessor, ob der erste Satz mit der ersten grafischen Datenstruktur verknüpft ist. Wenn nicht, erzeugt der Prozessor einen dritten Satz, der verborgen ist und einen Zeiger zu dem ersten Satz aufweist. Danach verbindet der Prozessor den dritten Satz mit dem zweiten Satz.
In einem Aspekt der Erfindung wird ein Verfahren zur Vereinigung von Datenstrukturen bereit gestellt, wobei das Verfahren umfasst: (a) Kopieren von Informationen aus einer ersten Merkmalsstruktur in eine zweite Merkmalsstruktur; dadurch gekennzeichnet, dass aus der ersten Merkmalsstruktur in die zweite Merkmalsstruktur kopierte Informationen erste Satzdaten, die eine erste Kombination von Kontexten darstellen, enthalten; (a1) Bestimmen, ob Satzdaten, die die gleiche Kombination von Kontexten wie die ersten Satzdaten darstellen, bereits in die zweite Merkmalsstruktur kopiert worden sind; und (a2) wenn nicht, Erzeugen zweiter Satzdaten in der zweiten Merkmalsstruktur; die zweiten Satzdaten stellen die erste Kombination von Kontexten dar; die zweiten Satzdaten sind verborgene Satzdaten, die unabhängig von den Kontexten in der ersten Kombination behandelt werden können.
In einem weiteren Aspekt der Erfindung wird ein System zur Vereinigung von Datenstrukturen bereit gestellt, wobei das System umfasst: eine Verarbeitungseinrichtung; und eine Speichereinrichtung zum Speichern von Datenstrukturen, wobei die gespeicherten Datenstrukturen erste und zweite Merkmalsstrukturen enthalten; die Verarbeitungseinrichtung kopiert beim Vereinigen von Datenstrukturen Informationen von der ersten Merkmalsstruktur in die zweite Merkmalsstruktur; dadurch gekennzeichnet, dass die Verarbeitungseinrichtung erste Satzdaten aus der ersten Merkmalsstruktur in die zweite Merkmalsstruktur kopiert, wobei die ersten Satzdaten eine erste Kombination aus Kontexten darstellen; die Verarbeitungseinrichtung bestimmt ferner, ob die Satzdaten, die die gleiche Kombination von Kontexten wie die ersten Satzdaten repräsentieren, bereits in die zweite Merkmalsstruktur kopiert worden sind; und wenn dies der Fall ist, erzeugt die Verarbeitungseinrichtung zweite Satzdaten in der zweiten Merkmalsstruktur, wobei die zweiten Satzdaten die erste Kombination von Kontexten repräsentieren; die zweiten Satzdaten sind verborgene Satzdaten, die unabhängig von den Kontexten in der ersten Kombination behandelt werden können.
Im Folgenden wird die Erfindung beispielhaft mit Bezug zu den begleitenden Zeichnungen beschrieben; es zeigen:
Fig. 1 ein Beispiel einer kontextbezogenen Vereinigung in Fig. 7;
Fig. 2 zeigt ein Computersystem;
Fig. 3-6 zeigen ein weiteres Beispiel der kontextbezogenen Vereinigung;
Fig. 7 ist ein Diagramm der Softwareroutinen;
Fig. 8 ist ein Flussdiagramm der Hauptroutine in Fig. 7;
Fig. 9 ist ein Flussdiagramm der Prozessrandbedingungsroutine in Fig. 7;
Fig. 10 ist ein Flussdiagramm der "Copy AV Pair" Routine in Fig. 7;
Fig. 11 ist ein Flussdiagramm der "Expand Lazy Links" Routine in Fig. 7;
Fig. 12 ist ein Flussdiagramm der "Copy Facts" Routine in Fig. 7;
Fig. 13 ist ein Flussdiagramm der "Conjoin Clauses" Routine in Fig. 7;
Fig. 14 ist ein Flussdiagramm der "Import Clause" Routine in Fig. 7; und
Fig. 15 ist ein Flussdiagramm der "Get Edge Solutions" Routine in Fig. 7.
Fig. 2 zeigt ein Computersystem 30, das Verfahren für verborgene Sätze enthält. Instruktionen 60 ändern das Verhalten des Computersystems 30, und versetzen das System 30 in die Lage, kontextfrei Datenstrukturen mit der dritten Potenz der Zeit zu vereinigen. Kurz gesagt, die Instruktionen 60 reduzieren die Vereinigungsbearbeitungszeit durch Verwenden von verborgenen Sätzen bei der Verbindung von Sätzen. Das vorliegende Verfahren erlaubt bei Anwendung in Verbindung mit kontextbezogener Vereinigung und kontextbezogenen einfachen Verknüpfungen eine Vereinigung in der dritten Potenz der Zeit für die Teile der Grammatik, die kontextfrei oder dazu äquivalent sind.
Das Computersystem 30 umfasst einen Monitor 32 zur sichtbaren Darstellung von Information für einen Computeranwender. Das Computersystem 30 gibt ferner Informationen mittels Drucker an den Computeranwender aus. Das Computersystem 30 stellt dem Computeranwender diverse Dateneingabemöglichkeiten bereit. Eine Tastatur 34 sowie eine Maus 35 erlauben es dem Computeranwender, Daten manuell einzugeben. Der Computeranwender kann ebenso Informationen durch Schreiben mit einem Stift 38 auf eine elektronische Tafel eingeben. Alternativ kann der Computeranwender auf einem maschinenlesbaren Medium 40, etwa einer Diskette, gespeicherte Daten eingeben, indem die Diskette in das Laufwerk 42 eingeführt wird. Eine optische Zeichenerkennungseinheit (OCR-Einheit) 44 erlaubt es den Anwendern, ein umgangssprachliches Dokument 46 einzuspeisen, das in eine codierte elektronische Darstellung umgewandelt wird, typischerweise in einen amerikanischen Nationalstandardcode für Informationsaustausch (ASCII). Der Prozessor 48 steuert und koordiniert den Betriebsablauf des Computersystems 30, um die Befehle des Computeranwenders auszuführen. Der Prozessor 48 bestimmt eine entsprechende Aktion und nimmt diese vor in Reaktion auf jeden Befehl, indem elektronisch in einem Speicher, entweder dem Speicher 50 oder auf einer Diskette 40 in dem Diskettenlaufwerk 42 gespeicherte Instruktionen ausgeführt werden. Typischerweise sind Arbeitsinstruktionen für den Prozessor 48 in einem Festspeicher gespeichert, wodurch ein häufiger und schneller Zugriff auf die Instruktionen möglich ist. Der Speicher 50 umfasst ferner einen Cache-Speicher zum Speichern von Sätzen und eingeschränkten Lösungen. Zu Halbleiterspeicherbausteinen, die zur Verwirklichung des Speichers 50 verwendbar sind, gehören Nur-Lese-Speicher (ROM), Direktzugriffsspeicher (RAM), dynamische Direktzugriffsspeicher (DRAM), programmierbare Nur-Lese- Speicher (PROM), löschbare programmierbare Nur-Lese-Speicher (EPROM) und elektrisch löschbare programmierbare Speicher (EEPROM) etwa Flash-Speicher.
Das kontextbezogene Einfachkopieverfahren nutzt vorteilhafterweise die Tatsache, dass herkömmliche Lösungsansätze zur Analyse auf Vereinigung beruhender Grammatiken ein exponentielles Zeitverhalten zeigen, selbst wenn die modulierten linguistischen Erscheinungsformen kontextfrei sind. Das heißt, selbst wenn linguistische Erscheinungsformen darstellbar sind durch Verwendung einfacher Phrasierungsstrukturregeln, so dass ein Phrasierungsstrukturanalysator höchstens eine Zeit von der Ordnung O(n³) zur Analyse eines Satzes benötigt, wobei n die Länge des Satzes in Worten ist, benötigt ein standardmäßiger Merkmalsstrukturanalysator basierend auf Vereinigung, der den gleichen Satz moduliert, eine Zeit in der Ordnung O(2n). Ein Verständnis, warum das Hinzufügen von Merkmalsstrukturen so dramatisch die Analysezeit ansteigen lässt, erfordert ein Verständnis, wie kontextfreie Grammatik in der dritten Potenz der Zeit unter Verwendung einer Auflistung analysiert werden kann, und warum das Hinzufügen von Merkmalsstrukturen das resultierende System exponentiell macht, wenn die standardmäßigen Lösungsansätze angewendet werden.
Eine Auflistung bzw. Liste ist einfach eine Datenstruktur zur Aufzählung der Konstituenten, die bereits von einem Analysator gebildet worden sind. Der Hauptvorteil des Bereitstellens einer Auflistung besteht darin, dass der Analysator bestehende Konstituenten erneut verwenden kann, wenn er versucht, den Satz auf unterschiedliche Weisen zu analysieren. Wenn die Grammatik kontextfrei ist, muss der Analysator nicht wissen, wie die Konstituenten aufzubauen sind, sondern nur dass diese gebildet werden können.
Beispielsweise muss der Analysator wissen, ob es eine NP (Hauptwortphrase) gibt, die von dem fünften Wort zu dem zehnten Wort geht, aber er muss nicht wissen, ob die NP eine PP (präpositionale Phrase) darin aufweist. Aufgrund dessen gibt es lediglich unterschiedliche Konstituenten in der Ordnung O(Cn²), die für einen Satz mit der Längen konstruierbar sind, wobei C die Zahl der unterschiedlichen Kategorien darstellt, die die Grammatik zulässt. Das n² kommt von dem Kreuzprodukt aller möglichen Wortstellungen. Konzeptionell ist die Auflistung lediglich ein dreidimensionales Feld aus (Kategorie, linke Position, rechte Position), das anzeigt, ob es einen Konstituenten des Typs Kategorie gibt, der an der linken Position beginnt und an der rechten Position endet. Ein Satz besitzt eine Syntaktik, wenn es eine S-Kategorie gibt, die am Satzanfang beginnt und am Satzende endet. Eine Möglichkeit, die Auflistung auszuführen, besteht darin, mit allen Einwortkonstituenten zu beginnen und dann alle Zweiwortkonstituenten bilden, dann die Dreiwortkonstituenten usw., wobei jede Ebene auf den Ergebnissen der vorhergehenden Ebene aufbaut. Dies wird als CKY-Algorithmus bezeichnet. Der Grund dafür, dass der Algorithmus von der Ordnung On³ anstelle der Ordnung On² ist, besteht darin, dass jeder Konstituent auf viele Weisen gebildet werden kann. Im schlimmsten Falle kann ein Konstituent der Größenordnung On auf On-unterschiedliche Arten gebildet werden. Um On²-Konstituenten auf On-Weisen zu bilden, wird eine Zeit in der Größenordnung On³ benötigt. Der CKY-Algorithmus erfordert, dass die Konstituenten in einer speziellen Reihenfolge - von klein zu groß - gebildet werden. Eine flexiblere Weise zum Aufbau einer Auflistung besteht darin, eine Liste von Konstituenten beizubehalten, die noch nicht bearbeitet sind. Die Konstituenten werden aus der Liste herausgenommen und wie folgt verarbeitet. Jeder Konstituent schaut nach links und nach rechts nach Konstituenten, mit denen er kombiniert werden kann. Wenn ein Konstituent zur Kombination ermittelt worden ist, wird die Auflistung überprüft, um zu sehen, ob der resultierende Konstituent bereits in der Auflistung ist. Wenn dies nicht der Fall ist, dann wird der Konstituent der Auflistung hinzugefügt und auf der Liste platziert. Dann geht der Prozess weiter bis die Liste leer ist. Die Liste ermöglicht ein flexibleres Vorgehen, da Konstituenten in beliebiger Reihenfolge aus der Liste herausgenommen werden können. Diese Art des Analysators wird als "aktiver Listenanalysator" bezeichnet.
Die vorhergehenden Algorithmen bestimmen lediglich, ob ein Satz analysierbar ist oder nicht, sie bestimmen nicht, welche die gültigen syntaktischen Baumstrukturen sind. Diese Information kann jedoch durch einfache Additionen dieser Algorithmen erhalten werden. Immer wenn ein Konstituent aus Teilkonstituenten aufgebaut ist, wird der Aufbau als eine fokale Teilstruktur in dem Konstituent, der gebildet wurde, aufgezeichnet. Eine mit derartigen Teilstrukturen gekennzeichnete Auflistung wird als ein "syntaktischer Wald" bezeichnet. Wenn der Analysator fertig ist, kann eine spezielle syntaktische Struktur ausgelesen werden, indem bei dem S-Konstituenten begonnen wird, der den gesamten Satz überspannt und indem eine Teilstruktur zufällig ausgewählt wird. Dann wird für jeden Tochterkonstituenten eine Teilstruktur zufällig gewählt. Dieser Prozess wird ausgeführt bis die Baumstruktur vollständig spezifiziert ist. Im Allgemeinen können exponentiell viele solcher vollspezifizierter Baumstrukturen vorhanden sein, aber der syntaktische Wald dafür kann in der dritten Potenz der Zeit erzeugt werden, da diese in einer kompakten Darstellung gespeichert sind.
Viele grammatikalische Formalismen fügen Merkmalsstrukturen zu einem Gerüst aus kontextfreien Phrasenstrukturregeln hinzu. Abhängig von der Grammatik können die kontextfreien explizit oder implizit sein.
Ein standardmäßiger Ansatz zur Analyse von Merkmalsstrukturen, unabhängig, ob die kontextfreien Regeln explizit oder implizit sind, besteht darin, zunächst eine kontextfreie Phrasenstrukturauflistung zu bilden und dann einen zweiten Durchlauf mit der Auflistungsdatenstruktur zu absolvieren, wobei Merkmalsstrukturen von unten nach oben gebildet werden. Zunächst werden Merkmalsstrukturen beispielhaft aus lexikalischen Begriffen gemäß den vorgegebenen Merkmalsbedingungen erstellt. Wenn die lexikalischen Begriffe in irgendeiner Weise zweideutig sind, ergibt dies viele Merkmalsstrukturen. Anschließend werden Merkmalsstrukturen für einen Mutterkonstituenten aufgebaut, indem das Kreuzprodukt der Merkmalsstrukturen genommen wird, die zu den Tochterkonstituenten gehören. Das Kreuzprodukt wird verwendet, um Kombinationen auszufiltern, die inkonsistent sein können. Das Ergebnis ist ein Satz an Merkmalsstrukturen, die bis hierhin konsistent sind. Wenn es mehr als eine Art des Aufbaus des Mutterkonstituenten aus den Tochterkonstituenten gibt, dann werden die Sätze der Merkmalsstrukturen, die aus den gesamten Analysen erzeugt werden, zusammen vereinigt. Dieser Prozess wird von unten nach oben fortgesetzt, bis Merkmalsstrukturen für alle Konstituenten gebildet worden sind.
Dieser Prozess ist aufgrund des Kreuzproduktes, das in jeder Ebene auftritt, im schlimmsten Falle exponentiell. Wenn beispielsweise jeder lexikalische Begriff auf zweifache Art mehrdeutig ist, kann es selbst, wenn die Phrasenstrukturgrammatik eindeutig ist, für den obersten Konstituenten unterschiedliche Merkmalsstrukturen von der Ordnung O(2") geben. Wenn lediglich Merkmale mit begrenzten Werten verwendet werden, kann ein Analysator so erstellt werden, um in der dritten zeitlichen Potenz zu arbeiten. Dies liegt daran, dass lediglich eine begrenzte Anzahl an Merkmalsstrukturen möglich sind, und dass auf jeder Ebene lediglich verfolgt werden muss, welche dieser Strukturen möglich ist, ohne alle Möglichkeiten aufzuzählen, mit denen diese erhalten wurden. Wenn die obere Grenze der Anzahl der möglichen Merkmalsstrukturen erreicht ist, hört die Anzahl der Merkmalsstrukturen in jeder Ebene auf zu wachsen. Wenn alle Merkmalswerte binär sind, so kann der Konstituent der obersten Ebene höchstens von der Ordnung O(2k) unterschiedliche Merkmalsstrukturen aufweisen, wobei k die Anzahl der unterschiedlichen Merkmale ist. Somit kann man ein Exponentialverhalten der Satzlänge in eine exponentielle Grammatikkonstante unter Anwendung lediglich finiter Merkmalsgraphen umwandeln. Leider kann die zur Analyse nicht finiter Merkmalsstrukturen erforderliche Zeit nicht in der gleichen Weise reduziert werden.
Die hierin beschriebenen Verfahren reduzieren die zur Vereinigung von Merkmalsstrukturen während des Analysierens und des Erzeugens erforderliche Zeit durch Einführen kontextbezogener einfacher Kopierverbindungen. Diese neue Art einer einfachen Kopierverbindung ermöglicht es, dass viele alternative Werte als viele kontextbezogene einfache Kopierverbindungen dargestellt werden können, wobei jede mit den Kontextstellen, in denen diese gültig ist, gekennzeichnet worden ist. Die durch diese kontextbezogenen Einfachkopierverbindungen dargestellten Daten werden nicht in eine grafische Datenstruktur kopiert, solange diese nicht relevant sind, und werden allmählich entwickelt, um sicherzustellen, dass lediglich die notwendige Information kopiert wird. Kontextbezogene einfache Kopierverknüpfungen reduzieren, wenn sie in Zusammenhang mit kontextbezogener Vereinigung und verborgenen Kontexten verwendet werden, die zur Vereinigung von Merkmalsstrukturen erforderliche Zeit. Folglich wird das vorliegende Verfahren detailliert mit Bezug zu den Fig. 11 und 12 und als ein Teil eines Verfahrens zur Vereinigung kontextfreier Merkmalsstrukturen in der dritten Potenz der Zeit beschrieben.
Ein Beispiel einer kontextbezogenen Vereinigung mit einfachem kontextbezogenen Kopieren ist hilfreich in der folgenden detaillierten Erläuterung von Anweisungen 60 zum Ausführen einer kontextbezogenen Vereinigung mit kontextbezogenen einfachen Kopierverknüpfungen. Es ist daher Fig. 3 zu betrachten, die einen Rand 70 und dessen beide Tochterränder 72 und 82 darstellt. Die Tochter 72 startet mit einem leeren Graphen 74 mit kontextbezogenen einfachen Kopierverknüpfungen, die mittels gestrichelter Linien gekennzeichnet sind, und die zu alternativen vollspezifizierten Graphen 75, 76, 78 und 80 zeigen. Zu beachten ist, dass jede einfache Kopierverknüpfung mit einem Kontext p : 1, p : 2, p : 3 und p : 4 gekennzeichnet ist, von denen jeder eine sich gegenseitig ausschließende Auswahl repräsentiert. Die Situation der Tochter 82 ist analog zu jener der Tochter 72.
Die Vereinigung von Graphen 74 und 84 beginnt mit der Erzeugung eines leeren Graphen 71 und der Zuordnung kontextbezogener einfacher Kopierverknüpfungen vom Graphen 71 zu den Graphen 74 und 84. Diese kontextbezogenen einfachen Kopierverknüpfungen sind fettgedruckt, um anzuzeigen, dass eine Wechselwirkung zwischen den einfachen Kopierverknüpfungen erkannt worden ist, und dass der Graph 71 zu entwickeln bzw. erweitern ist, was wiederum eine Erweiterung der Tochtergraphen 74 und 84 erfordert.
Fig. 4 zeigt die Graphen 71, 74 und 84 nach der erforderlichen Entwicklung bzw. Erweiterung. Der Tochtergraph 84 wurde erweitert, indem die erste Ebene der alternativen Graphen 86, 88, 90 und 92 kopiert wurde. Als Folge davon ist der Graph 84 nicht mehr leer und enthält nunmehr die Attribute A, C und D. Die Werte dieser Attribute sind mittels mehrfacher kontextbezogener einfacher Kopierverknüpfungen gekennzeichnet, die zu Werten innerhalb der Merkmalsstrukturen 86, 88, 90 und 92 zeigen. Anzumerken ist, dass, obwohl das Attribut C Werte lediglich in den Kontexten q : 1 und q : 2 und das Attribut D Werte lediglich in den Kontexten q : 3 und q : 4 annehmen, ein einzelner Graph 84 erzeugt werden kann, der alle diese sich gegenseitig ausschließenden Alternativen repräsentiert. Der Tochtergraph 74 wird in einer ähnlichen Weise erweitert. Anschließend wird der Graph 71 erweitert, indem in diesen die Attribute der ersten Ebene der Graphen 74 und 84 A, B, C und D mit den kontextbezogenen einfachen Kopierverknüpfungen kopiert werden, die zu den alternativen Werten für diese Attribute zeigen. Das Fettdrucken der kontextbezogenen einfachen Kopierverknüpfungen, die mit dem Attribut A verknüpft sind, zeigt an, dass diese wechselwirken. Somit muss das Attribut A des Graphen 71 erweitert werden, was bedeutet, dass die Attribute A der Graphen 74 und 84 ebenso erweitert werden müssen.
Fig. 5 zeigt die Graphen 71, 74 und 84 nach der Erweiterung ihrer Attribute A. Im Graphen 74 ersetzt diese Erweiterung die kontextbezogenen einfachen Kopierverknüpfungen durch zwei Kontextwertepaare. Das Attribut A nimmt den Wert + an, wenn der Kontext p : 1, p : 2 oder p : 3 WAHR ist. Andererseits nimmt das Attribut A den Wert - an, wenn der Kontext p : 4 WAHR ist. Im Gegensatz zum Graphen 74 ergibt die Erweiterung des Attributs A im Graphen 84 einen einzelnen nicht kontextbezogenen Wert, da das Attribut A den gleichen Wert in allen Kontexten, die mit der Merkmalsstruktur 84 verknüpft sind, annimmt. Die Vereinigung der Attribute A der Graphen 74 und 84 führt zu zwei Kontextwertepaaren für das Attribut A des Graphen 71. Ein Kontextwertepaar gibt an, dass A = + in allen Kontexten ist, während das andere Kontextwertepaar angibt, dass A = - in Kontext p : 4 ist. Diese zwei Kontextwertepaare führen zu dem Nogood p : 4, da das Attribut A nicht gleichzeitig die Werte + und - annehmen kann.
Nach Ausführung aller Vereinigungen wird die Nogood-Datenbank verwendet, um die möglichen Lösungen für die Liste zu bestimmen. Das naive Kombinieren der Nogoods kann zu einer exponentiellen Bearbeitungszeit führen, um die Lösungen für die Liste zu ermitteln. Wenn ferner präpositionale Variablen von den Töchtern zu ihren Müttern herauskopiert werden, können diese präpositionalen Variablen die Baumstruktur codieren, und dabei die Kontextfreiheit verletzen und eine exponentielle Bearbeitungszeit erfordern. Um diese Probleme zu vermeiden, werden neue verborgene präpositionale Variablen in jeder Ebene eingeführt. Diese präpositionalen Variablen werden "verborgen" bezeichnet, da ihre interne Struktur nicht in der höheren Ebene verfügbar ist, in die sie importiert werden. Der Vorgang des Verbergens einer präpositionalen Variablen vor dem Importieren wird als Einhüllen bezeichnet. Die Nogood-Datenbank wird dann lokal hinsichtlich der verborgenen Variablen, die von unterhalb importiert werden, gelöst. Wenn die Grammatik kontextfrei oder äquivalent dazu ist, wird die Anzahl der verborgenen Variablen beschränkt, wodurch die Nogood-Datenbank lokal hinsichtlich der verborgenen Variablen, die von unterhalb importiert werden, gelöst werden kann.
Im Allgemeinen besitzt jeder Tochterkonstituent einen Satz verborgener Variablen, die durch den Import der zur Konstruktion eines Mutterkonstituenten verwendeten Teilbaumstruktur importiert worden sind. Lösungen, die die Werte WAHR oder FALSCH zuordnen, können für diese verborgenen Variablen unter Verwendung der Nogood- Datenbank ermittelt werden. Diese Lösungen werden gefunden, indem das Kreuzprodukt der Tochterlösungen verwendet wird, die dann durch die lokalen Nogoods gefiltert werden. Wenn es mehrere Teilbaumstrukturen gibt, dann wird der Kontext der lokalen Baumteilstruktur zu jeder Lösung hinzu addiert. Für jede Lösung werden die verborgenen Variablen des Mutterkonstituenten ermittelt, um zu bestimmten, ob die lokale Lösung der Baumteilstruktur die verborgenen Variablen als WAHR oder FALSCH kennzeichnet. Jede derartige Zuordnung wird eine Lösung für die verborgenen Variablen der Mutter. Es können mehrere lokale Lösungen für jede Wertezuweisung der verborgenen Variablen der Mutter existieren. Dies ist analog zu der Existenz mehrerer Baumteilstrukturen für jeden Konstituenten in einem kontextfreien Analyse-"Wald", wobei der "Konstituent" in diesem Falle ein gewisser Satz der Merkmalswertkombinationen ist.
Fig. 6 zeigt die Lösung der Liste, die in den Fig. 3 bis 5 erläutert ist. Die Tochtermerkmalsstruktur 74 besitzt zwei verborgene Variablen: O1 und O2. Im Gegensatz dazu besitzt die Tochtermerkmalsstruktur 84 keine verborgenen Variablen, da keiner ihrer Kontexte exportiert wird. Diese Situation erzeugt zwei externe Lösungen für die Tochter 72. O1 O2 und O2 O1. Die O1 O2-Lösung repräsentiert drei innere Lösungen: p1, p2 und p3. Die O2 O1-Lösung repräsentiert lediglich die innere Lösung p : 4. Die Tochtermerkmalsstruktur 84 erzeugt genau eine externe Lösung in dem WAHR-Kontext, die vier interne Lösungen repräsentiert. Lösungen für den Mutterrand 70 werden so aufgebaut, indem das Kreuzprodukt der externen Lösungen, die von den Tochterrändem 72 und 82 importiert werden, verwendet werden, und diese Lösungen durch das lokale Nogood 02 gefiltert werden. Dies erzeugt eine interne Lösung O1 O2 für den Rand 70, die mit der externen Lösung WAHR verknüpft ist. Die internen Lösungen jeder Mutter werden verwendet, um die daraus stammenden Tochterlösungen zu verfolgen, um das Nummerieren der Lösungen zu erleichtern.
Fig. 7 zeigt schematisch die Instruktionen 60 für eine einfache kontextbezogene Vereinigung von Merkmalsstrukturen, während eine Sprachzeichenkette analysiert oder erzeugt wird. Die Instruktionen 60 können in maschinenlesbarer Form in einem Speicherelement 50 oder einer Diskette 42, die in dem Diskettenlaufwerk 40 angeordnet ist, gespeichert sein. Die Instruktionen 60 können durch eine beliebige Computersprache einschließlich Prolog, LISP und C++ realisiert sein.
Die Instruktionen 60 sind als ein hierarchischer Satz aus Unterroutinen 100, 102, 104, 106, 108, 110, 112 und 116 organisiert. Die Hauptroutine 100 steuert das Analysieren der Zeichenkette durch Aufrufen von Process Edge Constraints 102 und Get Edge Solutions 104. Process Edge Constraints 102 nimmt die jedem Rand zugewiesenen Nebenbedingungen und erzeugt Randdatenstrukturen für jeden Rand. Dabei ruft das Unterprogramm 102 Copy AV Pairs 106 auf. Das Unterprogramm 106 übernimmt das Kopieren von Attributwertepaaren von einem Graph zu einem anderen durch Aufrufen der Unterprogramme 108 und 110. Expand Lazy Links 108 entwickelt bzw. erweitert eine kontextbezogene einfache Kopierverknüpfung durch Aufwärtskopieren um eine Attributebene und Hinzufügen einer neuen kontextbezogenen einfachen Kopierverknüpfung für jedes kopierte Attribut. Copy Facts 110 kopiert Attribute von einem Graphen in einen anderen. Dabei ruft das Unterprogramm 110 Conjoin Clauses 112 auf. Conjoin Clauses 112 verbindet zwei Kontexte oder Sätze, um einen neuen Satz zu erzeugen, der gegebenenfalls verborgen sein kann. Import Clause 116 erzeugt verborgene Sätze, wenn ein Satz in einen Graphen importiert wird. Schließlich nimmt Get Edge Solutions 104 die durch das Unterprogramm 102 erzeugten Merkmalsstrukturen und bestimmt mögliche Lösungen für den zugrundeliegenden generierenden Rand.
Die folgende detaillierte Diskussion der Instruktionen 60 wird durch die Kenntnis der verwendeten Datenstrukturen erleichtert, die in dem Speicher 50 gespeichert sind. In den Instruktionen 60 werden vier Klassen von Datenstrukturen verwendet: Listen-, Graphen-, Satz- und Lösungsdatenstrukturen. Listendatendatenstrukturen schließen Randdatenstrukturen und Baumdatenteilstrukturen mit ein. Jede Randdatenstruktur repräsentiert einen Rand und beinhaltet die folgende Information: Rand
Jede Baumdatenteilstruktur repräsentiert eine Baumteilstruktur in Chomsky Normalform und enthält die folgenden Informationen: Subtree
Zu beachten ist, dass jede Teildatenbaumstruktur lediglich zwei Töchter enthält, "partial" und "complete", obwohl konzeptionell kontextfreie Regeln eine beliebige Anzahl von Töchtern pro Baumteilstruktur zulassen. Die Anwendung einer standardmäßigen Transformation in eine Grammatik erzeugt eine neue Grammatik, in der alle Regeln binär sind. Durch beispielsweise Anwenden dieser Transformation auf die Regel S→NP VP ADV werden zwei Regeln erzeugt S→S1 ADV und S1→NP VP.
Die Klasse der grafischen Datenstrukturen enthält drei Typen: Graph, AVPair und CVPair. Jede grafische Datenstruktur repräsentiert eine Merkmalsstruktur und damit verknüpfte Information und umfasst die folgende Information: Graph
Jede AVPaar-Datenstruktur repräsentiert ein Wertepaar im Kontext zu einem Attribut und umfasst die folgende Information: AVPaar
Jede CV-Paar-Datenstruktur repräsentiert ein Kontextwertepaar und umfasst die folgende Information: CVPaar
Es gibt zwei Arten von Satzdatenstrukturen: Satz und Disjunktion. Jede Satzdatenstruktur repräsentiert einen Satz und besitzt ihren eigenen Satzspeicher, der eine Liste aus Speicherbegriffen ist. Eine Satzdatenstruktur umfasst die folgende Information: Clause bzw. Satz:
Jede Disjunktionsdatenstruktur repräsentiert eine Disjunktion und umfasst die folgende Information: Disjunction
Es gibt drei Arten von Lösungsdatenstrukturen: Restriktionssatz- bzw. mengen, eingeschränkte Lösungs- und interne Lösungsdatenstrukturen. Jeder Graph besitzt einen Lösungsspeicher in dem Speicher 50, der die drei Lösungsdatenstrukturen des Graphen speichert.
Jede Restriktionsmengendatenstruktur repräsentiert eine Ansammlung aus Sätzen, für die Lösungen gesucht werden, und umfasst die folgende Information: Restriktionsmenge
Jede interne Lösungsdatenstruktur repräsentiert interne Lösungen für eine Restriktionsmenge und umfasst die folgende Information: Internat Solution bzw. Interne Lösung
Fig. 8 zeigt ein Flussdiagramm der Anweisungen von Main 100. Kurz gesagt, Main 100 bildet eine Liste für eine umgangssprachliche Zeichenkette, prozessiert die Rahmenbedingungen und bildet grafische Datenstrukturen für die Liste von unten nach oben. Nach Ermitteln der grafischen Merkmalsstruktur für den den Ursprung umspannenden Rand ermittelt der Prozessor 48 Lösungen für diesen Rand.
Nach Erhalt einer umgangssprachlichen Zeichenkette in maschinenlesbarer Form beginnt der Prozessor 48 mit der Ausführungen der Instruktionen 100 mit dem Schritt 120. Während des Schritts 120 bildet der Prozessor 48 eine kontextfreie Analyse-Wald- Struktur, d. h. eine Liste für diese umgangssprachliche Zeichenkette. Es werden standardmäßige Verfahren, die dem Fachmann bekannt sind, angewendet, um diese Liste zu bilden. Nach Bildung der Liste verlässt der Prozessor 48 den Schritt 120 und geht zum Schritt 122 weiter.
Während des Schritts 122 bestimmt der Prozessor 48, ob die Liste eine Zeichenkette D definiert, die die gesamte umgangssprachliche Zeichenkette aufspannt. Wenn die Liste dies nicht tut, dann besitzt sie keine Lösung, und der Prozessor 48 verzweigt zum Schritt 124. Wenn andererseits die Liste ein S definiert, das die gesamte umgangssprachliche Zeichenkette aufspannt, dann kann die Liste eine Lösung besitzen. Daraufhin geht der Prozessor 48 vom Schritt 122 zum Schritt 126 weiter. Während des Schritts 126 fügt der Prozessor 48 die lexikalischen und grammatikalischen Bedingungen, die mit der verwendeten Grammatik verknüpft sind, der Liste hinzu. Standardmäßige Verfahren zur Ausstattung der Liste werden dabei angewendet. Nach der Ausstattung der Liste verlässt der Prozessor 48 den Schritt 126 und geht zum Schritt 128 weiter.
Der Prozessor 48 ermittelt Lösungen für den Ursprung aufspannenden Rand der Liste während des Schritts 128 mittels rekursivem Aufrufen von "Process Edge Constraints" 102 und durch Bilden von grafischen Datenstrukturen für die Liste. Diese rekursiven Aufrufe bewirken, dass der Prozessor 48 die Liste abarbeitet, bis ein Punkt erreicht ist, an dem der Prozessor 48 beginnt, grafische Datenstrukturen zu bilden und sich wieder nach oben in der Liste bewegt. "Process Edge Constraints" 102 wird später detailliert mit Bezug zu Fig. 9 beschrieben. Nachdem der Prozessor 48 die grafischen Datenstrukturen für die Liste erzeugt hat, geht der Prozessor vom Schritt 128 zum Schritt 130 weiter und beginnt damit, eine Lösung für die Liste zu ermitteln. Dies bewerkstelligt der Prozessor 48, indem "Get Edge Solutions" 104 aufgerufen wird. Der Prozessor 48 findet Lösungen für den Ursprung aufspannenden Rand, indem er sich in der Liste nach unten bewegt, verborgene interessierende Kontexte nach unten weiterreicht, bis eine Verzweigung erreicht ist. An diesem Punkt beginnt der Prozessor 48 damit, lokale Lösungen für verborgene Kontexte zu bestimmen, die importiert worden sind, und diese Lösungen in der Liste nach oben weiterzureichen. Dies wird fortgesetzt, bis für den den Ursprung aufspannenden Rand der Liste Lösungen gefunden worden sind.
Das Prozessieren von Randlösungen mittels Instruktionen 104 geschieht in der dritten Potenz der Zeit für kontextfreie Teile der Grammatik. Die Kontextfreiheit bewirkt, dass lokale Nogoods in einfacher Weise in Faktoren zerfallen. Obwohl daher die Zeit für die Lösungsberechnung exponentiell zu der Anzahl der verborgenen Variablen K ist, so zeigt die Erfahrung dennoch, dass die Anzahl der tatsächlich erzeugten Lösungen tendenziell klein ist. Nach Ausführen der Anweisungen 104 verlässt der Prozessor 48 den Schritt 130 und verzweigt zum Schritt 124, wobei das Verarbeiten der umgangssprachlichen Zeichenkette abgeschlossen ist.
Die Routine "Process Edge Constraints" 102, die in Fig. 9 dargestellt ist, ermöglicht es dem Prozessor 48, eine grafische Datenstruktur für einen Rand zu erzeugen, wobei ein Zeiger für den relevanten Rand gegeben ist. Kurz gesagt, da jede grafische Datenstruktur alle alternativen Möglichkeiten repräsentiert, aus denen der Rand konstruierbar ist, beginnen die Anweisungen 102 damit, dass eine grafische Datenstruktur, die mit dem Rand verknüpft ist, in den Schritten 150 bis 188 erzeugt wird. Um eine grafische Datenstruktur für einen Rand zu erzeugen, werden zunächst grafische Datenstrukturen für jede Tochter der Baumteilstruktur in den Schritten 154 bis 164 erzeugt. Damit werden grafische Datenstrukturen für jede Baumteilstrukturen in den Schritten 166 bis 186 erzeugt, und mit diesen wird schließlich eine grafische Datenstruktur für den Rand während der Schritte 190 bis 212 geschaffen.
In Reaktion auf den Empfang eines Zeigers auf einen ausgewählten Rand beginnt der Prozessor 48 mit der Ausführung der Anweisungen 102 im Schritt 140. Während des Schritts 140 bestimmt der Prozessor 48, ob eine grafische Datenstruktur konstruiert werden muss, indem der eben empfangene Zeiger untersucht wird. Ein Nullzeiger zeigt an, dass der ausgewählte Rand nicht existiert, da dieser vielleicht aus einer Baumteilstruktur stammt, die keinen partialen Rand aufweist. In Reaktion auf einen Nullrandzeiger verzweigt der Prozessor 48 vom Schritt 140 zum Schritt 142. Während des Schritts 142 zeigt der Prozessor 48 an, dass der ausgewählte Rand WAHR ist, d. h., dass dieser mit einem anderen Rand kombinierbar ist, indem der in dem grafischen Feld der ausgewählten Randdatenstruktur gespeicherte Zeiger auf einen Wert von 0 gesetzt wird. Danach kehrt der Prozessor im Schritt 144 zu der aufrufenden Routine zurück.
Wenn der Randzeiger nicht 0 ist, verzweigt der Prozessor 48 vom Schritt 140 in den Schritt 150. Im Schritt 150 beschäftigt sich der Prozessor 48 mit dem Aufbau einer grafischen Datenstruktur für den ausgewählten Rand. Um dies zu bewerkstelligen, muss der Prozessor 48 zunächst grafische Datenstrukturen für jede mit dem ausgewählten Rand verknüpfte Baumteilstruktur erzeugen. Somit bestimmt der Prozessor 48 während des Schritts 150, ob es Baumteilstrukturen gibt, für die eine grafische Datenstruktur erzeugt werden sollte. Solange es welche gibt, geht der Prozessor vom Schritt 150 zum Schritt 152 weiter.
Der Prozessor 48 wählt eine der verbleibenden Baumteilstrukturen als die ausgewählte Baumteilstruktur während des Schritts 152 und geht dann zum Schritt 154 weiter. Der Prozessor 48 erzeugt eine grafische Datenstruktur für die ausgewählte Baumteilstruktur, indem zunächst grafische Datenstrukturen für die linke Tochter und die rechte Tochter erzeugt werden. Somit schafft der Prozessor 48 während des Schritts 154 eine grafische Datenstruktur für die linke Tochter der ausgewählten Baumteilstruktur durch rekursives Aufrufen von "Process Edge Constraints" 102 und durch Kennzeichnen der linken Tochter als den ausgewählten Rand. Nach Erzeugung einer grafischen Datenstruktur für die linke Tochter der ausgewählten Baumteilstruktur verlässt der Prozessor 48 den Schritt 154 und geht zum Schritt 156 weiter.
Während des Schritts 156 bestimmt der Prozessor 48, ob der Graph für die linke Tochter ein Nogood ist. Der Prozessor 48 führt diese Bestimmung aus, indem das Nogood- Feld der grafischen Datenstruktur für die linke Tochter untersucht wird, oder wenn der Zeiger zu dem Graphen der Nogood-Wert ist; d. h. 1 ist. Wenn der Graph ein Nogood ist, dann ist der Graph für die ausgewählte Baumteilstruktur ebenfalls ein Nogood. In diesem Falle schreitet der Prozessor 48 zum Schritt 160 weiter und erzeugt eine nogood-grafische Datenstruktur für die ausgewählte Baumteilstruktur. Danach kehrt der Prozessor 48 zum Schritt 150 zurück. Wenn andererseits der Graph für die linke Tochter kein Nogood ist, dann verlässt der Prozessor 48 den Schritt 156 und geht zum Schritt 162 weiter.
Der Prozessor 48 ist dann mit der Erzeugung einer grafischen Datenstruktur für die rechte Tochter der ausgewählten Baumteilstruktur während des Schritts 162 beschäftigt. Der Prozessor 48 vollführt diese Aufgabe, indem "Process Edge Constraints" 102 aufgerufen wird und indem angezeigt wird, dass die rechte Tochter der ausgewählte Rand ist. Danach bestimmt der Prozessor 48, ob die grafische Datenstruktur im Schritt 164 nogood ist oder nicht. Wenn dies der Fall ist, kehrt der Prozessor 48 zum Schritt 160 zurück. Wenn nicht, verlässt der Prozessor 48 den Schritt 164 und geht zum Schritt 166 weiter.
Nach dem Erzeugen grafischer Datenstrukturen für die linke und die rechte Tochter der ausgewählten Baumteilstruktur beginnt der Prozessor 48 den Vorgang des Aufbaus einer grafischen Datenstruktur für die ausgewählte Baumteilstruktur während des Schritts 166. Bei diesem Vorgang liegt die erste Aufgabe darin, grammatische Bedingungen, die mit der ausgewählten Baumteilstruktur verknüpft sind, in eine grafische Datenstruktur umzuwandeln. Anschließend speichert während des Schritts 168 der Prozessor 48 einen Zeiger zu der grafischen Datenstruktur, die unmittelbar vorher geschaffen worden ist, in dem grafischen Feld der Baumteildatenstruktur der ausgewählten Baumteilstruktur. Dann geht der Prozessor 48 zum Schritt 180 weiter.
Während des Schritts 180 beginnt der Prozessor 48 damit, Bedingungen in die ausgewählte Baumteilstruktur aufzunehmen, die durch die linke Tochter auferlegt sind. Der Prozessor 48 vollführt dies, indem "Copy AVPair" 106 aufgerufen wird, die ein AVPaar pro Zeiteinheit kopiert, wie dies später detailliert beschrieben wird. Anschließend bestimmt im Schritt 182 der Prozessor 48, ob dies bewirkt, dass die grafische Datenstruktur der ausgewählten Baumteilstruktur ein Nogood ist. Wenn ja, kehrt der Prozessor 48 zum Schritt 150 zurück. Bei nein, verlässt der Prozessor 48 den Schritt 182 und geht zum Schritt 184 weiter.
Der Prozessor 48 nimmt in die ausgewählte Baumteilstruktur im Schritt 184 auf, die durch die rechte Tochter auferlegt sind. Der Prozessor 48 erledigt dies, indem wiederum "Copy AVPair" 106 aufgerufen wird. Der Prozessor 48 bestimmt dann im Schritt 186, ob diese Bedingungen den Graphen der ausgewählten Baumteilstruktur zu einem Nogood machen. Wenn ja, kehrt der Prozessor 48 zum Schritt 160 zurück. Wenn der Graph kein Nogood ist, kehrt der Prozessor 48 vom Schritt 186 zum Schritt 150 zurück.
Der Prozessor 48 durchläuft die Schritte 150 bis 186, solange es grafische Datenstrukturen gibt, die für die mit dem ausgewählten Rand verknüpften Baumteilstrukturen zu erzeugen sind. Wenn alle grafischen Baumteildatenstrukturen erzeugt worden sind, verlässt der Prozessor 48 den Schritt 150 und verzweigt zum Schritt 188, um den Vorgang des Erzeugens einer einzelnen grafischen Datenstruktur für den ausgewählten Rand, der jeweils Baumteilstrukturen, die nicht Nogoods sind, repräsentiert, zu erzeugen. Der Prozessor 48 zählt zunächst die Anzahl der mit dem ausgewählten Rand verknüpften Baumteilstrukturen, die keine Nogood-(d. h. "gute")Graphen aufweisen, während des Schritts 188. Anschließend bestimmt im Schritt 190 der Prozessor 48, ob die Anzahl der Baumteilstrukturen mit guten Graphen größer oder gleich 2 ist. Wenn diese Anzahl kleiner als 2 ist, bestimmt der Prozessor 48 im Schritt 192, ob es zumindest eine Baumteilstruktur mit einem guten Graphen gibt. Wenn es eine Baumteilstruktur mit einem guten Graphen gibt, geht der Prozessor 48 zum Schritt 193 weiter und speichert einen Zeiger zu der grafischen Datenstruktur für die gute Baumteilstruktur in dem grafischen Feld der Randdatenstruktur des ausgewählten Randes. Wenn andererseits nicht einmal eine Baumteilstruktur mit einem guten Graphen vorliegt, dann verlässt der Prozessor 48 den Schritt 192 und geht zum Schritt 194 weiter. Der Prozessor 48 verwendet dann das grafische Feld der ausgewählten Randdatenstruktur, um anzuzeigen, dass der Rand nogood ist, indem ein Zeigerwert von 1 gespeichert wird. Nach Fertigstellung des Aufbaus einer grafischen Datenstruktur für den ausgewählten Rand während des Schritts 194 oder 193 geht der Prozessor 48 zum Schritt 144 weiter.
Der Prozessor 48 geht zum Schritt 196 weiter, wenn die Anzahl der Baumteilstrukturen mit guten Graphen größer oder gleich 2 ist. In diesem Falle ist die grafische Datenstruktur des ausgewählten Rands ein ODER-Typ, da dieses mehrere alternative Baumteilstrukturen repräsentiert. Daher markiert der Prozessor 48 während des Schritts 196 den Graphen als einen ODER-Typ durch geeignetes Festlegen des disjunkten Feldes der ausgewählten Randdatenstruktur. Danach verlässt der Prozessor 48 den Schritt 196 und geht zum Schritt 198 weiter.
Während des Schritts 198 bildet der Prozessor 48 Disjunktionsdatenstrukturen für den ODER-Satz, der zuvor im Schritt 196 erzeugt wurde. Der Prozessor 48 setzt das Zählerfeld der Disjunktionsdatenstruktur auf die Anzahl der guten Graphen fest, die während des Schritts 188 gezählt wurden. Der Prozessor 48 schließt dann den Aufbau der Disjunktionsdatenstruktur ab, wodurch kontextbezogene Variablen erzeugt werden, um jede der guten Baumteilstrukturen zu repräsentieren, die mit dem ausgewählten Rand verknüpft sind. Danach geht der Prozessor 48 zum Schritt 200 weiter.
Mit dem Schritt 200 beginnt der Prozessor 48 mit dem Aufnehmen von Informationen von den Baumteilstrukturen in die grafische Datenstruktur für den ausgewählten Rand. Der Prozessor 48 verzweigt zu der Schleife aus den Schritten 200, 210 und 212, bis die Information aus allen guten Baumteilstrukturen in die ausgewählte Randdatenstruktur mit aufgenommen ist. Während des Schritts 210 wählt der Prozessor 48 eine der Baumteilstrukturen mit einem guten Graphen aus und ermittelt den mit der Baumteilstruktur verknüpften Kontext mittels der Disjunktionsdatenstruktur aus. Der Prozessor 48 kopiert dann in die ausgewählte Randdatenstruktur Information aus der ausgewählten Baumteilstruktur hinauf, indem "Copy AVPairs" 106 aufgerufen und der ausgewählte Satz im Schritt 212 gekennzeichnet wird. Danach kehrt der Prozessor 48 zum Schritt 200 zurück. Nach dem Kopieren von Information aus allen Baumteilstrukturen mit guten Graphen in die grafische Datenstruktur für den ausgewählten Rand kehrt der Prozessor 48 zum Schritt 144 zurück.
Die Routine "Copy AVPair" 106, die in Fig. 10 dargestellt ist, erlaubt es dem Prozessor 48, Informationen aus einer Quellen-AVPaar-Datenstruktur in eine Empfänger-AVPaar- Datenstruktur zu kopieren. Es werden die Instruktionen 106 angewendet, um Informationen von Töchtern in ihre Mutter zu kopieren, sowie Informationen von Baumteilstrukturen in deren zugehörigen Rand zu kopieren. Kurz gesagt, die Instruktionen 106 versuchen, das Kopieren von Informationen zu vermeiden, indem dem Empfänger-AVPaar kontextbezogene einfache Kopierverknüpfungen hinzugefügt werden, die zurück zu dem Quellen-AVPaar zeigen. Wenn die relevante Information bereits durch eine kontextbezogene Kopierverknüpfung repräsentiert ist, dann kopiert der Prozessor 48 die erste Ebene an Informationen von der Quelle zu dem Empfänger-AVPaar mittels Aufrufen von "Expand Lazy Links" 108 und "Copy Facts" 110.
Der Prozessor 48 beginnt das Ausführen der Instruktionen 106 in Reaktion auf einen Zeiger zu dem Quellen-AVPaar, dem Empfänger-AVPaar und einem ausgewählten Satz. Während des Schritts 230 bestimmt der Prozessor 48, ob bereits eine kontextbezogene Kopierverknüpfung zwischen den beiden AVPaaren für den ausgewählten Satz besteht. Der Prozessor 48 führt diese Bestimmung aus, indem die Kopierfelder des Quellen- und Empfänger-AVPaars überprüft werden. Wenn eine Kopierverknüpfung zu dem ausgewählten Satz in der Quelle oder dem Empfänger gefunden wird, dann ist keine weitere Handlung notwendig, und der Prozessor 48 reagiert, indem er zum Schritt 244 verzweigt. Wenn andererseits keine kontextbezogene Kopierverknüpfung zu dem ausgewählten Satz zwischen dem Quellen- und dem Empfänger-AVPaar besteht, verlässt der Prozessor 48 den Schritt 230 und verzweigt zum Schritt 232.
Während des Schritts 232 beginnt der Prozessor 48 damit, zu bestimmen, ob er das Quellen-AVPaar in dem Empfänger-AVPaar mittels einer kontextbezogenen einfachen Kopierverknüpfung repräsentieren kann. Dies hängt teilweise davon ab, ob die anderen einfachen Kopierverknüpfungen des Empfängers bereits erweitert worden sind. Der Prozessor 48 bestimmt, ob dies der Fall ist, indem das erweiterte Bit des Empfänger- AVPaars untersucht wird. Wenn dieses Bit anzeigt, dass einfache Kopierverknüpfungen bereits erweitert worden sind, kann der Prozessor 48 in der Lage sein, das Quellen- AVPaar unter Verwendung einer kontextbezogenen einfachen Kopierverknüpfung zu repräsentieren, wenn diese Verknüpfung die einzige einfache Kopierverknüpfung des Empfänger-AVPaars in einem überlappenden Kontext ist. Der Prozessor 48 bestimmt während des Schritts 234, ob das Empfänger-AVPaar bereits andere kontextbezogene einfache Kopierverknüpfungen innerhalb des Kontexts, der als Argument an "Copy AV- Pair" übergeben wird, beinhaltet, indem die einfachen Kopierverknüpfungen, die in dem Kopierfeld von dem AVPaar sind, gezählt werden, und indem für jede einfache Kopierverknüpfung deren Kontext mit dem ausgewählten Kontext verbunden wird. Wenn alle Verbindungen nogood sind, dann geht der Prozessor 48 zum Schritt 236. Im Schritt 236 wird eine kontextbezogene einfache Kopierverknüpfung von dem Empfänger-AVPaar zu dem Quellen-AVPaar hinzugefügt; Der Kontext der hinzugefügten Verknüpfung ist der ausgewählte Kontext. Wenn andererseits ein verbundener Kontext nicht nogood ist, dann geht der Prozessor 48 zum Schritt 238 weiter.
Der Prozessor 48 geht vom Schritt 234 zum Schritt 238 weiter, wenn alle einfachen Kopierverknüpfungen, die mit dem Empfänger-AVPaar verknüpft sind, noch zu erweitern sind. Der Prozessor 48 erweitert jene einfachen Kopierverknüpfungen während des Schritts 238, indem "Expand Lazy Links" 108 aufgerufen wird. Danach geht der Prozessor 48 zum Schritt 240 weiter.
Der Prozessor 48 erreicht den Schritt 240, wenn das Quellen-AVPaar in dem Empfänger-AVPaar nicht durch eine einfache Kopierverknüpfung repräsentierbar ist. Um in dem Quellen-AVPaar zu kennzeichnen, dass es in den Empfänger kopiert worden ist, fügt der Prozessor 48 zu dem Kopierfeld des Quellen-AVPaars eine Vorwärtskopierverknüpfung hinzu, die zu dem Empfänger zeigt. Anschließend kopiert im Schritt 242 der Prozessor 48 die Rahmenbedingungen des Quellen-AVPaars in das Empfänger-AVPaar, indem "Copy Facts" 110 aufgerufen wird. Danach verlässt der Prozessor 48 den Schritt 242 und geht zum Schritt 244 weiter.
Die Routine "Expand Lazy Links" 108, die in Fig. 11 dargestellt ist, erlaubt es dem Prozessor 48, eine kontextbezogene einfache Kopierverknüpfung durch eine Ebene größeren Details und gegebenenfalls durch andere kontextbezogene einfache Kopierverknüpfungen zu ersetzen. Nach dem Hinzufügen von Vorwärtskopierverknüpfungen in der Quelle, um die Erweiterung einer einfachen Kopierverknüpfung zu dokumentieren, kopiert der Prozessor 48 die relevante Information, indem "Copy Facts" 110 aufgerufen wird.
Der Prozessor 48 beginnt das Ausführen der Instruktionen 108 mit dem Schritt 260 in Reaktion auf den Empfang eines Zeigers zu dem ausgewählten AVPaar, dessen einfache Kopierverknüpfungen zu erweitern sind. Während des Schritts 260 bestimmt der Prozessor 48, ob die kontextbezogenen einfachen Kopierverknüpfungen des ausgewählten AVPaars bereits erweitert worden sind, indem das Erweiterungsbit untersucht wird. Wenn dieses Bit anzeigt, dass die mit dem ausgewählten AVPaar verknüpften kontextbezogenen einfachen Kopierverknüpfungen bereits erweitert worden sind, geht der Prozessor 48 zum Schritt 276 weiter. Wenn andererseits die kontextbezogenen einfachen Kopierverknüpfungen noch nicht erweitert worden sind, verzweigt der Prozessor 48 vom Schritt 260 in den Schritt 262.
Der Prozessor 48 beginnt das Erweitern der kontextbezogenen einfachen Kopierverknüpfungen des ausgewählten AVPaars, indem der Wert des Erweiterungsfeldes festgelegt wird, um die Erweiterung zu kennzeichnen. Danach geht der Prozessor 48 zum Schritt 264 weiter, um das Erweitern der kontextbezogenen einfachen Kopierverknüpfungen zu beginnen, wobei eine kontextbezogene einfache Kopierverknüpfung pro Zeiteinheit bearbeitet wird. Solange eine kontextbezogene einfache Kopierverknüpfung zu erweitern ist, geht der Prozessor 48 vom Schritt 264 zum Schritt 266 weiter. Während des Schritts 266 wählt der Prozessor eine der verbleibenden kontextbezogenen einfachen Kopierverknüpfungen in dem Kopierfeld für das Erweitern aus. Anschließend geht der Prozessor 48 zum Schritt 270 weiter.
Häufig wird das Ziel-AVPaar, auf das die ausgewählte kontextbezogene einfache Kopierverknüpfung zeigt, durch einfache Kopierverknüpfungen repräsentiert, die ebenso einer Erweiterung bedürfen. In Erwartung einer derartigen Situation ruft der Prozessor 48 während des Schritts 270 "Expand Lazy Links" 108 auf, um die einfachen Kopierverknüpfungen zu erweitern, auf die von der ausgewählten kontextbezogenen einfachen Kopierverknüpfungen gezeigt wird. Während des Schritts 272 fügt der Prozessor 48 eine Vorwärtskopierverknüpfung hinzu, die von dem Ziel-AVPaar zu dem ausgewählten AV- Paar zeigt. Danach geht der Prozessor 48 vom Schritt 272 zum Schritt 274 weiter.
Nach dem Erweitern des Ziel-AVPaars kann nun der Prozessor 48 die ausgewählte einfache Kopierverknüpfung erweitern, indem eine Informationsebene von dem Ziel- AVPaar in das ausgewählte AVPaar kopiert wird. Der Prozessor 48 tut dies, indem "Copy Facts" 110 aufgerufen wird. Danach kehrt der Prozessor 48 zum Schritt 264 zurück und durchläuft die Schritte 226, 270, 272, 274 und 264, bis jede mit dem ausgewählten AVPaar verknüpfte kontextbezogene einfache Kopierverknüpfung erweitert worden ist. Fig. 12 zeigt ein Flussdiagramm der Instruktionen von "Copy Facts" 110. Kurz gesagt, die Anweisungen 110 erlauben es dem Prozessor 48, Informationen von einem Quellenattributewertepaar in ein Empfängerattributewertepaar zu kopieren. Jedes Attributewertepaar umfasst eine Reihe von Attributen sowie eine Anzahl kontextbezogener Werte, zu dem das Attributwertepaar gleich ist. Die Instruktionen 110 verwenden analoge Mittel zum Kopieren von Attributen während der Schritte 292-302 und kontextbezogener Werte während der Schritte 304-312; folglich werden nur die Schritte 292 bis 302 detailliert beschrieben. Der Prozessor 48 beginnt das Ausführen der Instruktionen 110 mit dem Schritt 290 in Reaktion auf den Empfang von Zeigern zu dem Quellen-AVPaar und dem Empfänger-AVPaar, sowie eines ausgewählten Satzes, der mit dem Empfänger verknüpft ist. Der Prozessor 48 beginnt im Schritt 290, wobei bestimmt wird, ob irgendwelche Fakten zu kopieren sind. Es sind keine Fakten zu kopieren, wenn diese mit einem Nogood-Satz verknüpft sind. Der Prozessor 48 prüft daher das Nogood-Feld des Satzes, und wenn der ausgewählte Satz nogood ist, verlässt der Prozessor 48 den Schritt 290 und geht zum Schritt 292 weiter.
Im Schritt 292 beginnt der Prozessor 48 damit, die mit dem Quellen-AVPaar verknüpften Attribute in das Empfänger-AVPaar zu kopieren. Wenn Attribute zu kopieren sind, wählt der Prozessor 48 während des Schritts 294 die verbleibenden Attribute aus. Anschließend verbindet der Prozessor 48 während des Schritts 296 den ausgewählten Satz mit dem mit dem ausgewählten Attribut verknüpften Satz. Der Prozessor 48 vollführt dies, indem "Conjoin Clauses" 112 aufgerufen wird, die den resultierenden Satz zurückgibt. Wenn der resultierende Satz kein Nogood ist, verzweigt der Prozessor 48 vom Schritt 298 zum Schritt 300.
Wenn während des Schritts 300 nicht bereits eine AVPaar-Datenstruktur für den Empfänger vorhanden ist, erzeugt der Prozessor 48 eine, die zu dem Empfänger-AVPaar zurückzeigt und fügt einen Zeiger zu diesem neuen AVPaar in dem Attributfeld des Empfänger-AVPaars hinzu. Nach dem Erzeugen einer Datenstruktur, in die Information kopierbar ist, geht der Prozessor 48 zum Schritt 302 weiter und ruft "Copy AVPair" auf. "Copy AVPair" kann Information von dem Quellen-AVPaar kopieren oder auch nicht, abhängig davon, ob es eine Wechselwirkung zwischen den kontextbezogenen einfachen Kopierverknüpfungen gibt. Danach verlässt der Prozessor 48 den Schritt 302 und kehrt zum Schritt 292 zurück.
Der Prozessor 48 durchläuft die Schleife aus den Schritten 292-302 bis "Copy AVPair" für jedes relevante Attribut des Quellen-AVPaars aufgerufen worden ist. Wenn dies geschieht, verlässt der Prozessor 48 den Schritt 292 und geht zum Schritt 304 weiter, um das Kopieren von Werten des Quellen-AVPaars in das Empfänger-AVPaar in im Wesentlichen der gleichen Weise zu kopieren, wie die Attribute kopiert wurden. Nach dem Kopieren aller kontextbezogener Werte, die mit dem Quellen-AVPaar verknüpft sind, geht der Prozessor 48 zum Schritt 320 weiter. Während des Schritts 320 überprüft der Prozessor 48 die neuen Bedingungen, die dem Empfänger-AVPaar auferlegt sind, und deduziert falls möglich neue lokale Nogoods. Danach kehrt der Prozessor 48 zu der aufrufenden Routine zurück.
Die Instruktionen 60 verbinden zwei Sätze, um einen neuen Satz zu erzeugen, der in dem Satzspeicher des Speichers 50 gespeichert wird. Dies wird im Wesentlichen in herkömmlicher Weise durchgeführt. Wenn die Sätze disjunkt sind, dann wird jedes Paar aus getrennten Teilen verbunden, und die verbundenen getrennten Teile werden dann getrennt verarbeitet. Wenn die beiden Sätze Konjunktionen sind, dann werden alle Konjunktionspaare verbunden und überprüft, um festzustellen, ob die resultierende Verbindung ein Nogood ist. Wenn keine der verbundenen Konjunktionen eine Nogood ist, dann werden diese zusammengeführt, wodurch redundante Konjunktionen vermieden werden.
Zwei Unterschiede zwischen herkömmlichen Lösungen und zwischen der Art, wie die Instruktionen 60 Sätze verbinden, bestehen jedoch. Erstens, vor dem Beginn des Zusammenführens zweier Sätze sucht der Prozessor 48 den Satzspeicher nach einem Eintrag ab, der die gleichen zwei Sätze betrifft. Der Prozessor 48 beginnt eine derartige Suche, indem das Speicherfeld der Satzdatenstruktur mit der höheren Identifizierung untersucht wird, um die gewünschte Operation und den Operanden zu finden. Wenn ein derartiger Eintrag gefunden wird, kann das zuvor gespeicherte Ergebnis ohne Durchführen der Verbindung gespeichert werden, wodurch Verarbeitungszeit gespart wird. Der zweite Unterschied zwischen der herkömmlichen Lösung zum Verbinden von Sätzen besteht in der Verwendung von verborgenen Sätzen. Das Flussdiagramm aus Fig. 13 zeigt jene Bereiche von "Conjoin Clauses" 112, die verborgene Sätze verarbeiten, um die Vereinigungsverarbeitungszeit zu verringern. Kurz gesagt, wenn zwei verborgene Sätze aus dem gleichen Graphen importiert werden, werden die beiden verborgenen Sätze enthüllt, miteinander verbunden, um einen neuen Satz zu bilden, und der neue Satz wird eingehüllt, um einen neuen verborgenen Satz zu erzeugen, der dann importiert wird. Die verborgenen Sätze könnten ursprünglich durch Aufrufen von "Import Clause" 116 erzeugt worden sein.
Der Prozessor 48 beginnt die Ausführung der Anweisungen 112 mit dem Schritt 360. Der Prozessor 48 ist in der Lage, die Anzahl der präpositionalen Variablen, die zwischen den Graphen importiert worden sind, wenn die beiden verborgenen Sätze mit der gleichen grafischen Datenstruktur verknüpft sind, zu reduzieren. Der Prozessor 48 überprüft diese Möglichkeit während des Schritts 360, indem die grafischen Felder der beiden zu verbindenden Satzdatenstrukturen, Satz 1 und Satz 2, untersucht werden. Wenn beide Sätze mit dem gleichen Graphen verknüpft sind, verlässt der Prozessor 48 den Schritt 360 und verzweigt zum Schritt 362.
Aufgrund der Möglichkeit, dass das Verbinden der zwei verborgenen Sätze in einem einfacheren Satz, etwa WAHR oder nogood, resultieren könnte, "enthüllt" der Prozessor 48 den Satz 1 und den Satz 2 während des Schritts 362. Der Prozessor 48 enthüllt die verborgenen Sätze durch Auslesen des importierten Feldes jedes der verborgenen Sätze. Danach verbindet der Prozessor 48 die beiden enthüllten Sätze während des Schritts 364 durch Aufrufen von "Conjoin Clauses" 112. Der Prozessor 48 prüft im Schritt 366 den resultierenden Satz, um zu bestimmen, ob dieser nogood ist. Wenn ja, geht der Prozessor 48 zum Schritt 368 weiter und gibt einen Zeiger zurück, der anzeigt, dass der resultierende Satz nogood ist. Wenn andererseits der resultierende Satz nicht nogood ist, verzweigt der Prozessor 48 vom Schritt 366 zum Schritt 370.
Der Prozessor 48 "hüllt" den resultierenden Satz "ein" und importiert dann den neuen verborgenen Satz während des Schritts 370 durch Aufrufen von "Import Clause" 116. Danach geht der Prozessor 48 vom Schritt 370 zum Schritt 372 weiter.
Um ein weiteres Aufwenden von Bearbeitungszeit zum Verbinden des Satzes 1 und des Satzes 2 zu verhindern, speichert der Prozessor 48 im Schritt 372 das Ergebnis des Zusammenfügens von Satz 1 und Satz 2 im Satzspeicher des Speichers 50. Vorzugsweise werden Sätze in dem Satzspeicher entsprechend dem Satz mit der höchsten Identifizierung indiziert, und die gespeicherte Information ist ein Tripel: Operator, Operand und resultierender Satz. In diesem Falle wäre das Tripel: Verbinden, Satz 2, resultierender Satz. Danach speichert der Prozessor 48 einen Zeiger zu diesem Eintrag in dem Satzspeicher in dem Satzfeld der Satzdatenstruktur für den Satz mit der höchsten Identifizierung. Der Prozessor 48 führt den Schritt 372 aus, immer wenn zwei Sätze zu verbinden sind oder zu trennen sind, unabhängig davon, ob diese verborgen sind. Speichern der Ergebnisse aller an Sätzen ausgeführten Operationen hilft, die Prozesszeit zur Vereinigung von grafischen Datenstrukturen zu verringern.
Fig. 14 zeigt ein Flussdiagramm für die Instruktionen 116 zum Importieren eines Satzes in einen Graphen. Dabei erzeugt der Prozessor 48 eine neue verborgene Satzdatenstruktur, um den Satz, der importiert wird, "einzuhüllen". Dies stellt sicher, dass der für den Ursprung aufspannenden Rand erzeugte Graph nach Möglichkeit kontextfrei äquivalent ist, indem mehrere präpositionale Variable durch eine einzelne präpositionale Variable ersetzt werden.
Der Prozessor 48 beginnt die Ausführung der Anweisungen 116, indem im Schritt 400 bestimmt wird, ob der ausgewählte Satz - der, der zu importieren ist - bereits in den ausgewählten Graphen importiert worden ist. Der Prozessor 48 erreicht dies, indem der Satzspeicher auf einen Eintrag hin abgesucht wird, dessen resultierender Satz gleich dem ausgewählten Satz ist. Wenn der Prozessor 48 einen derartigen Eintrag findet, dann ist der ausgewählte Satz bereits zu dem ausgewählten Graphen exportiert worden, so dass kein Bedarf mehr zum Exportieren besteht. In Reaktion darauf verzweigt der Prozessor 48 vom Schritt 400 zum Schritt 402 und gibt den importierten Satz zurück. Wenn andererseits der Satzspeicher nicht anzeigt, dass der ausgewählte Satz bereits exportiert worden ist, verzweigt der Prozessor 48 vom Schritt 400 zum Schritt 404.
Im Schritt 404 erzeugt der Prozessor 48 eine neue verborgene Satzdatenstruktur, wobei der ausgewählte Satz in dem importierten Feld gespeichert wird. Anschließend zeichnet der Prozessor 48 im Schritt 406 auf, dass die verborgene Variable in das importierte Feld exportiert worden ist und zeigt an, zu welchem Graphen diese exportiert worden ist, indem ein Zeiger zu dem ausgewählten Graphen in dem grafischen Feld gespeichert wird. Schließlich speichert im Schritt 408 der Prozessor 48 das Ergebnis dieser Operation in dem Satzspeicher des Speichers 50 ab, indem das Tripel gespeichert wird: ausgewählter Satz, verborgen, neuer verborgener Satz. Nach dem Importieren des neuen verborgenen Satzes kehrt der Prozessor 48 vom Schritt 408 zum Schritt 402 zurück.
Fig. 15 zeigt ein Flussdiagramm für die Instruktionen 104 zum Erhalten von Lösungen für einen ausgewählten Rand, bei gegebenen Sätzen, für die Lösungen gesucht werden, die auch als Restriktionsmenge bezeichnet werden, da Lösungen nicht für alle Sätze, die mit dem ausgewählten Rand verknüpft sind, gesucht werden. Ein Zeiger zu dem ausgewählten Rand, mit dem die Restriktionsmenge verknüpft ist, wird auch in die Anweisungen 104 eingeführt. Kurz gesagt, die Routine "Get Edge Solutions" 104 erzeugt Lösungen für den ausgewählten Rand, indem ermittelt wird, welche Kombinationen von Sätzen der Restriktionsmenge Lösungen besitzen. Der Prozessor 48 identifiziert mögliche interne Lösungen einer Baumteilstruktur zu einer gegebenen Zeit, indem zunächst Lösungen für die linke und die rechte Tochter der ausgewählten Baumteilstruktur ermittelt werden. Anschließend nimmt der Prozessor 48 das Kreuzprodukt der Lösungen für die linke und rechte Tochter. Der Prozessor 48 bewertet die Gültigkeit der möglichen internen Lösungen unter Verwendung der lokalen Nogoods. Bei Vorhandensein nicht zulässiger interner Lösungen bestimmt der Prozessor 48 dann, welche davon, falls WAHR, bewirken, dass Sätze der ausgewählten Restriktionsmenge ein WAHR ergeben. Jene Sätze der Restriktionsmenge, die ein WAHR ergeben, werden dann zu einer Restriktions- bzw. eingeschränkten Lösung gemacht.
Das Ausführen der Instruktionen 104 beginnt mit dem Schritt 405, währenddessen der Prozessor 48 beginnt, offensichtliche Lösungen für den ausgewählten Rand zu suchen. Es gibt drei. Zunächst untersucht der Prozessor 48 den Zeiger zu dem ausgewählten Rand. Wenn der Zeiger 0 ist, bedeutet dies, dass der ausgewählte Rand erfolgreich mit einem anderen Rand kombinierbar ist. In Reaktion auf eine derartige Entdeckung geht der Prozessor 48 zum Schritt 452 weiter und zeigt an, dass die Lösung für den ausgewählten Rand WAHR ist. Anschließend kehrt der Prozessor 48 zum Schritt 454 zurück. Wenn andererseits der Zeiger zu dem ausgewählten Rand nicht 0 ist, verzweigt der Prozessor 48 zum Schritt 460, um eine weitere offensichtliche Lösung für den ausgewählten Rand zu untersuchen. Im Schritt 460 untersucht der Prozessor 48 das Nogood- Feld des Graphen der ausgewählten Randdatenstruktur, um zu bestimmen, ob der ausgewählte Rand nogood ist. Wenn dies der Fall ist, setzt der Prozessor 48 während des Schritts 462 die Lösung für den ausgewählten Rand auf 0 fest und kehrt zum Schritt 454 zurück. Wenn der ausgewählte Rand nicht als nogood kategorisiert wird, verlässt der Prozessor 48 den Schritt 460, um nach der letzten offensichtlichen Lösung zu suchen. Im Schritt 464 sucht der Prozessor 48 den Lösungsspeicher des Graphen ab, um zu ermitteln, ob diese Restriktionsmenge bereits gelöst worden ist. Wenn dies der Fall ist, liefert der Prozessor 48 einen Zeiger zu den Lösungen, falls vorhanden, im Schritt 466.
Wenn das Bemühen zum Auffinden einer offensichtlichen und einfachen Lösung fehlschlägt, verlässt der Prozessor 48 den Schritt 464 und geht zum Schritt 468 weiter. Der Prozessor 48 erzeugt eine eingeschränkte Lösungsdatenstruktur für die ausgewählten Sätze in dem Lösungsspeicher, wobei alle Felder auf 0 gesetzt sind. Danach geht der Prozessor 48 zum Schritt 470 weiter, um damit zu beginnen, nach Lösungen für die ausgewählte Restriktionsmenge zu suchen, wobei eine Baumteilstruktur nach der anderen verwendet wird. Im Schritt 472 wählt der Prozessor 48 eine der Baumteilstrukturen aus, die noch eine Lösung erfordern. Anschließend bestimmt der Prozessor 48, ob die ausgewählte Baumteilstruktur nogood ist, indem das Nogood-Feld der grafischen Datenstruktur für die ausgewählte Baumteilstruktur untersucht wird. Wenn die ausgewählte Baumteilstruktur nogood ist, untersucht der Prozessor 48 andere Baumteilstrukturen, indem er zum Schritt 470 zurückkehrt. Wenn andererseits der Graph für die ausgewählte Baumteilstruktur nicht nogood ist, dann geht der Prozessor 48 vom Schritt 474 zum Schritt 476 weiter.
Das Auffinden von Lösungen für die ausgewählte Baumteilstruktur erfordert zunächst das Auffinden von Lösungen für die linken und rechten Töchter der ausgewählten Baumteilstruktur. Dies geschieht in den Schritten 476 bis 486. Zunächst bestimmt der Prozessor 48, welche Sätze des Baumteilstrukturgraphen von seiner linken Tochter importiert sind, wobei eine neue Restriktionsmenge definiert wird. Der Prozessor 48 nutzt diese Information während des Schritts 478, um Lösungen für die linke Tochter zu finden, indem "Get Edge Solutions" 104 aufgerufen wird. Wenn es keine Lösungen für die linke Tochter gibt, kann es keine Lösungen für die ausgewählte Baumteilstruktur geben. Der Prozessor 48 reagiert auf diese Situation, indem er vom Schritt 480 zum Schritt 470 verzweigt und sich somit einer weiteren Baumteilstruktur zuwendet. Wenn andererseits die linke Tochter eine Lösung besitzt, dann kann die ausgewählte Baumteilstruktur eine Lösung besitzen. Daraufhin verzweigt der Prozessor 48 vom Schritt 480 zum Schritt 482, um Lösungen für die rechte Tochter der ausgewählten Baumteilstruktur zu ermitteln. Der Prozessor 48 beginnt damit, zu identifizieren, welche der Sätze des Baumteilstrukturgraphen von der rechten Tochter importiert worden sind. Dies definiert eine neue Restriktionsmenge, die der Prozessor 48 anwendet, wenn er "Get Edge Solutions" 104 im Schritt 484 aufruft. Der Prozessor 48 reagiert auf diese Erkenntnis, dass die rechte Tochter keine Lösungen besitzt, indem er vom Schritt 486 zum Schritt 470 zurückkehrt. Wenn andererseits die rechte Tochter eine Lösung besitzt, verzweigt der Prozessor 48 vom Schritt 486 zum Schritt 490.
Bei gegebenen Lösungen für die linke und die rechte Tochter des ausgewählten Randes beginnt der Prozessor 48 im Schritt 490 damit, Lösungen für den ausgewählten Rand zu ermitteln. Diese Lösungen werden durch eine eingeschränkte Lösungsdatenstruktur repräsentiert. Im Schritt 490 erzeugt der Prozessor 48 lokale Lösungen auf der Grundlage der Disjunktionen, die eingeführt wurden, wenn die lokalen Rahmenbedingungen festgelegt wurden. Der Prozessor 48 nimmt dann das Kreuzprodukt der lokalen Lösungen und der Lösungen für die linke und die rechte Tochter, um eine Anzahl von möglichen internen Lösungen für den ausgewählten Rand zu erzeugen. Der Prozessor 48 untersucht diese möglichen internen Lösungen der Reihe nach in anschließenden Schritten.
In den Schritten 500 bis 506 wählt der Prozessor 48 eine der möglichen intemen Lösungen zur Bewertung aus und bewertet diese unter Verwendung lokaler Nogood-Sätze, um die Gültigkeit des ausgewählten möglichen internen Lösungssatzes zu bestimmen. Wenn der Prozessor 48 im Schritt 506 bestimmt, dass die ausgewählte mögliche interne Lösung nicht zulässig ist, kehrt der Prozessor 48 zum Schritt 500 zurück, um die Bewertung einer weiteren möglichen internen Lösung zu beginnen. Wenn andererseits die ausgewählte mögliche Lösung zulässig ist, geht der Prozessor 48 zum Schritt 508 weiter. Während dieses Schrittes wird jeder der Sätze in der ausgewählten möglichen internen Lösung als WAHR angenommen, und die Sätze der ausgewählten Restriktionsmenge werden untersucht, um zu bestimmen, welche von diesen WAHR sind. Der Prozessor 48 kennzeichnet jene Sätze der Restriktionsmenge im Schritt 510, die ein WAHR ergeben und vergleicht diese mit jenen, die in dem Satzfeld der eingeschränkten Lösungsdatenstrukturen aufgelistet sind, die mit der ausgewählten Restriktionsmenge verknüpft sind. Wenn im Schritt 512 bestimmt wird, dass diese noch nicht in den Lösungen für die Restriktionsmenge enthalten sind, erzeugt im Schritt 514 der Prozessor 48 neue eingeschränkte Lösungen mit dem gekennzeichneten Satz und fügt diese zu den Lösungen für die Restriktionsmenge hinzu. Schließlich fügt im Schritt 516 der Prozessor 48 dem Abbildungsfeld der eingeschränkten Lösungsdatenstruktur einen Zeiger zu der Datenstruktur für die ausgewählte mögliche interne Lösung hinzu.
Nach Abschluss der Bewertung der möglichen Lösung kehrt der Prozessor 48 zum Schritt 500 zurück, um die Überprüfung von möglichen internen Lösungen fortzusetzen, wie dies mit Bezug zu den Schritten 502 bis 516 beschrieben ist. Nach Untersuchung der möglichen internen Lösungen für die ausgewählte Baumteilstruktur verzweigt der Prozessor 48 vom Schritt 500 zum Schritt 470. Nach Verarbeitung aller Baumteilstrukturen, die mit dem ausgewählten Rand verknüpft sind, kehrt der Prozessor 48 zum Schritt 454 zurück und liefert Lösungen für die Restriktionsmenge.

Claims

1. Verfahren zur Vereinigung von Datenstrukturen, wobei das Verfahren umfasst:

(a) Kopieren einer Information von einer ersten Merkmalsstruktur in eine zweite Merkmalsstruktur;

dadurch gekennzeichnet, dass die von die ersten Merkmalsstruktur in die zweite Merkmalsstruktur kopierte Information erste Satzdaten enthält, die eine erste Kombination von Kontexten repräsentieren;

wobei das Verfahren ferner umfasst:

(a1) Bestimmen, ob Satzdaten, die die gleiche Kombination von Kontexten wie die ersten Satzdaten repräsentieren, bereits in die zweite Merkmalsstruktur kopiert worden sind; und

(a2) falls nicht, Erzeugen zweiter Satzdaten in der zweiten Merkmalsstruktur; wobei die zweiten Satzdaten die erste Kombination von Kontexten repräsentieren, und wobei die zweiten Satzdaten verborgene Satzdaten sind, die unabhängig von den Kontexten in der ersten Kombination handhabbar sind.

2. Das Verfahren nach Anspruch 1, wobei die zweiten Satzdaten einen Zeiger zu den ersten Satzdaten aufweisen.

3. Das Verfahren nach Anspruch 1 oder 2, das ferner umfasst:

(b) Verbinden der zweiten Satzdaten mit dritten Satzdaten, die eine zweite Kombination von Kontexten repräsentieren, durch:

(b1) Bestimmen, ob die dritten Satzdaten verborgene Satzdaten sind, die unabhängig von den Kontexten in der zweiten Kombination handhabbar sind, und ob die dritten Satzdaten in der zweiten Merkmalsstruktur sind;

(b2) wenn die dritten Satzdaten verborgene Satzdaten sind und in der zweiten Merkmalsstruktur enthalten sind:

(b2a) Verwenden der zweiten Satzdaten, um die ersten Satzdaten zu ermitteln;

(b2b) Verwenden der dritten Satzdaten, um vierte Satzdaten zu erhalten, die die zweite Kombination von Kontexten repräsentieren, wobei die vierten Satzdaten keine verborgenen Satzdaten sind;

(b2c) Verbinden der ersten Satzdaten und der vierten Satzdaten, um fünfte Satzdaten zu erzeugen, wobei die fünften Satzdaten keine verborgenen Satzdaten sind, und wobei die fünften Satzdaten eine dritte Kombination von Kontexten repräsentieren, die eine Konjunktion der ersten und zweiten Kombinationen von Kontexten ist;

(b2d) Erzeugen sechster Satzdaten in der zweiten Merkmalsstruktur, wobei die sechsten Satzdaten die dritte Kombination von Kontexten repräsentieren, und wobei die sechsten Satzdaten verborgene Satzdaten sind, die unabhängig von den Kontexten in der dritten Kombination handhabbar sind.

4. Das Verfahren nach einem der vorhergehenden Ansprüche, wobei erste und zweite Randdatenstrukturen vereinigt werden und wobei die ersten und zweiten Merkmalsstrukturen in der ersten Randdatenstruktur liegen.

5. Das Verfahren nach Anspruch 4, wobei die ersten und zweiten Merkmalsstrukturen graphische Datenstrukturen sind.

6. System (30) zum Vereinigen von Datenstrukturen mit:

einer Verarbeitungseinrichtung (48); und

einer Speichereinrichtung (40, 42, 50) zum Speichern von Datenstrukturen, wobei die gespeicherten Datenstrukturen erste und zweite Merkmalsstrukturen beinhalten;

wobei die Verarbeitungseinrichtung beim Vereinigen von Datenstrukturen eine Information aus der ersten Merkmalsstruktur in die zweite Merkmalsstruktur kopiert;

dadurch gekennzeichnet, dass die Verarbeitungseinrichtung erste Satzdaten von der ersten Merkmalsstruktur in die zweiten Merkmalsstruktur kopiert, wobei die ersten Satzdaten eine erste Kombination von Kontexten repräsentieren; die Verarbeitungseinrichtung bestimmt, ob Satzdaten, die die gleiche Kombination von Kontexten als die ersten Satzdaten repräsentieren, bereits in die zweite Merkmalsstruktur kopiert worden sind; und, wenn dies der Fall ist, die Verarbeitungseinrichtung zweite Satzdaten in der zweiten Merkmalsstruktur erzeugt, wobei die zweiten Satzdaten die erste Kombination von Kontexten repräsentieren und die zweiten Satzdaten verborgene Satzdaten sind, die unabhängig von den Kontexten in der ersten Kombination handhabbar sind.