CLOPS

command-not-found has a gdbm database that maps commands to lists of
packages. Now they added the spell checking code from Peter Norvig (to
which I linked before).

An article discussing the recently added behaviour for the
command-not-found hook in bash for ubuntu.

http://webupd8.blogspot.com/2009/08/command-not-found-becomes-more-useful.html

It might be worth checking the implementation for this, how they go from a
list of potential commands and the users input to suggestions of what they
might have meant.

Levenshtein Distance is not quite what you want in a spell-checker.
Luckily, it's really easy to implement a spell-checker:
http://norvig.com/spell-correct.html

Apache commons lang has an implementation of Levenshtein Distance that
could be used. See
org.apache.commons.lang.StringUtils.getLevenshteinDistance(String,String)->int.

There's more to it though than just looking at what can appear at a
position. We get an unknown option also when a user uses a genuine option
somewhere in the format that it cannot appear.

Due to the new error reporting system it might make sense for
UnknownOptionError to carry an optional payload of information. Even
without suggesting via edit distance we should be able to differentiate
between when a real option is used in the wrong place and when an unknown
option is used.

that sounds quite similar to the TAB completion problem, if you know which
strings can appear at some position, you can pick the one with smallest
edit distance