Optimal coding of infinite streams of data
Kevin Atteson · 2002
Huffman coding minimizes the expected coding length for data generated by a known distribution on a finite set. In practice, a stream of data having no known end is often encountered as, for example, over a transmission line, making the total amount of data infinite or large enough to make Huffman coding impractical. In this paper, we present a mathematical formalism for such infinite or repeated coding and demonstrate that pure arithmetic coding produces the minimal cumulative (not per-symbol) expected coding length which is equal to the entropy (not the entropy rate) for all finite data lengths.