I'm looking around for an efficient algorithm for typehead/autocomplete on a website. That is, as you're typing into a text box, the page makes an AJAX call and displays a list of search terms that are similar to what you're typing. You see this a lot on travel websites where as you type the name of a departure/destination city/airport, all the choices that match your text pop up quickly. I have some decent ideas of how to do it using HashMaps but I'm sure there are standard solutions to this common problem. However, a quick google search didn't turn up anything too satisfying. The general problem requirements are:
* You have a dictionary of search terms
* Given some input string, you want to return 4-5 results from the dictionary that "match" the input string.
* The "match" can be simple, such as returning words from the dictionary that start with the input string, or more complicated, such as any words that contain the input string or even similar strings.
I'm just interested in seeing the different approaches to this problem so any/all algorithms you guys know of for this are appreciated.
* You have a dictionary of search terms
* Given some input string, you want to return 4-5 results from the dictionary that "match" the input string.
* The "match" can be simple, such as returning words from the dictionary that start with the input string, or more complicated, such as any words that contain the input string or even similar strings.
I'm just interested in seeing the different approaches to this problem so any/all algorithms you guys know of for this are appreciated.
Facebook
Twitter