# similarity/distance measurement between two ranked sequence

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.

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

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).