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.


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.