Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
This is not a research-level question. Please see the faq. –  JɛffE Nov 14 '12 at 14:09
    
A bit off-topic, but for fast Levenshtein matching you might consider using Levenshtein Automata. –  Peter Nov 15 '12 at 18:22

2 Answers 2

up vote 4 down vote accepted

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).

share|improve this answer
    
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. –  Denis Bazhenov Nov 14 '12 at 22:20
    
@Denis, I think it would help if you add the motivation for the question to the post and also use application-of-theory tag. –  Kaveh Nov 15 '12 at 0:06
    
@Kaveh, I guess, you right. Thank you. –  Denis Bazhenov Nov 15 '12 at 4:24
    
"But it could be smaller than k, of course." This doesn't answer the question: Why can it be smaller than k? –  Don Larynx Mar 24 at 1:02
    
I added an example to the answer. –  Andrej Bauer Mar 24 at 12:54

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?

share|improve this answer
    
Oh, you answered your own question above. Excellent. You could also just edit my answer, it would then be easier to spot your explanation. –  Andrej Bauer Mar 24 at 12:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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