Gedcom-Datei parsen

[hansklok]

Hallo,

ich schreibe heute, da ich mir von der Community meiner alten Lieblingsprogrammiersprache Hilfe erhoffe, die mir die Kollegen des aktuellen Frameworks "Xojo" nicht geben können. An sich geht es um einen Algorithmus, deswegen ist die Plattform egal.

Was soll gepasst werden?

Eine Gedcom-Datei. Gedcom ist eine Textdatei, ein Format mit der Endung ".ged", in der Ahnenforscher Ihre Daten zum Stammbaum sichern können. Sie enthält Hauptobjekte (INDI, FAM, SOUR, OBJ, NOTE), die mit durch eine "0" am Zeilenanfang gekennzeichnet sind, und Unterobjekte (z.B. DATE, EVEN, PLAC etc.), die mit "1" oder größer gekennzeichnet werden.

Ich möchte eine Anwendung erstellen, die bestehende Gedcom-Dateien einlesen kann, um so mit den Daten zu arbeiten.

Wie?

Mein Gedanke war folgender: Erst einmal die Datei einlesen. Zum Beispiel in eine Stringlist. Anschließend alle Zeilen durchlaufen. Sollte die Zeile ein Hauptobjekt kennzeichnen, so soll die Zeilennummer als Anfangszeile in einer Variable gespeichert werden. Nennen wir sie A. Anschließend geht die Schleife weiter, bis zum nächsten Hauptobjekt. Nun soll in Variable B die Zeilennummer vor dem neuen Hauptobjekt gespeichert werden (B = Zeilennummer -1)

Haben A und B einen Wert, sollen diese als TPoint in einer Objektliste gespeichert werden.

Später, wenn die Springlist durchgelaufen ist, sollte man eine Liste haben, die alle Hauptobjekte, oder z.b. nur Personen enthält.
Für jeden Eintrag hat man nun die Start- und die Endzeilennummer und kann nun ebenfalls in einer Schleife jedes Objekt einzeln passen.

Darum gehts.

Was?

Ich suche Hilfe für den Algorithmus, der an sich sehr einfach sein sollte. Ich fände klasse, wenn man konzeptionelle Gedanken austauschen würde und/oder gemeinsam ein Strukturramm für diesen ersten Schritt zum einlesen einer Gedcom-Datei macht.

Wichtig: Das Xoxo-Framework bietet keine StringStreams.

Delphi-Quellcode:

procedure Parse(Gedcom As Stringlist)
var
  AktuelleZeile: String;
  AktuellesObjektName, AktuellesObjekt: String;  // INDI, FAM, SOUR, OBJ, NOTE
  i, Start, Ende: Integer;
  istObjekt: Boolean = False;
begin
  for i:=1 to Gedcom.Count do
  begin
    AktuelleZeile:= Gedcom.Items[i];
    if LeftStr(AktuelleZeile, 1) = "0" then    
        AktuellesObjektName = Copy(AktuelleZeile, 3, 4);
        AktuellesObjektName = Trim(AktuellesObjektName);
        // solange diese nicht der Header ist
        if AktuellesObjektName <> "HEAD" then
          // Typ auslesen (INDI, FAM etc.)
          AktuellesObjekt = RightStr(AktuelleZeile, 4);
          AktuellesObjekt = Trim(AktuellesObjekt);
          case AktuellesObjekt of
            "INDI":
              begin
                if istObjekt then
                  B = i-1
                  istObjekt = False
                  // an dieser Stelle würde ich nun einem Point A und B zuweisen und das Objekt in einer Liste speichern
                else
                  A = i;
                  istObjekt = True
                end;
              end;
          end;
        end;
    end;
  end;
end;

Das war so ein erster Gedankenansatz. Ich hoffe, ihr konntet mir folgen.

Eines ist noch zu bedenken: Das Ende einer Gedcom-Datei wird ebenfalls mit einer 0 am Beginn gekennzeichnet ("0 TRLR"). Sollte istObjekt = True sein, muss als B Gedcom.Count-1 gesetzt werden.

Ich freue mich über einen regen Austausch.
Gute Nacht!

[Perlsau]

Mir ist nicht so recht klargeworden, welche Hilfe du erwartest. Die Vorgehensweise zum Parsen der genannten Textdatei hast du doch bereits ausführlich beschrieben. Woran hapert es also noch? Funktioniert dein Code nicht? Erhältst du Fehlermeldungen? Wenn ja, welche?

