Bewertung: 5.0 von 10 Benutzern
klaus_b
Jeder der sich schon einmal mit der “Suche an sich” beschäftigt hat, kennt das Problem der Erkennung von ähnlichen Wörtern. Egal ob es sich dabei um Tippfehler handelt oder nach ähnlich klingenden Wörtern gesucht werden soll.
Prinzipiell gibt es zwei gangbare Verfahren die Problematik umzusetzen. Einmal die Fuzzy-Suche auf Basis der Levenshtein-Distanz und zum andere die phonetische Ähnlichkeit. Günther Foidl hat den Algorithmus der Fuzzy-Suche auf Basis der Levenshtein-Distanz bereits hier sehr schön in C# umgesetzt.
Ich bin der Meinung, dass sich die Fuzzy-Suche besser zum Vergleich mit festen Wortlisten einsetzen lässt, wie etwa in einer Rechtschreibkorrektur, als zur Verwendung in einer Suche mit ständig wechselndem Inhalt. Auch deshalb habe ich mich einmal etwas intensiver mit der phonetischen Suche auseinander gesetzt.
Als erstes stößt man meist auf den Soundex Algorithmus. Da dieser ursprünglich für die englische Sprache Entwickelt wurde eignet er sich nur sehr bedingt für die Verwendung in anderen Sprachen. Auch wird das Abbild eines Wortes immer auf 4 Zeichen, einen Buchstaben gefolgt von 3 Zahlen, begrenzt. Diese Vorgabe kann beim Vergleich sehr langer Wörter zu unvorhergesehenen Ergebnissen führen.
Die wesentlich bessere alternative, gerade für den deutschen Sprachraum, bietet hier die Kölner Phonetik oder auch Kölner Verfahren genannt. Mit diesem Algorithmus werden alle Buchstaben eines Wortes als Ziffer zwischen 0 und 8 abgebildet. Die exakte Definition des Algorithmus kann unter dem vorherigen Link nachgelesen werden.
Im Wesentlichen läuft die Kodierung eines Wortes in drei Schritten ab.
- Buchstabenweise Kodierung aller Buchstaben eines Wortes.
- Entfernen aller mehrfach hintereinander vorkommenden Ziffern.
- Entfernen aller “0”-Ziffern, außer die erste Ziffer ist eine “0”. Diese bleibt erhalten.
Zum kodieren der einzelnen Buchstaben sowie einigen Regeln wann ein bestimmter Buchstabe wie kodiert wird, ist eine kurze Tabelle die Basis. Ebenfalls unter dem Link zum Artikel in der Wikipedia einzusehen.
Hier nun meine Umsetzung des phonetischen Algorithmus:
Da ja die Kodierung buchstabenweise erfolgt und meistens Wörter als Zeichenfolgen, also als string, behandelt werden, ist der kleinste gemeinsame Nenner ein einzelnes Zeichen. Im .NET-Framework ein Wert vom Typ char. Als erstes habe ich jene Buchstaben-Gruppen der Liste, welche mit festen Werten belegt sind, in verschiedene Array vom Typ char verpackt. Auch verschiedene Buchstaben-Gruppen die in verschiedenen Regeln verwendet werden konnten so schon vorab zusammengefasst werden.
/// <summary>
/// Hält eine Gruppe von Buchstaben die dem Code "0" zugeordnet werden.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] group0 = new char[] { 'A', 'E', 'I', 'J', 'O', 'U', 'Y', 'Ä', 'Ö', 'Ü' };
/// <summary>
/// Hält eine Gruppe von Buchstaben die dem Code "3" zugeordnet werden.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] group3 = new char[] { 'F', 'V', 'W' };
/// <summary>
/// Hält eine Gruppe von Buchstaben die dem Code "4" zugeordnet werden.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] group4 = new char[] { 'G', 'K', 'Q', };
/// <summary>
/// Hält eine Gruppe von Buchstaben die dem Code "6" zugeordnet werden.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] group6 = new char[] { 'M', 'N' };
/// <summary>
/// Hält eine Gruppe von Buchstaben die dem Code "8" zugeordnet werden.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] group8 = new char[] { 'S', 'Z', 'ß' };
/// <summary>
/// Hält eine Gruppe von Folgebuchstaben wenn "C" ein Anlaut ist.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] groupCFirst = new char[] { 'A', 'H', 'K', 'L', 'O', 'Q', 'R', 'U', 'X' };
/// <summary>
/// Hält eine Gruppe von Folgebuchstaben wenn "C" kein Anlaut ist.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] groupCNoFirst = new char[] { 'A', 'H', 'K', 'O', 'Q', 'U', 'X' };
/// <summary>
/// Hält eine Gruppe von die vor "C" stehen können.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] groupCPrevious = new char[] { 'S', 'Z' };
/// <summary>
/// Hält eine Gruppe von Buchstaben die vor "D" oder "T" stehen können.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] groupDTPrevious = new char[] { 'C', 'S', 'Z' };
/// <summary>
/// Hält eine Gruppe von Buchstaben denen "X" folgen kann.
/// </summary>
/// <remarks>n/a</remarks>
private static char[] groupXFollow = new char[] { 'C', 'K', 'Q' };Nun erfolgt als erstes die buchstabenweise Kodierung einer Zeichenfolge. Dazu wird als erstes die übergebene Zeichenfolge in Großbuchstaben gewandelt und in ein Array vom Typ char kopiert um die Buchstaben bequem einzeln zu verarbeiten. Um die Ziffern eines jeden Buchstaben zusammenfügen zu können, habe ich mich für den StringBuilder entschieden. Dieser ist nicht nur wesentlich performanter als String-Operationen sondern zudem auch flexibler beim Anfügen von char-Werten.
Beim iterieren durch das char-Array wird als erstes geprüft, ob das aktuelle Zeichen auch einem Buchstaben entspricht. Sollte dies nicht der Fall sein, wird das Zeichen ignoriert und mit dem nächsten Zeichen fortgefahren. Als nächstes wird geprüft, ob das Zeichen in einer der Standardgruppen enthalten ist und gegebenenfalls der entsprechende Wert an die StringBuilder-Instanz angefügt. Sollte das Zeichen in keiner der Gruppen enthalten sein, werden jetzt nacheinander die Sonderregeln geprüft.
private static string GetEncoding(string input)
{
// die Eingabe in ein Zeichen-Array wandeln
char[] content = input.ToUpperInvariant().ToCharArray();
// eine Stringbuilder-Instanz zum ausnehmen
// der Ziffernabbildung
StringBuilder sb = new StringBuilder();
// durch das Zeichen-Array iterieren
for (int i = 0; i < content.Length; i++)
{
char entry = content[i];
// ignorieren wenn kein Buchstabe
if (!Char.IsLetter(entry))
{
continue;
}
// H ignorieren
if (entry.Equals('H'))
{
continue;
}
// prüfen ob das Zeichen in einer der
// Standard-Wertegruppen enthalten ist
if (group0.Contains(entry))
{
sb.Append("0");
continue;
}
if (group3.Contains(entry))
{
sb.Append("3");
continue;
}
if (group4.Contains(entry))
{
sb.Append("4");
continue;
}
if (group6.Contains(entry))
{
sb.Append("6");
continue;
}
if (group8.Contains(entry))
{
sb.Append("8");
continue;
}
if (entry.Equals('B'))
{
sb.Append("1");
continue;
}
if (entry.Equals('L'))
{
sb.Append("5");
continue;
}
if (entry.Equals('R'))
{
sb.Append("7");
continue;
}
// Zeichen auf spezielle Wertung überprüfen
if (entry.Equals('P'))
{
// prüfen ob letztes Zeichen im Array
if (i + 1 >= content.Length)
{
sb.Append("1");
continue;
}
// das Folgezeichen lesen
char next = content[i + 1];
// wenn Folgezeichen "H"
if (next.Equals('H'))
{
sb.Append("3");
continue;
}
sb.Append("1");
continue;
}
if (entry.Equals('X'))
{
// wenn erstes Zeichen im Array
if (i == 0)
{
sb.Append("48");
continue;
}
// vorhergehendes Zeichen lesen
char previous = content[i - 1];
// mit Gruppe vorhergehender Zeichen vergleichen
if (groupXFollow.Contains(previous))
{
sb.Append("8");
continue;
}
sb.Append("48");
continue;
}
if (entry.Equals('D') || entry.Equals('T'))
{
// prüfen ob letztes Zeichen im Array
if (i + 1 >= content.Length)
{
sb.Append("2");
continue;
}
// Folgezeichen lesen
char next = content[i + 1];
// prüfen ob das Folgezeichen
// in der Ausnahmegruppe enthalten ist
if (groupDTPrevious.Contains(next))
{
sb.Append("8");
continue;
}
sb.Append("2");
continue;
}
if (entry.Equals('C'))
{
// wenn C ein Anlaut
if (i == 0)
{
// Folgezeichen lesen
char next = content[i + 1];
// wenn Folgezeichen in der Gruppe
// C-Folgezeichen enthalten ist
if (groupCFirst.Contains(next))
{
sb.Append("4");
continue;
}
sb.Append("8");
continue;
}
else // kein Anlaut
{
// prüfen ob letztes Zeichen im Array
if (i + 1 >= content.Length)
{
continue;
}
// das nächste und vorherige Zeichen lesen
char next = content[i + 1];
char previous = content[i - 1];
// prüfen ob das Vorhergehende Zeichen in
// der entsprechenden Gruppe enthalten ist
if (groupCPrevious.Contains(previous))
{
sb.Append("8");
continue;
}
else
{
// prüfen ob das Folgezeichen in der
// entsprechenden Gruppe enthalten ist
if (groupCNoFirst.Contains(next))
{
sb.Append("4");
continue;
}
sb.Append("8");
continue;
}
}
}
}
return sb.ToString();
}Nach der Erstellung der buchstabenweisen Kodierung, werden als nächstes alle mehrfach hintereinander vorkommenden Ziffern entfernt. Dazu wird wiederum die übergebene Zeichenkette in ein char-Array kopiert und Zeichenweise immer mit dem vorangegangenen Zeichen verglichen. Sind die beiden Zeichen ungleich, wird das aktuelle Zeichen in eine StringBuilder-Instanz geschrieben.
private static string CleanDoubles(string input)
{
StringBuilder sb = new StringBuilder();
char[] content = input.ToCharArray();
char previous = new char();
for (int i = 0; i < content.Length; i++)
{
char entry = content[i];
if (!entry.Equals(previous))
{
sb.Append(entry);
}
previous = entry;
}
return sb.ToString();
}Als letztes brauchen jetzt nur noch alle 0-Zeichen aus der Ziffernfolge entfernt zu werden. Natürlich mit Ausnahme der ersten Ziffer, sollte diese ein 0-Zeichen sein.
Insoweit ist die Umsetzung des Algorithmus abgeschlossen.
In den nächsten Tagen werde ich eine vernünftige Klasse erstellen und auch ein lauffähiges Beispiel veröffentlichen.
Wenn ihnen der Artikel gefallen hat oder er für sie hilfreich war, bitten "kicken" sie ihn.
