Feedback

C# - Fuzzy Suche

Veröffentlicht von am 01.06.2009
(7 Bewertungen)
Dieses Snippet zeigt eine einfache Implementierung zur Fuzzy Suche (unscharfe Suche). Informationen darüber zB in http://de.wikipedia.org/wiki/Fuzzy-Suche.

Beispiel:

static void Main(string[] args)
{
string word = "Waidring";
List<string> wordList = new List<string>
{
"Waidring",
"Woadring",
"Weitharing",
"waidring",
"woadring",
"Waidring "
};

List<string> foundWords = StringSearching.FuzzySearch(word, wordList, 0.65);
foreach (string s in foundWords)
Console.WriteLine(s);

Console.ReadKey();
}
using System;
using System.Collections.Generic;

namespace gfoidl.Tools
{
	/// <summary>
	/// Stellt Methoden für String-Suchalgorithmen bereit.
	/// </summary>
	public class StringSearching
	{
		/// <summary>
		/// Ermittelt die Levenshtein-Distanz von zwei Zeichenfolgen.
		/// </summary>
		/// <param name="src">
		/// 1. Zeichenfolge
		/// </param>
		/// <param name="dest">
		/// 2. Zeichenfolge
		/// </param>
		/// <returns>
		/// Levenshstein-Distanz
		/// </returns>
		/// <remarks>
		/// Siehe http://de.wikipedia.org/wiki/Levenshtein-Distanz
		/// </remarks>
		public static int LevenshteinDistance(string src, string dest)
		{
			int[,] d = new int[src.Length + 1, dest.Length + 1];
			int i, j, cost;
			char[] str1 = src.ToCharArray();
			char[] str2 = dest.ToCharArray();

			for (i = 0; i <= str1.Length; i++)
			{
				d[i, 0] = i;
			}
			for (j = 0; j <= str2.Length; j++)
			{
				d[0, j] = j;
			}
			for (i = 1; i <= str1.Length; i++)
			{
				for (j = 1; j <= str2.Length; j++)
				{

					if (str1[i - 1] == str2[j - 1])
						cost = 0;
					else
						cost = 1;

					d[i, j] =
						Math.Min(
							d[i - 1, j] + 1,					// Deletion
							Math.Min(
								d[i, j - 1] + 1,				// Insertion
								d[i - 1, j - 1] + cost));		// Substitution

					if ((i > 1) && (j > 1) && (str1[i - 1] == str2[j - 2]) && (str1[i - 2] == str2[j - 1]))
					{
						d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
					}
				}
			}

			return d[str1.Length, str2.Length];
		}
		//---------------------------------------------------------------------
		/// <summary>
		/// Sucht strings nach dem Prinzip der Fuzzy-Suche.
		/// </summary>
		/// <param name="word">
		/// Eingabe
		/// </param>
		/// <param name="wordList">
		/// Liste mit den Wörtern in denen gesucht werden soll.
		/// </param>
		/// <param name="fuzzyness">
		/// Paremeter für die Unschärfe. Ein Wert von 0.8 bedeutet zB
		/// dass der Unterschied zwischen der Eingbe und den gefundenen
		/// Wörtern nicht mehr als 20% betragen darf.
		/// </param>
		/// <returns>
		/// Eine Liste mit den gefundenen Wörtern.
		/// </returns>
		public static List<string> FuzzySearch(
			string word,
			List<string> wordList,
			double fuzzyness)
		{
			List<string> foundWords = new List<string>();

			foreach (string s in wordList)
			{
				// Levenshtein-Distanz berechnen:
				int levenshteinDistance =
					StringSearching.LevenshteinDistance(word, s);

				// Länge des längeren Strings:
				int length = Math.Max(word.Length, s.Length);

				// Trefferquote errechnen und der Liste hinzufügen:
				double score = 1.0 - (double)levenshteinDistance / length;

				// Treffer?
				if (score > fuzzyness)
					foundWords.Add(s);
			}

			return foundWords;
		}
	}
}

4 Kommentare zum Snippet

klaus_b schrieb am 30.07.2009:
Sehr schöner Ansatz, den ich mir mal in aller Ruhe zu Gemüte führen muss.
Rainer Hilmer schrieb am 30.07.2009:
Eine Perle
Günther Foidl schrieb am 30.07.2009:
Danke für die Blumen!
Siehe auch: http://www.codeproject.com/KB/recipes/fuzzysearch.aspx
Das ganze kann noch parallelisiert werden und sonst noch ein wenig optimiert.
Oliver Kremer schrieb am 18.11.2009:
Sehr schön! S. zur Vertiefung auch: http://wwwlgis.informatik.uni-kl.de/archiv/wwwdvs.informatik.uni-kl.de/agdbis/staff/Haustein/DOCS/dahausteintext.pdf
 

Logge dich ein, um hier zu kommentieren!