internes Speichern von Auszeichnungstexten

stefanjann

Hallo,

ich erhalte von einem Kunden ein spezielles Dateiformat. Das kann man grob mit MXL vergleichen, nur dass es ein paar spezielle Unterschiede gibt, die es unmöglich machen, einen fertigen XML-Parser zu verwenden. Der wichtigste Unterschied ist, dass anstatt "<>" die Zeichen "()" verwendet werden. Liegt wohl daran, dass im Inhalt keine runden Klammern vorkommen können, wohl aber spitze Klammern.

Aber es gibt auch Tags, diese haben Attribute (nur ohne Wert) und jeder Tag hat einen Inhalt. Und es wird auch verschachtelt. Beispiel:

(LINIE braun small)(/)
(BOX gelb)(LINIE quer)FooBar(/)(/)

In XML würde das so aussehen

<LINIE braun="braun" small="small" />
<BOX gelb="gelb"><LINIE quer="quer">FooBar</LINIE></BOX>

Leider kann ich an dem Format nichts ändern, das die Software die dieses Format liefert nicht mehr supportet wird!
Das Format zu parsed ist kein Problem. Die Syntax ist relativ leicht.

Meine Frage ist, wie speichere ich sowas sinnvoll in C++11 ab (mit Visual Studio) um mich durch die Tags und durchzuarbeiten.

Zwei Ideen:
1. Idee
Die Werte innerhalb der Klasse speichern: (Pseudo-Ideen-Code)

class KlammerBasis
{};

class KlammerTag : public KlammerBasis
{
public:
  wstring TagName;
  vector<KlammerBasis> Kindelemente;
};

class KlammerText : public KlammerBasis
{
public:
 wstring TextInhalt;
};

2. Idee
Die Werte in einer Zeichenkette speichern, die von den Klassen verwendet wird: (Pseudo-Ideen-Code)

class KlammerBasis
{
  KlammerSpeicherverwaltung* WoAllociereIch;
  wstring* KompletteDatei;
  size_t MeinInhaltStart;
  size_t MeinInhaltLaenge;
};

class KlammerTag : public KlammerBasis
{
};

class KlammerText : public KlammerBasis
{
};

class KlammerSpeicherverwaltung
{
  wstring KompletteDatei;
  void BraucheMehrLaenge(KlammerBasis*,size_t& WieViel);
};

Gedankengut
Also bei der ersten Idee gehe ich wie in der Struktur vor. Somit ist alles innerhalb der Klasse aufgeräumt. Aber ich glaube es kostet viel Zeit bei sehr großen Dateien mit vielen Tags den Speicher zu allocieren und freizugeben. Wenn ich dann eine Ausgabe mache, muss ich den ganzen Baum durchgehen und alle Elemente in einen String übertragen. Änderungen innerhalb eines Elementes würden wahrscheinlich sehr schnell gehen.

Bei der zweiten Idee liegt die richtige Syntax bereits in der Speicherverwaltung. Was glaube ich für die Speicherverwaltung sehr entlasstend ist, weil ich "nur" allocieren muss, wenn length() zu klein ist. Wenn ich eine Ausgabe mache, muss ich im Endeffekt nichts mehr machen, als nur "KompletteDatei" zu verwenden. Änderungen innerhalb eines Elementes würden wahrscheinlich länger dauern.

So, im groben waren das meine Gedanken.
Ich hoffe ihr versteht was ich meine.
Meine Fragen sind:

- Wie machen das andere Parser? Wie speichern die Ihre Daten intern ab? Also z.B. XML oder HTML-Parser, die ja eigentlich die gleiche Datenstruktur haben (nur die Syntax weicht ab).

- Es geht mir nicht drum, was mehr Tipparbeit für mich ist, innerhalb des Codes. Welche Idee ist besser für schnelle Verarbeitung. Meint Parsen, Ändern, Ausgeben.

- Sonstige Meinungen?

Noch ein Hinweis: Ob ich jetzt wstring oder einen wchar_t* oder sonst was nehme ist momentan noch nicht so relevant. Ich bin ja gerade erst in der Planung des Projektes.

Danke schon mal,
Stefan

inflames2k

Ich hätte ins blaue geschossen einfach die () durch <> ersetzt und umgekehrt. Muss man nur eben drauf achten, das man nicht 2 mal die gleiche Klammer ersetzt.

Dann könnte man es wie jedes XML mit dem geeigneten Parser verarbeiten.

Ich würde einfach einen Parser schreiben der XML ausspuckt und dann auf eine fertige Lösung für XML zurückgreifen.

inflames2k schrieb:

Ich hätte ins blaue geschossen einfach die () durch <> ersetzt und umgekehrt.

Reicht nicht wegen der Attribute.

stefanjann

Naja, aber parsen muss ich auf alle Fälle. Und daher stellt sich immer noch die gleiche Frage: Was ist sinnvoller in Bezug auf Schnelligkeit.
Erst parsen, dann in XML wandeln und dann wieder parsen (lassen vn fertigem Tool) kann wohl nicht performant sein....
Wir sprechen durchaus von Dateien zwischen 100 und 50000 Tags.

µ schrieb:

inflames2k schrieb:

Ich hätte ins blaue geschossen einfach die () durch <> ersetzt und umgekehrt.

Reicht nicht wegen der Attribute.

...und der End-Tags...

(LINIE braun start 12.5 18.6 ende 22.7 16.5)(/)

stefanjann schrieb:

(LINIE braun start 12.5 18.6 ende 22.7 16.5)(/)

Was bedeutet denn das? start={12.5,18.6}?

Gib mal das gesamte Format an, bzw. ein repräsentatives Subset davon, dann probier ich mich vielleicht an einem Parser.

Grundsätzlich gilt bei Parsern:
- Am effizientesten ist es, gleich in das Endformat zu parsen, d.h. du entscheidest, wie du die Daten halten möchtest, dass sie effizient in der späteren Nutzung sind (mal ohne Rücksicht auf Parsen). Dann versuchst du, diese Struktur gleich beim Lesen der Datei zu erstellen.
- Substrings hältst du als Start- und Endpointer auf den grossen String aus der Datei. Dafür kann man sich eine string_ref-Klasse schreiben (Beispielimplementation findest du auf Boost.org).
- 50'000 Tags ist quasi nichts. Selbst die langsamste Kette Datei->XML->Datenstruktur sollte in weit unter 0.1s laufen.
- Du wirst nie so schnell wie gute XML-Parser. Rekord liegt bei etwa 4*strlen()-Zeit, das wirst du nie ohne weiteres schaffen (noch brauchen). Deshalb vermute ich schon, dass ein schneller Präparser Format->XML sogar effizienter sein könnte, als alles selbst zu parsen. Kommt auf das genaue Format drauf an, ob sich dieser Weg lohnt.
- Noch einmal, weil es so wichtig ist: 50'000 Tags erfordert keinen schnellen Parser. Ich würde da selbst Regex in Betracht ziehen. Wenn sich herausstellt, dass das zu langsam ist, kannst du den Parser immer noch leicht auswechseln, wenn das Programm halbwegs gut designt ist. Aber meistens ist die Zeit anderswo besser investiert.