Fuzzy Matching in Python

In der Welt der Daten hat man öfters mal das Problem, das man Daten miteinander vergleichen möchte, die auf das gleiche referenzieren aber dennoch unterschiedlich sind. Dies kann durch Tippfehler oder unterschiedlichen Schreibweisen geschehen.

Hierfür wäre es praktisch, wenn man zwei Werte auf Gemeinsamkeiten überprüfen kann. Und da kommt auch schon für das Fuzzy Matching die fuzzywuzzy Library von Python ins Spiel.

Installationen

Zuerst installieren wir die fuzzywuzzy Library:

pip install fuzzywuzzy -U

Anschließend installieren wir auch die Levenshtein Library, um den Vergleichsprozess zu beschleunigen:

pip install python-Levenshtein -U

Der Levenshtein Algorithmus wurde von Vladimir Levenshtein entwickelt, um auszurechnen wie sehr sich zwei Wörter oder Sätze unterscheiden. Dabei wird die kleinste Anzahl an Änderungen, die benötigt werden, um String A zu String B umzurechnen, errechnet.

Fallbeispiele

Import

from fuzzywuzzy import fuzz
from fuzzywuzzy import process

Code

StringA = "Mittagspause"
StringB = "Mittag Pause"
print(fuzz.ratio(StringA,StringB))

Output

83

Anhand dieses Beispiels können wir sagen, dass StringA zu 83% StringB ähnelt.

Die fuzz.ratio() Function errechnet hierbei nur die Levenshtein Distanz der beiden Strings.

 

Wenn wir im oberen Fall noch ein .lower() bei den Strings anwenden, dann erhalten wir schon ein Ergebnis von 92%.

Code

StringA = "Mittagspause"
StringB = "Mittag Pause"
print(fuzz.ratio(StringA.lower(),StringB.lower()))

Output

92

 

fuzzywuzzy ermöglicht uns ebenfalls eine substring Suche. Diese ist insofern Wichtig, wenn wir zwei Wort Sequenzen haben, die beide das gleiche Aussagen wobei eine von den beiden kleiner ist.

Code

StringA = "Coca Cola"
StringB = "Cola"
print(fuzz.partial_ratio(StringA,StringB))

Output

100

Die partial_ratio() Function nimmt hier den kürzeren der beiden Strings und gleicht in mit jedem Sub-String im längeren String ab.

 

Wenn wir dies aber nun mit einem Namen versuchen und dabei den Vor- und Nachnamen jeweils vertauschen wird unser Ergebnis schlechter:

Code

StringA = "Stefan Noir"
StringB = "Noir Stefan"
print(fuzz.partial_ratio(StringA,StringB))

Output

71

 

Für so einen Fall hat fuzzywuzzy ebenfalls eine Lösung: token_sort_ratio()

Diese Funktion macht im Hintergrund mehrere Arbeitsschritte wie das Entfernen von Satzzeichen, das Umwandeln in Kleinbuchstaben und ein alphabetisches Sortieren der einzelnen Wörter. Dies führt in unserem Fall dazu, dass die beiden Input String nach den Umwandlungen „noir stefan“ beinhalten. Daraufhin wendet token_sort_ratio() nur noch die ratio() Funktion an und wir erhalten den Übereinstimmungswert.

Code

StringA = "Stefan Noir"
StringB = "Noir Stefan"
print(fuzz.token_sort_ratio(StringA,StringB))

Output

100

 

Was nun, wenn unsere Strings mehr Wörter enthalten, aber trotzdem noch dieselbe Bedeutung haben?

In so einem Fall können wir uns fuzz_token_set_ratio() zunutze machen:

Code

StringA = "Stefan van der Hall Noir"
StringB = "Stefan vdH Noir"
print(fuzz.token_set_ratio(StringA,StringB))

Output

85

Jetzt stellt sich nur die Frage, was die Funktion anders als sort_ratio macht.

Bei der set_ratio Funktion werden die Strings nicht sofort in Tokens umgewandelt, sortiert und verglichen, sondern es werden drei Gruppen gebildet.

Gruppe1 = Überschneidungen sortiert

Gruppe2 = Rest von StringA sortiert

Gruppe3 = Rest von StringB sortiert

Die erste Gruppe beinhaltet die Wörter, in denen sich die Strings überschneiden. Die zweite Gruppe beinhaltet alles, was von unserem ersten String übriggeblieben ist. Die dritte Gruppe beinhaltet alles, was vom zweiten String übriggeblieben ist.

Zur Veranschaulichung:

Code

StringA = "Stefan van der Hall Noir"
StringB = "Stefan vdH Noir"

Gruppe1 = "Noir Stefan"
Gruppe2 = "Noir Stefan" + " der Hall van"
Gruppe3 = "Noir Stefan" + " vdh"

ratio1 = fuzz.ratio(Gruppe1, Gruppe2)
ratio2 = fuzz.ratio(Gruppe1, Gruppe3)
ratio3= fuzz.ratio(Gruppe2, Gruppe3)
print("Ergebnis Gruppe1&2:",ratio1)
print("Ergebnis Gruppe1&3:",ratio2)
print("Ergebnis Gruppe2&3:",ratio3)
print("Ergebnis Funktion:",fuzz.token_set_ratio(StringA,StringB))

Output

63
85
67
85

Da die Gruppe1 in beiden Strings gleich ist erhöht sich die Trefferanzahl, wenn entweder:

• Die Gruppe1 einen größeren Teil der Gruppe2 oder Gruppe3 ausmacht.
• Die Reste der String, Gruppe2 und Gruppe3 sich ähnlicher sind.

In unserem Fall macht Gruppe1 (Noir Stefan) einen großen Teil der Gruppe3 aus (Noirt Stefan vdh).

 

Schlussendlich wollen wir noch zeigen, wie man einen String mit einer Liste vergleichen und den String, mit der höchsten Trefferquote erhält:

Code

StringBasis = "Stefan Noir"
Sammlung = ["Stefan van der Hall Noir","Stefan vdH Noir","Stefan Zak","Stefan van Hall"]
ratios = process.extract(StringBasis,Sammlung)
print(ratios)
print(process.extractOne(StringBasis,Sammlung)

Output

[('Stefan vdH Noir', 95), ('Stefan van der Hall Noir', 86), ('Stefan Zak', 71), ('Stefan van Hall', 67)]
('Stefan vdH Noir', 95)

Fazit

Fuzzy Matching in Python ist ein hilfreiches Mittel, um Daten, die nicht eins zu eins vergleichbar sind, vergleichbar zu machen. Mittels fuzzywuzzy und eigenen Vorgaben lassen sich so Entscheidungen, die ein Computer selbst nicht bewältigen kann, lösen.