How does google do the "did you mean...."?

[Gene_Tani]

there's several ways: Levenshtein distance, soundex, Metaphone and
Phonex algo's. There've been threads on "spelling correction" here
and in rubytalk.

[August_Lilleaas]

A bunch of useful stuff: http://text.rubyforge.org/

[Michael_Latta]

Have you looked at SOLR or other full text search plug-ins.

Michael