Universal compression with restricted training data and constrained latency
J. Ziv · 2002
In practice, universal data compression algorithms can benefit from a restricted length training data only, and are constrained by a given, limited decoding latency. It is demonstrated that under these constraints, fixed-to-variable schemes are essentially as effective as the more general variable-to-variable schemes. A lower-bound on the compression of any dictionary-type algorithm (such as LZ, for example) is then derived. Finally, it is demonstrated that this lower-bound is essentially achievable.