Back to Search
Start Over
A Novel Representation for Permutations.
- Source :
-
IEEE Transactions on Information Theory . Mar2021, Vol. 67 Issue 32, p1920-1927. 8p. - Publication Year :
- 2021
-
Abstract
- In this paper, we present a variable-length binary code for permutations of degree n, where n is a power of 2. The Lehmer code and its variants provide a bijection between permutations and the indexes in lexicographic ordering. They provide compression of permutations approaching Shannon bound at the expense of structural information. The variable-length code proposed in this paper has asymptotically optimal compression capability while preserving structural information of permutations. In other words, the code encodes the way a permutation is organized, and is optimal in the sense that the ratio of average codeword length and the entropy of permutations approaches 1 as n tends to infinity. The encoding and decoding are efficient. Like the Lehmer code and other enumerative codes, it is not necessary to construct look-up tables. The code is complete and satisfies the prefix condition. Furthermore, the codeword length indicates how “well shuffled” a permutation is. Permutations with longer codewords seem more “random.” An enumeration method of the variable-length code is also given by using T. Cover’s enumerative coding scheme and Schalkwijk code. This gives a different indexing from the Lehmer code. This work can be extended to the case of arbitrary $n$ in a straightforward way. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PERMUTATIONS
*HUFFMAN codes
*BINARY codes
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 32
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 148822604
- Full Text :
- https://doi.org/10.1109/TIT.2020.3048905