The Z-Coder Adaptive Binary Coder

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.

Léon Bottou, Paul G. Howard and Yoshua Bengio: The Z-Coder Adaptive Binary Coder, Proceedings IEEE Data Compression Conference 1998, IEEE, Snowbird, April 1998.

dcc-zcoder-1998.djvu dcc-zcoder-1998.pdf dcc-zcoder-1998.ps.gz

@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},
}

Erratum and Precisions

  • 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.
papers/bottou-howard-bengio-98.txt · Last modified: 2007/12/12 16:55 by leonb
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0