如何以模糊方式在C#中使用String.Contains()函数？

Question

如何以模糊方式在C#中使用String.Contains()函数？

c#fuzzy-search

4

我有一个人员列表，想要在筛选时进行搜索。每次用户输入搜索字符串时，都会应用过滤。

需要考虑两个挑战：

1. 用户可能只输入姓名的一部分 2. 用户可能输错字

第一个问题可以通过搜索子字符串（例如String.Contains()）来简单解决。第二个问题可以通过使用模糊实现（例如https://fuzzystring.codeplex.com）来解决。

但我不知道如何同时解决这两个挑战。

例如：当我输入以下之一时，我想找到"Dr.Martin Fowler"：

- "Martin" - "Fawler" - "Marten Fauler"

我猜我需要编写一个"FuzzyContains()"逻辑，来处理我的需求并且具有可接受的性能。有什么建议吗？

- mamuesstack

你可以写一个自己的比较函数，将输入字符串中每个位置上的字符进行匹配，并给出每个名称的匹配度百分比，再根据相似度排序显示列表。 - Logard

逐一遍历所有字符串，首先应用包含关系，如果匹配则添加到ListA中，然后应用FuzzyString，如果匹配则添加到ListB中。最后，所有匹配的字符串列表为ListA.Union(ListB)。 - Haojie

7个回答

4

似乎这是Levenshtein距离算法的工作(C#有许多实现之一)。

你提供给该算法两个字符串(一个是用户输入的，一个是列表中的)，然后它计算出从第一个字符串到第二个字符串需要替换、添加或删除多少个字符。接着，你可以获取与距离小于等于三(例如)的所有元素来找到简单的拼写错误。

如果你掌握了这种方法，也许可以这样用它:

var userInput = textInput.Text.ToLower();
var matchingEmployees = EmployeeList.Where(x =>
    x.Name.ToLower().Contains(userInput) ||
    LevenshteinDistance.Compute(x.Name.ToLower(), userInput) <= 3).ToList();

- Oliver

谢谢这个想法。问题是当输入“Marten”搜索“Dr. Martin Fowler”时，它并不包含，而Levenshtein距离为16！ - mamuesstack

2

你可以在每个名称的空格处分割它们（例如 x.Name.ToLower().Split(' ')），并使用Levenshtein测试所有元素。但是我认为，如果您稍后有一个真正的（可能很大）列表，您将得到许多有效条目，这些条目绝对不匹配。 - Oliver

为了使其真正起作用，您可以实现某种学习算法，通过保存用户尝试的关键字以及他最终选择的关键字并将这些内容保存在某个地方。然后，您不仅可以将用户输入与实际列表进行测试，还可以将其与此映射列表进行测试。但是，如果这里已经提到的机制不符合您的需求，那么我认为要做到真正正确可能相当困难。 - Oliver

这个解决方案可行，但是使用修改版的Levenshtein距离算法可以更高效地完成。 - Anderson Green

1

我以前也做过类似的事情，开始使用了wikipedia approximate string matching上列出的一些方法。完成后，我对我的算法进行了调整，这些调整并不是通用的，但在我的领域中给我带来了更好的匹配。

如果你的整个字典都在内存中且不太大，你可以简单地将你的匹配算法应用于字典中的每个成员。如果你的字典很大，这可能会过度使用你的资源，你需要一个更好的算法。你可能还想考虑使用数据库的全文搜索功能。

在我的情况下，我遍历了字典中的每个字符串，比较“匹配运行”，即两个字符匹配得2分，三个字符匹配得3分，直到8个字符匹配。我遍历了所有可能的组合，对每个字典条目进行评分，并选择最高得分的匹配项。容忍拼写错误、单词顺序等，但计算代价昂贵——我的字典最多只有几千个短语，所以这对我非常有效。这是Dice's coefficient.的修改版本。

- Gary Walker

0

我之前在学校有一个项目，其中我们有一个文本框，学生可以在其中搜索与学校有关的每个员工、学生。我们谈论了几百人。在Core i3处理器上，我们使用的简单Linq查询非常快速。每当用户在文本框中输入内容时，我们就会在TextChanged事件中调用类似于以下的查询：

var resultData = EmployeeList.Where(x=>x.Name.ToLower().Contains(textInput.Text.ToLower())).ToList();

当然，这个逻辑只适用于一个属性或成员中有“Dr. Martin Fowler”的情况。

- Nikola.Lukovic

是的，当输入名称的一部分进行查找时，它可以工作。但是，当输错时它就无法工作了。 - mamuesstack

0

你尝试过暴力破解吗？最简单的方法是将搜索字符串与目标字符串的子字符串从开头开始匹配，然后从所有匹配中选择最接近的匹配。

但从性能的角度来看，这可能不可接受。

- Euphoric

0

也许你可以使用这个soundex实现：CodeProject。Soundex的作用是比较两个字符串，并以百分比计算“发音相似度”。以前我曾经利用这个函数构建了一个搜索功能（PHP内置此功能）。

- N1C0

谢谢分享。Soundex实现仅在用户输入错误时有所帮助，当仅输入名称的一部分时无法使用。 - mamuesstack

我会使用 string.contains()。 - N1C0

0

在其他编程语言中，比如Python，我们有很酷的文本处理工具，包括距离计算。有一些算法，例如Levenshtein，可以计算两个字符串之间的模糊距离。我看到了一些C#的实现（在这里），还有另一个模块是difflib，可以在这里找到。这些算法的输出是一个数字，越接近0越好。

- Ahmad Mousavi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mamuesstack · Accepted Answer

我修改了Oliver的答案，他建议使用Levenshtein Distance算法，但在只输入部分名称时，计算出的距离太大，不是最佳选择。因此，我最终使用了由棒极了的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();