compression as close to entropy as possible?

Giganews Newsgroups
Subject: compression as close to entropy as possible?
Posted by:  Joey Dewille (joey19…@fastmail.co.uk)
Date: Tue, 6 Jul 2004

Hello group,

Is there an algorithm that satisfies these requirements:

1) it operates on the whole file, unlike other algorithms that partition a large file into buffers,
    compress them individually and concatanate the results.
2) there exists a constant  K :- 1 <= K < 1+C such that the compression ratio R achieved
    by the algorithm satisfies:  R < K * E / uncompressed_filesize, where E is the
  entropy of the file and C  is as small as possible (e.g. C < 0.2)
3) can be implemented in a programming language such as C

In other words the compression ratio approaches the entropy and is provably
only slightly higher at best.

Replies