<p>If the only thing that can happen is that characters disappear, I think you only need to solve the <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow">longest common subsequence problem</a>.  (A subsequence is a generalization of a substring: there can be multiple locations in the subsequence where material was removed from the larger sequence, not just at the start and/or end.)</p>

<p>Beyond that, have you seen <a href="http://en.wikipedia.org/wiki/Levenstein_Distance#Relationship_with_other_edit_distance_metrics" rel="nofollow">this list of metrics</a>?</p>

<p>I may be misunderstanding your problem statement, but it seems to me that if you define precisely how errors can occur (deletion, transposition, etc.) and then build a suffix tree, it should be possible to have a pretty fast algorithm, after paying the memory and preprocessing cost of building the suffix tree.</p>

CC BY-SA 2.5
2010-10-20T22:06:34.623Z
Thanks for this!  You showed me some new things to consider.
Jason Kleban
CC BY-SA 2.5
2010-10-20T22:44:31.137Z
Errors could occur as inserts, deletes.  Transpositions and swaps would be nice, but are compositions of the basic inserts and deletes - in case that makes it easier to satisfy.
Jason Kleban
CC BY-SA 2.5
2010-10-20T19:39:02.230Z
2010-10-20T19:39:02.230Z
Aaron Sterling
<p>It sounds to me like your simple thing should work. Each packet contains the position and the character, e.g. </p>

<p><code>The = &lt;1, T&gt;, &lt;2, h&gt;, &lt;3, e&gt;</code> </p>

<p>Then you compare the first pair of A with the first pair of B etc. This should give you Levenshtein.</p>

CC BY-SA 2.5
2010-10-20T21:55:51.153Z
But what if an early character in the string is missing, then all of the later pairings would be off by 1, right?  If we take out 'q' in [B], then [B]'s <u, 5> != [A]'s <u, 6>, [B]'s <i, 6> != [A]'s <i, 7>
Jason Kleban
CC BY-SA 2.5
2010-10-20T21:59:19.843Z
Put another way, if I understand your suggestion correctly it is equivalent to string/sequence equality.
Jason Kleban
CC BY-SA 2.5
2010-10-21T14:06:26.280Z
@uosɐſ: the sender would know the correct order though, right? They would send <u, 6>; the receiver might get it as the fifth packet, but if they get it at all they'll know it's the sixth letter.
Xodarap
CC BY-SA 2.5
2010-10-20T21:46:29.133Z
2010-10-20T21:46:29.133Z
Xodarap
<p>There's indeed some research in this vein for the edit distance with some positive and some negative results. (I might not be understanding the question precisely, so I'll try to answer questions I know to answer.)</p>

<p>Here's one interpretation: (I1) you want to compute, for each string A a set f(A) such that, for any two strings A,B, the edit distance ed(A,B) is equal to the symmetric difference between f(A) and f(B) (in some sense the opposite of intersection of the two sets). This question has been well-studied (though by far is not solved), and is known as the question of <em>embedding edit distance into Hamming distance ($\ell_1$)</em>. In particular, achieving (I1) precisely is not possible, but is possible up to some approximation (i.e., we approximate ed(A,B) up to some factor):</p>

<ul>
<li><p><a href="http://www.wisdom.weizmann.ac.il/~robi/papers/KR-EmbedLB-SICOMP09.pdf" rel="nofollow">Krauthgamer and Rabani</a> prove that $\Omega(\log n)$ approximation is required ($n$ is the length of the strings);</p></li>
<li><p><a href="http://www.cs.ucla.edu/~rafail/PUBLIC/68.pdf" rel="nofollow">Ostrovsky and Rabani</a> prove that $2^{O(\sqrt{\log n\log\log n})}$ approximation is achievable.</p></li>
</ul>

<p>Here's a slightly more liberal interpretation: (I2) we produce some <em>sketch</em> f(A) for each string A, and we estimate the distance ed(A,B) via <em>some calculation</em> on f(A), f(B) (i.e., not necessarily by taking the symmetric difference).  The question is to have f(A) to be much shorter than the length of the original string, $n$ (otherwise, one has a trivial solution by f(A)=A). This interpretation (I2) is more general than (I1) (=easier to achieve), though we do not know of any strictly better solutions. There's some <a href="http://arxiv.org/abs/1005.4033" rel="nofollow">partial progress</a>, where the estimation of ed(A,B) is done from f(A) and B (i.e., one string, say B, is fully known).</p>

