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

Groups > comp.compression > #2238 > unrolled thread

Possible flaw with my Huffman implementation...

Back to article view | Back to comp.compression

Contents

  Possible flaw with my Huffman implementation... Harry Potter <rose.joseph12@yahoo.com> - 2014-02-25 08:30 -0800
    Re: Possible flaw with my Huffman implementation... Harry Potter <rose.joseph12@yahoo.com> - 2014-03-05 07:55 -0800
      Re: Possible flaw with my Huffman implementation... Harry Potter <rose.joseph12@yahoo.com> - 2014-03-05 11:32 -0800
        Re: Possible flaw with my Huffman implementation... BGB <cr88192@hotmail.com> - 2014-03-05 19:31 -0600
          Re: Possible flaw with my Huffman implementation... Harry Potter <rose.joseph12@yahoo.com> - 2014-03-06 06:17 -0800
            Re: Possible flaw with my Huffman implementation... BGB <cr88192@hotmail.com> - 2014-03-06 20:31 -0600

#2238 — Possible flaw with my Huffman implementation...

So I have what seems to be a *better* compression technique.  The main reason for this is a technique about which nobody knows.  However, after all my optimizations and tweaks, it is still not quite as good as the Deflate technique *without* this idea.  I'm trying to figure out what I'm doing wrong.  I looked at the APPNOTE.TXT file and the article at http://en.wikipedia.org/wiki/DEFLATE#Bit_reduction, and don't quite understand how it does Huffman codes.  All I was able to figure out is that it uses a 288-character table to store a Huffman header.  I use a tree approach to define the Huffman codes and only define values used.  I use several chances to define a LZ77 block based on distance and length values.  I also use several methods to better these.  However, with just these, I can only *approach* the Deflate technique.  I am unwilling to give further details, as it is my own technique and I don't want to reveal it until it's time.  :(  Any suggestions and help would be appreciated.

[toc] | [next] | [standalone]

#2241

Found a possible problem: a less than efficient way of referencing a LZ77 block.  Now I just need to figure out a way to do Deflate's method my own way.

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

#2242

On Wednesday, March 5, 2014 10:55:45 AM UTC-5, Harry Potter wrote:
> Found a possible problem: a less than efficient way of referencing a LZ77 block.  Now I just need to figure out a way to do Deflate's method my own way.

I have an idea on how to do that.  It should usually do the offset of LZ77 with less bits than Deflate.  The problem is that the sliding dictionary's size is *not* a power of 2.  This might result in a smaller dictionary size than Deflate's 32k, causing slightly less compression ratio on larger files. 

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

#2243

On 3/5/2014 1:32 PM, Harry Potter wrote:
> On Wednesday, March 5, 2014 10:55:45 AM UTC-5, Harry Potter wrote:
>> Found a possible problem: a less than efficient way of referencing a LZ77 block.  Now I just need to figure out a way to do Deflate's method my own way.
>
> I have an idea on how to do that.  It should usually do the offset of LZ77 with less bits than Deflate.  The problem is that the sliding dictionary's size is *not* a power of 2.  This might result in a smaller dictionary size than Deflate's 32k, causing slightly less compression ratio on larger files.
>


although it depends on the data, IME the size of the sliding window 
seems to be a pretty big factor (along with how effective the match 
search algorithm is, and possibly also including logic for cases where 
the match would be counter-productive, *).

*: there may be cases where the number of bits needed to encode the 
match will exceed those needed to encode the data directly, usually 
involving short matches with long distances. my encoders (partly for 
this reason) will throw away any matches which have a distance more than 
64kB but are less than 6 bytes.


other things, such as the number of extra-bits or efficiency of the 
entropy-coding, tend to be a lesser issue IME.

though, there are a few possible tricks here (can save bits, at a slight 
speed cost):
allowing the use of a hash-table to "predict" matches, if one of these 
predictions has a match, it can be favored over the normal LZ77 style 
matches, however, this strategy is fairly expensive in that it requires 
using hash-chaining on the decoder side, and is ill-behaved in that the 
hash on both the encoder and decoder need to behave identically for the 
decoder to work.

slightly cheaper/less-problematic, is noting that distances and match 
lengths will often repeat, so it may make sense to be able to encode 
matches which reuse the same length and/or distance values as a recent 
prior match.


sometimes the encoder mostly just needs to be fast.