Auch deinen Hinweis, daß das Xoxo-Framework keine StringStreams biete, verstehe ich nicht so ganz: Inwiefern ist das ausschlaggebend, wenn du doch gar nicht mit diesem Framework arbeiten willst, sondern lediglich mit der bezeichneten Textdatei?

[TiGü]

Ist das jetzt nur für dich als Spielerei gedacht oder soll das ein ernsthaftes Produkt werden?
Bei so übermächtigen Konkurrenten wie MyHeritage braucht ihr schon ein dickes Alleinstellungsmerkmal, um gegenüber denen zu bestehen.

[CCRDude]

Ich glaube, er hat nicht gesagt, dass er nicht mit dem Framework arbeiten möchte, sondern dass es egal sei, weil es nur um den Algorithmus und nicht die konkrete Implementierung gehe.
Sprich: er will Hilfe zum Algorithmus, und meint auch hier gut aufgehoben zu sein, obwohl wir Pascal sprechen

Zur Idee an sich: Zeilennummern merken wird sehr komplex. Was, wenn einer Person ein Feld hinzugefügt wird? Dann müssen alle Indizes danach angepasst werden. Ditto umgekehrt für Löschen.

Zum Parsen Personenblöcke übergeben mag noch gehen.
Pro Personenobjekt den Personenblock im Speicher halten auch, um unbekannte Felder uminterpretiert mitschleifen zu können.
Aber globale Indizes halte ich für zu unnötig umständlich.

Eine alternative Idee für das Umgehen mit dateiweiten Indizes wäre, jede Zeile als Objekt zu betrachten, denn Zeiger wären im Gegensatz zu Indizes bei Einfügeoperationen etc. stabil.

[TiGü]

Ich würde mich einfach mal durch die Quelltexte dieser Open Source Projekte lesen:

http://sourceforge.net/directory/hom...ently-updated/

Die müssen ja auch alle irgendwie die GEDCOM-Datei parsen.

[Dejan Vu]

Das sieht doch ganz wie eine Baumstruktur aus. Klar, wenn der Level (erste Ziffer) größer wird, hängt ein Kind dran. Wird er wieder kleiner, ist es ein weiterer Knoten im letzten Knoten des gleichen Levels. Nicht weiter wild, das einzulesen. Ich glaube, die Notation heißt 'Infix' (im Gegensatz zu Postfix oder Prefix)

Und es ist auch nicht weiter wild, das wieder abzuspeichern (Wieder Infix).
Ich würde mir also keine Gedanken darüber machen, die einzelnen Zeilennummern mitzuspeichern, denn sobald Du irgendwo etwas umsortiertst, entfernst oder hinzupackst, stimmten die Nummern ja nicht mehr.

Ich würde mir also eine Klasse für einen abstrakten Knoten definieren und davon die einzelnen Datentypen/Knotentypen ableiten (INDI, SOUR etc.)

Ein Knoten ist ein Ding mit Nutzdaten und eine Liste von Unterknoten. Die Nutzdaten ist Text, Datum, ein Dokument vielleicht, ein Bild(?) etc.

Xojo kann Klassen? Wenn ja: Fein. Wenn nicht. Dann... Oh je, wie war das doch gleich? Ach ja, wir bauen uns dann selbst einen Baum zusammen. Auf abstrakte Knoten etc. müssen wir dann eben pfeifen und alles über Arrays abbilden.

[hansklok]

Zitat von Perlsau:

Mir ist nicht so recht klargeworden, welche Hilfe du erwartest. Die Vorgehensweise zum Parsen der genannten Textdatei hast du doch bereits ausführlich beschrieben. Woran hapert es also noch?

Es geht um den konzeptionellen Gedanken für einen Algorithmus, also die Performance, da ja doch etliche Stringelemente pro Objekt ausgelesen werden müssen.

Zitat von TiGü:

Ist das jetzt nur für dich als Spielerei gedacht oder soll das ein ernsthaftes Produkt werden?
Bei so übermächtigen Konkurrenten wie MyHeritage braucht ihr schon ein dickes Alleinstellungsmerkmal, um gegenüber denen zu bestehen.

