fuzzy matches via sql

[mkinzler]

Beispiel einer einfachen Levenstein-Funktion:

Delphi-Quellcode:

function LevenshteinDistance( s: string; t: string): Integer;
var
  i, j, cost, h: Integer;
  d: array[0..255, 0..255] of integer;
  n,m: integer;
begin
   n := Length(s);
   m := Length(t);

   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
       for j := 1 to m do
       begin
           if s[i] = t[j] then cost := 0
                          else cost := 1;
           h := min(d[i-1,j  ] + 1,    // Einfügen
                             d[i,  j-1] + 1); // Löschen
           d[i,j] := min(    h,
                             d[i-1,j-1] + cost); // Ersetzen
        end;
   result :=  d[n,m];
end;

Wenn du diese Funktion in eine UDF verpackst, kannst du diese in einer SP verwenden.

[Kedariodakon]

SQL-Code:

Select Top 1 Abs( feld - x ) As Sort, * From tabelle
Order By Sort

Bye

Edit funzt zumindest solange x eine Zahl ist :wink:

[sancho1980]

Zitat:

Beispiel einer einfachen Levenstein-Funktion:

Cool, danke
Am elegantesten wärs natürlich wenn ich das Ganze jetz als stored procedure implementiere
geht das?
keine angst, versuch das dann selbst irgendwie zu bauen; nur mal so ne frage ob's möglich ist, (feld-)variablen in einer sp zu deklarieren...

Zitat:

zumindest solange x eine Zahl ist

was ja mal eben nicht der Fall ist :mrgreen:

[mkinzler]

Ich habe hier mal zum Test, die UDF und eine SP erzeugt. Ich hoffe es hilft dir.

[sancho1980]

cool danke,
voll nett
versuch das abend gleich mal zu installieren
evtl muss ich nochmal nerven :stupid:

[mkinzler]

Ich habe die UDF um einen Parameter erweitert und die SP angepasst.

Die UDF hat unterschiedliche Längen der beiden Strings berücksichtigt. Das in diesem Fall zu falschen Ergebnissen führen kann.

z.B.

Daten Tabelle:

ID TEXT
...
10 Gemüse
11 Z

Suchtext: gem

Es wird der Datensatz 11 zurückgeliefert da zur Umformung hier weniger Schritte notig sind als beim Datensatz 10.

Es gibt nun einen weiteren Parameter in dem den Umgang der Längen steuern kann
0: Wie bisher
1: Länge erster String ( 2. String wird ggf mit Leerzeichen aufgefüllt)
2: Länge zweiter String ( 1. String wird ggf mit Leerzeichen aufgefüllt)
3: es wird die Länge des kürzesten Strings verwendet.

Ich habe das Originalarchiv ersetzt.

[Kedariodakon]

Naja, das ist halt Levenshtein :wink:
Für das Problem kann man verschiedene Kosten implementieren, wass schlußendlich noch Levenshtein ist im gegensatz zu dem was du da mit dem Auffüllen machst :roll:

Levenshtein

Zudem is deine Levenshtein Funktion ein wenig naja, wenn die Zeichenketten mit mehr als 255 Zeichen bekommt, knallts...

Besser wer sicher ein dynamisches Array... :)

Bye Keda

[mkinzler]

Das ganze war auch nicht als Universal-Lösung gedacht, sondern als Beispiel wie man das lösen könnte.

[mkinzler]

In Anlehnung an die Bemerkung von [user="Kedariodakon"] habe ich meine unvollständige, fehlerhaftes Test-UDF/SP nochmal überarbeitet. Auch dieses ist gewiss unvollständig und zerstörrt möglicherweise euren Rechner und ... ;-)

Die Kosten sind nun als 4. Parameter implementiert.

Ich habe wieder das Original ersetzt.

[sancho1980]

Hi Leute,
hab mir die Geschichte mit dem Levenshtein mal zu Gemüte geführt. Dazu 2 Fragen:

1.

Zitat:

Die Kosten sind nun als 4. Parameter implementiert.

Wieso? Die Kosten sind doch der Rückgabewert.. Was gibt's da zu übergeben?

2.
Hab mir auch mal durchgelesen wie der Algorithmus funktioniert. Interessant, dass es funktioniert; aber kapiert einer von euch wie man auf sowas kommt? Gibt's irgendwo nen Beweis, dass der Algorithmus immer das richtige Ergebnis liefert?

Gruß,

Martin