Ajax Girl

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 “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 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.

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.

Source: Ajaxian » Front Page
Original Article: http://feeds.feedburner.com/~r/ajaxian/~3/331814206/reverse-autocomplete-the-details-matter