Pseudo StringSimilarity() Funktion

[Aphton]

Hiermit möchte meine noch nicht allzu durchtachte kleine Stringvergleichsfunktion vorstellen.
Der Algorithmus geht den kürzeren String durch und addiert auf das Ergebnis einen transformierten Positionsdifferenzwert hinzu. Hinzu kommt noch, dass auf Groß- & Kleinschreibung geachtet wird!

Hab mich nie wirklich mit ähnlichen Sachen beschäftigt; habs vor fünf Minuten gebraucht und da sich im Internet nichts Ähnliches finden ließ, dachte ich mir, warum nicht selbst schreiben.

Er erfüllt seine Pflicht ausreichend. Für Verbesserungsvorschläge stehe ich immer offen und würde darum eig. dringendst bitten!

Übrigens, je ähnlicher die Strings sind, desto näher ist das Ergebnis dem Wert 1 und je verschiedener, desto näher 0!

Delphi-Quellcode:

function StringSimilarity(Str1, Str2: String): Single;
var
  Str1Len, Str2Len: Integer;
  smallLen, bigLen: Integer;
  smallStr, bigStr: PString;
  i, p, f: Integer;
  equalLetterSize: Boolean;
begin
  Result    := 0;
  Str1Len   := Length(Str1);
  Str2Len   := Length(Str2);    
  if Min(Str1Len, Str2Len) = 0 then Exit;
  if Str1Len > Str2Len then
  begin
    bigStr := @Str1;
    smallStr := @Str2;
    bigLen := Str1Len;
    smallLen := Str2Len;
  end else
  begin
    smallStr := @Str1;
    bigStr := @Str2;
    smallLen := Str1Len;
    bigLen := Str2Len;
  end;
  for i := 1 to smallLen do
  begin
    equalLetterSize := True;
    p := Pos(smallStr^[i], bigStr^);
    if p = 0 then
    begin
      equalLetterSize := False;
      p := Pos(LowerCase(smallStr^[i]), Lowercase(bigStr^));
    end;
    if p = 0 then continue;
    bigStr^[p] := #0;
    f := 1;
    if not equalLetterSize then inc( f );
    Result := Result + (bigLen-Abs(i-p)) / (f*bigLen);
  end;
  Result := Result*4 / (bigLen*smallLen*Max(bigLen-smallLen, 1));
end;

Code:

  StringSimilarity( 'Abcd', 'Abcd' ) = 1
  StringSimilarity( 'Abcd', 'abcd' ) = 0.875
  StringSimilarity( 'Abcd', 'acbd' ) = 0.75
  StringSimilarity( 'Abcd', 'dcba' ) = 0.4875
  StringSimilarity( 'Abcd', 'A' )     ~ 0.333*
  StringSimilarity( 'Abcd', 'a' )     ~ 0.166*

[shmia]

Du kommst 46 Jahre zu spät. 8-) 8-)
Levenshtein-Distanz

[Aphton]

Boah, danke ^^
Endlich mal Stoff zum Lesen xD

[Sir Rufo]

Oder mit Fuzzy

[Deep-Sea]

Oder, wenn man auf phonetische Ähnlichkeit prüfen mag: Double Metaphone :thumb:

[ChrisE]

Zitat:

Zitat von Deep-Sea (Beitrag 1093866)

Oder, wenn man auf phonetische Ähnlichkeit prüfen mag: Double Metaphone :thumb:

SoundEx wäre dafür etwas vergleichbares fertiges, oder?

Gruß, Chris

[Deep-Sea]

Schon fertig in Delphi implementiert ist SoundEx, ja. Aber vergleichbar? Ungefähr so, wie 'n VW Käfer mit 'nem Porsche :P
SoundEx klappt halt nur halbwegs gescheit bei englischen Wörtern, während (Double) Metaphone u.a. auch bei deutschen Wörtern sehr gute Ergebnisse liefert.
Habe selbst schon öfters in Datenbänken von unseren Kunden eine Person mit Hilfe von Double Metaphone gesucht, die einen türkischen oder anderen, ausländischen Namen hatten - klappt wunderbar. :-D

Aber wie immer: Es kommt drauf an, was man erreichen will.

[shmia]

SoundEx ist "Schrott" und sollte nicht verwendet werden.
Begründung:
1.) passt nur für englische Sprache
2.) selbst bei englischen Wörtern können zwei völlig ungleiche Wörter als gleich angesehen werden (siehe hier)
3.) ähnliche Wörter (z.B. Buchstabendreher) werden häufig nicht als ähnlich erkannt
3.) SoundEx wurde zu einer Zeit entwickelt, da es noch keine Computer gab. :shock:
Jedem Wort wird ein Soundex-Code mit 4 Zeichen zugeordnet.
Für diese Codes gab es früher sicher Nachschlagewerke (ähnlich einem Telefonbuch)
weil man den Algorithmus nur im menschl. Gehirn durchführen konnte.

Anstatt dass zwei Wörter direkt miteinander verglichen werden, vergleicht man diese 4-stelligen SoundEx-Codes auf Gleichheit.
Dies ist die ganz grosse Schwäche des Verfahrens.

==> also werft SoundEx auf den Müllhaufen der Geschichte

[Deep-Sea]

Zitat:

Zitat von shmia (Beitrag 1093883)

Anstatt dass zwei Wörter direkt miteinander verglichen werden, vergleicht man diese 4-stelligen SoundEx-Codes auf Gleichheit.
Dies ist die ganz grosse Schwäche des Verfahrens.

Das macht (Double) Metaphone aber auch so ähnlich. Das hat nämlich auch Vorteile: Man kann den dazugehörigen Code (bzw. bei Double Metaphone sind es ja zwei) z.B. in eine Datenbank mit zum eigentlichen Wort ablegen, so dass man nur den Code des Wortes erzeugen muss das man sucht und danach die ähnlichen Wörter dank Datenbank in Windeseile findet.
Sonst müssten man ja jeden Eintrag einzeln durchgehen - das könnte bei einer großer Datenmenge eine Ewigkeit dauern :wink:

[MarcoWarm]

Hallo miteinander.

bei Entwicklung zu unserem SuggestEdit sind ein paar Units abgefallen, die hier vielleicht hilfreich sind.

• SoundEx
• Metaphone
• Fuzzy String via NGram (siehe Sir Rufo)
• Kölner Phonetik
• Double Metaphone
• Levenshtein

Die Units erheben keinen Anspruch auf Vollständigkeit. Und natürlich hat jede ihr spezielles Anwendungsgebiet. Wer einen Fehler findet, ist eingeladen ihn uns gern zu schicken.

Sobald sich chaosben von seiner OP erholt hat, wird's das Ganze sicherlich auch als Firebird UDFs geben :-D

Gruß
Marco