自动建议：子字符串匹配

Question

我想实现自动建议使用三元搜索树（TST），但TST是有用的，当我们正在寻找前缀搜索，我们如何实现自动建议子字符串匹配也？ 有没有其他可以使用的数据结构？

例如，子字符串匹配： 当我尝试使用自动建议搜索UML时，即使字符串“Beginners Guide for UML”也应匹配。

Answer 1

这是从我的头顶，没有任何适当的和成熟的数据结构/算法：

1. 选择的所有法律字符N个符号映射（为简单：拉丁字母和26个符号类似的非拉丁字母忽略大小写+1非字母=总共27个符号）。

2. 从字典中，创建一个最大分支因子为N（即相当高）的浅层树。叶节点将包含对包含从根到叶的符号组合的所有单词的引用（中间节点可能包含对比叶节点的深度更短的单词的引用，或者可以忽略那些短的单词）。

3. 树的深度是可变的，可能在1..4的范围内，这样每个叶子节点将包含大约相同数量的词（当然，在许多叶子下面列出的词当然是相同的，例如树叶下的MATCH，ATC如果树深度恰好为3，则为TCH）。

4. 当用户输入字母时，请尽量沿着树走，直到剩下相对较少的单词为止。然后对树中的叶子进行线性过滤，然后用户输入更多文本进行匹配。 （可选）过滤出符号匹配这实际上不是字符相匹配，尽管它可能是好的，当用户进入ao0还搭配äöO等

5. 符号的优化数你映射你的字符来，有良好的分支系数那个树。优化每叶单词以获得体面的内存使用，而不需要太多的单词在到达树叶之后进行线性过滤。

---

当然也有在一大块文本的查找字符串（什么用户输入）（要匹配所有的短语/字），像Aho–Corasick和Rabin–Karp实际研究算法，可能值得调查。