Back to my homepage

Reverse autocomplete

This is a proposal for a small improvement on the autocomplete feature, commonly found in many applications. To my knowledge, it hasn't been described or implemented elsewhere. If you know otherwise, or have some comments or suggestions, drop me a line to the address below. [note]

1. Introduction
2. Problem
3. Solution
4. Implementation

1. Introduction

Autocomplete is a well-known user interface feature implemented in many different kinds of software:

Web browsers complete the address typed in the address field with entries from the browsing history
Word processors (Word, Openoffice.org) have an autocomplete option which suggests previously entered words to speed up typing
Programming editors (Vim, Emacs, Eclipse) can autocomplete function names, member variables or other text depending on the current context
Most input boxes on web pages (except those for passwords) have autocomplete
In command line terminals or interpreted programming environments (Matlab, R, etc.) it is possible to autocomplete the typed command or the directory/file name (usually with TAB or ESC key)
In Google Suggest, as soon as I start typing, a drop-down list appears with popular queries that match with what I typed so far
When I enter the first few letters of an email address or name of the person, most email clients (both Desktop and web-based) offer to complete the rest of the address
many other examples...

There are many variations in the implementation details of this feature:

User interface: can be a drop-down box (1, 3, 4, 6, 7) or text inserted directly, in many cases with auto-selection (1 for some older browsers, 2, 5)
Exact/fuzzy match: in case of word processors or web queries it is often useful to allow for fuzzy matches, thus providing spell correction (for example in Google Suggest, if I enter "amrei", it offers to correct "American ..."; In web browsers if I start typing the address omitting the beginning "http://", autocomplete still works correctly)
Where is the suggestion database stored: in memory locally or remotely on server. While the first solution is much more responsive, the latter allows the usage of larger databases (as in the case of Google Suggest).
Make suggestion from past input of user or from larger database
Full or partial autocomplete (example for partial autocomplete is the command line interface, where autocompletion is done until the first point of ambiguity)
Completion is for atomic elements from a list or in a stream of continuous text (between two separators, such as word boundaries)
Passive or active autocomplete (wait for user to ask / always suggest completion, if available) (the command line interface is an example of the first)
Suggest one completion / suggest a list of completions ranked according to some criteria (possible criteria are: most frequent, most recent, etc.)
many other details...

2. Problem

While there are many different approaches in designing an autocomplete system, I believe most existing systems use either a simple set/list when there are only a small number of elements, or a variant of the prefix tree (trie), or Radix tree data structures for many elements. They dynamically fill up this structure with elements, which are then matched against the text that appears to the left of the cursor.

One drawback, in my opinion, of existing implementations (including all of those mentioned above) is that they don't look at the location of the cursor and the text to the right of the cursor. Of course, when the cursor is at the rightmost position, which is the case most of the time, there is nothing to look at. In some cases however, the user is going back to make some correction. In this case, autocomplete behaves in various ways in the implementations I've seen, but none of them feels really natural.

Let's see some examples of this behaviour:

I enter "German football team" in Google Suggest, then I change my mind and go back to change the query to "Italian football team". Autocomplete doesn't help me with this. Even when I entered "Italia| football team", (the | sign shows the cursor location), autocomplete doesn't do anything, as it doesn't look to the right from the cursor. For the record, "Italian football team" is a frequent query, if I type it normally from the beginning, as soon as I get to "f", Google Suggest knows what I want. Google Suggest seems to look at the text as a whole, trying to autocomplete to the right, ignoring the cursor. [note]
In the browser I typed "mail.yahoo.com". Then I want to go to "mail.google.com" next. Even though "mail.google.com" appears in the history, when I correct the middle part, such as to "mail.g|.com" or even "mail.googl|.com", the autocomplete is clueless. Again, the same behaviour as before.
I entered a command in the terminal, but realized the file path was wrong. I go back, delete part of the path, use TAB to ask for help, and manage to enter the correct address. In this case the autocomplete works, it knows where the cursor is, but it still ignores the text to the right of the cursor. Suppose, I typed the path "/home/myuser/Desktop/myStuff", then I went back to change "myuser" to "otheruser". Autocomplete does help me with that, it inserts "otheruser", but it has no idea that "otheruser" does not have the directory "/Desktop/myStuff" and this messes up the command. The natural behavior in this case would be not to do autocompletion, unless the string to the right of the cursor (until the first separator) is also part of the autocompleted text (the path exists). If space is the separator, I can hit a space and go left to it, and then autocomplete works again without looking to the right.
I typed "jenny@fictivecompany.com" in the e-mail To: field. Now I go back to change it to "jennifer@fictivecompany.com". Even though this address is in the address book, "jen|@fictivecompany.com" does not activate the autocomplete. This problem is similar to the previous one, but in this case space and the comma can both be considered a separator, as the boundary for autocompletions.

