0

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

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

4

1 回答 1

1

这是我的想法，不是任何适当且经过验证的数据结构/算法：

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

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

  3. 树的深度将是可变的，可能在 1..4 的范围内，因此每个叶节点将包含大约相同数量的单词（当然在许多叶子下列出相同的单词，例如 MATCH 在叶子 MAT、ATC、TCH 如果树深度碰巧是3）。

  4. 当用户输入字母时，沿着树一直往前走，直到留下相对较少的单词。然后在您处于树的叶子之后对剩余的单词进行线性过滤并且用户输入更多文本进行匹配。äöO可以选择过滤掉实际上不是字符匹配的符号匹配，尽管在用户输入ao0等时匹配也可能很好。

  5. 优化您将字符映射到的符号数量，以使树具有良好的分支因子。优化每个叶子的单词以获得良好的内存使用，而在到达树的叶子后没有太多的单词需要线性过滤。

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

于 2013-04-02T11:37:04.613 回答