Take a look at Text::Soundex and Text::Metaphone. Those will help you pick close matches quickly. Then use Text::Levenshtein (or Text::LevenshteinXS, Text::Brew, Text::WagnerFischer, or one of the other "edit distance" modules to get narrow things down or order by likelihood.

-sauoq
"My two cents aren't worth a dime.";

If a "plain" or "direct" search fails, you could try the following things:

• Note the search in a log and manually create an alias every day for the top 10 failed searches. This will improve the perceived results of your users vastly, but requires lots of manual work every day.
• Normalize all your products by using some phonetic normalization, do the same for your search term and then do the search again. This works nice if the first method still doesn't provide a satisfactory result.
• Apply the Levenshtein distance or some other distance to select the "closest" matching/available word. For example, an interesting metric could be to see how many characters need to be inserted or swapped to get from one word to the next. This is expensive to compute but could yield interesting results too.

The idea of manually adjusting the search results comes from a talk by Martin Pauly which discussed the work he did for Blackstar Video, I think. It is a nice idea on how to gradually improve a very simplicistic approach in my opinion.

e.g. search for *mp3* *pla* *lay* *ayr*. The search engine should search for all of these expressions and then rank the results according to which documents matched the most

This technique is used on commercial websites to make up for inaccurate spelling. e.g. brittany spears

You could consider doing this with AJAX

There's an example using Catalyst. There's Prototype.js, Rico and maybe a few things on JSAN.

Won't be as quick a solution as the other nodes in this thread, but it's quite a cool way to do it and a bit like Google Suggest ;-)