How to format search autocompletion part lists?

Question

I'm currently working on an AppEngine project, and I'd like to implement autocompletion of search terms. The items that can be searched for are reasonably unambiguous and short, so I was thinking of implementing it by giving each item a list of incomplete typings. So foobar would get a list like [f, fo, foo, foob, fooba, foobar]. The user's text in the searchbox is then compared to this list, and positive matches are suggested.

There are a couple of possible optimizations in this list that I was thinking of:

• Removing spaces punctuation from search terms. Foo. Bar to FooBar.
• Removing capital letters
• Removing leading particles like "the", "a", "an". The Guy would be guy, and indexed as [g, gu, guy].
• Only adding substring longer than 2 or 3 to the indexing list. So The Guy would be indexed as [gu, guy]. I thought that suggestions that only match the first letter would not be so relevant.

The users search term would also be formatted in this way, after which the DB is searched. Upon suggesting a search term, the particles, punctuation, and capital letters would be added according to the suggested object's full name. So searching for "the" would give no suggestions, but searching for "The Gu.." or "gu" would suggest "The Guy".

Is this a good idea? Mainly: would this formatting help, or only cause trouble?

Answer 1

I have already run into the same problem and the solution that I adopted was very similar to your idea. I split the items into words, convert them to lowercase, remove accents, and create a list of startings. For instance, "Báz Bar" would become ['b', 'ba', 'bar', 'baz'].

I have posted the code in this thread. The search box of this site is using it. Feel free to use it if you like.