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

Groups > comp.compression > #2247

Re: Truffman coding

Show all headers | View raw

On 3/5/2014 10:40 PM, James Dow Allen wrote:
> Pursuing a recent discussion here, I developed a new static-probability
> coding method I call "Truffman Coding."  It may seem obvious and
> uninteresting but AFAIK I've never seen such a variant published.  (I think
> 20th-century quasi-arithmetic codes mostly handle only binary decisions.)
>
> I've described the invention at
>     http://fabpedigree.com/james/truffman.htm#sect2
> (I've pointed this URL at section 2, which may be the only section of that
> long-winded description worth reading.)
>
> This code is similar to Huffman coding except that trits are sometimes
> developed and used for probabilities not well approximated by a power of
> 1/2.  Huffman codes have an inherent waste of, typically, almost 0.03 bits
> per token compared with the Shannon limit.  With Truffman coding the
> inefficiency can be reduced to about 0.01 bits per token.
>
> For various reasons, this new code may have no real practical value
> whatsoever.  Nevertheless, it may be interesting enough for a conference
> paper, or suggest a related method that would be useful.  Any interest?
>

looking.

yeah, I suspect (from the description) that it would likely be a bit 
slower than normal Huffman, and likely also slower and less efficient 
than feeding Huffman-coded bits through a bitwise arithmetic coder.


though, OTOH, (regarding the Huffman+AC case) if anyone can figure a 
good way to either avoid the nearly 2x slowdown, or give compression 
improvements significantly over 5-10%, that would be good (a 2x slowdown 
for 5% isn't so good, but, say an under 25% slowdown or 15% or more 
compression improvement would be better).

I guess this implies that AC saves around 0.05-0.10 bits per bit in my 
usual test-cases. but, the arithmetic coder seems to save closer to 0.15 
bits-per-bit when I feed JPEG images though it, but I suspect this may 
be more due to weaknesses in the VLC scheme used by JPEG (*).

though, I never did get around though to implementing a branch-free 
arithmetic coder though.


*: you still need 1 or 2 extra-bits per nonzero coefficient, whereas, 
for example, if the coefficients are coded more Deflate-like, then small 
nonzero coefficients don't need extra-bits (and the number of extra bits 
is reduced). however, this comes at a slight cost of needing more bits 
to encode longer runs of zero coefficients.


JPEG uses what could be called Z4V4:
Z=0..15 preceding zeroes;
V=-32768..32767, encoded as the number of bits (0-15), followed by the 
bits (which are then sign-extended).

whereas, another option is a Z3V5 scheme:
Z=zeroes;
   0    0
   1    1
   2    2
   3    3
   4+2  4..7
   5+3  8..15
   6+4  16..31
V=-32768..32767 (via sign-folding)
   0..3 0..3
   4/5  4..7
   6/7  8..15
   8/9  16..31
   ...
Z=7 has generally been used as an escape-case (to allow for commands and 
large coefficients).

in my tests, Z3V5 variants have tended to compress better than Z4V4 
variants (other things being equal, like using the same type of 
block-transform and colorspace).


more subtly, the VLC scheme used by JPEG also wastes around 1 bit per 
coefficient implicitly by allowing for encoding overlong coefficients.

example:
0(+0): 0
1(+1): 0, -1
2(+2): 0, 1, -2, -1
3(+3): 0, 1, 2, 3, -4, -3, -2, -1

so, for each number of bits, effectively half the value-space can be 
coded via a shorter code.

if we eliminated this waste bit:
0(+0): 0
1(+0): -1
2(+1): 1, -2
3(+2): 2, 3, -4, -3 (or: 2, -3, 3, -4)

or:
   0/1  0/1
   2    2/3
   3    4..7
   4    8..15

or, essentially, a steeper version of the stepping used by Z3V5.

also, IME, around several-hundred bytes can be shaved off the size of an 
image by using an entropy-encoded encoding for the headers and tables as 
well, ...

nevermind things like DCT vs WHT or YCbCr vs YCoCg (DCT and YCbCr 
compress better, but WHT and YCoCg allow for lossless compression, ...).


> James Dow Allen
>

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

Thread

Truffman coding James Dow Allen <gmail@jamesdowallen.nospam> - 2014-03-06 04:40 +0000
  Re: Truffman coding BGB <cr88192@hotmail.com> - 2014-03-07 00:34 -0600
  Re: Truffman coding Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2014-03-09 16:56 +0200

csiph-web