Ähnliche Strings

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo allerseits

Ich suche einen Algorithmus, der zwei Strings mit einander vergleicht und die Übereinstimmung als Zahl ausgibt. Also je größer die Zahl, umso besser die Übereinstimmung.
Z. B. 1 für komplette Übereinstimmung (Meier und Meier)
0.9 für Ähnlichkeit (Meier und Meyer)
0 für gar keine Ähnlichkeit.

Kann mir da jemand weiterhelfen?

Ratz

#2

hallo.

primitivalgorithmus:
nimm die länge des strings als 100%. für jeden übereinstimmenden buchstaben zählst du um den entsprechenden prozentsatz nach oben.
bei unterschiedlichen längen macht das allerdings probleme.

gruß

michael

#3

Ich suche einen Algorithmus, der zwei Strings mit einander
vergleicht und die Übereinstimmung als Zahl ausgibt. Also je
größer die Zahl, umso besser die Übereinstimmung.
Z. B. 1 für komplette Übereinstimmung (Meier und Meier)
0.9 für Ähnlichkeit (Meier und Meyer)
0 für gar keine Ähnlichkeit.

Wenn dir ein Ansatz mit ganzen Zahlen weiterhelfen könnte, wwirst du vielleicht unter dem Begriff Hamming-Abstand aus der Codierungstheorie fündig.

/dirk

#4

Hallo Ratz

Ich suche einen Algorithmus, der zwei Strings mit einander
vergleicht und die Übereinstimmung als Zahl ausgibt.

Welche Art Vergleich benötigst du denn? Sind die Differenzen in den Strings auf Tippfehler zurückzuführen oder auf Verständnisprobleme (z.B. Erfassen eines Kundennamens am Telefon), oder eine Kombination, oder…?

Als Ansatz kann ich dir den Soundex -Algorithmus empfehlen. In seiner Grundform (für phonetische Suche nach Namen, mit 26 Buchstaben) lautet er wie folgt:
Evtl. vorher Sonderzeichen aus den Strings entfernen und Umlaute in zwei Buchstaben auflösen (ä -> ae). Alles in Grossbuchstaben umwandeln, und/oder die Tabelle (s.u.) erweitern.

  1. Code = erster Buchstabe des Wortes
  2. Code = Code & Transformiere([Wort ohne ersten Buchstaben], Tabelle)
  3. Alle Nullen aus dem Code entfernen
  4. Alle hintereinanderstehenden gleichen Zahlen auf eine Zahl reduzieren.
    (5. Den ganzen Code auf maximal vier Stellen beschränken (um das Ende sehr langer Strings zu ignorieren).)

Die Funktion „Transformiere“ wandelt Buchstaben in Zahlen gemäss dieser Tabelle um:

Buchstabe(n) Code
A E I O U H W Y 0
B F P V 1
C G J K Q S X Z 2
D T 3
L 4
M N 5
R 6

Beispiel: „Meier“ „Mayer“:
Meier 1. M -> 2. M0006 -> 3. M6
Mayer 1. M -> 2. M0006 -> 3. M6
Gleicher Code -> die Namen sind phonetisch gleich.

Beispiel: „Lutscher“ „Ludschah“:
Lutscher 1. L -> 2. L0322006 -> 3. L3226 -> 4. L326
Ludschah 1. L -> 2. L0322000 -> 3. L322 -> 4. L32
Ähnlicher Code (dies musst du selber bewerten) -> die Namen sind phonetisch ähnlich.

In dieser einfachen Form funktioniert der Algorithmus allerdings nicht in allen Fällen zufriedenstellend. Insbesondere typische Tippfehler (Buchstabendreher etc.) können damit nicht erkannt werden. Am besten kombinierst du verschiedene Algorithmen und bewertest dann die verschiedenen Ergebnisse aufgrund deiner Anforderungen.
Z.B. mit einer Auswertung analog „Master Mind“, also: Zeichen kommt vor, Zeichen kommt an der selben Stelle vor. Dann noch einen Vergleich der absoluten Stringlängen, usw, usf…

Also je größer die Zahl, umso besser die Übereinstimmung.

Eine Bewertungsfunktion müsstest du dann noch selber entwickeln. Diese ist aber sicherlich vom Einsatzzweck abhängig.

Z. B. 1 für komplette Übereinstimmung (Meier und Meier)

Das ist ja wohl einfach :wink:

Gruss
Peter

#5

Hi, Peter,

…ein Dank von einem eifrigen Mitleser. :wink:

CU DannyFox64 :smile:
__ 30550102 _____

[…]