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

Groups > comp.compression > #2246

Re: Possible flaw with my Huffman implementation...

Show all headers | View raw

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...

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

Thread

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

csiph-web