Und wieder Stringvergleich

[thatsme01]

Hallo

Ich beschäftige mich noch nicht so lange mit Delphi, möchte aber trotzdem 2 Strings vergleichen und bin auf der Suche nach einer Lösung.

Beispiel:
Es kommt ein String von einem OCR-Prog.

StringA=der Codename uon James Bond?

soll mit Memo.Lines verglichen werden. Dort steht

StringB=der Codename von James Bond?

Allerdings gibt mir das OCR-Prog nicht immer so leichte Fehler aus. StringA könnte auch mal so aussehen:

StingA=der Cod%ame *on Ja*es Bond*

Momentan habe ich als Lösung MatchPattern. Damit bin ich nicht ganz glücklich. Der Obere StringA wird dabei nicht erkannt, aber der Untere mit den Wildcards. Wie kann ich das anstellen, dass der Obere auch erkannt wird? Seit 2 Tagen bin ich auf der Suche nach einer Lösung, aber ich finde einfach keinen Ansatz. Es wär toll, wenn Ihr mir ein paar Ansätze liefern könntet.
Das Abzählen der Buchstaben und dann einen Vergleich machen, wieviel Übereinstimmungen es gibt würde, glaub ich, nicht viel bringen, weil ich vom OCR nur einen Teil geliefert bekomme und im Memo der String teilweise 3x so lang ist.

Gruß
Andy

[FredlFesl]

Stichworte sind "Fuzzy String matching", z.B. "Levenshtein-Distanz"

[rollstuhlfahrer]

Was willst du genau machen? - Soll dein Programm herausfinden, ob der String, den dein OCR-Programm mit dem, den du schon kennst, einigermaßen übereinstimmt?

Dann würde ich vielleicht den Fuzzy-Stringvergleich (Levenshtein-Distanz) verwenden. Dann bekommst du den Abstand zwischen 2 Strings und wenn dieser kleiner ist, als dein Grenzwert (der Grenzwert steht dazu allerdings in Abhängigkeit zu der Länge des Strings), hast du einen ähnlichen String, ansonsten sind beide zu verschieden.
Das sollte alles abdecken, was man so braucht.

Bernhard

PS: Da war mal wieder einer schneller

[FredlFesl]

Levenshtein ist nur eine Möglichkeit. Fuzzy-String-Matching ist eine Wissenschaft für sich. Richtig gemacht wird man diverse Verfahren nehmen und die Einzelergebnisse mit einer Heuristik bewerten.

[stahli]

Es gab hier schon einmal eine umfangreiche Diskussion.

[thatsme01]

Habt Dank für Eure Antworten und Anregungen. Ich werde mir die Sachen mal zu Gemüte führen und ausgiebig testen.

LG
Andy

[Bjoerk]

Hab‘ mal Levenshtein probiert. Läuft ganz gut soweit. Ist sicherlich noch ausbaufähig. Dein Beispiel (der CodeName von James Bond?, der Cod%ame *on Ja*es Bond*) hätte hiernach 85 % Übereinstimmung.

Delphi-Quellcode:

function Min3(const X, Y, Z: integer): integer;
begin
  if (X < Y) then
    Result:= X
  else
    Result:= Y; 
  if (Z < Result) then Result:= Z; 
end; 


function LevenshteinDistance(const S1, S2: string; const IgnoreCase: boolean): integer;
var
  Distance: array of array of integer;
  I, J, C, A1, A2, A3, N, M: integer;
  F: boolean;
begin
  N:= Length(S1);
  M:= Length(S2);
  SetLength(Distance, N+1, M+1);
  Distance[0, 0]:= 0;
  for I:= 1 to N do
    Distance[I, 0]:= 1;
  for J:= 1 to M do
  begin
    Distance[0, J]:= Distance[0, J-1]+1;
    for I:= 1 to N do
    begin
      if IgnoreCase then
        F:= (AnsiLowerCase(S1[I]) = AnsiLowerCase(S2[J]))
      else
        F:= (S1[I] = S2[J]);
      if F then
        C:= 0
      else
        C:= 1;
      A1:= Distance[I-1, J-1]+C;
      A2:= Distance[I, J-1]+1;
      A3:= Distance[I-1, J]+1;
      Distance[I, J]:= Min3(A1, A2, A3);
    end;
  end;
  Result:= Distance[N, M]; 
  SetLength(Distance, 0, 0); 
end;


function ImproveString(const S: string): string; 
const
  TCharSet: 
    Set of char = ['a'..'z', '0'..'9', 'A'..'Z',
      'ä', 'ö', 'ü', 'Ä', 'Ö', 'Ü', 'ß', ' ', '_'];
var
  I: integer;
begin
  Result:= '';
  for I:= 1 to Length(S) do
    if S[I] in TCharSet then Result:= Result+S[I]; 
end;


function CopyS(var S: string; I, J: integer): boolean;
begin
  if J > Length(S)-I+1 then
    Result:= false
  else
  begin
    Result:= true; 
    S:= Copy(S, I, J); 
  end; 
end; 


function StringCompare(const S1, S2: string; const IgnoreCase: boolean = true): integer;
var
  Distance, L1, L2: integer;
  T, T1, T2: string;
  I, J: integer;
begin
  T1:= ImproveString(S1);
  T2:= ImproveString(S2);
  if Length(T1) > Length(T2) then
  begin
    T:= T1; T1:= T2; T2:= T;
  end;
  Result:= 0;
  L1:= Length(T1);
  L2:= Length(T2);
  if L1 > 0 then
  begin
    Result:= L2;
    for I:= 1 to L1 do
      for J:= 1 to L1 do
      begin
        T:= T1;
        if CopyS(T, J, I) then
        begin
          Distance:= LevenshteinDistance(T, T2, IgnoreCase);
          // ShowMessage (T+#13+T2+#13+IntToStr(Distance));
          if Distance < Result then Result:= Distance;
        end;
      end;
    Result:= Round(100-100/L2*Result); // Übereinstimmung in %
  end;
end;


procedure TForm1.Button4Click(Sender: TObject);
begin
  ShowMessage ('Übereinstimmung = '+IntToStr(StringCompare(Edit1.Text, Edit2.Text))+' %');
end;