<p>There's surely more literature in this vein, but let me know first if this is anywhere close to what you meant.</p>

CC BY-SA 2.5
2010-10-21T04:14:41.673Z
Forgot to mention: if you are using edit distance for biometric information, you might want to take a look at <a href="http://arxiv.org/abs/cs.CR/0602007">this paper of Dodis, Ostrovsky, Reyzin, and Smith</a>.
Alex Andoni
CC BY-SA 2.5
2010-10-21T23:30:52.513Z
It's actually NOT for biometric information.  I find it puzzling that Fuzzy Vaults might work for biometrics, but couldn't be used for something "simpler" such as a string of text.
Jason Kleban
CC BY-SA 2.5
2010-10-21T23:31:24.573Z
Your answer is great, thanks.  Let me think about it and research ...
Jason Kleban
CC BY-SA 2.5
2010-10-25T21:27:17.913Z
Yes, your descriptions are on point - they feel right.  +50!  Out of curiosity, is my intended application of this clear through the original question and our comments?
Jason Kleban
CC BY-SA 2.5
2010-10-28T16:22:48.013Z
Hi Alex, I think the site has a bug.  I awarded you the full 50 points, but I get a message that the answer was autoselected - giving you only 25.  Sorry about that.
Jason Kleban
CC BY-SA 2.5
2010-11-03T21:14:29.527Z
@Jason: actually I'm not 100% I understand the intended application, but would certainly be curious to find out the details! As I mentioned, I wrote mostly about things I know :) (the biometric application was mentioned in some comments, that's why I thought it could interest you.)
Alex Andoni
CC BY-SA 2.5
2010-11-03T21:16:45.390Z
no problem regarding reputation of course -- it's not the most important part of the site, I hope :)
Alex Andoni
CC BY-SA 2.5
2010-10-21T04:07:13.363Z
2010-10-21T04:07:13.363Z
Alex Andoni
<p>The phrases:</p>

<blockquote>
  <p>The quick brown fox jumps over the lazy dog [A]</p>
</blockquote>

<p>and </p>

<blockquote>
  <p>The uick brown fox jumps oower the lazy dog [B]</p>
</blockquote>

<p>can be compared using Levenshtein Distance algorithm to determine similarity by calculating the minimum number of single character additions, deletions, or replacements are necessary to transform A into B.</p>

<p>I'm interested to know if there is an intermediate representation, or possibly a coding scheme for the Levenshtein Distance.  Not for use between two phrases, but just a coding applied to a single phrase such that character index does not affect comparisons.</p>

<p>In B, the 'q' is missing compared to A.  A normal string comparison would match <code>'The '</code> and then fail at <code>'uick brown fox...'</code> merely because of a single character offset.  The Levenshtein Distance could be used to compare it to the original phrase A for a more forgiving comparison, but in my case, I won't have two phrases, just one.</p>

<p>So, I'm looking for some way of unambiguously coding a sentence in <em>packets</em> of information, little atoms of truth (I'm thinking one packet per character?) that maintain a local ordering and so-on, but if some of the packets are wrong, it doesn't affect later characters.</p>

<p>Each unique phrase should map to one and only one unique encoding/intermediate representation, Sets <code>A'</code> and <code>B'</code>.  Computing the Levenshtein Distance of A and B would then be the same as computing the intersection of sets <code>A' = B'</code>.</p>

