Ähnlichkeit von Strings messen

Forumthread: Ähnlichkeit von Strings messen

20.02.2013 14:17:15

Strings

Hallo,
ich habe in zwei Zellen Strings, deren Ähnlichkeit ich messen möchte. Beispiel:
HEIDELBERGER DRUCKMASCHINEN WEB-SOLUTIONS CEE GES.M.B.H.
Heidelberger Druckmaschinen WEB-Solution CEE Ges.m.b.H
Unterschiede sind hier die Groß-/Kleinschreibung, das fehlende "s" bei Solutions sowie der fehlende Punkt am Ende des zweiten Strings. Der eine String ist immer in Großbuchstaben, der andere nicht.
Meine Überlegung war nun, wie folgt vorzugehen:
1. Umwandlung des einen Strings in Großbuchstaben
2. Trennung der beiden Strings in die einzelnen Zeichen
3. Aufsteigende Sortierung der einzelnen Zeichen für jeden String
4. Paarweise Vergleich der einzelnen Zeichen. Wenn das erste Zeichen des kürzeren Strings irgendwo im längeren String gefunden wird, gibt es einen Punkt, und das Zeichen wird aus dem Bestand der Vergleichsdaten gelöscht. Entsprechend für alle weiteren Zeichen.
5. In meinem Beispiel würden alle 54 Zeichen des kürzeren Strings in den 56 Zeichen des längeren Strings gefunden werden. Der Stringvergleich ergäbe also 54 von 56 möglichen Punkten. Damit wäre der zu berechnende Index 54/56. Der Index wäre immer zwischen 0 und 1 und die Ähnlichkeit umso größer, je näher der Wert an 1 ist. Bei Identität der Strings wäre der Wert 1.
5a. Alternativ wäre es auch möglich, auszuzählen, wie oft welches Zeichen im kürzeren String vorkommet und das mit einer Auszählung der Zeichen im längeren String zu vergleichen.
Beispiel: 1. AAABCCCC 2. AAAACCDDDD
Gemeinsam sind AAA und CC, d.h. die Ähnlichkeit ist 5/10 oder 0,5.
Meine Fragen: Hat jemand Erfahrungen mit einer solchen Aufgabenstellung? Ist die Herangehensweise grundsätzlich geeignet? Wie könnte man das in VBA lösen?
Ich habe die Aufgabe hier vereinfacht dargestellt. Konkrete geht es darum, dass in 2 Tabellen zu mehreren Hundert "Objekten" je drei Strings abgelegt sind (Name, Land, Ort) anhand derer die Ähnlichkeit gemessen werden soll. Wenn ich für den Namen (so.) eine Lösung habe, kann ich das aber übertragen.
Danke im voraus
Martin

Beiträge zum Forumthread

Beiträge zu diesem Forumthread

Betreff

Datum

Anwender

AW: Ähnlichkeit von Strings messen

20.02.2013 14:19:12

Strings

Hi,
wurde gerade eben behandelt, hier der Link:
https://www.herber.de/forum/messages/1300051.html
du findest da Lösungen für phonetische, mathematische und sonstige Ähnlichkeiten von Strings.
Grüße,
Klaus M.vdT.

AW: Ähnlichkeit von Strings messen

21.02.2013 12:45:03

Strings

Hallo Klaus,
vielen Dank für den Hinweis. Das ist ein ziemlicher Zufall, am Wochenende hatte ich noch die Recherche bemüht und nicht gefunden. Das Stichwort "Levenshtein-Distanz" war sehr gut, ich denke damit komme ich weiter.
Vielen Dank und Gruß
Martin

Danke für die Rückmeldung! owT.

21.02.2013 12:48:39

Klaus

Levenshtein-Distanz mit benutzerdef. Funktion

21.02.2013 13:23:10

mpb

Hallo,
und schon gibt es ein Problem. Mit diesem im Internet aufgeschnappten Code kann ich für zwei Strings die Levenshtein-Distanz berechnen:

Function levenshtein(a As String, b As String) As Integer
Dim i As Integer
Dim j As Integer
Dim cost As Integer
Dim d() As Integer
Dim min1 As Integer
Dim min2 As Integer
Dim min3 As Integer
If Len(a) = 0 Then
levenshtein = Len(b)
Exit Function
End If
If Len(b) = 0 Then
levenshtein = Len(a)
Exit Function
End If
ReDim d(Len(a), Len(b))
For i = 0 To Len(a)
d(i, 0) = i
Next
For j = 0 To Len(b)
d(0, j) = j
Next
For i = 1 To Len(a)
For j = 1 To Len(b)
If Mid(a, i, 1) = Mid(b, j, 1) Then
cost = 0
Else
cost = 1
End If
' Since Min() function is not a part of VBA, we'll "emulate" it below
min1 = (d(i - 1, j) + 1)
min2 = (d(i, j - 1) + 1)
min3 = (d(i - 1, j - 1) + cost)
'            If min1

Für einen Vergleich von Texten in den Zellen D2 und B2 funktioniert das auch einwandfrei. Ich möchte aber den Text in der Zelle D2 "nacheinander" mit den Texten in den Zellen B2:B82 vergleichen und von den 81 berechneten Distanzen nur den Minimalwert zurückgeben, also eine Arrayfunktion, die sinngemäß so aussieht:
{=MIN(levenshtein(D2; B2:B82))}
Wie müsste ich den obigen Code (für eine allgemeine, nicht nur auf mein Beispiel bezogene Lösung) anpassen? Bin z.Z. etwas eingerostet... ;-)
Gruß
Martin

