fuzzy matches via sql

[sancho1980]

hallo
ich habe eine frage,
stellt euch folgende sql-abfrage vor:

SQL-Code:

select * from tabelle where feld = x

angenommen, die ergebnismenge ist leer; kann ich meine select-abfrage irgendwie abändern, so dass ich trotzdem noch wenigsten denjenigen datensatz zurückbekomme, dessen feld-wert von allen am nächsten an x dran ist?
danke,
martin

[Catbytes]

Zitat:

Zitat von sancho1980

hallo
ich habe eine frage,
stellt euch folgende sql-abfrage vor:

SQL-Code:

select * from tabelle where feld = x

angenommen, die ergebnismenge ist leer; kann ich meine select-abfrage irgendwie abändern, so dass ich trotzdem noch wenigsten denjenigen datensatz zurückbekomme, dessen feld-wert von allen am nächsten an x dran ist?
danke,
martin

Wie wäre es mit LIKE?

SQL-Code:

select * from tabelle where feld LIKE x

[sancho1980]

klingt naheliegend nur leider bekomm ich da die gleiche ergebnismenge zurück wie bei '='; also leer wenn es keinen datensatz mit GENAU dem wert gibt :-(

[Klaus01]

wenn es sich um einen Strinwert handelt kannst Du auch mit Wildcards arbeiten.

select * from tabelle where feld LIKE %x%

Grüße
Klaus

[marabu]

Hallo Martin,

das ist ein Standardproblem und es wird so gelöst:

SQL-Code:

/* predecessor when missing */
select * from tabelle where feld <= :x order by feld desc rows 1

/* successor when missing */
select * from tabelle where feld >= :x order by feld rows 1

Grüße vom marabu

[sancho1980]

Hmmm,
das is aber nicht ganz das Gleiche, weil ich da vorher wissen muss, ob ich den Vorgänger oder den Nachfolger will. Ich will aber genau denjenigen Eintrag, der am geringsten von Beiden von meinem gewünschten String entfernt ist. Wenn es irgendwie 'ne Möglichkeit gäbe, in SQL nach der Differenz zwischen zwei Strings zu fragen, dann müsstes irgendwie gehen...

[mkinzler]

Dein Problem kannst du möglicherweise in einer SP in Verbindung mit einer SoundEx-Funktion lösen. In der SP interierst du über alle Datensätze und vergleichst den Suchstring mit dem Werten und merkst dir den Datensatz mit der höchsten Ähnlichkeit. Diesen gibst du dann zurück.

[Klaus01]

hier ist mal ein Lin, wo über soundex diskutiert wurde
-> http://www.wer-weiss-was.de/theme165...le1718061.html
Ist nicht sehr erbaulich was dabei herauskam.

Grüße
Klaus

[sancho1980]

Zitat:

In der SP interierst du über alle Datensätze und vergleichst den Suchstring mit dem Werten

Sehr rechenintensiv, oder?
Wär's nicht besser einfach nur zu schauen, OB der Datensatz da ist und wenn er NICHT da ist einfach mit Vorgänger und Nachfolger zu vergleichen und dann den mit der geringsten Differenz zurückzugeben?
Das Problem ist nur, dass ich nicht genau weiß wie ich das ausdrücken muss
ich meine wie ich so eine Stored Procedure definiere, krieg ich ja vielleicht noch raus, aber wie berechne ich die Differenz zwischen zwei Strings? Oder besser: wie bestimme ich, welcher von Zwei Strings x und y dem String z am ähnlichsten ist??

Zitat:

hier ist mal ein Lin, wo über soundex diskutiert wurde

Hab mal gegooglet was Soundex ist: Ne, sowas mein ich nicht. Es geht mir nicht darum, denjenigen Datensatz zu finden, der am ähnlichsten KLINGT, sondern den, der gemäß der in der Datenbank gesetzten Sortierreihenfolge am ähnlichsten GESCHRIEBEN wird und zwar unabhängig davon, ob's der Nachfolger oder Vorgänger ist...

[marabu]

Hallo Martin,

Zitat:

Zitat von sancho1980

Ich will aber genau denjenigen Eintrag, der am geringsten von Beiden von meinem gewünschten String entfernt ist. Wenn es irgendwie 'ne Möglichkeit gäbe, in SQL nach der Differenz zwischen zwei Strings zu fragen, dann müsstes irgendwie gehen...

es gibt beliebig viele Metriken zur Bestimmung des Abstandes zweier Strings. Der amerikanische Soundex-Algorithmus zielt ja nur auf den Gleichklang von Namen. Weiter verbreitet ist der Editierabstand nach Levenshtein - der Name ist auch hier in der DP schon aufgetaucht. Du solltest vielleicht mal deine Anforderungen genauer erklären - um so hilfreicher werden die Beiträge.

marabu

[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

[mkinzler]

zu 2.) Es wird berechnet in wie vielen Schritten durch Hinzufügen, Entferen oder Ersetzen ein String zu einem anderen umgeformt werden kann.

z.B. Von Hans -> Dampf

Hans
Dans 1 Ersetzen
Damp 2 Ersetzen
Dampf 3 Hinzufügen

1.) Zurückgeliefert wird die Anzahl der Schritte, Kosten sind ein Gewichtsfaktor um verschiedene Umwandlungsformen verschieden zu bewerten.

[Kedariodakon]

So ist es :wink:

Hier habt ihr eine Funktion, bei welcher man die verschiedenen Kosten angeben kann, oder man benutzt sie ohne Angaben wie eine normale.

Delphi-Quellcode:

Function  WeightedLevenshteinDistance( Const FromStr, ToStr: String; Const CostCase: Integer = 0;
  Const CostSubst: Integer = 1; Const CostIns: Integer = 1; Const CostDel: Integer = 1 ): Integer;
Var Costs:  Array Of Array Of Integer;
    Len1:   Integer;
    Len2:   Integer;
    i1:     Integer;
    i2:     Integer;
    Cost:   Integer;
Begin
  Len1  := Length( FromStr );
  Len2  := Length( ToStr   );
  Try
    SetLength( Costs, Len2 + 1, Len1 + 1 );
    For i2 := 0 To Len1 Do Costs[ 0, i2 ] := i2 * CostDel;
    For i1 := 1 To Len2 Do Begin
      Costs[ i1, 0 ] := i1 * CostIns;                                       
      For i2 := 1 To Len1 Do Begin 
        If      ToStr[ i1 ]              = FromStr[ i2 ]               Then Cost := 0
        Else If UpperCase( ToStr[ i1 ] ) = UpperCase( FromStr[ i2 ] )  Then Cost := CostCase        
        Else                                                                Cost := CostSubst;
        Costs[ i1, i2 ]  := Min( Min( Costs[ i1 - 1, i2     ] + CostIns,
                                      Costs[ i1    , i2 - 1 ] + CostDel ),
                                 Costs[ i1 - 1, i2 - 1 ] + Cost );
      End;
    End;  
    Result  := Costs[ Len2, Len1 ];
  Finally
    Finalize( Costs );
  End;
End;

Bye