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

Groups > comp.compression > #2243

Re: Possible flaw with my Huffman implementation...

Show all headers | View raw

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

Back to comp.compression | Previous | Next — Previous in thread | Next 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