There are two popular approaches for "suggesting" at the large scale.

The first involves analyzing a huge volume of prior search queries.

• Compare the second-to-last query and the last query a user supplied during any short session.
• Assume that the last was more "successful" in the user's view than the second-to-last.
• If the query strings are "close" by some measure, such as off by a single character, then the next time someone types in a query that looks like that second-to-last, perhaps we should suggest the query string that the earlier user was apparently satisfied with.

Of course, it takes an enormous amount of data-crunching to create reliable suggestions using this technique. Furthermore, the suggestions are likely be specific to the search domain, so analyzing e.g. the pirate bay's search query logs would not necessarily yield good suggestions for e.g. apple.com.

The second approach to suggesting is to find documents which are "nearby" in term-space to the query's term space. For a small scale illustration of vector-based similarity measures, there's an excellent article on perl.com about building a vector space search engine, but for large scale you need to reduce the dimensional space using a tool such as Latent Semantic Analysis, or LSA. LSA and its relatives are typically used to power those "more like this" queries.

You could also combine the two approaches by using vector similarity as another measure for determining whether the last and next-to-last queries are related.

None of this does you any good, though, except for explaining to your client what's truly involved in providing high quality suggestions -- because to the best of my knowledge, there are no open source implementations of either of these algorithms. (The patent on LSA expires this year.)

However, it's possible to use ASpell to provide spell checks, and if you're feeling ambitious, you can feed ASpell with custom dictionaries. Peter Karman wrote Search::Tools::SpellCheck for precisely such an application.