Adaptive Weighing of Context Models for Lossless Data Compression

Free registration required

Executive Summary

Until recently the state of the art in lossless data compression was prediction by partial match (PPM). A PPM model estimates the next-symbol probability distribution by combining statistics from the longest matching contiguous contexts in which each symbol value is found. The paper introduces a context mixing model which improves on PPM by allowing contexts which are arbitrary functions of the history. Each model independently estimates a probability and confidence that the next bit of data will be 0 or 1. Predictions are combined by weighted averaging. After a bit is arithmetic coded, the weights are adjusted along the cost gradient in weight space to favor the most accurate models.

  • Format: PDF
  • Size: 83.1 KB