New Algorithms and Lower Bounds for Sequential-Access Data Compression

Free registration required

Executive Summary

This paper concerns sequential-access data compression, i.e., by algorithms that read the input one or more times from beginning to end. In this paper, the authors consider adaptive pre x coding, for which they must read the input character by character, outputting each character's self-delimiting codeword before reading the next one. They show how to encode and decode each character in constant worstcase time while producing an encoding whose length is worst-case optimal. The authors also consider one-pass compression with memory bounded in terms of the alphabet size and context length, and prove a nearly tight tradeoff between the amount of memory they can use and the quality of the compression they can achieve.

  • Format: PDF
  • Size: 377.74 KB