2017/03/23 by Abubakar Siddique, Siddique, Abu Bakar
Computer Science · #Advanced Data Compression Techniques #Algorithms and Data Compression #Cellular Automata and Applications #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1703.08127
openalex publication_date 2017/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper proposes a novel entropy encoding technique for lossless data compression. Representing a message string by its lexicographic index in the permutations of its symbols results in a compressed version matching Shannon entropy of the message. Commercial data compression standards make use of Huffman or arithmetic coding at some stage of the compression process. In the proposed method, like arithmetic coding entire string is mapped to an integer but is not based on fractional numbers. Unlike both arithmetic and Huffman coding no prior entropy model of the source is required. Simple intuitive algorithm based on multinomial coefficients is developed for entropy encoding that adoptively uses low number of bits for more frequent symbols. Correctness of the algorithm is demonstrated by an example.