Intermediate/Coding representation for Levenshtein Distance

Question

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.

Answer 1

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 prove that $\Omega(\log n)$ approximation is required ($n$ is the length of the strings);

• Ostrovsky and Rabani 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, 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.

Answer 2

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.

Answer 3

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]

Answer 4

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.