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. –  Petro Nov 15 '12 at 18:22
add comment

1 Answer

up vote 3 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.

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
add comment

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.