我有一个在过滤时要搜索的人员列表。每次用户输入搜索字符串,都会应用过滤。
要考虑两个挑战:
第一个可以简单地通过搜索子字符串来解决,例如String.Contains()。第二个问题可以通过使用模糊实现(例如https://fuzzystring.codeplex.com)
解决但是我不知道如何同时掌握两个挑战。
例如:输入以下其中一项时,我想找到人“ Martin Fowler博士”:
我想我需要编写一个“ FuzzyContains()”逻辑,该逻辑可以满足我的需求,并且具有可接受的性能。任何建议如何开始?
似乎是Levenshtein距离算法(one of the dozens C# implementations)的工作。
您为此算法提供了两个字符串(用户输入的一个字符串,列表中的一个字符串)。然后,它计算从第一个字符串到第二个字符串必须替换,添加或删除多少个字符。然后,您可以从列表中所有距离小于或等于三(例如)的元素中查找简单的错字。
如果您有此方法,则可以那样使用:
var userInput = textInput.Text.ToLower();
var matchingEmployees = EmployeeList.Where(x => x.Name.ToLower().Contains(userInput)
|| LevenshteinDistance.Compute(x.Name.ToLower(), userInput) <= 3)
.ToList();
我修改了Oliver answer,他提出了Levenshtein距离算法,这不是最佳选择,因为仅输入部分名称时,计算出的距离就很大。因此,我最终使用了很棒的Longest Common Subsequence algorithm实现的FuzzyString Lib。
const int TOLERANCE = 1;
string userInput = textInput.Text.ToLower();
var matchingPeople = people.Where(p =>
{
//Check Contains
bool contains = p.Name.ToLower().Contains(userInput);
if(contains) return true;
//Check LongestCommonSubsequence
bool subsequenceTolerated = p.Name.LongestCommonSubsequence(userInput).Length >= userInput.Length - TOLERANCE;
return subsequenceTolerated;
}).ToList();
我之前已经做过此事,并从wikipedia approximate string matching中列出的一些方法开始。完成后,我以不通用的方式对算法进行了调整,但是在我的领域中给了我更好的匹配。
如果整个字典都在内存中并且不太大,则只需对字典中的每个成员应用匹配算法。如果字典很大,这可能会浪费资源,并且您需要一个更好的算法。您可能还想考虑使用数据库的全文本搜索功能。
[在我的情况下,我迭代了字典中的每个字符串,比较了“匹配运行”,即2个字符匹配2点,3个字符匹配3点到8个字符匹配。我用了所有可能的配对,三联等等。-为每个字典条目评分并选择得分最高的匹配项。可以忍受拼写错误,单词顺序等问题,但计算量很大-我的字典最多只能包含几千个词组,因此对我来说效果很好。这是Dice's coefficient.
的修改版本您是否尝试过蛮力?最简单的方法是从头开始将搜索字符串与目标字符串的子字符串匹配,然后从所有匹配项中选择最接近的匹配项。
但是从性能角度来看这可能是不可接受的。
也许您可以使用此soundex实现:CodeProjectsoundex所做的是比较两个字符串,并以百分比计算“发音相似度”。前段时间,我借助此功能(PHP hasit内置)来构建搜索]
前段时间我有一个学校项目,我们有一个文本框,学生可以在其中搜索每个与学校有关的员工。我们当时谈论的是数百人。我们使用的简单Linq查询在Core i3处理器上非常快。每次用户在文本框中键入内容时都会调用该查询。在TextChanged事件中,我们调用了一个看起来像这样的查询:
var resultData = EmployeeList.Where(x=>x.Name.ToLower().Contains(textInput.Text.ToLower())).ToList();
当然,仅当您在一个财产或成员中有“ Martin Fowler博士”时,此逻辑才适用。