以下帖子中的评论对于理解部分算法特别有帮助。
然而问题仍然存在。我在 Chrome 上做了一些实验：
当我输入“eddit”时，它只建议“reddit”用于一般的谷歌搜索，而如果我完全输入“reddit”，历史reddit url会弹出。
如果我输入“facebook”或“google”或“youtube”的子字符串，则 urls 会成功弹出。说“ceb”、“ogl”、“utu”。因此尝试不应该是这里使用的（唯一）数据结构。
此外，我知道 Chrome 正在使用 sqlite 的 fts 进行全文搜索（sqlite 属性 fts 3/4 to Google）。所以我猜Chrome正在使用sqlite中的倒排索引。
我的问题是：
Chrome 如何自动完成“utu”->“youtube”？（基于我的本地历史记录 url）
- 我知道后缀数组/树可以有效地匹配子字符串。但是找到特定的词“youtube”将是线性的。
- 我猜一个定制的标记器（用于 fts3/4）可以实现这一点。说“谷歌”-> {“g”，...，“gle”，..}。但是会产生太多的token。