Interessantes Problem: Generierung von Bäumen aus flachen Daten

[Jesus_666]

(Hinweis: Dies ist kein "ich suche Hilfe"-Thread; ich finde nur, daß das Problem interessant genug ist, um hier diskutiert zu werden.)

Ich bin gerade dabei, ein Programm zu schreiben, das zwischen verschiedenen Textformaten konvertieren kann. Genau gesagt konvertiere ich Text in Drehbuchform zwischen HTML (nur Ausgabe), XML und zwei spezifischen Formaten, TXML (ein nicht standardkonformer XML-Dialekt) und TML (eine völlig eigene Sprache).

Das Programm funktioniert so, daß ich den Text intern als einen Baum von Objekten repräsentiere. Es gibt grundsätzlich fünf Arten von Objekten:

• Episode: Ein Blockelement, das die Wurzel jedes Dokuments darstellt. Kann Instanzen von Scene und ggf. Comment beinhalten.
• Scene: Ein Blockelement, das eine konkrete Szene beschreibt. Beinhaltet Comment, Line, Event und Camera.
• Comment: Ein Kommentar. Äquivalent zu XMLs <!-- -->.
• Line: Eine Textzeile, die von jemandem gesprochen wird.
• Event: Ein Ereignis.
• Camera: Eine Regieanweisung, Kameraeinstellung oder ähnliches.

Ein Beispielbaum mit Metadaten könnte so aussehen:

Code:

[Episode, id=152, name="Herbert stirbt im Wald"]
  [Scene, description="Im Wald"]
    [Line, character="Herbert"]
      "Hallo."
    [Event]
      "Herbert stirbt."
  [Scene, description="Auf dem Friedhof"]
    [Camera]
      "Auf Herberts Grabstein steht: 'Hallo.'"

So weit, so gut. Aus korrektem XML einen derartigen Baum zu generieren ist relativ einfach, allerdings habe ich jetzt vor, einen Baum aus TML zu generieren. Der Haken: TML ist darauf ausgelegt, kompakter als XML zu sein und deshalb nicht hierarchisch.

Hier mal das obige Dokument in TML:

Code:

#152: Herbert stirbt im Wald
<Im Wald>
Herbert: Hallo.
[Herbert stirbt.]
<Auf dem Friedhof>
{Auf Herberts Grabstein steht: 'Hallo.'}

In meinem Fall kann ich ausnutzen, daß die Tiefe des Baums begrenzt ist: Szenen können keine andere Blockelemente beinhalten, also kann ich ein Szenenobjekt definieren, dort alles reinschieben und beim Lesen einer neuen Szenenbeschreibung einfach das Objekt ersetzen.

Was aber im allgemeinen Fall? Natürlich kann man nicht beliebige Bäume unzweideutig in einem nichthierarchischen Format ablegen, aber was ist eurer Meinung nach das Komplexeste, das man sinnvoll machen kann?

(BTW, ich könnte es mir viel einfacher machen und einfach per Regexps TML nach XML umformen, aber mit direktem Einlesen ist alles modularer und erweiterbarer. Und wir wissen ja alles, daß "einfach" und "robust" gegen "theoretisch erweiterbar" nicht anstinken kann.)

[dead_orc]

Erstmal: Yay, du machst endlich erste Anstalten, Thang weiterzuschreiben.

Zum Thema: Ich kann mir mal wieder nix komplexeres vorstellen, als eine Konstellation, in der jeder Objekttyp nur Child von _einem_ anderen Objekttyp sein kann, was ja in deinem Fall eintritt. Eine Szene kann nur in einer Episode sein - andersrum wäre es zumindest komisch. Eine Kameraeinstellung kann nicht direktes Kind einer Episode sein, da die Episode erstmal zwangsläufig in Episoden aufgeteilt ist.

Oder anders formuliert: Beim Auftauchen des Elements muss deutlich erkennbar sein, welche Verschachtelungsebene es hat. Es wäre natürlich auch denkbar, dass man die Szene manchmal weglässt, wenn eine ganze Episode nur aus einer Szene besteht. Dann würde eine solche Vorschrift für Event beispielsweise lauten können: "Kann nur als direktes Kind von Scene auftreten, oder als direktes Kind von Episode, falls das Elternelement Episode kein Scene Element enthält."

