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

Groups > comp.compression > #2244 > unrolled thread

Truffman coding

Back to article view | Back to comp.compression

Contents

  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

#2244 — Truffman coding

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?

James Dow Allen

[toc] | [next] | [standalone]

#2247

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
>

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

#2248

James Dow Allen <gmail@jamesdowallen.nospam> writes:
> 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?

Not read it closely, but it seems as if there are some ?Tunstall-related
ideas in your Truffmann.

Phil
-- 
Religion is too important a matter to its devotees to be a subject of 
ridicule. If they indulge in absurdities, they are to be pitied rather
than ridiculed. -- Immanuel Kant (1724-1804), lecture at Konigsberg, 1775

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web