Asymptotic Optimal Lossless Compression via the CSE Technique

Hidetoshi Yokoo

2011 · 17 citations · 7 references

Concepts

Abstract

A novel loss less compression algorithm known as compression by sub string enumeration (CSE) is analyzed and modified. The CSE compression algorithm is a block-based, off-line method, as is the case with enumerative codes and the block-sorting compression scheme. First, we propose an encoding model that achieves asymptotic optimality for stationary ergodic sources. The codeword length attained by the proposed model converges almost surely to the entropy rate of a source when the length of a string generated by the source tends to infinity. Then, we propose a novel decoding algorithm that requires fewer code words than the original CSE.

References

7