Und nun, rock me Amadeus! Zeigt mir, was ich alles vergessen und übersehen habe!

[Jesus_666]

Um ehrlich zu sein glaube ich, daß es tatsächlich so ist: Wenn die Verschachtelungshierarchie weder extern noch intern definiert ist, kannst du keine sinnvolle Verschachtelung erstellen. Im Falle meines Beispiels ist die Verschachtelung extern definiert.

Ich versuche, auf einen Regelsatz zu kommen, der es erlaubt, einen Knotentyp in verschiedenen Hierarchieebenen zu haben, aber mir fällt gerade keiner ein...

[Ineluki]

Im Grunde hast du das Problem doch gar nicht, denn dein TML ist isomorph, bijektiv auf dein Metadatenformat abbildbar, was praktisch XML mit [] statt <> und ohne Endtags ist.

#num:text\n -> [Episode, id=num, name=text]
<text>\n -> [Scene, description=text]
name:text\n -> [Line, character=name] text
{text} \n -> [Camera] text

Im Grunde hast du nur eine kurznotation, das format der Daten aendert sich nicht, sie beschreiben den selben Baum und sind damit eben auch nicht flach.

Deine Aktuelle Strukturierung der Daten erlaubt keine tiefere Verschachtelung als bis zur Scene ebene. (Warum auch .. Szenen innerhalb Szenen ?) Darauf ist auch dein Format ausgerichtet, denn du implizierst durch das weglassen der Endtags automatisch, das gleiche Elemente hierarchisch auf der selben Ebene angelegt werden. Wenn du auf eine Stelle wie <s1> <s2> stoesst, weisst du automatisch, das sie im selben Episodenobjekt liegen, wenn du ein neues Episodenobjekt, weisst du damit, das alte ist beendet, da das neue ja dazu parallel liegen muss.

Bei einem Hierarchisch geordneten Baum beliebiger Tiefe hast du allerdings stattdessen 3 Moeglichkeiten, was du tun kannst, wenn du auf eine struktur wie <s1><s2> stoesst.

1. s2 ist ein Subelement von s1 und spannt damit eine weitere Tiefenebene auf.
2. s2 liegt auf der selben Ebene wie s1. Damit wird s1 automatisch geschlossen und parallel dazu s2 eingefuegt (und mit dem Elternknoten verbunden).
3. s2 liegt in (irgendeiner) Ebene unterhalb von s1 und alle Knoten unterhalb von s1 bis zu der Ebene, in der s2 liegen soll, muessen geschlossen werden.

Wie du sehen kannst, kannst du mit einem weiteren (optionalen) Parameter komplexe hierarchieebenen aufbauen. Wenn du also jedem Construct ein Symbol der Form (!([0..9]*))? voranstellst, kannst du beliebig tiefe und komplexe Baeume aufbauen.

Ein <text> wuerde parallel zu einem eventuell vorhandenem Scene Objekt im aktiven Elternknoten eingefuegt werden.
Ein !<text> macht das letztoffene (und sinnvolle) Objekt zum neuen Elternknoten und fuegt das Scene Objekt dort ein.
Ein !2<text> geht 2 Ebenen tiefer, schliesst auf dem Weg alle offenen Knoten darueber, macht den dort befindlichen Knoten zum aktiven Elternknoten und fuegt das Szene-Objekt ein.

Das Format ist zudem 100% abwaertskompatibel zu deinem Format (indem einfach kein ! am Zeilenanfang vorkommt).
Irgendwie hat das ganze was von Turtle-Graphik ^^

[Jesus_666]

Ein interessanter Ansatz, den ich aber um negative Zahlen erweitern würde, um Fälle abzudecken, wo mehrere Elemente auf einmal enden.

[Ineluki]

Deine "Erweiterung" versteh ich nicht so ganz, da ein !2<text> ja alle bisherigen Objekte schliesst, die auf den letzten 2 Ebenen noch offen waren.

Vielleicht sollte das ganze ein Beispiel verdeutlichen.
Wir definieren jetzt, das Scene-Objekte weitere Scene-Objekte enthalten duerfen (was mir als Subszenen einzig sinnvoll erscheint). Alles andere bleibt beim alten.

