Algorithms for edit distance give a measure of the distance between two strings.

Question: which of these measures would be most relevant to detect two different persons names which are actually the same? (different because of a mispelling). The trick is that it should minimize false positives. Example:

Obaama Obama => should probably be merged

Obama Ibama => should not be merged.

This is just an oversimple example. Are their computer scientists out there who worked out this issue in more detail?

  • 2
    $\begingroup$ This sort of recognition is used by search engines, and the choice of edit distance is a minor factor in this. I think Levenshtein/Damerau-Levenshtein are the basic standards in the field, and most of the tricks come from having a good corpus of names to measure distance from. $\endgroup$ – Aron Ahmadia Aug 12 '12 at 10:25

I recommend looking into this,


With the correct training data, you can likely taylor the solution to just formal names.

  • $\begingroup$ Also, if you prefer a video based introduction to a probabilistic spelling corrector you can see one here $\endgroup$ – Carleton Aug 13 '12 at 12:52

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.