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

Quoting Ben Johnson <rails-mailing-list@andreas-s.net>:

I have a search on my website that search names, so I know all of the values they could enter. How do I do something like google where if I type jonson it would say "did you mean johnson"?

Any ideas?

Thanks.

Pete Norvig explains how he did it: http://norvig.com/spell-correct.html

There's also a plugin for the feature:

http://agilewebdevelopment.com/plugins/acts_as_suggest