Beispiel 1
#152: Herbert stirbt im Wald
<Im Wald>
Herbert: Hallo.
<Auf dem Friedhof>
Herbert: Ich lebe noch

Das generiert wie gehabt folgende struktur

Code:

<episode>
  <scene "Im Wald">
    <line>Hallo</line>
  </scene>
  <scene "Auf dem Friedhof">
    <line>Ich lebe noch</line>
  </scene>
<episode>

Erklaehrung:
#152: Herbert stirbt im Wald -> Erstes Objekt (Episode) = Wurzel
<Im Wald> -> Episode kann Scene enthalten. -> Episode.insert(new Scene)
Herbert: Hallo. -> Scene kann Line enthalten, Episode aber nicht -> Scene.insert(new Line)
<Auf dem Friedhof> -> Sowohl Episode als auch Scene koennen Scene enthalten. Da kein ! angegeben ist, soll es auf die gleiche Ebene, wie andere Scene objekte -> Alle offenen Tags unterhalb von Episode schliessen (rekursiv) -> Episode.insert(new Scene)
Herbert: Ich lebe noch -> nur Scene kann line enthalten -> oberster offener Scene Knoten bekommt zuschlag -> Scene.insert(new line)
EOF -> Implizites Close All


Beispiel 2:
#152: Herbert stirbt im Wald
<Im Wald>
Herbert: Hallo.
!<Auf dem Friedhof>
Herbert: Ich lebe noch

Das generiert folgende struktur

Code:

<episode>
  <scene "Im Wald">
    <line>Hallo</line>
    <scene "Auf dem Friedhof">
      <line>Ich lebe noch</line>
    </scene>
  </scene>
<episode>

Bis zum !<Auf dem Friedhof> ist alles wie gehabt.
<Auf dem Friedhof> -> Sowohl Episode als auch Scene koennen Scene enthalten. Da ! angegeben ist, soll es eine Ebene hoeher hinein -> Scene.insert(new Scene) -> Basiszeiger eine Ebene hoeher

Bei Beispiel 3 fuegen wir Beispiel 2 eine weitere Szene hinzu.

Beispiel 2:
#152: Herbert stirbt im Wald
<Im Wald>
Herbert: Hallo.
!<Auf dem Friedhof>
Herbert: Ich lebe noch
!1<Herberts Haus>
Herbert: Hier wohne ich schon lange

Das generiert folgende struktur

Code:

<episode>
  <scene "Im Wald">
    <line>Hallo</line>
    <scene "Auf dem Friedhof">
      <line>Ich lebe noch</line>
    </scene>
  </scene>
  <scene "Herberts Haus">
    <line>Hier wohne ich schon lange</line>
  </scene>
<episode>

Bis zu !1<> ist alles wie in Beispiel 2.
!2<Herberts Haus> -> Die neue scene koennte innerhalb der Friedhofsszene liegen (das waere bei !<> der Fall) oder parallel dazu (ohne !). Sie koennte aber auch parallel zur Waldszene liegen. Momentan befinden wir uns innerhalb der Waldszene, denn wenn wir kein ! angeben, wuerden wir eine weitere Szene parallel zur Friedhofsszene einfuegen. Das !1 sagt uns aber, wie sollen eine Ebene tiefer gehen und alle offenen tags schliessen -> Scene (Friedhof).close -> Scene(Wald).close -> Nun sind wir eine Ebene unterhalb und fuegen die neue Szene ein -> Episode.insert(new Szene(Haus))

Soweit alles klar ?

Wenn du willst, kannst du natuerlich auch statt der (![0..9])? notation auch eine ([+]|[-]+)? notation verwenden, das ist vielleicht intuitiver

<scene> fuegt eine szene parallel ein
+<scene> fuegt die szene innerhalb des letzten sinnvollen offenen objekts ein
-<scene> geht eine Ebene im baum tiefer, schliesst offene Tags und fuegt dort die szene ein
---<scene> geht drei ebenen in richtung wurzel, schliesst alle offenen tags auf dem weg und fuegt dann die szene ein

[Jesus_666]

Ah. Ich hatte deine Notation vorher verkehrt herum interpretiert.