次の投稿のコメントは、アルゴリズムの一部を理解するのに特に役立ちます。
Chrome は URL バーの補完をどのように更新しますか?
しかし、ここで疑問が残ります。Chromeでいくつかの実験を行いました：
「eddit」と入力すると、一般的な Google 検索の「reddit」のみが提案されますが、「reddit」を完全に入力すると、過去の reddit の URL が表示されます。
「facebook」、「google」、または「youtube」の部分文字列を入力すると、URL が正常に表示されます。「ceb」、「ogl」、「utu」と言ってください。したがって、ここで使用される (唯一の) データ構造は、try であってはなりません。
さらに、Chrome が sqlite の fts を使用して全文検索を行っていることも知っています (sqlite 属性 fts 3/4 to Google)。したがって、Chrome は sqlite で URL の逆インデックスを使用していると思います。
私の質問は：
Chrome はどのようにして "utu" -> "youtube" をオートコンプリートできますか? (ローカル履歴の URL に基づく)
- 接尾辞配列/ツリーが部分文字列を効率的に照合できることはわかっています。しかし、特定の単語「youtube」を見つけることは線形になります。
- 調整されたトークナイザー（fts3/4用）がこれを達成できると思います。「google」と発声 -> {"g",..., "gle", ..}. しかし、生成されるトークンが多すぎます。