[theora-dev] What sort of math i required?

David Kuehling dvdkhlng at gmx.de
Thu Dec 11 07:45:42 PST 2003



>>>>> "Christoph" == Christoph Lampert <chl at math.uni-bonn.de> writes:

> On Thu, 11 Dec 2003, Mike Melanson wrote:
>> On Thu, 11 Dec 2003, Martin Jeppesen wrote:
>> 
>> > Why are people still using Huffman? Haven't there come better
>> algorithms > since?
>> 
>> Hey, if it works...but there are some alternatives. Most notably,
>> there is something called arithmetic coding which offers better
>> compression than Huffman. There is placeholder support for it in the
>> JPEG spec and probably other specs. The big problem with using it is
>> that someone has a patent on it and has not been shy about enforcing
>> it. Oh, and arithmetic coding is also really, really slow, on both
>> sides (coding and decoding).

All the alternatives mentioned so far are entropy coders.  Why hasn't
anybody used something like the deflation scheme used by GZip and pkzip?
Or even better something like burrows-wheeler transform (bzip2).  For
software-players that are supposed to run on PC hardware, buffering some
data shouldn't be a problem.  Currently famous MPEG4-implementations
(DivX etc.) use 10-second spaced key frames.  That result in about 1Mb
blocks that could be block-compressed without interfering with seeking.

I just can't imagine that the kind of data produced by Theora and other
video codecs is "immune" against more evolved compression schemes.  From
my experience dictionary-based lossless codecs are very much better than
huffman, quite much independent from the data being compressed.

Here is one staticstic that I could just dig up (for a self-made
deflation codec that is somewhat less efficient than gzip):
                        
                  huffman               deflation
                  ratio(%)              ratio(%)

text file         -38%                   -65%
(47K)

68K binary        -20%                   -35%
(13K)

3-plane grayscale -41%                   -45%
picture (11K)

David

-- 
GnuPG public key: http://user.cs.tu-berlin.de/~dvdkhlng/dk.gpg
Fingerprint: B17A DC95 D293 657B 4205  D016 7DEF 5323 C174 7D40

--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'theora-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.




More information about the Theora-dev mailing list