Tolleranter String-Vergleich

[Florian H]

Hi,

ich habe 2 Strings und möchte prüfen, ob die beiden annährern das gleiche enthalten.
Also z.B. bei "Guten Tag" sollte der Alogrithmus erkennen, dass "Gutn Tag" fast das selbe ist.
Ich hab da erst an diesen einen Alog. gedacht der die abweichenden Zeichen in einem String zählt (Hallo und Holla --> 2) aber da wäre das PRoblem, dass wenn ein Buchstabe z.B. fehlt, alle nachfolgenden Zeichen falsch gewertet würden. Abgesehen davon habe ich dessen name vergessen

Viele Grüße
Florian

[Chewie]

Meinst du vielleicht Levenshtein Levenshtein

Das lustige an dem Namen ist, dass eine Suchmaschine ebendiesen Algorithmus anwenden muss, um was zu finden, weil kein Mensch das Wort richtig schreibt

[Florian H]

ja genau den meine ich (wie soll ich mir sowas merken können ^^)
Der kann sogar das erkennen von "HAllo" und "xHAllo" = 1 richtig.

nur gibts das auch schon fertig als Delphi-Unit o.Ä.?

Google liefert leider fast nur PHP-Funktionsreferenzen...

[Florian H]

ok

Delphi-Quellcode:

unit Levenshtein;
//Objeto que calcula la distancia de Levenshtein entre 2 cadenas.
//Alvaro Jeria Madariaga. 04/10/2002
//[e-mail]
interface
uses sysutils, Math;
type
  Tdistance = class(TObject)
  private
    function minimum(a, b, c: Integer): Integer;
  public
    function LD(s, t: string): Integer;
  end;

implementation

function Tdistance.minimum(a, b, c: Integer): Integer;
var mi: Integer;
begin
  mi := a;
  if (b < mi) then
    mi := b;
  if (c < mi) then
    mi := c;
  Result := mi;
end;

function Tdistance.LD(s, t: string): Integer;
var
  d: array of array of Integer;
  n, m, i, j, costo: Integer;
  s_i, t_j: char;
begin
  n := Length(s);
  m := Length(t);
  if (n = 0) then begin
      Result := m;
      Exit;
    end;
  if m = 0 then begin
      Result := n;
      Exit;
    end;
  setlength(d, n + 1, m + 1);
  for i := 0 to n do
    d[i, 0] := i;
  for j := 0 to m do
    d[0, j] := j;
  for i := 1 to n do
    begin
      s_i := s[i];
      for j := 1 to m do
        begin
          t_j := t[j];
          if s_i = t_j then costo := 0 else costo := 1;
          d[i, j] := Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i -1][j - 1] + costo);
        end;
    end;
  Result := d[n, m];
end;
end.

danke

[FriFra]

Soundex wäre auch eine Lösung für Dein Problem