Gedcom-Datei parsen

[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.

[hansklok]

[QUOTE=TiGü;1283119]

Zitat von hansklok:

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.

Genau das ist der Grund, warum ich mich so schwer tue, alles in einer Binärbaum-Struktur unterzubringen.

Die Personen/Familien werden alle in einer eigenen Liste gespeichert. Auf sie zugreifen kann man über deren UUID. Dann ist es auch möglich Spezialfälle wie Inzucht oder Cousin- & Cousinenehen darzustellen.

[Sir Rufo]

Die GEDCOM-Datei ist aber nun mal in einer Baum-Struktur abgelegt. Um das vernünftig aufbrechen zu können packt man den Dateiinhalt in so einen Baum und kann sich dann aus diesem Baum einfach bedienen.

Der Baum ist nur für das Einlesen gedacht. Kann aber, wenn der Baum durch die Daten befüllt wird auch dazu dienen wieder eine GEDCOM-Datei zu erstellen.

Das muss man ganz klar trennen.

Beispiel der Knoten NOTE kann Unterknoten CONT und der Unterknoten CONC haben. Da alle zugehörigen aber an NOTE hängen, kann ich aus dem Knoten NOTE den gesamten Text auslesen und in ein Memo-Feld einer Datenbank speichern.

[hansklok]

OK, soweit habe ich das verstanden.

Ich lese die Datei via TextInputStream ein (in Delphi TStringList) - und zwar Zeilenweise. Ich überprüfe, ob die Zeile mit 0 beginnt und extrahiere dann den Typ. Soweit klappt das.
Wenn Das Objekt vom z.B. Typ "INDI" ist, Erstelle ich dementsprechend eine neues IndividualRecord und rufe dessen Parser-Methode auf. Auch das klappt. ABER, und jetzt wieder zum Algorithmus, wie kann ich die Folgezeilen auslesen, ohne, dass ich unendlich viele und unnötige Schleifen aufmache?

[Sir Rufo]

Also das hier lädt mir eine komplette StressTest-Demo-Datei ein

Delphi-Quellcode:

procedure TGedFile.LoadFromFile( const Filename: string );
var
  LValue: TDataRecord;
  LCurrent: TNode;
  LCurrentIdx: Integer;
  LLines: TStringList;
  LLine: string;
begin
  LCurrent := Self;
  LCurrentIdx := 0;

  LLines := TStringList.Create;
  try

    LLines.LoadFromFile( Filename );

    for LLine in LLines do
      begin

        LValue := ParseLine( LLine );

        while LCurrentIdx <> LValue.Level do
          begin
            if LCurrentIdx < LValue.Level
            then
              begin
                LCurrent := LCurrent.LastChild;
                Inc( LCurrentIdx );
              end
            else
              begin
                LCurrent := LCurrent.Parent;
                Dec( LCurrentIdx );
              end;
          end;

        if LValue.DataIsReference
        then
          LCurrent := TRefNode.Create( LCurrent, TNodeType.Create( LValue.NodeTypeStr ), LValue.Data, FReferenceDict )
        else
          LCurrent := TDataNode.Create( LCurrent, TNodeType.Create( LValue.NodeTypeStr ), LValue.Data );

        Inc( LCurrentIdx );

        if not LValue.Reference.IsEmpty
        then
          FReferenceDict.Add( LValue.Reference, LCurrent );
      end;

  finally
    LLines.Free;
  end;

end;

function TGedFile.ParseLine( const ALine: string ): TDataRecord;
var
  LValues: TArray<string>;
  LPrefix: string;
begin
  LValues := ALine.Split( [' '], 3 );
  Result.Level := LValues[0].ToInteger;

  // Reference gefunden?
  if LValues[1].StartsWith( '@' )
  then
    begin
      Result.Reference := LValues[1];
      Result.NodeTypeStr := LValues[2];
    end
  else
    begin
      Result.Reference := '';
      Result.NodeTypeStr := LValues[1];
      SetLength( LValues, 2 );
    end;

  LPrefix := string.Join( ' ', LValues );

  Result.Data := ALine.Substring( LPrefix.Length + 1 );
  Result.DataIsReference := Result.Data.StartsWith( '@' );
end;

Damit habe ich die im Speicher und kann auf jeden Knoten ganz gemütlich zugreifen um die Daten nun auszulesen und sonstwie zu verarbeiten. Die erzeugten Nodes parsen hier gar nichts ... wozu auch

[hansklok]

Zitat von Sir Rufo:

Also das hier lädt mir eine komplette StressTest-Demo-Datei ein

Kannst Du den Quellcode bitte bisschen kommentieren? Was ist bei Dir TDataRecord?

Was macht LValue.DataIsReference?

[hansklok]

Zitat von Sir Rufo:

Also das hier lädt mir eine komplette StressTest-Demo-Datei ein

Kannst Du bitte deinen gesamten Source posten, dann kann ich ersten besser nachvollziehen und zweitens versuchen in Xoxo zu übersetzen, an sich nicht schwer.