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.
Intermediate/Coding representation for Levenshtein Distance
string matching;edit distance
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.