Wer war nicht schon einmal in der Situation zwei Wörter nicht auf ihre Gleichheit, sondern auf ihre Ähnlichkeit zu prüfen? Wenn ein Kunde nach dem umgangssprachigen Begriff Schraubenzieher sucht, im Katalog aber nur die korrekte Bezeichnung Schraubendreher vorhanden ist, stoßen die üblichen Vergleiche an ihre Grenzen.
Wie soll so ein Vergleich also aussehen?
Als Ergebnis des Vergleich sollte ein Wert zwischen 0 und 1 zurückgegeben werden. Wobei 0 keine Ähnlichkeit bedeutet und 1 die Wörter sind identisch aussagt.
Für so einen Vergleich bietet sich entweder der Editierabstand, auch Levenshtein-Distanz genannt, oder eben der Dice-Koeffizient an.
Der Dice-Koeffizient “d” lässt sich als Definition, wie unter obigem Link in der Wikipedia zu sehen, darstellen oder als einfache Bruchrechnung:
2 (Übereinstimmungen aus a und b)
d(a,b) = ----------------------------------------------------------------
Anzahl N-Gramme(a) + Anzahl N-Gramme(b)
Um den Dice-Koeffizienten zweier Wörter zu bestimmen, müssen die einzelnen Wörter erst einmal in N-Gramme zerlegt werden; also in Teilzeichenfolgen der Länge N.
N mit 1 zu bestimmen währe nicht sehr vorteilhaft, da diese Prüfung einem ordinalen Vergleich entsprechen würde, der bereits im Framework als Member Ordinal der StringComparison-Enumeration vorhanden ist.
In der Praxis haben sich Trigramme, also Teilzeichenfolgen aus 3 Buchstaben, bewährt.
Sehen wir uns jetzt einmal so eine Berechnung des Dice-Koeffizienten anhand des Vergleichs der Wörter Schraubenzieher und Schraubendreher an.
Nach der Zerlegung der beiden Wörter in Trigramme, ergibt sich folgendes Bild:
Trigramme : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Schraubenzieher: Sch, chr, hra, rau, aub, ube, ben, enz, nzi, zie, ieh, ehe, her
Schraubendreher: Sch, chr, hra, rau, aub, ube, ben, end, ndr, dre, reh, ehe, her
Übereinstimmungen : 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1
Daraus ergibt sich als Ergebnis:
2*9
d(a,b )= --------- = 0,6923077 oder eine 69%ige Ähnlichkeit.
13+13
Da die Anzahl der Übereinstimmungen immer in Relation zur Anzahl der vorhandenen Trigramme steht, ergeben sich bei sehr kurzen Wörtern immer extrem ungünstige Ähnlichkeiten. Beim Vergleich von Maus und Haus etwa, würde das oben beschriebene Vorgehen so aussehen,
Trigramme ; 1, 2
Maus ; Mau, aus
Haus; Hau, aus
Übereinstimmungen : 0, 1
Und als Ergebnis;
2*1
d(a,b) = ------ = 0,25 oder eine 25%ige Ähnlichkeit.
2+2
Um dieses Verhalten zu kompensieren, nutzt man Füllzeichen um alle Buchstaben zum Vergleich heranzuziehen. diese Füllzeichen werden am Anfang und am Ende der Zeichenkette hinzugefügt. Im folgenden Beispiel verwende ich einen “_” als Füllzeichen.
Trigramme ; 1, 2, 3, 4, 5, 6
Maus ; __M, _Ma. Mau, aus, us_, s__
Haus; __H, _Ha, Hau, aus, us_, s__
Übereinstimmungen : 0, 0, 0, 1, 1, 1
Und als Ergebnis;
2*3
d(a,b) = ------ = 0,5 oder eine 50%ige Ähnlichkeit.
6+6
Bei der Implementierung des Algorithmus sollte dieses Verhalten bereits bei der Erzeugung der Trigramme berücksichtigt werden. Es gilt hier noch einen Schwellenwert zu bestimmen, ab welcher Wortlänge, oder Anzahl von Buchstaben, Füllzeichen verwendet werden. Für erste Versuche habe ich hier eine Größe von fünf Buchstaben bestimmt.
Zur Erzeugung der Trigramme einer Zeichenfolge, habe ich als Container eine List<T> vom Typ string gewählt. Abhängig ob Füllzeichen verwendet werden, wird ein Parameter vom Typ bool an die Methode übergeben.
private static List<string> GetTriGrams(string term, bool useFiller)
{
var list = new List<string>();
var chars = term.ToCharArray();
if (useFiller)
{
list.Add("__" + chars[0]);
list.Add("_" + chars[0] + chars[1]);
}
for (int i = 0; i < chars.Length - 2; i++)
{
list.Add(chars[i].ToString() + chars[i + 1] + chars[i + 2]);
}
if (useFiller)
{
list.Add(chars[chars.Length - 2].ToString() + chars[chars.Length - 1] + "_");
list.Add(chars[chars.Length - 1].ToString() + "__");
}
return list;
}Jetzt muss nur noch der Inhalt der beiden Listen auf Übereinstimmungen geprüft werden.
Um Fehler bei unterschiedlich langen Listen vorzubeugen, wird als Obergrenze einer for-Schleife die Länge der kürzeren Liste verwendet. Im folgenden Listing wird für den Vergleich der Trigramme auf eine Unterscheidung der Groß- und Kleinschreibung verzichtet. Hier währe eine Überladung der Methode denkbar, der ein weitere Parameter mitgegeben wird, welcher das Verhalten beeinflusst.
private static float GetSimilarity(string first, string second)
{
bool useFiller = first.Length < 5 ? second.Length < 5 : false;
var firstList = TriGram.GetTriGrams(first, useFiller);
var secondList = TriGram.GetTriGrams(second, useFiller);
var length = Math.Min(firstList.Count, secondList.Count);
int equals = 0;
for (int i = 0; i < length; i++)
{
if (firstList[i].Equals(
secondList[i],
StringComparison.OrdinalIgnoreCase))
{
equals++;
}
}
return 2 * (float)equals /
(float)(firstList.Count + secondList.Count);
}Eine öffentliche Methode zum ermitteln des Dice-Koeffizienten zweier Wörter könnte in etwa so aussehen:
public static float Similarity(string first, string second)
{
if (string.IsNullOrEmpty(first))
{
throw new ArgumentException(
"first ist ein null-Verweis oder eine leere Zeichenfolge.",
"first");
}
if (string.IsNullOrEmpty(second))
{
throw new ArgumentException(
"second ist ein null-Verweis oder eine leere Zeichenfolge.",
"second");
}
return TriGram.GetSimilarity(first, second);
}Oder die Ermittlung der Ähnlichkeit unter Angabe eines Schwellenwertes in etwa so:
public static bool IsSimilar(string first, string second, float threshold)
{
if (string.IsNullOrEmpty(first))
{
throw new ArgumentException(
"first ist ein null-Verweis oder eine leere Zeichenfolge.",
"first");
}
if (string.IsNullOrEmpty(second))
{
throw new ArgumentException(
"second ist ein null-Verweis oder eine leere Zeichenfolge.",
"second");
}
return TriGram.GetSimilarity(first, second) >= threshold;
}Wie man anhand der Beispiele sehen kann, sind hier viele Möglichkeiten gegeben.
Es währe durchaus auch eine Methode vorstellbar, welche die beste Übereinstimmung aus einer Liste von Wörtern wählt.
Eine Verwendungsmöglichkeit sehe ich überall dort, wo nicht die Übereinstimmung von Zeichenfolgen gefragt ist, sondern die Ähnlichkeit.
Wenn ihnen der Artikel gefallen hat oder er für sie hilfreich war, bitte "kicken" sie ihn.
