What Makes a Good Autocomplete?

Redesign

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.

The Problem

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?

The Rubric

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%
Unix-Style: 27%
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 adaptive interfaces are efficient, they are not habit-respecting.

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?

In some situations it’s quicker to use the mouse, rather than type. I suggest a combination of mouse & keyboard to access Enso commands to reduce the amount of letters typed.

I think Enso needs to have the command manual visible while in the Enso mode, by using radial, or pie menus. Each Enso command would be given a position, and could be put into clusters/groups by the user, the menu could also be sorted/arranged in different ways, such as popularity, latest used, user-arranged, by category. There could also be an option to search the commands, that would work in a similar way Enso works now.

Search selection could = press capslock, move mouse up-right, type what you want to search, release capslock.

Open could = press capslock, move mouse up, type what you want to open, release capslock.

Edit typeface could = press capslock, move mouse right, and then to the typeface option, type the typeface, release capslock.

Also if you wanted to use the keyboard only, search, open, edit, could be abbreviated. So that if you want to use just the keyboard you could, hold capslock, press o (for open), type what you want to open. Is this how it works now?

Stuff based on popularity or last-used would not work, because it’s not respecting your habits, or rather, doesn’t let you build a habit.

capslock + “o TAB” is Open, but I find it way easier to just type the full word because of ergonomics.

I *do* like the idea of a radial menu, or something similar, but I also really love using full words for commands: search, open, google, wiki, go; there’s no ambiguity, it’s very grokkable. So how do you do radial that starts from a variable-width command?

Maybe the command can be affixed to one border of the screen, say, center-left. And say you type “open fir.” On top, you see “Mozilla Firefox.” To the right, “Windows Firewall.” To the bottom, “Mozilla Firefox (safe mode).” All of these would be accessible with the Up, Right, and Down arrow keys, respectively; and if you need to see more options, hit the Left arrow.

That’s all I got. I’ve no clue if this would work or not. Love the blog and Enso.

Whatever it’s usability flaws (and it could be argued that they are legion), Quicksilver has a solution to the problem of typing “open” before every command that works very well: you begin by specifying the object you want to work with — Firefox, in your example — and Quicksilver guesses what you want to do with it.

For the most part this works exceedingly well. 99% of the time, if I’ve selected an application I want to open it. If I’ve selected a file, I want to open it in its default application. If I’ve selected an e-mail address, I probably want to send an e-mail to that address. By making good assumptions about what I want to do with the object in question, Quicksilver avoids having me specify the obvious every time.

Another thing that I think Quicksilver does well is allowing me to form habits and respecting those habits. Like Enso, Quicksilver provides a list of possible completions for the abbreviation I type and allows me to select one of the completions using the arrow keys. What Quicksilver adds is memory of which completion I selected. If I later enter the same abbreviation, then the default completion is the one I have selected most often for that abbreviation.

This certainly meets the definition of an adaptive interface, but I think it adapts in a habit respecting way. The adaptive behavior only takes effect when the abbreviation that I have typed so far is an exact match for an abbreviation that I have used in the past, and it simply gives more weight to the most frequent command for that exact abbreviation.

I’ve found this to be a real problem in the current version of Enso. For example, I can type the abbreviation “outl” expecting to select “Microsoft Office Outlook”. However, the completion list I get always starts with 3 or 4 favorites links to articles about Outlook. No matter how many times I scroll down to “Microsoft Office Outlook”, Enso won’t make it the default selection for the “outl” abbreviation.

I’d say that completion not necessary should give one and only one command to execute, but rather quickly narrow-down all that large namespace to few matching commands. I would prefer “camel humps completion”, and it works great for large namespaces like vocabulary of large program. For Enso, it means that typing “OMF” will show just few cases, like “open mozilla firefox” and “open my files”.

I have to say guys that this problem has already been solved, at least for me; QuickSilver. Best autocomplete I have ever used. I haven’t hit an edge case that QuickSilver makes cumbersome.

It would be great if there was an option in Enso to remove the “open” in front of many commands. Something like “learn open as default” or “default to open” could set/change the default command that is assumed when you just type “firefox”. This would most likely (though I don’t know all the commands) allow functionality preservation while making the most-used task that much easier.

Why not just treat ‘Firefox’ as a verb. A typical person only uses a dozen applications and they all have non-ambiguous names.

You have a mental model of what your application grammar should be… your users won’t have this. They will type the short form… Outlook, Excel, Powerpoint, IE (instead of internet explorer) and you should be smart enough to auto-complete most of these with 2-3 letters.

BTW: You should also be able to handle web-applications like regular ones… , Google, Yahoo, Mapquest, are just as much applications as Firefox.

Greg raises a good point when he says why not use “Firefox” as a verb. To put it another way, why not object-verb order instead of verb-object? (This is the recommendation in The Humane Interface!)

