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

Groups > comp.compression > #2075

Re: Best Huffman if Weights Known?

Show all headers | View raw

On 11/6/2013 8:12 AM, Harry Potter wrote:
> On Tuesday, November 5, 2013 9:36:37 PM UTC-5, BGB wrote:
>> Static Huffman:
>> fast encoding/decoding (masking, shifts, and tables), but largely
>> non-viable for higher order context models (beyond order-0);
>> a higher-order context-adaptive transform can be used, but kills much of
>> the speed advantage, and a Huffman table beyond order-0 tends to be too
>> large and eats any compression advantage.
>>
> I assume that order-0 means that the lowest value compressed is 0.  I was working on Static Huffman, and you're right: the table of a test text file was ~80 bytes.  Again, I developed a way to shrink the size of a value by at least one bit.  If I also alphabetize the values, I might be able to shorten some values to an offset from the previous.
>

order-0: each symbol is encoded independently, for example, if you have 
256 possible byte values, each will have a certain probability 
regardless of what precedes them.

order-1: one prior symbol is taken into account, so for 256 symbols you 
have 65536 possible probabilities (every symbols' probability is 
relative to the symbol that preceded it).

order-2: two prior symbols are taken into account, so for 256 symbols 
you have 16777216 possible probabilities.

...


>> use of multiple context-dependent tables can be used to good effect though.
>>
> I don't understand multiple context-dependent tables.  :(  Can you explain it for me please?
>

usually, the entropy coding stage will be designed for a specific data 
format.

in this case, one can use different tables for different symbol types.

for example, you could have different tables for commands vs literal 
byte values vs distance values.

or, say you are developing a format which encodes 8x8 blocks of numbers:
the DC value (item 0) might be special and encoded with its own table;
the normal AC values (items 1-63) might have their own table (or 
possibly even subdivided, noting that 1-23 may have different 
probabilities than 24-63, etc);
escape-coded cases might also be given another table (say, if you have 
smaller items which might be encoded directly in a single symbol, and 
larger items which may require multiple symbols).


>> Adaptive Huffman:
>> overly complex with lackluster speed and worse compression than
>> (Adaptive) Arithmetic or Range coding.
>>
> I have a way that can minimize the number of bits per byte in an Adaptive Huffman NYT.  However, it will only save a few bytes per file.
>
> And as for arithmetic coding, I am currently not doing it because I am working on the 8- and 16-bit versions of my codec.  I will work on 32-bit versions later.
>
> James Dow Allen:
>
> Right now, I'm doing *everything* to create the best technique, so any idea would be useful.  BTW, I'll look at Golomb run coding now.
>

looking up Golomb-run and similar, found some interesting results.

in a lot of my formats, I have often used Rice coding for things like 
tables (Huffman and Quantization), as this tends to be simpler and 
cheaper (*) than using Huffman-coded tables, and more compact than naive 
byte-based tables.


*: it kind of a waste to set up a Huffman table only to use it to decode 
a small number of items, namely, another Huffman table.

actually, for the most part (in past format), I had been using a fairly 
direct adaptation of Deflate's Huffman table design over to using Rice 
coding. could probably consider a simpler (and "more elegant") design 
(Difference+RLE+Rice, or maybe MTF+RLE+Rice).


or such...

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-05 08:24 -0800
  Re: Best Huffman if Weights Known? Willem <willem@turtle.stack.nl> - 2013-11-05 17:47 +0000
    Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-05 09:59 -0800
  Re: Best Huffman if Weights Known? Thomas Richter <thor@math.tu-berlin.de> - 2013-11-05 20:01 +0100
    Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-05 11:10 -0800
  Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-05 20:36 -0600
    Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-06 06:12 -0800
      Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-06 06:18 -0800
      Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-06 12:57 -0600
        Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-07 06:32 -0800
  Re: Best Huffman if Weights Known? James Dow Allen <gmail@jamesdowallen.nospam> - 2013-11-06 06:54 +0000
    Re: Best Huffman if Weights Known? sg <sgesemann@gmail.invalid> - 2013-11-07 10:59 +0100
      Re: Best Huffman if Weights Known? Noob <root@127.0.0.1> - 2013-11-07 12:09 +0100
        Re: Best Huffman if Weights Known? James Dow Allen <gmail@jamesdowallen.nospam> - 2013-11-08 08:46 +0000
          Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-08 17:05 -0600
      Re: Best Huffman if Weights Known? pfraser <pete_fraser@comcast.net> - 2013-11-07 13:08 -0800
  Re: Best Huffman if Weights Known? Sebastian Garth <sebastiangarth@gmail.com> - 2013-11-07 23:10 -0800
    Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-08 06:12 -0800
      Re: Best Huffman if Weights Known? Sebastian Garth <sebastiangarth@gmail.com> - 2013-11-08 08:39 -0800
        Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-08 11:27 -0800
        Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-11 11:38 -0800
        Re: Best Huffman if Weights Known? jdallen2000@yahoo.com - 2013-11-11 13:50 -0800
          Re: Best Huffman if Weights Known? Sebastian Garth <sebastiangarth@gmail.com> - 2013-11-11 15:28 -0800
            Re: Best Huffman if Weights Known? James Dow Allen <gmail@jamesdowallen.nospam> - 2013-11-12 09:40 +0000
              Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-12 06:36 -0800
                Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-12 07:28 -0800
                Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-12 08:13 -0800
                Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-13 06:17 -0800
              Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-12 13:34 -0600
    Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-08 06:36 -0800

csiph-web