jecasc - 3:01 pm on Aug 4, 2011 (gmt 0)
I had a similar problem and created a fuzzy search solution using an adaptation of the Damerau-Levenshtein algorithm. I have all words occuring in product names in a database and when someone types in a word into the searchbox the letters are compared with the words in the database and possible solutions are returned in order of Damerau-Levenshtein Distance. If a customer types in "bleu wodgat" instead of "blue widget" he still gets a result. The fuzzy search logic has considerably increased conversions on my website.
It works for me, since I only have a little more than thousand products in my database so the speed is acceptable. I also cache the search results, so if a second customer makes the same typo I do not need to run the algorithm.
If you have a high number of products or lack the expertise to build your own custom solution I would consider outsourcing search and use a third party solution like "Exorbyte". There you provide a feed of all your products and the search is completly processed on a third party server.