One other difference with Quicksilver is that it lets you skip letters, so as long as what you type is in the correct order, it will match. So I can type “ff” for Firefox.

Definitely need memory of some kind. It turns out that I don’t actually use ENSO that much (nor indeed Qicksilver on my Mac which I think I have used only once) - I just don’t seem to work that way or haven;t got in to the habit of working that way. However I was using it last week to run Movie Maker which wasn’t on my start menu - and I found it really irritating that it was always the second option rather than the first even after I had used it 4 or 5 times. (BTW I hate personalised menus in applications - this is different)

I also agree with the object verb idea - that makes much more sense to me. typing open feels redundant most of the time

How about the system as you have it now but the use of the down cursor key will cycle through all the possible commands in alphabetical order and the up cursor key in reverse alphabetical order. This way the user can habituate to typing a certain set of characters and the appropriate number of up or down cursor key presses.
When typing all of these possible commands will be seen in a list although if there are many the user may need to cursor down or up. The user could also keep typing to get a closer match. The possible commands will change as the user keeps typing.

Since launching applications is one of the most common if not thee most common actions a user does with an application why not have the word of an application on it?s own set to open it. So if the user wants to open firefox they just type firefox. If they want to do anything else they have to specify the action they want to performed, like print filename.

I think the reason that the action comes first (in commands) rather than object action, is that it is more common and thus more natural for a native English speaker to say open door rather than door open.

I’ve been thinking, to satisfy those who regularly launch applications that appear 3rd or 4th down the list you could have a method of *explicitly* bumping them up. Rather than having the dangerous adaptive behaviour they could say something like “promote Firefox” (though a better word, I just can’t think of it). This means that it will have a much higher weighting.

This way the default work flow of a user will be the optimum, but the interface still does not change without their explicit command.

To me, the beauty of a system like Quicksilver is that I don’t need a separate command to teach it what abbreviations I want to use. I just type in the abbreviation that I want to use for a certain command. If Quicksilver doesn’t choose the correct command the first time, I can teach it what command I want by simply selecting it in the list. I don’t remember ever having to arrow to a command more than once unless I change what abbreviation I’m using.

I would also like to see the habit aspect be “portable” between machines. If I use Enso on two different machines with differing amounts of software installed, the same application will likely be in different positions in the completion list. If I have to type “x y z down down” at home but “x y z down down down down” at work then I can’t form a habit for that application.

I think the current completion method works well on the built-in commands because it is a limited set designed as simple command verbs. Choosing between “open”, “close”, and “go” by typing the first few letters is easy. I can usually enter one letter and TAB and get what I want. Start Menu application names and favorite link titles, on the other hand, are designed to be descriptive rather than easy to type. Two applications that I use a lot as a developer are “Microsoft Visual Studio .NET 2003″ and “Microsoft Visual Studio 2005″. I don’t want to start at “studio” because that is also used in a variety of other apps. So I’m left with typing out “visual studio .” or “visual studio 2″ to select them, and it would be even worse if Microsoft had been consistent in their naming and used “Microsoft Visual Studio .NET 2005″. It would be nice to be able to use simple, mnemonic abbreviations like “vs03″ and “vs05″ to narrow these down.

What if you could write commands either as object-verb or verb-object? “firefox !open” matches “open Mozilla Firefox”. A search for objects reduces the number of matching commands (and so the number of keystrokes) more than a search for verbs, because on average fewer verbs match an object than objects a verb. It’s especially useful for commands like “define” and “google”. Also, an object-verb order is arguably more intuitive, as your users say.

There are even fewer keystrokes if the most common action (”open”) is the first match for any applicable object (any object that can be opened). Thus to open Firefox, type “firefox” (or even “fire” if that is the only object that begins with “fire”). But to switch to the firefox window type “firefox !switch” or “firefox !window”. As far as I can see, this satisfies all the other requirements listed in the original post.

I do not understand the paragraph about “A Particularly Challenging Bit”.

Many of your users say they prefer an adaptive, modal interface; maybe some degree of adaptiveness and modality should be allowed for the sake of ergonomics.

Because I am on a PC, I have not used Quicksilver before, but I have used Launchy. It “learns” what programs I want to open and auto-suggests programs as I type. I have found it very good at suggesting items and being quick.

I disagree that you need to have a command before the target in Enzo. To make it a useful launcher, “open” should simply be the default when dealing with most things. This still allows you to add commands for future extensibility.

Oh, how’s Vista compatibility coming?

I think that a lot of very good suggestions have been made so far. I’d like to agree and disagree with a few before I give my idea:

* The idea of having Enso remember what command you chose last time you typed “omf” and offering that first (a la Quicksilver) is a very good one. I agree that this would be adaptive in a habit-respecting way.

