-1
$\begingroup$

We have a spellchecker software. And one of it crucial parts is hypothesis generator which use Levenshtein distance as a measure of distance between words. The problem with Levenshtein distance is that it's not so easy to calculate (from application performance point of view), so we are came up with an idea to use Hamming distance as a fast reject algorithm for candidates.

So I interested in formal proof of the following statement: suppose you have two strings of equal length. Is it right that Levenshtein distance between them is no more that Hamming distance?

$\endgroup$
  • 4
    $\begingroup$ This is not a research-level question. Please see the faq. $\endgroup$ – Jeffε Nov 14 '12 at 14:09
  • $\begingroup$ A bit off-topic, but for fast Levenshtein matching you might consider using Levenshtein Automata. $\endgroup$ – Peter Nov 15 '12 at 18:22
4
$\begingroup$

Homework, I bet.

Suppose $a$ and $b$ are strings of equal length with Hamming distance $k$. This means the strings differ in $k$ places, say $a_{i_1} \neq b_{i_1}$, ..., $a_{i_k} \neq b_{i_k}$. It takes $k$ edits to change $a$ into $b$, namely replacement of the characters $a_{i_1}, \ldots, a_{i_k}$ by the corresponding $b_{i_1}, \ldots, b_{i_k}$. Therefore the Levenshtein distance between $a$ and $b$ is no more than $k$. But it could be smaller than $k$, of course (consider abcdef and bcdefg).

$\endgroup$
  • $\begingroup$ In fact, no. It's not a homework. We are using Hamming distance as a fast reject algorithm when searching spellchecking candidates in our search system. And I'm intrested in formal proof of this aspect of a Hamming distance. $\endgroup$ – Denis Bazhenov Nov 14 '12 at 22:20
  • $\begingroup$ @Denis, I think it would help if you add the motivation for the question to the post and also use application-of-theory tag. $\endgroup$ – Kaveh Nov 15 '12 at 0:06
  • $\begingroup$ "But it could be smaller than k, of course." This doesn't answer the question: Why can it be smaller than k? $\endgroup$ – Don Larynx Mar 24 '15 at 1:02
  • $\begingroup$ I added an example to the answer. $\endgroup$ – Andrej Bauer Mar 24 '15 at 12:54
1
$\begingroup$

To add on Andrej's answer, consider two strings "1234567890" and "0123456789". Attempt to convert one into the other. One takes 2 operations (namely, insert and delete) and the other takes 10 (substitution only). Can you figure out which is which?

$\endgroup$
  • $\begingroup$ Oh, you answered your own question above. Excellent. You could also just edit my answer, it would then be easier to spot your explanation. $\endgroup$ – Andrej Bauer Mar 24 '15 at 12:53

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.