The comment in the following post is particularly helpful in understanding part of the algorithm.
How does Chrome update URL bar completions?
Yet questions remain here. I did some experiment on Chrome:
When I input "eddit", it only suggests "reddit" for general google search, while if I input "reddit" fully, historical reddit url pops.
If I input substring of "facebook" or "google" or "youtube", then urls pop successfully. Say "ceb", "ogl", "utu". Hence tries should not be the (only) data structure used here.
Furthermore, I know Chrome is using sqlite's fts to do full text search(sqlite attribute fts 3/4 to Google). So I guess that Chrome is using inverted index of url in sqlite.
My question is:
How does Chrome manages to autocomplete "utu" -> "youtube"?(based on my local history urls)
- I know suffix array/tree can match substring efficiently. But finding the particular word "youtube" will be linear.
- I guess a tailored tokenizer(for fts3/4) may achieve this. Say "google" -> {"g",..., "gle", ..}. But there will be too many tokens generated.