An Algorithm for Entropy Coding: Combinatorial Coding

Entropy coding (esp. order-OJ was one of the first techniques for lossless data compression, dating back to the invention of modern information theory. Over such a long period of time different schemes were invented and entropy coding has experienced various improvements: Huffman published his minimal tree structured codes and than Witten, Neal and Cleary presented a scheme leading to even better results. While entropy compression is still used in todays data compression schemes it has not lost its significance. This paper presents an encoding and its corresponding decoding algorithm not using trees or intervals to do entropy compression. Instead it derives permutations from the input which are mapped to natural numbers. Furthermore this paper includes mathematical details and gives an impression about the compression performance.