I'm looking for some kind of edit distance measure between what may be called 'non-discrete symbols sequences'.
By a discrete symbol sequence I would mean something like a string, where each symbol has a fixed length and there are fixed positions for symbols. A well-known edit distance measure between strings is the Levenshtein distance.
levenshtein('abc', 'abde') = 2
However the data that I want to compare is not strings. It's what I think is called a 'range map', for example:
{
(0, 1.4): 'a',
(1.4, 3.2): 'b',
(3.2, 5): 'c'
}
So there is still a linear sequence of symbols ('a', 'b' and 'c') but the symbols are different 'sizes' (1.4, 1.8 and 1.8) and the boundaries are not in fixed positions (0, 1.4, 3.2, 5).
Now given two of these range maps I would like to get a distance measure similar to Levenshtein for strings. There are a lot of intuitions that I have about what certain differences between two range maps would mean for the distance between them, but I wonder if there is an existing measure. I thought about how to adapt Levenshtein to this data but didn't get very far.
I did come up with one slow, inaccurate possibility: cut the range up into tiny intervals, get the values of the range maps for each interval, and then use those discrete sequences to do Levenshtein. This works but it requires choosing the interval size, and the algorithm gets slower with higher accuracy (smaller intervals).
However I do believe that, taking inspiration from Python's difflib, 2.0 * M / T
converges for the above algorithm as the interval size is decreased. Is there a faster algorithm (no tiny intervals) that computes the number that this algorithm converges on?
2.0 * M / T
? What isM
? What isT
? $\endgroup$ – D.W.♦ Apr 6 '18 at 19:21