title: How does Google Chrome Omnibox autocomplete work?
body: <p>The comment in the following post is particularly helpful in understanding part of the algorithm.</p>
  
  <p><a href="https://stackoverflow.com/questions/18241512/how-does-chrome-update-url-bar-completions">How does Chrome update URL bar completions?</a></p>
  
  <p>Yet questions remain here. I did some experiment on Chrome:</p>
  
  <ol>
  <li><p>When I input "eddit", it only suggests "reddit" for general google search, while if I input   "reddit" fully, historical reddit url pops.</p></li>
  <li><p>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.</p></li>
  </ol>
  
  <p>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. </p>
  
  <p>My question is:</p>
  
  <p>How does Chrome manages to autocomplete "utu" -> "youtube"?(based on my local history urls)</p>
  
  <ol>
  <li>I know suffix array/tree can match substring efficiently. But finding the particular word "youtube" will be linear.</li>
  <li>I guess a tailored tokenizer(for fts3/4) may achieve this. Say "google" -> {"g",..., "gle", ..}. But there will be too many tokens generated.</li>
  </ol>