c# - 部分文本搜索的快速算法

Question

我有一个描述动作的单词列表，例如：

New
Open
Save
Save as
Copy
Paste
Cut
Select all

等等

我希望用户能够通过连续输入几个字母来找到命令。因此，如果用户输入例如“ae”，他应该会收到：

sAvE
sAvE as
pAstE

一般来说，当用户输入“abc”时，我想返回所有匹配正则表达式的字符串.*a.*b.*c.*。由于验证字符串是否匹配这个表达式是线性的，并且蛮力算法也是线性的，所以正则表达式对优化搜索没有多大帮助。

关于这个列表的重要一点是它在编译时是已知的，所以我可以设计一个数据结构，它将包含所有这些术语以加快搜索速度。

是否有数据结构或算法可以加快为特定用户条目查找所有匹配词的速度，超出 O(m*n)（其中 m 是术语计数，n - 平均术语长度）？

标签： c#regexalgorithm

Answer 1

对我来说，这听起来像是一个过早优化的案例。荒谬的为时过早。即使您有 70 个命令而不是只有 7 个，对所有命令进行顺序搜索所需的时间也非常短，以至于您的用户不会注意到它。这并不是一个你每秒会调用数百或数千次的函数。因此，花费数小时实施花哨的搜索以节省几毫秒的时间，这只是浪费时间。您的用户在程序的整个生命周期中节省的时间很可能甚至不会接近您花在设计、编写和调试优化解决方案上的时间。

您有少量非常短的命令。电脑速度很快。这里没有要解决的问题。把时间花在真正有益于用户的功能上。

现在，如果您要搜索大量（数万）字符串，那么您可能会从一些优化中受益。在这种情况下 。. .

您可以从制作一个以字母为键的字典开始，其值是包含该字母的所有单词的列表。所以你的例子是这样的：

a, [Save, Save as, Paste]
c, [Copy, Cut, Select all]
e, [New, Open, Save, Save as, Paste, Select all]
n, [New, Open]
... etc.

然后，在字典中输入“字母跟随字母”。这很快就会变大。例如，“粘贴”将有条目：

pa ps pt pe as at ae st se te

您可以继续为更长的子字符串制作这些键。例如，您得到：

pas pat pae pst pse pte

当字符串很短时，这可能非常有效。当字符串变得更长时，它变得不太有效，因为字符串包含特定字母组合的可能性随着字符串长度的增加而增加。

您可能可以通过创建trie来节省一些空间，但技术本质上是相同的。

也可能有用：后缀树和广义后缀树。