30 Mar 2007
What Makes a Good Autocomplete?
We’ve been working on a problem for the past couple of weeks: an optimal autocomplete algorithm.
Many of our users have said that while Enso is great, it requires a bit too much typing. We’re inclined to agree. Yet, figuring out the best solution is tricky: there are more autocomplete algorithms than bones in a school of lionfish. There are straightforward algorithms, too-clever-for-their-own-good algorithms, standard command-line-style autocomplete algorithms, and the list goes on. A lot of the algorithms seem to go down fairly easily when you first start playing with them, but they end up getting stuck in your throat due to some unforeseen edge-case. This post explains our thought process in evaluating the algorithms given the (g)astronomical number of possibilities.
Let’s start by defining the problem. Autocomplete asks the question of how ones maps a series of user keystrokes to one command name among a thousand possibilities.
Enso currently uses a slightly modified version of the “Obvious Solution”. The obvious solution requires that the keystrokes entered match the beginning of the command name, then picks the alphabetically first among all such command names. This is exactly what the Windows command prompt uses (at least the NT prompt; the old DOS prompt doesn’t have this autocomplete feature). Other systems use variations of this; most URL bars, for instance, require that what is typed be the beginning of some URL (not including the http:// bit). Enso improves on the obvious solution by allowing the user to entirely skip words during entry. Thus, Enso lets “open firefox” complete to “open mozilla firefox”.
Unfortunately, this solution has much more typing than necessary. In Enso, typing “open ” before typing the name of the application is frustrating; especially since there are keystroke launchers out there that don’t have any such requirement. However, Enso can do a whole lot more than launching — and in the future Enso will do vastly more than it does today — so we can’t simply drop the prefix. The prefix is what makes it clear that the user is launching something rather than any of the hundred other things they could possibility be doing (like printing it, deleting it, compressing it, or sending it as an attachment). The number of commands that Enso might have is just too large to eliminate the need for verb prefixes and structured name spaces.
So we come to the question: how can we implement an autocomplete solution that allows Enso users to use fewer keystrokes, without losing the memorability of semantic language that makes Enso powerful?
Like all interesting problems, the constraints put upon a good autocomplete algorithm are often opposing. The key to a good solution lies in striking a good balance, satisfying as many of the requirements as is possible in a delicate tug-o-war.
Keystroke Efficient. The autocomplete mechanism should minimize the number of keystrokes. That’s the point of autocomplete. In other words, an autocomplete should have maximal information efficiency. We ran some numbers on a large set of Enso commands to figure out the efficiency of a couple autocomplete algorithms. The worst case algorithm is one where you have to type every character of the command name; the Unix-Style algorithm uses tab to autocomplete the command until it reaches an ambiguous place; the current Enso behavior is as described above. Here are the efficiencies:
Worst Case: 9%
Current Enso Behavior: 38%
As you can see, even the current Enso autocomplete has a lot of room for improvement.
Transparent The autocomplete mechanism should be transparent to the user. That is, with little or no explanation, the user should be able to simply type a small number of keystrokes that they think are related to what they are trying to reach, and the autocomplete mechanism should present them with the command they are expecting. It should either be magic (i.e., guess what the user means so well that the user never has to think about the mechanism), or predictable (i.e., operate so simply that with little or no explanation, the user understands how it works and can make the mechanism do what he wants it to do), and preferably both.
These two requirements describe the fundamental tension that autocomplete tries to resolve: descriptive power versus efficiency. The totally transparent interface simply waits for the user to type something descriptive and meaningful, like “open firefox”. The totally efficient interface ignore all semantic meaning and assigns all commands to one- or two-keystroke shortcuts. Neither is a satisfying solution; the totally efficient interface is difficult to learn, easy to forget, and has no meaningful association. The totally transparent interface requires the user to type vastly more keystrokes than is necessary, and of the keystrokes typed, only a few of them actually make a difference in distinguishing this command from the other commands.
But these two things are not the only requirements of a good autocomplete mechanism. A good autocomplete system also satisfies these requirements:
Lenient The autocomplete algorithm should be lenient and forgiving, especially where the user’s memory is concerned. To give an Enso example, the user should be able to type “open firefox” instead of the full name of “open mozilla firefox”. Trouble lies around the bend, however. If the algorithm is too lenient, the autocomplete mechanism will no longer be transparent.
Reversible If there is an autocompleted command, then tapping a key and then tapping backspace should cause the autocomplete mechanism to revert to its previous state. Note that Enso currently doesn’t behave this way if you use “enter” or “tab” to autocomplete. This eliminates the bash-style autocomplete, and any other autocomplete algorithm which “autotypes” characters. Think of many autocomplete systems that mess you up because typing the backspace key deletes the autocompletion, not the last key you typed, requiring you to double-tap the backspace key (but only if there’s a completion–otherwise, beware!).
Ergonomic The autocomplete mechanism should not cause undo ergonomic strain on the user. This applies especially to any case where there is a key with special meaning. For example, if the tab key means “complete to the end of the next word”, then using autocomplete becomes physically uncomfortable bad when holding down the quasimode key. Choosing an ergonomically perfect key like the space bar is nice, but overloads the meaning of “space”.
Habit Respecting The autocomplete mechanism should map a fixed user input to the exact same command every time, unless the set of available commands has changed. Even if you believe that
Scalable The autocomplete mechanism needs to work for command namespaces that include literally thousands of commands. For example, the mechanism “the user’s keystrokes must appear somewhere in the command name” works well for small namespaces, but does not work well for large namespaces, because there will be all kinds of unexpected matches for any fixed small number of keystrokes.
Visible Ideally, the autocomplete mechanism should be visible to the user. This encompasses a couple different points. First, if the user has typed, and the command they want is not the one that is completed, there should be some indication as to what they need to type to get to the command they want. Second, if possible (and in general it may not be possible), the user should be able to see the minimum keystroke path to the command name highlighted (or should be able to look this information up somewhere).
A Particularly Challenging Bit
The place where the algorithm becomes really hard is in Enso’s arbitrary commands: you can type anything after commands like “define”, “google”, and “learn as open”. This means that anything the user types could possibly be matched to the arbitrary portion of those commands. In Unix, you can skip to the arbitrary portion of a command by using tab (although this isn’t reversible). Are there other ways? We think there are.
What do you think?
We’d like to open this up to the community and see what sort of discussion we can have about autocomplete, autocomplete algorithms, and rubrics for judging them. What autocompletes out there do you love, and which do you hate? What makes them good, and what makes them bad?
by Aza Raskin