public class FuzzySearch
{
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];
}
public static List<string> Search(string word, List<string> wordList, double fuzzyness)
{
//List<string> foundWords = new List<string>();
//foreach (string s in wordList)
//{
// // Calculate the Levenshtein-distance:
// int levenshteinDistance =
// LevenshteinDistance(word, s);
// // Length of the longer string:
// int length = Math.Max(word.Length, s.Length);
// // Calculate the score:
// double score = 1.0 - (double)levenshteinDistance / length;
// // Match?
// if (score > fuzzyness)
// foundWords.Add(s);
//}
// Tests have prove that the !LINQ-variant is about 3 times
// faster!
List<string> foundWords =(from s in wordList
let levenshteinDistance = LevenshteinDistance(word, s)
let length = Math.Max(s.Length, word.Length)
let score = 1.0 - (double)levenshteinDistance / length
where score > fuzzyness
select s
).ToList();
return foundWords;
}
}
Tuesday, December 6, 2011
Search Algorithm
Subscribe to:
Post Comments (Atom)
TinyMCE Insert/Edit link not editable
To fix this add e.stopImmediatePropagation() as below. $(document).on('focusin', function (e) { if ($(e.target).close...
-
I spent plenty of time for delving into this problem' depths. I can summarize the solution as follows: 1. Create The Entity Class (e.g...
-
Presentation>Nop.Web>AppData>setting.txt Nopcommerce and ecommerce websites services
-
Image upload with CKEditor. My latest issue was how to integrate CKFinder for image upload in CKEditor. Here the solution. 1. Download C...
interesting article.... fuzzy logic and LINQ
ReplyDeletethanks for sharing