* Any habit that involves learning to hit the up or down arrows a certain number of times is a bad idea. This will always change as you add applications or switch between computers.

* Similarly, any use of the mouse is right out. That doesn’t mean however, that you couldn’t do some kind of radial display reached by the arrow keys, thought I’m not sure how that would be better than what Enso does now.

* Ergonomically, CAPS LOCK+TAB is horrible, as you say. Might it be better to use a combination such as SPACE+SHIFT to replace TAB?

* I agree that object-verb is often better than verb-object. But why shouldn’t you be able to type either one? It seems unlikely that “Firefox open” could ever mean something different from “open Firefox”. The main problem would be, I imagine, a vastly increased search space.

* I really like the idea of explicitly defining “firefox” as “open firefox”, so that in a set of commonly-used cases, you can skip the verb. This seems like it would vastly improve efficiency without limiting the future expansion of Enso.

* On the other hand, how many things could “firefox” possibly mean? It seems to me that the default should be “open”, and if it’s already open, “go” is chosen, unless some other verb is typed. Given a list of installed apps (which Enso has), which is a finite list, what’s wrong with defaulting to “open”?

OK, now I have two ideas to add. First: You’ve got two sets: commands (e.g., open) and arguments (e.g., word). The list of commands is always finite at any given point, and the list of arguments would appear to be infinite, since you can google for any string at all. But in reality, most commands take a finite set of arguments: you can only open the apps that are installed, and you can only open the files that are on your hard drive (I’m ignoring certain web apps here). So it’s really the arguments for specific commands (like google) that are infinite. So why not just disallow auto-complete for the infinite sets but let it work for the finite ones? So, “goo-TAB” gets you “google” and then auto-complete stops working. However, “off” still works for “open Firefox”.

If you combined this with memorizing the commands chosen for each set of characters typed, you could quite quickly get to a point where Enso “magically” predicts what the user wants most of the time.

I have another idea, but since this post is getting absurdly long, I’ll post it separately.

Here’s my other suggestion, which as far as I know, is pretty outside-the-box. It’s inspired by experimental methodolgy in linguistics, which is my field.

What if Enso were to measure the milliseconds between keystrokes and take the speed at which the user is typing into consideration when mapping the keystrokes to a command? This may sound weird, but my hunch is that we type those commands we use a lot *much* faster that we type commands we don’t use much. So, this would essentially reward decisiveness and muscle memory.

Of course, this shouldn’t be used in such a way that it can really screw people up; maybe it should be optional. The default would have to be something like “unless the typing was faster than X, use the default algorithm”.

Do you think that might work?

Cn yu rd ths? I cldn’t blve tht I cld actlly undrstnd wht I ws rdng. Te phnmnl pwr of te hmn mnd, acrdng to a rsrch at Cmbrdge Unvrsty, it dsn’t mttr in wht ordr tht lttrs are in or wrd are, the only imprtnt thng is tht te frst and lst lttr be in te rght plce. Te rst cn be a ttl mss and you cn stll read it wthut a prblm. Ths is bcse te hmn mnd ds nt rd evry lttr by itslf, bt te wrd as a whle. Amzing huh? Yh and I alwys thght splling ws imprtnt. (http://interfce.com)

PS Mybe ths txt-trnsfrm cld bcme a cmnd in Enso. :) Or cld be a way to type lss, for an auto cmplte?

It may be possibly to read without vowels, but switching your mindset to writing it is more than it’s worth.

gd pnt

Another vote here for object-verb rather than verb-object.

You really should spend some time using LaunchBar and Quicksilver on the Mac. One pattern that you’ll come upon is what I’d call directObject-verb-indirectObject, which I think is important to accommodate.

Nice work, in any case. Looks great, too!

How about the user being able to specify where in the list they want a command, e.g. first second or third in the list. This would help in being able to arrange the list order and keep consistance if multiple machines are used.

take a look at partial completion in emacs. David Gillespie’s work

Speech-to-text… just say what you want to do, like “open firefox” etc

Enso is great I love the program. I use it daily from reports to even forum posts. I don’t think Id live without it sometimes, misspelling and minor word definitions have come to be a minor problem.

Only last week i was trying to find Fraps on my desktop and couldn’t find it. So I held caps lock, type in the command and the program, Simple! With only the key board I can open programs rather than opening up different folders and documents to get to one thing.

Thanks guys Enso rules

Well just a general comment on what we’re dealing with.

Auto-completion makes the assumption that we want to enter a command: few words, made up of letters, probably entered sequentially, most of the time.

The sequential nature of command entry is good for simplicity, maybe less for quick entry, since we want to save keystrokes.

This is a matter of maximizing entropy, trying to put as much information into every keystroke, in order to prune the tree of possible completions, quickly.

The given nature of commands, actions and arguments leads to proposals like changing object/verb order.

