Aron is right in his comment, that the corpus is important, not just the distance metric between a pair of strings.
I think the link that Carleton mentions is on the right track, in terms of having a rule set for defining the allowable misspellings.
I'm a little unclear how the probability measures help.
A few decades ago I wrote a rule-driven spelling corrector (in Pascal, and also in Fortran, if you can believe it).
The corpus was a character-based trie containing all the words.
In addition to being easy to search, it's easy to build-in arbitrary prefixes and suffixes by just connecting together parts of the trie into a FSM.
So for example it could recognize "nationalizational", or other words that would not really be in any dictionary but still are words - sort of.
The advantage of that is you can dramatically reduce the size of the corpus.
The algorithm was similar to branch-and-bound, but it consisted of a recursive tree walk with an error budget.
When called with an error budget of 0, it would only "print" exact matches.
When called with an error budget of 1, it would print all entries in the trie that could be gotten from the input key by applying 1 misspelling rule, such as insertion, deletion, transposition, or simple replacement of a character of group of characters by another that could "sound alike".
You can tune the rule set for the kinds of misspellings appropriate for the particular subject matter.
If no match was found with a budget of 0 or 1, then the budget was increased to 2, etc.
The performance was of course exponential in the error budget, for small budgets.
What that means is that the effort spent at budget level N only differed by a constant factor from the sum of the effort spent at lower levels of budget.
So it's OK to just call repeatedly with successively larger budgets.
For large budgets, the performance is linear in the corpus size.
I found it much easier to write the rule-based search as a recursive tree-walk than as a kind of breadth-first or branch-and-bound algorithm, because at any moment in time it only has to manage a single hypothetical misspelling.
One thing I did not do, and I should have, is to precompile both the corpus trie and the rule set into a compiled language (like C), because the corpus and rule set change very seldom.
This would have given higher speed, by a couple orders of magnitude.
