|Subject:||compression as close to entropy as possible?|
|Posted by:||Joey Dewille (joey19…@fastmail.co.uk)|
|Date:||Tue, 6 Jul 2004|
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.