Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2162 > unrolled thread

Finite State Entropy

Back to article view | Back to comp.compression

Contents

  Finite State Entropy yann.collet.73@gmail.com - 2013-12-17 01:53 -0800
    Re: Finite State Entropy sg <sgesemann@gmail.invalid> - 2013-12-22 15:38 +0100
      Re: Finite State Entropy Jarek Duda <dudaj@interia.pl> - 2013-12-22 14:18 -0800
      Re: Finite State Entropy earl_colby_pottinger@yahoo.com - 2013-12-22 14:22 -0800
        Re: Finite State Entropy Jarek Duda <dudaj@interia.pl> - 2013-12-22 14:29 -0800
          Re: Finite State Entropy earl_colby_pottinger@yahoo.com - 2013-12-23 07:12 -0800

#2162 — Finite State Entropy

A new method to perform Entropy compression,
featuring the speed of Huffman, and the accuracy of Arithmetic :

http://fastcompression.blogspot.fr/2013/12/finite-state-entropy-new-breed-of.html

[toc] | [next] | [standalone]

#2173

Am 17.12.2013 10:53, schrieb yann.collet.73@gmail.com:
> A new method to perform Entropy compression,
> featuring the speed of Huffman, and the accuracy of Arithmetic :
> 
> http://fastcompression.blogspot.fr/2013/12/finite-state-entropy-new-breed-of.html

Consider adding a concise abstract of what this article is about and how
your idea compares to well-established state-of-the-art. The only thing
to that effect I found so far was

  "In a nutshell, this coder provides the same level of
   performance as Arithmetic coder, but only requires additions,
   masks, and shifts."

But this is actually not unique to your implementation. There are
already more than one table-driven (multiplierless) arithmetic coders
out there that are already used in current standards like JBIG,
JPEG2000, and H264.

Cheers!
sg

[toc] | [prev] | [next] | [standalone]

#2175

sg, indeed there is so called quasi arithmetic coding, but it rather operates on binary alphabet. ANS allows to operate on any alphabet size - Yann's implementation uses 256 size alphabet, so in place of 8 binary choices of (quasi) arithmetic coding, there is now only a single table use - leading to faster codding than Huffman, with rates like arithmetic.

So it basically makes Huffman obsolete. It rather requires constant probabilities (within a block), so for bitwise adaptive ultracompressors we should rather use arithmetic coding (but this approach also provides alternative for that: ABS).
Here is a poster gathering basic information: https://dl.dropboxusercontent.com/u/12405967/poster.pdf
And more developed discussion: http://encode.ru/threads/1845-Finite-State-Entropy
Cheers,
Jarek

[toc] | [prev] | [next] | [standalone]

#2176

Checkout:
http://encode.ru/threads/1845-Finite-State-Entropy

http://arxiv.org/abs/0902.0271

[toc] | [prev] | [next] | [standalone]

#2177

This version is much better: http://arxiv.org/abs/1311.2540

[toc] | [prev] | [next] | [standalone]

#2178

On Sunday, 22 December 2013 17:29:22 UTC-5, Jarek Duda  wrote:
> This version is much better: http://arxiv.org/abs/1311.2540

Thank you.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web