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.

[TiGü]

Zitat von hansklok:

So richtig hilft mir der Gedankenansatz nicht weiter

Was ist denn dein konkretes Problem?
Suchst du nach der passenden Baum- und/oder Klassenstruktur?

[hansklok]

Zitat von TiGü:

Zitat von hansklok:

So richtig hilft mir der Gedankenansatz nicht weiter

Was ist denn dein konkretes Problem?
Suchst du nach der passenden Baum- und/oder Klassenstruktur?

Die Klassenstruktur habe ich. Ich habe sie nach der Gedcom 5.51 Definition erstellt.

Das war an sich auch nicht das Problem, da ich ja nun die Datenstruktur/Modell habe. Es geht einzig und allein darum, wie ich eine bestehende Gedcom-Datei schnell einlesen kann. Und ich befürchte, dass das bei den ganzen Stringoperationen und bei Gedcom-Dateien mit 10000 Personen und/oder Familien und mehr etc. gar nicht so einfach ist, einen guten, schnellen Algorithmus zum parsen zu schreiben.

[Sir Rufo]

Hier mal so ein Minimalprogramm zum Veranschaulichen

Delphi-Quellcode:

program dp_183093;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.Generics.Collections,
  System.SysUtils;

type
  TNode = class
  private
    FParent: TNode;
    FChildren: TList<TNode>;
    function GetLastChild: TNode;
    function GetChildCount: Integer;
    function GetChild( Index: Integer ): TNode;
  public
    constructor Create( AParent: TNode );
    destructor Destroy; override;

    procedure AddChild( ANode: TNode );

    property ChildCount: Integer read GetChildCount;
    property Children[Index: Integer]: TNode read GetChild;

    property Parent: TNode read FParent;
    property LastChild: TNode read GetLastChild;
  end;

  TGedFile = class( TNode )
  private
    function GetParent( Index: Integer ): TNode;
  public
    constructor Create( AValues: TArray<Integer> );
  end;

  { TNode }

procedure TNode.AddChild( ANode: TNode );
begin
  if Assigned( ANode.Parent ) and ( ANode.Parent <> nil )
  then
    raise Exception.Create( 'Fehlermeldung' );

  ANode.FParent := Self;

  if not FChildren.Contains( ANode )
  then
    FChildren.Add( ANode );
end;

constructor TNode.Create( AParent: TNode );
begin
  inherited Create;
  FChildren := TObjectList<TNode>.Create;
  if Assigned( AParent )
  then
    AParent.AddChild( Self );
end;

destructor TNode.Destroy;
begin
  FChildren.Free;
  inherited;
end;

function TNode.GetChild( Index: Integer ): TNode;
begin
  Result := FChildren[Index];
end;

function TNode.GetChildCount: Integer;
begin
  Result := FChildren.Count;
end;

function TNode.GetLastChild: TNode;
begin
  Result := FChildren.Last;
end;

{ TGedFile }

constructor TGedFile.Create( AValues: TArray<Integer> );
var
  LValue: Integer;
begin
  inherited Create( nil );

  for LValue in AValues do
    begin
      TNode.Create( GetParent( LValue ) );
    end;
end;

function TGedFile.GetParent( Index: Integer ): TNode;
begin
  Result := Self;
  while Index > 0 do
    begin
      if not Assigned( Result )
      then
        raise Exception.Create( 'Fehlermeldung' );
      Result := Result.LastChild;
      Dec( Index );
    end;
end;

procedure OutputNode( ANode: TNode; ALevel: Integer = 0 );
var
  LIdx: Integer;
begin
  Write( '':ALevel, ANode.ToString );
  if ALevel > 0
  then
    Write( ' (', ALevel - 1, ')' );
  WriteLn;
  for LIdx := 0 to ANode.ChildCount - 1 do
    OutputNode( ANode.Children[LIdx], ALevel + 1 );
end;

procedure Main;
var
  LFile: TGedFile;
begin
  LFile := TGedFile.Create( TArray<Integer>.Create( 0, 1, 2, 3, 1, 1, 1, 2, 3, 3, 3, 3 ) );
  try
    OutputNode( LFile );
  finally
    LFile.Free;
  end;
end;

begin
  try
    Main;
  except
    on E: Exception do
      WriteLn( E.ClassName, ': ', E.Message );
  end;
  ReadLn;

end.

Ausgabe ist dann wie folgt

Code:

TGedFile
 TNode (0)
  TNode (1)
   TNode (2)
    TNode (3)
  TNode (1)
  TNode (1)
  TNode (1)
   TNode (2)
    TNode (3)
    TNode (3)
    TNode (3)
    TNode (3)

[TiGü]

Zitat von hansklok:

Und ich befürchte, dass das bei den ganzen Stringoperationen und bei Gedcom-Dateien mit 10000 Personen und/oder Familien und mehr etc. gar nicht so einfach ist, einen guten, schnellen Algorithmus zum parsen zu schreiben.

Dann dauert das eben ein bisschen beim Einlesen.
Wie oft man das für eine GEDCOM-Datei? => Einmal!
Das reine GEDCOM auslesen ist ja nicht das Problem, oder?

Viel schwieriger stelle ich mir vor, die logische Verknüpfung und Visualisierung hinzugekommen.
Meine Ur-ur-ur-Großeltern waren beispielsweise entfernte Cousins und hatten einen gemeinsamen Ur-ur- bzw. Ur-ur-ur-Großvater.
Wie erkennt man solche "geschlossenen Kreise" im Stammbaum?
Gerade bei 10.000 Personen, die sonst wie miteinander verwandt sein können, hast du zwangsläufig die unmöglichsten Konstellationen.