<p>Homework, I bet.</p>

<p>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 <code>abcdef</code> and <code>bcdefg</code>).</p>

CC BY-SA 3.0
2012-11-14T22:20:44.663Z
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
CC BY-SA 3.0
2012-11-15T00:06:10.603Z
@Denis, I think it would help if you add the motivation for the question to the post and also use [tag:application-of-theory] tag.
Kaveh
CC BY-SA 3.0
2015-03-24T01:02:10.873Z
"But it could be smaller than `k`, of course." This doesn't answer the question: Why can it be smaller than `k`?
Don Larynx
CC BY-SA 3.0
2015-03-24T12:54:53.487Z
I added an example to the answer.
Andrej Bauer
CC BY-SA 3.0
2012-11-14T13:12:14.427Z
2015-03-24T12:54:40.863Z
2015-03-24T12:54:40.863Z
Andrej Bauer
<p>To add on <a href="https://cstheory.stackexchange.com/a/14324/32515">Andrej</a>'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?</p>

CC BY-SA 3.0
2015-03-24T12:53:50.297Z
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
CC BY-SA 3.0
2015-03-24T01:04:28.947Z
2015-03-24T01:04:28.947Z
2017-04-13T12:32:28.167Z
Don Larynx
<p>We have a spellchecker software. And one of it crucial parts is hypothesis generator which use <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">Levenshtein distance</a> 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 <a href="http://en.wikipedia.org/wiki/Hamming_distance" rel="nofollow">Hamming distance</a> as a fast reject algorithm for candidates.</p>

<p>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?</p>

CC BY-SA 3.0
2012-11-14T14:09:24.190Z
This is not a research-level question.  Please see the [faq].
Jeffε
CC BY-SA 3.0
2012-11-15T18:22:54.677Z
A bit off-topic, but for fast Levenshtein matching you might consider using [Levenshtein Automata](http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata).
Peter
<it.information-theory><application-of-theory>
How can I prove that Hamming distance is upper bound for Levenshtein distance?
Denis Bazhenov
# How can I prove that Hamming distance is upper bound for Levenshtein distance?

(Asked by: username_0 on 2012-11-14)

We have a spellchecker software. And one of it crucial parts is hypothesis generator which use [Levenshtein distance](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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?

**Tags:** it.information-theory, application-of-theory

> **Comments:**
> **username_1**: This is not a research-level question.  Please see the [faq].  
> **username_2**: A bit off-topic, but for fast Levenshtein matching you might consider using [Levenshtein Automata](http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata).  

---

## 2 answers

### Answer by username_3 on 2012-11-14. Score: 4 | Accepted 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 (consider `abcdef` and `bcdefg`).

> **Comments:**
> **username_0**: 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.  
> **username_4**: @Denis, I think it would help if you add the motivation for the question to the post and also use [tag:application-of-theory] tag.  
> **username_5**: "But it could be smaller than `k`, of course." This doesn't answer the question: Why can it be smaller than `k`?  
> **username_3**: I added an example to the answer.  

---

### Answer by username_5 on 2015-03-24. Score: 1

To add on [Andrej](https://cstheory.stackexchange.com/a/14324/32515)'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?

> **Comments:**
> **username_3**: Oh, you answered your own question above. Excellent. You could also just edit my answer, it would then be easier to spot your explanation.  

---

