What kind of algorithm does an HTML SELECT element uses to show results as you type?

Question

I'm trying to replicate an HTML SELECT element (drop-down-list or combobox) in Flash (AS3).

In most browsers, when you have one in focus and you type something, the combobox will try to find the value within its options and show the closest one. I was wondering what kind of algorithm is used for that. I don't think its Levenshtein or similar since it only works with the beginning of the string.

I'm thinking that it works by keeping a buffer of what has been written, and tries to find a string starting with that... if it doesn't find anything, it clears the buffer, and searches a string beginning with the last character pressed.

I already prototyped this, and it works quite ok, with one caveat... In HTML, when you repeatedly press the same key, it will rotate between all options starting with that character. I think I could fix this, but was wondering if someone has already done it, to compare the algorithms... its turning into quite a complex code to test and debug, and I'm not sure I'm covering all the possibilities...

Answer 1

I don't know what algorithm is used in the browsers but one that comes to mind that would do what you want is sequence alignment or a longest common subsequence algorithm. It would allow you to match any part of the string to any other part of the string (with possible gaps between the matched sub strings). It's not massively quick though.

http://en.wikipedia.org/wiki/Sequence_alignment

there's also some very good lecture videos online at MIT open course ware

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed15.htm

Answer 2

Just did some tests on firefox, and I noticed (this is not official information, just pure speculation):

• Key pressed event:
  • Esc (firefox only): clear buffer
  • Arrow up/down: move up/down on the list, clear buffer
  • Page up/down: move up/down by 20 on the list, clear buffer
  • Home: move to the top of the list, clear buffer
  • End: move to the end of the list, clear buffer
  • Other:
    • Empty buffer?
      • Yes: add key to buffer
    • buffer.length == 1 AND key is same as last key pressed?
      • Yes: go on next item starting with key.
      • No: add key to buffer and search next item starting with buffer.
• 1.5 seconds passed event: clear buffer

This will need a timer of course.

Answer 3

The reaction of form widgets to keyboard interaction is not standardised and different browsers don't agree. This is always an issue when creating ersatz form controls from script.

In HTML, when you repeatedly press the same key, it will rotate between all options starting with that character.

This feature comes from Windows and is quite unintuitive. The exact rule isn't that exactly, is quite obscure, and gives different results in IE and Opera versus the other browsers.

IMO this behaviour is highly undesirable. Since no average user is going to be able to predict how the rule works, I personally would leave it out and simply select the first option to match the typed leftstring. This is easier for you to code and easier for the user to understand.

Answer 4

In HTML, when you repeatedly press the same key, it will rotate between all options starting with that character. I think I could fix this, but was wondering if someone has already done it, to compare the algorithms

You might want to reset to the top of the dropdown after every key press and then search for the appended buffer.