algorithm - wordweb(英语词典)中使用的索引结构

Question

我的一个 friend 在他最近的采访中遇到了这个问题。我在这里发布 2 个问题以获得更好的解决方案和 fyi。

--如果你输入“light”，下拉菜单中的建议大多以“light”开头，并且在你输入时出现并随每个字符变化，但如果你输入“tigress”或“possi”，建议包括“离题”或其他一些(相同的声音词？)。如何实现这个建议功能？

--存储和检索同义词、反义词、类型、typeof 等的最佳方式是什么？请查看这些选项卡。

我不认为这可以通过简单的字典算法来解决(如果我错了请纠正我)。尽管没有要求他编写任何示例代码，但这对我来说听起来是个棘手的问题。

Answer 1

第一个问题:

我会使用基于公共(public)前缀属性的 Trie 数据结构，并将其构建为产生光 -> 光。我的猜测是，当我们不得不绕着 tigress -> digress 走另一条路时，使用公共(public)后缀属性构建 Trie。也就是说，不是逐个字符地从左到右构建 trie，而是从右到左构建它。

因此，tigress 将被解析为:s->s->e->r->g->i->t AND离题将被解析为:s->s->e->r->g->i->d

我认为这对一开始的建议有用。但是，我想了解我们如何在开头和结尾都支持建议下一个字符。