Kendall tau sequence distance: Extending Kendall tau from ranks to sequences

Abstract

An edit distance is a measure of the minimum cost sequence of edit operations to transform one structureinto another. Edit distance can be used as a measure of similarity as part of a pattern recognition system, withlower values of edit distance implying more similar structures. Edit distance is most commonly encounteredwithin the context of strings, where Wagner and Fischer’s string edit distance is perhaps the most well-known.However, edit distance is not limited to strings. For example, there are several edit distance measures forpermutations, including Wagner and Fischer’s string edit distance since a permutation is a special case ofa string. However, another edit distance for permutations is Kendall tau distance, which is the number ofpairwise element inversions. On permutations, Kendall tau distance is equivalent to an edit distance withadjacent swap as the edit operation. A permutation is often used to represent a total ranking over a setof elements. There exist multiple extensions of Kendall tau distance from total rankings (permutations) topartial rankings (i.e., where multiple elements may have the same rank), but none of these are suitable forcomputing distance between sequences. We set out to explore extending Kendall tau distance in a differentdirection, namely from the special case of permutations to the more general case of strings or sequences ofelements from some finite alphabet. We name our distance metric Kendall tau sequence distance, and defineit as the minimum number of adjacent swaps necessary to transform one sequence into the other. We providetwo O(n lg n) algorithms for computing it, and experimentally compare their relative performance. We alsoprovide reference implementations of both algorithms in an open source Java library.

Keywords

• edit distance
• kendall tau
• pattern recognition
• sequences
• similarity
• strings