Fuzzy Suche

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

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;
		}
	}
}