# Intermediate/Coding representation for Levenshtein Distance

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.

• Maybe I'm missing something, but it seems like you want a block error-correcting code. en.wikipedia.org/wiki/Block_code – S Huntsman Oct 12 '10 at 21:27
• Certainly seems like that's in the ballpark, but I don't know how I'd apply that here. – Jason Kleban Oct 12 '10 at 22:19
• How about (e.g.) ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4557110 – S Huntsman Oct 13 '10 at 0:00
• 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 Oct 13 '10 at 21:04
• 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 Oct 15 '10 at 21:35

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

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

• Forgot to mention: if you are using edit distance for biometric information, you might want to take a look at <a href="arxiv.org/abs/cs.CR/0602007">this paper of Dodis, Ostrovsky, Reyzin, and Smith</a>. – Alex Andoni Oct 21 '10 at 4:14
• 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 Oct 21 '10 at 23:30
• Your answer is great, thanks. Let me think about it and research ... – Jason Kleban Oct 21 '10 at 23:31
• 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 Oct 25 '10 at 21:27
• 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 Oct 28 '10 at 16:22

If the only thing that can happen is that characters disappear, I think you only need to solve the 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?

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.

• Thanks for this! You showed me some new things to consider. – Jason Kleban Oct 20 '10 at 22:06
• 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 Oct 20 '10 at 22:44

This is just a thought, not a solution, but too long for a comment.

Could your set/representation be an alphabetic building of the string?
Example (for A):


1. Start with the empty string (^$) 2. Insert a between 1st ^ and 1st$ (now: ^a$) 3. Insert b between 1st ^ and 1st a (now: ^ba$)
4. Insert c between 1st ^ and 1st b (now: ^cba$) 5. Insert d between 1st b and 1st a (now: ^cbda$)
6. Insert d between 1st a and 1st ^ (now: ^cbdad$)  and so on... Your representation would be the steps you took to build the string (in alphabetic order): The element {a, {1,^}, {1,$}} represents step 2, while {d, {1,b}, {1,a}} represents the 5th step.

Provided you do this alphabetically in each case, you might have something you can use.

A complementary thought: start with enough copies of each letter "abcdd" (for the first 4) and then keep track of your transpositions to build the string. We're now moving vaguely into permutation theory.

[BTW, it's "jumps", not "jumped", otherwise there's no 's' -- yes, I realize you never said it was a pangram]

• First of all, interesting idea. ... And thanks for the 'Jumps' correction - I changed the post accordingly. – Jason Kleban Oct 20 '10 at 21:45
• I think a solution couldn't have a "5th step". Order can't matter - the packets can't be strongly linked to each other in ordering or reference - what if one packet is wrong/missing? – Jason Kleban Oct 20 '10 at 22:46

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.

• 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 Oct 20 '10 at 21:55
• Put another way, if I understand your suggestion correctly it is equivalent to string/sequence equality. – Jason Kleban Oct 20 '10 at 21:59
• @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 Oct 21 '10 at 14:06
• The idea is that you come up with a set T(s) for each string s, and then just compare T(s1) and T(s2) as sets to find T(s1)-T(s2) for example, and the number of elements in that difference is the distance. There is no "sender" and "receiver" – user1854 Oct 21 '10 at 17:42