2
$\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$

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.