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.