java - 自动提示 : Substring matching

Question

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

子字符串匹配的例子:当我尝试使用自动建议搜索 UML 时，甚至字符串“UML 初学者指南”也应该匹配。

Answer 1

这是我的想法，而不是任何正确且经过验证的数据结构/算法:

1. 选择所有合法字符到 N 个符号的映射(为简单起见:26 个符号用于拉丁字母和类似的非拉丁字母，忽略大小写 + 1 个用于非字母 = 总共 27 个符号)。

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

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

4. 当用户输入字母时，请尽可能地跟随树，直到剩下相对较少的单词集。然后在您位于树的叶子并且用户输入更多文本进行匹配后，对剩余的单词进行线性过滤。可选地过滤掉实际上不是字符匹配的符号匹配，尽管当用户输入 ao0 等时也匹配 äöO 可能会很好。

5. 优化您将字符映射到的符号数量，以便为树提供良好的分支因子。优化每片叶子的单词以获得合适的内存使用，而无需太多单词在到达树的叶子后进行线性过滤。

---

当然，有实际研究过的算法可以在一大段文本(您要匹配的所有短语/单词)中查找字符串(用户输入的内容)，例如 Aho–Corasick和 Rabin–Karp ，这可能值得研究。