GNU bug report logs - #16471
New entropy coding: faster than Huffman, compression rate like arithmetic

Previous Next

To reply to this bug, email your comments to 16471 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jarosław Duda <dudaj <at> purdue.edu>
To: bug-gzip <at> gnu.org
Subject: New entropy coding: faster than Huffman,
 compression rate like arithmetic
Date: Thu, 16 Jan 2014 18:47:36 -0500

Hallo,

Since I haven't found gzip development mailing list, I am sending it here.
There is a new approach to entropy coding: asymmetric numeral systems. 
It has some connection with arithmetic coding, but is simpler: uses a 
single natural number as the state, instead of two to represent the 
range. Thanks of it, we can put the entire behavior for given large 
alphabet probability distribution into a relatively small table: a few 
kilobytes for 256 size alphabet.
This way it turns out about 50% faster than Huffman decoding, still 
providing accuracy (compression rate) like arithmetic coding.

Here is some implementation: https://github.com/Cyan4973/FiniteStateEntropy
Just replacing Huffman with it, we get improvement of both speed and 
compression rate, like recently in Zhuff of Yann Collet: 
http://fastcompression.blogspot.fr/2013/12/zhuff-v09-or-first-fse-application.html
I thought it could also improve gzip DEFLATE in the same way?

Best,
Jarek

-- dr Jarosław Duda
Center for Science of Information, Purdue University, USA
http://www.soihub.org/people.php?id=484

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.