leon.bottou.org

Abstract: We present the Z-Coder, a new adaptive data compression coder for coding binary data. The Z-Coder is derived from the Golomb run-length coder, and retains most of the speed and simplicity of the earlier coder. The Z-Coder can also be thought of as a multiplication-free approximate arithmetic coder, showing the close relationship between run-length coding and arithmetic cod- ing. The Z-Coder improves upon existing arithmetic coders by its speed and its principled design. In this paper we present a derivation of the Z-Coder as well as details of the construction of its adaptive probability estimation table.

@inproceedings{bottou-howard-bengio-98,
  author = {Bottou, L'\{e}on and Howard, Paul G. and Bengio, Yoshua},
  title = {The {Z}-Coder Adaptive Binary Coder},
  booktitle = {Proceedings IEEE Data Compression Conference 1998},
  publisher = {IEEE},
  month = {April},
  address = {Snowbird},
  year = {1998},
  url = {http://leon.bottou.org/papers/bottou-howard-bengio-98},
}

• Page 3, before the pseudo-code of the Golomb coder, the variable Δ should be 1/2m instead of 1/m.

• All decoders described in the paper assume that the compressed bitstream is followed by an infinite sequence of 1.

• The DjVu code base contains a complete implementation of the Z-Coder. See files ZPCodec.h and ZPCodec.cpp. You should define the compilation symbol ZCODER in order to compile the Z-Coder instead of the ZP-Coder which is used by DjVu. The ZP-Coder is not very interesting: it was designed to appease the AT&T lawyers.