The autocomplete that couldn't finish a word

We turned the demo into a real geocoder. You type an address and get a rooftop coordinate, computed in your browser without a server. The last feature was autocomplete. It completes the city name while you type. We had shipped autocomplete as a command-line tool days earlier and seen it rank San Francisco above San Diego, so we considered it done. We connected the same function to the search box, typed New Yor, and it suggested Denver.

This raised three questions. Why does a function that handles San correctly fail on New Yor? How does completing a word differ from completing the word a person is still typing? How does an autocomplete that knows ten thousand cities fail to complete one of them?

The autocomplete we already had

Our gazetteer (every country, region, county, and city we resolve against) is stored as a finite-state transducer. It is a trie over place-name tokens, and each accepting state stores the places whose names end at that point. mailwoman autocomplete "San" walks the trie to the San node and reads off everything beneath it, ranked by importance: San Francisco, San Diego, San Bernardino. It is fast because the FST is the index, so no separate search runs. The walk reaches a node, and the answers are stored there.

This design fits a command line. You type a whole word, press tab, and get completions. The unit of input is the word, and the trie is keyed by words.

Then we typed half a word

A search box receives partial words such as New Yor or Chic. It gets the first part of a word and has to infer the rest.

A token trie requires whole tokens, and Yor begins a token. The trie steps through New, looks for an edge labeled Yor, finds none, and fails. A trie cannot match a fragment, so that failure is expected. The problem was the fallback, a fuzzy forward geocode over the gazetteer that returned the nearest fuzzy match. For New Yor, that was Denver. We do not know why it chose Denver. The fuzzy distance metric may have weighted string length unexpectedly, the token boundaries may have skewed the scoring, or the cause may be something else. We did not investigate, because the correct fix was to remove the need for the fallback.

It was worse than Denver

We then gave it whole tokens and got New → New London, four times.

Two problems combined. The first was missing deduplication. New London the city, New London the county, and a couple of smaller New Londons each took a slot, so the dropdown showed four rows of the same name before anything else. The second problem was more serious. The New node has 311 children. The walk collects completions breadth-first under a budget, and the dense New London branch filled the budget before the search reached New York. The trie contained New York, but the walk never reached it. The most prominent place a person was likely to mean was crowded out by smaller places that sorted first.

The fix

When the walk fails on a partial last token, the new code skips fuzzy search. It walks the complete prefix (New) and then filters that node's outgoing edges by the fragment, keeping every edge whose token starts with yor. york matches and london does not. The existing trie completes the word without fuzzy search.

The code also caps the number of places each branch can contribute. A dense New London branch therefore cannot crowd out New York before the search reaches it. The code also collapses same-name places to the most prominent one. With three changes (character-level completion via edge filtering, a per-branch cap, and name deduplication), New Yor becomes New York, Chic becomes Chicago, and San Fr becomes San Francisco.

Two problems wearing one name

"Complete a place word" and "complete the word a person is typing" look like one feature, but they are two. The first assumes the token is finished and asks what comes after it. The second assumes the token is unfinished, so it has to complete it character by character and rank the results well enough that the obvious choice appears first. The CLI only exercised the first case, so the second shipped untested.

The same function was correct on the command line and wrong in the search box. Its name, tests, and history gave no warning, because the command line never exercised partial words. We found the second case only when someone typed half a word and the demo suggested a city in Colorado.