3
$\begingroup$

Is there an efficient way to measure similarity/distance between two sequences of ranked numbers/letters. The two sequences are of different length, and only have some elements in common?

For example, if I have three rank ordered numeric sequences like this:

sequence A: 1,2,3,4,5,6

sequence B: 2,3,4,5,6,7,8,9,10

sequence C: 6,3,4,2,5,8,7,10,9

Intuitively, I guess sequence A and B are more similar, since they have more numbers in common and the common numbers have same order in both sequences. Sequence A and C are less similar since they have less number in common and the common numbers have difference orders in each sequence. Damerau-Levenshtein Distance seems to be an ok option, it measures the similarity between two strings of letters, which considers insertion, deletion, substitution and adjacent transposition of letters. But I also want to consider non-adjacent transposition, i.e., more that two letters between two swapped letters. For example, in sequence C above, '2' and '6' are swapped, but they are not adjacent letters since there are '3' and '4' in between them. Damerau-Levenshtein Distance doesn't seem to take this into account.

$\endgroup$
2
  • $\begingroup$ Just to push this ... I would be very interested in an answer to that, maybe scicomp.stackexchange.com/questions/23455/… is related? $\endgroup$
    – JohnDoe
    Mar 23 '16 at 15:47
  • $\begingroup$ There are some distance metrics specifically for time series. Dynamic time warping or move split merge $\endgroup$ May 23 at 18:38
0
$\begingroup$

As a starter, I would use the cost of bringing the elements into the same order. Of course this ignores the insertion of missing elements.

A simple solution would be insertion sort:

6,3 move 3 1 ahead => cost 1.
3,6,4 move 4 1 ahead => cost 1+1.
3,4,6,2 move 2 3 ahead => cost 1+1+3.
2,3,4,6,5 move 5 1 ahead => cost 1+1+3+1.
2,3,4,5,6,8 correct => cost 1+1+3+1.
2,3,4,5,6,8,7 move 7 1 ahead => cost 1+1+3+1+1.
2,3,4,5,6,7,8,10 correct => cost 1+1+3+1+1.
2,3,4,5,6,7,8,10,9 move 9 1 ahead => cost 1+1+3+1+1+1=8.

The algorithmic complexity would be $O(n^2)$.

A more efficient way would be to precompute the desired position for each element using an associative map and computing the distance. The result will be slightly different from the above.

mapB={0: 2, 1: 3, ...}
cost( 6)=abs(4-0)=4
cost( 3)=abs(1-1)=0
cost( 4)=abs(2-2)=0
cost( 2)=abs(0-3)=3
cost( 5)=abs(3-4)=1
cost( 8)=abs(6-5)=1
cost( 7)=abs(5-6)=1
cost(10)=abs(8-7)=1
cost( 9)=abs(7-8)=1
total=12

Using an ordered map (tree), ignoring rotations, would give $O(2n\log(n))=O(n\log(n))$. Using a hash table, ignoring collisions, would give $O(2n)=O(n)$.

Now, we would have to handle the insertion of missing elements. The second algorithm, allows us to count elements present in the second sequence but not present in the first (seq2only). If we eliminate/mark elements we have encountered in the first sequence, we can easily count elements present in the first sequence but not in the second (seq1only). The penalty for those would be insertioncost*(seq2only+seq1only).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.