<p>Alternatively - if this problem does not have a solution (and this sure maps to a well-trodden area of research, I wouldn't be surprised), some convincing argument/proof for its unsolvability.</p>

CC BY-SA 2.5
2010-10-12T21:27:24.407Z
Maybe I'm missing something, but it seems like you want a block error-correcting code. http://en.wikipedia.org/wiki/Block_code
S Huntsman
CC BY-SA 2.5
2010-10-12T22:19:15.947Z
Certainly seems like that's in the ballpark, but I don't know how I'd apply that here.
Jason Kleban
CC BY-SA 2.5
2010-10-13T00:00:35.530Z
How about (e.g.) http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4557110
S Huntsman
CC BY-SA 2.5
2010-10-13T21:04:16.587Z
For context, I would like to apply the concept of a fuzzy vault, which is usually applied to biometric measurements, to passphrases.  Rather than a set of measurements, this would be a set of atomic truths about a string of text.
Jason Kleban
CC BY-SA 2.5
2010-10-15T21:35:24.973Z
Thinking more about this - I'm having trouble thinking how to apply the principles of error-correcting codes to solve this.  The reason is that the passphrases are arbitrary and selected by a user, not dictated.  But maybe it's applicable in some less obvious way?
Jason Kleban
CC BY-SA 2.5
2010-10-21T00:41:18.233Z
Would some other way to preprocess the strings to enable quick edit distance computation be sufficient for your needs? (I don't have any such in mind.)
Warren Schudy
CC BY-SA 2.5
2010-10-21T23:28:28.460Z
@Warren - sure, that was just a guess to help me illustrate the problem.
Jason Kleban
<string-matching><edit-distance>
Intermediate/Coding representation for Levenshtein Distance
Jason Kleban
# Intermediate/Coding representation for Levenshtein Distance

(Asked by: username_0 on 2010-10-12)

The phrases:

> The quick brown fox jumps over the lazy dog [A]

and

> The uick brown fox jumps oower the lazy dog [B]

can be compared using Levenshtein Distance algorithm to determine similarity by calculating the minimum number of single character additions, deletions, or replacements are necessary to transform A into B.

I'm interested to know if there is an intermediate representation, or possibly a coding scheme for the Levenshtein Distance. Not for use between two phrases, but just a coding applied to a single phrase such that character index does not affect comparisons.

In B, the 'q' is missing compared to A. A normal string comparison would match `'The '` and then fail at `'uick brown fox...'` merely because of a single character offset. The Levenshtein Distance could be used to compare it to the original phrase A for a more forgiving comparison, but in my case, I won't have two phrases, just one.

So, I'm looking for some way of unambiguously coding a sentence in *packets* of information, little atoms of truth (I'm thinking one packet per character?) that maintain a local ordering and so-on, but if some of the packets are wrong, it doesn't affect later characters.

Each unique phrase should map to one and only one unique encoding/intermediate representation, Sets `A'` and `B'`. Computing the Levenshtein Distance of A and B would then be the same as computing the intersection of sets `A' = B'`.

Alternatively - if this problem does not have a solution (and this sure maps to a well-trodden area of research, I wouldn't be surprised), some convincing argument/proof for its unsolvability.

**Tags:** string-matching, edit-distance
> **Comments:**
> **username_1**: Maybe I'm missing something, but it seems like you want a block error-correcting code. http://en.wikipedia.org/wiki/Block_code  
> **username_0**: Certainly seems like that's in the ballpark, but I don't know how I'd apply that here.  
> **username_1**: How about (e.g.) http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4557110  
> **username_0**: For context, I would like to apply the concept of a fuzzy vault, which is usually applied to biometric measurements, to passphrases.  Rather than a set of measurements, this would be a set of atomic truths about a string of text.  
> **username_0**: Thinking more about this - I'm having trouble thinking how to apply the principles of error-correcting codes to solve this.  The reason is that the passphrases are arbitrary and selected by a user, not dictated.  But maybe it's applicable in some less obvious way?  
> **username_2**: Would some other way to preprocess the strings to enable quick edit distance computation be sufficient for your needs? (I don't have any such in mind.)  
> **username_0**: @Warren - sure, that was just a guess to help me illustrate the problem.  

---

## 3 answers

### Answer by username_5 on 2010-10-21. Score: 14 | Accepted answer

There's indeed some research in this vein for the edit distance with some positive and some negative results. (I might not be understanding the question precisely, so I'll try to answer questions I know to answer.)

Here's one interpretation: (I1) you want to compute, for each string A a set f(A) such that, for any two strings A,B, the edit distance ed(A,B) is equal to the symmetric difference between f(A) and f(B) (in some sense the opposite of intersection of the two sets). This question has been well-studied (though by far is not solved), and is known as the question of *embedding edit distance into Hamming distance ($\ell\_1$)*. In particular, achieving (I1) precisely is not possible, but is possible up to some approximation (i.e., we approximate ed(A,B) up to some factor):

* [Krauthgamer and Rabani](http://www.wisdom.weizmann.ac.il/~robi/papers/KR-EmbedLB-SICOMP09.pdf) prove that $\Omega(\log n)$ approximation is required ($n$ is the length of the strings);
* [Ostrovsky and Rabani](http://www.cs.ucla.edu/~rafail/PUBLIC/68.pdf) prove that $2^{O(\sqrt{\log n\log\log n})}$ approximation is achievable.

Here's a slightly more liberal interpretation: (I2) we produce some *sketch* f(A) for each string A, and we estimate the distance ed(A,B) via *some calculation* on f(A), f(B) (i.e., not necessarily by taking the symmetric difference). The question is to have f(A) to be much shorter than the length of the original string, $n$ (otherwise, one has a trivial solution by f(A)=A). This interpretation (I2) is more general than (I1) (=easier to achieve), though we do not know of any strictly better solutions. There's some [partial progress](http://arxiv.org/abs/1005.4033), where the estimation of ed(A,B) is done from f(A) and B (i.e., one string, say B, is fully known).

There's surely more literature in this vein, but let me know first if this is anywhere close to what you meant.

> **Comments:**
> **username_5**: Forgot to mention: if you are using edit distance for biometric information, you might want to take a look at <a href="http://arxiv.org/abs/cs.CR/0602007">this paper of Dodis, Ostrovsky, Reyzin, and Smith</a>.  
> **username_0**: It's actually NOT for biometric information.  I find it puzzling that Fuzzy Vaults might work for biometrics, but couldn't be used for something "simpler" such as a string of text.  
> **username_0**: Your answer is great, thanks.  Let me think about it and research ...  
> **username_0**: Yes, your descriptions are on point - they feel right.  +50!  Out of curiosity, is my intended application of this clear through the original question and our comments?  
> **username_0**: Hi Alex, I think the site has a bug.  I awarded you the full 50 points, but I get a message that the answer was autoselected - giving you only 25.  Sorry about that.  
> **username_5**: @Jason: actually I'm not 100% I understand the intended application, but would certainly be curious to find out the details! As I mentioned, I wrote mostly about things I know :) (the biometric application was mentioned in some comments, that's why I thought it could interest you.)  
> **username_5**: no problem regarding reputation of course -- it's not the most important part of the site, I hope :)  

---

### Answer by username_3 on 2010-10-20. Score: 5

If the only thing that can happen is that characters disappear, I think you only need to solve the [longest common subsequence problem](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem). (A subsequence is a generalization of a substring: there can be multiple locations in the subsequence where material was removed from the larger sequence, not just at the start and/or end.)

Beyond that, have you seen [this list of metrics](http://en.wikipedia.org/wiki/Levenstein_Distance#Relationship_with_other_edit_distance_metrics)?

I may be misunderstanding your problem statement, but it seems to me that if you define precisely how errors can occur (deletion, transposition, etc.) and then build a suffix tree, it should be possible to have a pretty fast algorithm, after paying the memory and preprocessing cost of building the suffix tree.

> **Comments:**
> **username_0**: Thanks for this!  You showed me some new things to consider.  
> **username_0**: Errors could occur as inserts, deletes.  Transpositions and swaps would be nice, but are compositions of the basic inserts and deletes - in case that makes it easier to satisfy.  

---

### Answer by username_4 on 2010-10-20. Score: 0

It sounds to me like your simple thing should work. Each packet contains the position and the character, e.g.

`The = <1, T>, <2, h>, <3, e>`

Then you compare the first pair of A with the first pair of B etc. This should give you Levenshtein.

> **Comments:**
> **username_0**: But what if an early character in the string is missing, then all of the later pairings would be off by 1, right?  If we take out 'q' in [B], then [B]'s <u, 5> != [A]'s <u, 6>, [B]'s <i, 6> != [A]'s <i, 7>  
> **username_0**: Put another way, if I understand your suggestion correctly it is equivalent to string/sequence equality.  
> **username_4**: @uosɐſ: the sender would know the correct order though, right? They would send <u, 6>; the receiver might get it as the fifth packet, but if they get it at all they'll know it's the sixth letter.  

---

