2012/11/13 by M. Oğuzhan Külekçi, M. Oguzhan Kulekci, Kulekci, M. Oguzhan · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Fractal and DNA sequence analysis #Information Theory (cs.IT) #cs.DM #cs.DS #cs.IT #math.IT #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1211.2926
arxiv created 2012/11/13 · openalex publication_date 2012/11/13 · arxiv updated 2012/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This study focuses on efficient schemes for enumerative coding of σ--ary sequences by mainly borrowing ideas from Öktem & Astola's \citeOktem99 hierarchical enumerative coding and Schalkwijk's \citeSchalkwijk72 asymptotically optimal combinatorial code on binary sequences. By observing that the number of distinct σ--dimensional vectors having an inner sum of n, where the values in each dimension are in range [0...n] is K(σ,n) = ∑i=0σ-1 n-1 \choose σ-1-i σ \choose i, we propose representing C vector via enumeration, and present necessary algorithms to perform this task. We prove log K(σ,n) requires approximately (σ-1) log (σ-1) less bits than the naive (σ-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 σ--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.