Infobox / Tutorial

Schritt-für-Schritt-Anleitung

Um die Ähnlichkeit von Strings in Excel zu messen, kannst du die Levenshtein-Distanz verwenden. Hier sind die Schritte, um dies in VBA zu implementieren:

Öffne den VBA-Editor: Drücke ALT + F11 in Excel.
Füge ein neues Modul hinzu: Rechtsklicke auf "VBAProject (DeinWorkbookName)", wähle Einfügen und dann Modul.

Füge den folgenden Code ein:

Function levenshtein(a As String, b As String) As Integer
   Dim i As Integer
   Dim j As Integer
   Dim cost As Integer
   Dim d() As Integer
   Dim min1 As Integer
   Dim min2 As Integer
   Dim min3 As Integer

   If Len(a) = 0 Then
       levenshtein = Len(b)
       Exit Function
   End If
   If Len(b) = 0 Then
       levenshtein = Len(a)
       Exit Function
   End If

   ReDim d(Len(a), Len(b))
   For i = 0 To Len(a)
       d(i, 0) = i
   Next
   For j = 0 To Len(b)
       d(0, j) = j
   Next
   For i = 1 To Len(a)
       For j = 1 To Len(b)
           If Mid(a, i, 1) = Mid(b, j, 1) Then
               cost = 0
           Else
               cost = 1
           End If
           min1 = (d(i - 1, j) + 1)
           min2 = (d(i, j - 1) + 1)
           min3 = (d(i - 1, j - 1) + cost)
           d(i, j) = Application.WorksheetFunction.Min(min1, min2, min3)
       Next j
   Next i
   levenshtein = d(Len(a), Len(b))
End Function

Speichere das Modul und schließe den VBA-Editor.
Verwende die Funktion in Excel: Um die Ähnlichkeit zwischen den Strings zu berechnen, kannst du die Funktion in einer Zelle aufrufen, z.B. =levenshtein(D2; B2).

Häufige Fehler und Lösungen

Fehler beim Aufrufen der Funktion: Stelle sicher, dass das Makrosicherheitseinstellungen in Excel so gesetzt sind, dass sie das Ausführen von VBA-Code erlauben.
Falsche Ergebnisse: Überprüfe, ob die Strings korrekt eingegeben sind und keine unerwarteten Leerzeichen oder Sonderzeichen enthalten.
Arrayfunktion nicht erkannt: Wenn du die Levenshtein-Distanz für mehrere Strings in einem Bereich berechnen möchtest, stelle sicher, dass du die Funktion als Arrayformel eingibst, indem du CTRL + SHIFT + ENTER drückst.

Alternative Methoden

Wenn du die Levenshtein-Distanz nicht in VBA implementieren möchtest, kannst du auch folgende Methoden ausprobieren:

Text vergleichen mit Excel-Funktionen: Nutze Funktionen wie VERGLEICH oder FINDEN, um einfache String-Vergleiche durchzuführen.
Externe Tools: Es gibt Online-Tools oder andere Software, die ähnliche Funktionen zur Berechnung der Textähnlichkeit anbieten.

Praktische Beispiele

Einfacher Stringvergleich: Um die Ähnlichkeit zwischen zwei Namen zu prüfen, kannst du die Levenshtein-Distanz zwischen "Heidelberger Druckmaschinen" und "Heidelberger Druckmaschinen GmbH" berechnen.
Erweiterte Nutzung: Angenommen, du hast eine Liste von Firmennamen in Spalte B und möchtest sie mit einem Firmennamen in Zelle D2 vergleichen. Verwende die Formel:
```
=MIN(levenshtein(D2; B2:B82))
```
Vergiss nicht, dies als Arrayformel einzugeben.

Tipps für Profis

Optimierung: Bei großen Datenmengen kann die Berechnung der Levenshtein-Distanz zeitaufwendig sein. Überlege, ob du die Daten vorab filtern kannst, um nur relevante Vergleiche durchzuführen.
Kombination mit weiteren Metriken: Um die Ähnlichkeit umfassender zu bewerten, kombiniere die Levenshtein-Distanz mit anderen Metriken wie Jaccard-Index oder Cosinus-Ähnlichkeit.

FAQ: Häufige Fragen

1. Was ist die Levenshtein-Distanz?
Die Levenshtein-Distanz ist ein Maß für die Anzahl der Änderungen (Einfügungen, Löschungen, Ersetzungen), die erforderlich sind, um einen String in einen anderen zu transformieren.

2. Wie kann ich die Levenshtein-Distanz in Excel nutzen?
Du kannst die oben beschriebene VBA-Funktion verwenden, um die Levenshtein-Distanz zwischen verschiedenen Strings direkt in Excel zu berechnen.

Beliebteste Forumthreads (12 Monate)

Forumthread: Ähnlichkeit von Strings messen

4 Beiträge zum Forumthread Beiträge zu diesem Forumthread

VBA Beispiele zu diesem und ähnlichen Themen

Infobox / Tutorial

Ähnlichkeit von Strings in Excel messen

Schritt-für-Schritt-Anleitung

Häufige Fehler und Lösungen

Alternative Methoden

Praktische Beispiele

Tipps für Profis

FAQ: Häufige Fragen

Beliebteste Forumthreads (12 Monate)

4
Beiträge zum Forumthread

Beiträge zu diesem Forumthread