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();
}
GFU-Schulungen  [Anzeige]

ASP.NET 2.0 und 3.5

Dieser Kurs vermittelt Ihnen alle Erweiterungen von Microsoft ASP.NET 2.0. Zu diesen zählen u. a. Data Bindung, Master Pages, und Security.

VB.NET Aufbau

Sie verfügen nach der Schulung über fundierte Kenntnisse in der Arbeit mit objektorientierten Modellen in VB.NET und können wiederverwendbare Komponenten eigenständig erzeugen.

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!