1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ There's earthmover distance, which can give you some ideas. $\endgroup$ – Yuval Filmus Apr 6 '18 at 18:27
  • $\begingroup$ What is 2.0 * M / T? What is M? What is T? $\endgroup$ – D.W. Apr 6 '18 at 19:21
  • $\begingroup$ @D.W. it's in the link I gave: "T is the total number of elements in both sequences, and M is the number of matches" $\endgroup$ – Marein Apr 6 '18 at 21:01
  • $\begingroup$ Please edit the question to incorporate that information in the question, so the question is self-contained. Readers shouldn't need to click on external links to understand what you are asking. (Also, if that link stops working, the question will become incomprehensible.) $\endgroup$ – D.W. Apr 6 '18 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.