I'm about to start writing a small search engine within my site and I'm wanting to get more into assisting the user in finding the results they want.

I have considered soundex() operations, but heard that they aren't always reliable, since longer more complex soundex() results may be truncated.

I've also looked into Levenshtein Distance, but again have problems. Seems like to get a search-engine to find suggestions based upon their levenshtein-distance from the original search-term, you need to have a list of terms waiting to be compared to everybody's search term, and that could be nasty on the server forcing a levenshtein equation 1,000+ times everytime somebody submits a search.

Even if you do the tiresome lookups, you'll get dozens of alternatives for each word - how do you decide which to suggest? Seems almost like I need to store search terms, and the number of their returned results in the database, and do levenshtein-comparisons against those, and sort the close ones by their number of last returned results...make sense?

So I humble myself and come before you all today Wink anybody know how to do this in an efficient way?