Thursday, July 10th, 2008

Reverse Autocomplete; The details matter

Category: LiveSearch

Reverse Autocomplete

Autocomplete was one of the first Ajax patterns to come about. We often talk about how it looks, but the how it works part is what really matters. How smart is the algorithm to work out what you are completing against? How long do you go before you kick in to see a result? Does it narrow enough?

László Kozma wrote up his thoughts on Reverse Autocomplete which talks about helping the user as they change their mind during autocomplete, and being away of what they are doing, instead of just using field.value as an absolute. He acknowledges that he isn’t the first to think about this, but there are some good ideas.

First, he shares a couple of use cases of the problem, such as:

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.

In the browser I typed “”. Then I want to go to “” next. Even though “” 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 typed “” in the e-mail To: field. Now I go back to change it to “”. Even though this address is in the address book, “jen|” 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.

And his 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.

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.

Posted by Dion Almaer at 10:23 am

3.8 rating from 40 votes


Comments feed TrackBack URI

eclipse autocomplete kinda solves this problem, and you can manually invoke a lookahead with ctrl-space (thats quite common across editors i beleive) perhaps what we need is ctr;-space for the web?

Comment by Dave Crighton — July 10, 2008

I’m working on Kelkoo (an european shopping engine) and our autocomplete works on both normal and reverse mode. You can have a look at it on :
We are using the Autocomplete YUI component with a few tweaks to handle our needs.

Comment by Remi — July 11, 2008

@Remi: Your autocomplete is a perfect example of the limitations that the author outlined above, namely, “ip| nano mp3 player” (where | is the cursor) brings up nothing even though “ipod nano mp3 player” is in your autocomplete list.

What I get out of this article is that it’d be nice if the cursor acted somewhat like a wildcard character, so that you can modify the contents of the input box anywhere in what you are typing and still get useful autocomplete results.

Comment by zulugrid — July 11, 2008

Leave a comment

You must be logged in to post a comment.