Charts
Charts sind eine Datenstruktur, die Verbindungen zwischen nummerierten Knoten erfasst.
Charts können als Tabelle oder gerichtete, azyklische Graphe visualisiert werden. Wir unterscheiden folgende Typen von Charts:
- Well-Formed Substring Tables (WFST), als Kante wird nur die LHS (Kategorie) einer Regel eingetragen
- Charts mit passiven Kanten, als Kante wird die sie erzeugende Regel eingetragen
- Charts mit aktiven Kanten enthalten zusätzlich Kanten mit noch nicht vollständig analysierten Konstituenten samt (hypothetischer) noch zu findender Struktur
Die Struktur der Charts ermöglicht es uns, effizientere Parser zu bauen, die gleiche Konstituenten nur einmal berechnen müssen.