C＃中部分单词的搜索算法＃

Question

我目前正在寻找一种方法来实现C＃中的部分单词模式算法。我现在的情况如下所示：

我得到了搜索模式的文本字段。每当用户在此字段中输入或删除字符时，都会触发重新运行搜索算法的事件。因此，如果我想在字符串

“Facebook”，“Facelifting”，“”Faceless Face“（无论应该是什么）或通常任何现实生活句子中以字符串的形式搜索词”face“，

该算法首先在字段中键入“f”时开始运行，然后在字符串所在列表的顶部显示最相关的字符串。第二次运行时键入“fa”，列表这是继续，直到“面”完全键入的文本字段和列表再次排序

然而我不知道什么算法可以使用我试着从答案阿兰（Getting the closest string match），简单的Levenshtein - 距离算法以及一个自制算法，该算法通过

priority = (length_of_typed_pattern) * (amount_of_substr_matches) 

计算优先在C＃，后者看起来像这样：

count = Regex.Matches(Regex.Escape(title), pattern).Count; 
priority = pattern.Length * count; 

图案以及标题仅由小写字母组成。 到目前为止，我的结论：

• 汉明距离将没有任何意义，因为字符串是不一样的长度大部分时间
• 从阿兰答案工作正常，但前提是至少一个单词完全匹配（当你至少有一个单词与模式相同时，你只能找到最相关的字符串/句子，所以如果你有“face”类型并且有一个包含单词“facebook”的字符串，那么包含“facebook”的字符串是几乎从不是最高优先

其他想法c我该试试吗？目标是在最早的时刻以最少的字母排列字符串列表（使用最少的字母）。

您可以在Sprung/WindowMatcher.cs和Sprung/Window.cs中查看我的存储库搜索分支中的实现（http://github.com/croemheld/sprung）。

感谢您的帮助。

Answer 1

首先，您需要在某个位置存储与字符串相关的频率（搜索特定字符串的次数），以便在搜索时显示最相关的一个。如果您需要显示k个最相关的条目，那么可以实施'k'大小的Min Heap。

案例1-如果字母被按压在第一次： -

步骤（a）读取从与FLAG_VALID数据的基础上或字典，并存储在一些数据结构（说DS1）开始的所有串（最初设置为1），这表明它是当前搜索字符的有效字符串（对于第一个字母，所有字符串都将有效）。 当你阅读字符串时，根据它们的频率填充最小堆，并且只有当频率大于最小值（即最小堆的第一个元素）时才插入一定频率的元素。为了显示结果，你需要按照与Min Heap相反的顺序显示元素，即Min Heap中的第一个元素的优先级最低，所以基本上我们需要逐个删除所有元素，并从最后到第一个显示它。 注： - 最小堆将包含参考特定字符串，因此字符串和它的频率可以在同一时间进行访问。

案例2 - 插入在搜索框旁边的字母：

步骤（a）中搜索DS1中的所有字符串都存在，并首先检查FLAG_VALID。如果它是一个有效的字符串比比较来自搜索框中的字符串，并从DS1的字符串。设置相应的标志（如果它是一个匹配-1或不-0）和填充的k最小堆，因为它是从上次搜索空的，因为在情况1

步骤（b）是像往常一样。

案例3-删除搜索框的一封信：

它类似于上述情况，但这个时候，我们需要寻找那些字符串也是其FALG_VALID为0（即字符串，它是无效的）。

这是一种粗搜索方法，并且可以使用特定的数据结构和调整算法得到改进。