1Compression in the Space of Permutations

In this paper, we investigate the problem of compression of data that are in the form of permutations. This problem has direct applications in the storage of rankings or ordinal data as well as in the analysis of sorting algorithms. Lossy compression of permutations constitute new information theoretic challenges because of the uniqueness of the data format. Following the classical theory of compression, we propose the rate-distortion problem for the permutation space under uniform distribution and analyze the required rate of compression R to achieve recovery-distortion D with respect to different practical and useful distortion measures, including Kendall tau distance, Spearman’s footrule, Chebyshev distance and inversion-`1 distance. Under these distortion measures, we establish equivalences of the source code designs, which follow from the near isometry of the distances. Our results are non-asymptotic. Furthermore, for all permutation spaces of interest, we provide explicit code designs that incur low encoding/decoding complexities. Apart from the uniform input distribution, we also comment on the compression of Mallows model, a popular nonuniform ranking model on the permutation space. We show that, for the Mallows model, both the entropy and the maximum distortion at zero rate are much lower than the uniform counterpart. This indicates greater compression ratio, and suggests that it would be worthwhile to solve the challenge of designing entropy-achieving compression schemes with low computational complexity for Mallows model. I