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