# How can I prove that Hamming distance is upper bound for Levenshtein distance?

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?

-
This is not a research-level question. Please see the faq. –  JɛﬀE 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

## 1 Answer

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.

-
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