Enumerative source encoding

This work provides an explicit scheme for calculating the index of any sequence in S according to its position in the lexicographic ordering of S, thus resulting in a data compression of (log\midS\mid)/n.

Abstract

Let S be a given subset of binary n-sequences. We provide an explicit scheme for calculating the index of any sequence in S according to its position in the lexicographic ordering of S . A simple inverse algorithm is also given. Particularly nice formulas arise when S is the set of all n -sequences of weight k and also when S is the set of all sequences having a given empirical Markov property. Schalkwijk and Lynch have investigated the former case. The envisioned use of this indexing scheme is to transmit or store the index rather than the sequence, thus resulting in a data compression of (\log\midS\mid)/n .