3. Solution

The solution is to simply take whatever method there was to search for the text before the cursor, and use it to match the text after the cursor as well. If a prefix tree is used, it is convenient to store the text to the right in reversed form for easier search. Most of the time the text after the cursor will be empty, so there won't be much overhead. When the cursor moves back, simply match the text both before and after the cursor, and only do autocomplete if something matches with both sides.

Example:

"United | America"

" are the separators or the boundaries of the text box
| is the cursor
a string is a candidate for autocompletion if it matches "United " in the left search tree and matches " America" in the right search tree, so "States of" can be correctly inserted.

4. Implementation

Traditional autocomplete:

Bidirectional autocomplete:

Bidirectional autocomplete, also appending at both ends [note]:

Enter names of American presidents (autocomplete is done on the whole name)...
Try for example "Theodore Roosevelt", then change "Theodore" to "Franklin".

This example implementation in javascript is based on AutoSuggest v1.0. I modified the code to perform the reverse search as well. Both the original and the modified version are under LGPL. For the cursor location code I modified this script. As this is just a user interface proof-of-concept, I don't recommend using the javascript code as such, as it is not more than a quick hack.

Text left and right of the cursor is shown for more clarity. Note that I didn't use any of the complex data structures mentioned, all we have is a simple array, as can be seen from the source.

Notes

It was pointed out that the idea is not entirely new, but still it is surprising that as of now, it does not exist in mainstream applications. Zsh performs the kind of validation of paths that was mentioned earlier. Emacs does allow for backward/forward matching. And of course, I did not claim that matching with wildcards was a new idea, obviously this is only a subset of regular expression matching. The idea is only to use the cursor location and the claim that if there is already a mechanism for autocompleting in the traditional way, it can be extended to look forward from the cursor, without any overhead. Matching in a more general context is discussed for example here.

Many people have pointed out that in order to be useful, an autocomplete system has to be able to append both to the beginning and the end of the text, regardless of the cursor position. In this way "States|of" should also match "United States of America", the same holds for "t|f" for example. This feature is mostly independent of the original idea to take cursor position into account. One possible issue is that this way sometimes too many suggestions are offered, especially for short strings. An other issue is that if we allow to expand the string at both the beginning, the end and at cursor location, a simple structure such as prefix tree can not be used for matching, which could be a problem for large databases. Arbitrary matching based on regular expressions can be done of course, but it is computationally more expensive. Additionally, fuzzy matching can also be allowed, to correct misspellings, as Google Suggest does.

I appreciate all the comments and suggestions on reddit and news.yc. In particular, "zem" and "yxhuvud" on reddit pointed me to the "gaddag" data structure aimed at solving a similar problem when filling in crossword puzzles or playing scrabble.

EDIT: 2010

As of now, Google has a new autocomplete behavior on their main search page which is more advanced than the earlier Google Suggest and seems to solve most of the problems discussed in this write-up, and more. For example the "Italia| football team" example works as expected (it seems however, that not the cursor location itself is used). Between July 2008 and July 2010 this write-up has been viewed close to half a million times and it has been covered on some usability blogs. I wonder if anyone picked up the idea of this post and implemented it in some system. In the applications mentioned in this post or in other applications I am aware of, as of 2010 (EDIT: 2014) no such feature is observable.

EDIT: 2014 (minor changes)