for example, I wrote an encoder recently which basically just does 
single-step matching using a hash-table, and basically does everything 
in a single pass, using a "lazy" strategy for updating the Huffman 
tables (where the tables are mostly built from current "running 
statistics", and the statistics are updated as the data is encoded).

mostly this is because the encoder was being used for real-time video 
encoding though (for 1680x1050 at 24 or 30 fps), and I kind of need to 
cut-corners in a lot of areas to make all this work (video recording is 
a bit performance sensitive).

though, OTOH, the LZ77+Huffman coding is still a fairly minor cost.
most of the time is going into dealing with the input pixels, where IME 
things dealing with input/output pixel data tend to dominate in terms of 
CPU time.


though, here was a test using it for desktop capture (and running around 
in Minecraft):
http://www.youtube.com/watch?v=RQUF0NEJAV4

seems almost not entirely obvious it is a VQ codec...

nevermind the high rate at which it chewed through HDD space in this 
test, the hash-function for the high-speed LZ77 encoder it turns out was 
broken at the time this test video was recorded.

there are also some visible ugly artifacts, but some work is underway to 
address them (they are more an issue with limitations imposed by 
real-time encoding than due to the format itself, *2).

*2: generally, the format uses a single color-curve for each 4x4 pixel 
block, which works better when one can afford a better algorithm to pick 
the color endpoints. for real-time encoding, it just uses the brightest 
and darkest pixels, which isn't always a good option. one option being 
worked on is supporting 2x2 pixel sub-blocks (as a special case) in the 
real-time encoder (with each 2x2 pixel sub-block having its own colors). 
special logic is used to detect which block-format is needed.


or such...

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

#2245

Thank you, BGB, for responding.  I don't know what you mean by "hash tables" but I am using a technique like the repeating of length/offset matching.  I won't discuss it here, but it helps a little.

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

#2246

On 3/6/2014 8:17 AM, Harry Potter wrote:
> Thank you, BGB, for responding.  I don't know what you mean by "hash tables" but I am using a technique like the repeating of length/offset matching.  I won't discuss it here, but it helps a little.
>

typically, one can use either preceding or following bytes to calculate 
an index into a table (this table being called a "hash table", and the 
calculation to generate the index is a "hash function").

this can be used mostly to help make the matching function faster (or, 
at least, less absurdly slow...).


for example, if the next 3 bytes are A, B, C, we could calculate a 
12-bit hash as, say:
((((A*251+B)*251+C)*251)>>8)&4095
or for 16-bits:
((((A*251+B)*251+C)*251)>>8)&65535
or also:
((((A*65521+B)*65521+C)*65521)>>16)&65535
or:
...

this will then "mix" the bits, and whatever is at these table indexes 
will have a "somewhat better than average" chance of matching these 3 bytes.


often, we might represent the sliding window as a big array, with each 
spot in the sliding window holding a reference to another spot in the 
sliding window.

then, we can have a hash-table with a hash of the next N bytes, holding 
a reference into the sliding window, which in turn may be used to walk a 
chain of locations which have the same hash.

whenever we step forwards (in the encoder), we then update the 
hash-chain, by moving the value from the hash-table entry into the 
sliding-window chain (for the current location), and moving the current 
location into this entry in the hash.

using this, it is possible to much more quickly lookup potential matches.


for faster encoding (albeit with worse compression), it is possible to 
skip doing a lookup (or building the hash chains), and just check 
directly if the hash-table entry happens to point to a match.

(my normal "moderately fast" encoding limits the match-searching to 
checking around 4 or 16 matches, mostly because deeper searching results 
in slower encoding. much deeper searches, such as 256 or 4096, may be 
used for encoding at higher compression levels though).


likewise, it may be possible to do the hashing like:
H2=(H2<<8)|C
H=((H2*65521)>>16)&65535
or:
H=((H2*251)>>8)&4095

which saves a little bit on arithmetic (C in this case being from 2 
characters forwards), but is less effective IME.

65521 and 251 in this case are prime numbers. primes (and in this case, 
"largest prime just below a given power of two") seem to have special 
properties here, and generate a very randomized value at the following 
power-of-2 bit position (except partly for Mersenne primes, which have 
slightly different behaviors, and seem to generate the most effective 
hash bits in the low-order bits, and are less effective for this 
particular use case).

I guess possible could be something like:
H=(((H<<5)+C)*31)&65535;
but, this is untested...

I am not entirely sure how this sort of arithmetic black-magic works 
exactly, but in my experience, it seems to work.


using hash tables as predictors is basically similar, except that prior 
state is used (so both the encoder and decoder can know the current 
state and hash values), leaving it mostly up to the encoder to "confirm" 
the various predictions made by the decoder. the drawback though is that 
it forces the encoder and decoder to work in lockstep (and limits how 
each may do things), as well as making the decoder slower (by it having 
to maintain a lot more context and state).


or such...

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web