how to build suggestion list for auto-suggest/auto-complete

I would like to implement auto suggest feature on a website that has a custom shopping cart/backend system. The system allows to enter a word that a customer might put and a list of suggestions; such as "cal" for words and "calcium, calorie" for suggestions. I have 6000 products and I'm confused on how to approach building such a list. I开发者_JS百科f we take the "calcium" example should I slice it to "ca","cal","calc" and create suggestions for it? Also how do I deal with misspelled words such as "calsium"? Is there a way to automate this process? Please advise. Thanks.

---

For starts, have your autocomplete trigger only when a certain number of characters are entered. Otherwise you're going to be doing searches for a, which might have more results than is necessary.

For matching words, if you're using a database, they usually support the LIKE comparison for wildcard matching:

SELECT `name` FROM `products` WHERE `name` LIKE 'cal%'

Note that you will want a table that supports full text indexes, or you really won't like the performance. I'd also recommend making a separate database, if possible on a separate server that is a simple data mining server, and duplicates your production server's product list. This way you don't hog resources of your main database for autocomplete.

For misspelt words, you can try something like Levenshtein distance which shows how closely spelt two words are.

---

Auto Suggest can be implemented using data structures like Trie, Ternary search tree.Hitting the DB is not a efficient solution and CPU intensive.