I have just started thinking of this, but I believe there are more ways to reduce possibilities. How useful they are is a matter of research.

Maybe users would like to use certain keys to move to a different section of the command which is less redundant, like having certain parts on different lines (no proposal, just as a picture how it might work). Or some arrangement into syllables. Or even not sequentially entering commands, but just a rather unique part of it?

It also depends very much on user’s taste. One might be happy with very short but cryptic extra names for her commands, even new synonyms, others might like more wordy approaches, but with lots of modal state.

Finally, the user wants something, quickly. He got mouse and keyboard and has to use it, until we can use eye-ball position feedback. :-) What I’m trying to say is that he did not want to spell commands in the first place, we just make him want this by making it easy and attractive. Maybe there are even simpler Interfaces possible.

I’m late to this party, but I’ve got a question and suggestion.

First, have you guys looked into SLIME’s * fuzzy completion mode? It’s pretty bright, and can expand something like “m-v-b” into multiple-value-bind, but will give a list of completions for ambiguous results. More generally, running a spell checker on inputted text could work out well (I’ve not yet tested this).

As far as an ideal completion system goes I have a few thoughts. It would:

1. Include everything listed in the blog entry. Sounds good to me. :)

2. Be clickable. This is such an easy yet unobtrusive feature to add, and I’m willing to bet money that someone, somewhere, will want to select a result with the mouse.

3. Deal gracefully even with omitted verbs, although of course including them in the completion it displays. Like many posters have said, it’s silly not to accept “firefox” when the user’s likely meaning is so obvious. This is just the autocompletion of verbs.

4. For equally ranked results from the completion of ambiguous commands, display the most used matches. I know, I know, it’s trouble for habits. But the alternative is to display matches in alphabetical order or something, which is useless if there are thousands of commands on the system. I’d rather be able to type “o f” or even “f” and get firefox as the top completion, rather than “faac” (the first completion for “f” in Bash on my system), which I’ve never even heard of. Coupled with clickability, this is also functionally equivalent to Windows XP’s frequently-used-apps list.

* The Superior Lisp Interaction Mode for Emacs — an Emacs mode for writing Lisp code. http://common-lisp.net/project/slime/.

There are many good ideas listed so far, but I want to add my 2p. The reason I came back to this website is I have SQL Server installed on my PC and out of the many many application installed beginning with “SQL Server” the primary program that I use never shows up anywhere on a list until I type “sql s”, any irregardless how many times I open them. This frustration brought me to search for a solution for a tool that should taken for granted. I am finding myself fighting the tool when it should be a natural extension of my intentions.

Some my suggestions:
1. Ability to define an alias for applications.

2. Learn usage patterns and generate lists based on usage. Another blog topic railed against MS implementation of the dynamic menus in the Office product, which I agree is not very usable. However, the dynamically updated list of programs on the start menu is a useful feature. In fact, in my particular case it is more useful than enso. This requires me to think about different ways to open each application, which is not very efficient.

So, enso. Any word on what’s going to happen?

On the object->verb or verb->object debate…
English is a verb first language (well, as long as the subject is implied as we all implicitly seem to agree should be the case), so from a ‘newbie’ standpoint, verb->object wins (at least outside the hindi world which uses verb last naturally)

However, I think object->verb is favored by everyone because we live in an application centric computing invironment, so you gain the most information about specifying the application (object) first.

My computer has dozens of applications, and basically I do two things with them; open them and close them. Then i use app specific commands or buttons. As long as this is the case, defining the application first will always give you more information (and therefore be quicker and ’smarter’).

If you want to make things both quick AND English friendly, Enso needs to be action oriented. I don’t want to ‘open’ firefox, I want to ‘read lifehacker.com’ or i want to ‘learn about russia’ or ‘draw a picture’ or ‘check email’

Here the verb actually tell us something. I can ‘read’ web pages and documents, but not images. Now any autocomplete would be given information about the possible following objects and be able to react appropriately with less chance of annoying errors.

Odd thing is, that this might make it harder to translate enso into different languages like hindi because now you not only have to change the words, but the grammar/thought process behind it.

and on habits….
Habits are a dangerous thing to have a computer adapt to because all sorts of variables that effect habits can change without the computer realizing it such as

-users. my girlfriend and I use the same computer, but might have drastically different habits, do we need to log out each time just because of that?

-time/day. If i use a computer during work hours my habits might be very different than if I use the same computer in my personal time. this is especially important when thinking about mobile computing

-context. if i have window A already open, my habit or first impulse might be different than if window B is open

I also use launchy and like that it remembers which choice I selected, but I’m a bit wary of my computer trying to be too smart for itself.

evolution of auto complete - you can read it here

http://www.logblo.com/2008/11/02/TheEvolutionOfAutoComplete.aspx