Ja, es ist eine private "Spielerei". Ich möchte meine Daten in eine spezielle Form bringen, die mir kein auf dem Markt befindliches Produkt so bietet und der Aufwand wird sich lohnen. Ich habe viel Zeit damit verbracht nach dem zu suchen, was ich will und habe es nicht gefunden.

Zitat von TiGü:

Ich würde mich einfach mal durch die Quelltexte dieser Open Source Projekte lesen:

http://sourceforge.net/directory/hom...ently-updated/

Die müssen ja auch alle irgendwie die GEDCOM-Datei parsen.

Ja, das habe ich schon getan. Für mich war aber bisher der richtige Ansatz noch nicht dabei.

Zitat von Dejan Vu:

Xojo kann Klassen? Wenn ja: Fein. Wenn nicht. Dann... Oh je, wie war das doch gleich? Ach ja, wir bauen uns dann selbst einen Baum zusammen. Auf abstrakte Knoten etc. müssen wir dann eben pfeifen und alles über Arrays abbilden.

Und ob Xojo Klassen kann und zwar klasse Die Sache mit dem Baum ist, und da kenne ich mich noch zu wenig aus. Vom Verständnis her.

Mit der Notation "Infix" kann ich leider nichts anfangen. Was ist das?

[Dejan Vu]

Infix bedeutet beim Aufzählen aller Knoten eines Baumes: Erst 'mich', dann meine Kinder.
Prefix bedeutet (beim binären Baum): Erst linkes Kind, dann mich, dann rechtes Kind
Postfix 'erst rechts, dann ich, dann links'
Vielleicht war ich zu voreilig, und es gibt Pre- und Postfix-Notation bei t-ären(t>2) Bäumen gar nicht. (t-ärer Baum: Jeder Knoten kann max t Kinder haben).

Beim Aufzählen (und damit beim *erzeugen* der GEDCOM-Datei) würde man in etwa so vorgehen:

Code:

print-gedcom (node, level):
  print level, node.type, node.description
  for each child in node.children
    print-gedcom(child, level + 1)

und der Aufruf startet mit

Code:

  foreach node in root-nodes 
    print-gedcom (node, 0)

Wie Du siehst, haben wir es hier mit einer rekursiven Datenstruktur zu tun, d.h. die Klasse 'Knoten' beinhaltet widerum 'Knoten' (nämlich die Liste der Kindknoten).

Mal das mal auf: Oben die Wurzel (hier: Level: -1)
darunter alle Hauptknoten (Level 0)
Unter jeden Hauptknoten kommen seine Unterknoten (Level 1)
und unter jeden Unterknoten (level k) wieder sein Unterknoten (Level k+1)
usw.

[hansklok]

Zitat von Dejan Vu:

Vielleicht war ich zu voreilig, und es gibt Pre- und Postfix-Notation bei t-ären(t>2) Bäumen gar nicht. (t-ärer Baum: Jeder Knoten kann max t Kinder haben).

Dankeschön. Genauso ist es, eine Person kann 0..* Kinder haben.

Die Wurzel ist immer das erste INDI-Record eine Gedcom-Datei (z.B. "0 @I1@ INDI").

So richtig hilft mir der Gedankenansatz nicht weiter

[Sir Rufo]

Wenn schon, dann solltest du die ganze Datei parsen. Dann beginnt es schon mal beim HEAD. Aber das ist schon der erste Knoten, die wirkliche Root-Node ist die Datei selber.

Die Zeile fängt immer mit einer Zahl an und die referenziert auf den Parent im aktuellen Kontext.

Du brauchst also schon mal ein Konstrukt, wo du immer auf die aktuelle Parents zugreifen kannst.

Code:

0 ...

Delphi-Quellcode:

// Node einfügen
AddNode( TNode.Create( GetParent( 0 ) );
// diese Node wird ab nun bei GetParent( 1 ) zurückgeliefert
// GetParent( n ) mit n > 1 liefert nun eine Exception!

Code:

1 ...
2 ...
3 ...
1 ...

Delphi-Quellcode:

AddNode( TNode.Create( GetParent( 1 ) );
AddNode( TNode.Create( GetParent( 2 ) );
AddNode( TNode.Create( GetParent( 3 ) );

AddNode( TNode.Create( GetParent( 1 ) );
// Ab nun kann man nicht mehr auf Parent 2/3 zugreifen

Das würde ich zunächst umsetzen. Wenn das funktioniert, dann weitere Ableitungen von der Node-Basisklasse erstellen und spezialisieren.