Enumeration of sequences with large alphabets

Abstract

This study focuses on efficient schemes for enumerative coding of $\sigma$--ary sequences by mainly borrowing ideas from Öktem & Astola's \cite{Oktem99} hierarchical enumerative coding and Schalkwijk's \cite{Schalkwijk72} asymptotically optimal combinatorial code on binary sequences. By observing that the number of distinct $\sigma$--dimensional vectors having an inner sum of $n$, where the values in each dimension are in range $[\mathrm{0...}n]$ is $K(\sigma ,n)={\sum }_{i=0}^{\sigma -1}\left(\genfrac{}{}{0ex}{}{n-1}{\sigma -1-i}\right)\left(\genfrac{}{}{0ex}{}{\sigma }{i}\right)$, we propose representing $C$ vector via enumeration, and present necessary algorithms to perform this task. We prove $\log K(\sigma ,n)$ requires approximately $(\sigma -1)\log (\sigma -1)$ less bits than the naive $(\sigma -1)\lceil \log (n+1)\rceil$ representation for relatively large $n$, and examine the results for varying alphabet sizes experimentally. We extend the basic scheme for the enumerative coding of $\sigma$--ary sequences by introducing a new method for large alphabets. We experimentally show that the newly introduced technique is superior to the basic scheme by providing experiments on DNA sequences.

Cited by in corpus (1)

• Enumerative Data Compression with Non-Uniquely Decodable Codes