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

Groups > comp.compression > #2066 > unrolled thread

Best Huffman if Weights Known?

Back to article view | Back to comp.compression

Contents

  Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-05 08:24 -0800
    Re: Best Huffman if Weights Known? Willem <willem@turtle.stack.nl> - 2013-11-05 17:47 +0000
      Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-05 09:59 -0800
    Re: Best Huffman if Weights Known? Thomas Richter <thor@math.tu-berlin.de> - 2013-11-05 20:01 +0100
      Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-05 11:10 -0800
    Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-05 20:36 -0600
      Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-06 06:12 -0800
        Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-06 06:18 -0800
        Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-06 12:57 -0600
          Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-07 06:32 -0800
    Re: Best Huffman if Weights Known? James Dow Allen <gmail@jamesdowallen.nospam> - 2013-11-06 06:54 +0000
      Re: Best Huffman if Weights Known? sg <sgesemann@gmail.invalid> - 2013-11-07 10:59 +0100
        Re: Best Huffman if Weights Known? Noob <root@127.0.0.1> - 2013-11-07 12:09 +0100
          Re: Best Huffman if Weights Known? James Dow Allen <gmail@jamesdowallen.nospam> - 2013-11-08 08:46 +0000
            Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-08 17:05 -0600
        Re: Best Huffman if Weights Known? pfraser <pete_fraser@comcast.net> - 2013-11-07 13:08 -0800
    Re: Best Huffman if Weights Known? Sebastian Garth <sebastiangarth@gmail.com> - 2013-11-07 23:10 -0800
      Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-08 06:12 -0800
        Re: Best Huffman if Weights Known? Sebastian Garth <sebastiangarth@gmail.com> - 2013-11-08 08:39 -0800
          Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-08 11:27 -0800
          Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-11 11:38 -0800
          Re: Best Huffman if Weights Known? jdallen2000@yahoo.com - 2013-11-11 13:50 -0800
            Re: Best Huffman if Weights Known? Sebastian Garth <sebastiangarth@gmail.com> - 2013-11-11 15:28 -0800
              Re: Best Huffman if Weights Known? James Dow Allen <gmail@jamesdowallen.nospam> - 2013-11-12 09:40 +0000
                Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-12 06:36 -0800
                  Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-12 07:28 -0800
                    Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-12 08:13 -0800
                      Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-13 06:17 -0800
                Re: Best Huffman if Weights Known? BGB <cr88192@hotmail.com> - 2013-11-12 13:34 -0600
      Re: Best Huffman if Weights Known? Harry Potter <rose.joseph12@yahoo.com> - 2013-11-08 06:36 -0800

Page 1 of 2  [1] 2  Next page →

#2066 — Best Huffman if Weights Known?

My compression technique-to-be pre-scans a file for information used by other ideas, and I'm wondering: in this condition, which produces better results, regular Huffman or Adaptive Huffman?  Or is another variant better?

[toc] | [next] | [standalone]

#2067

Harry Potter wrote:
) My compression technique-to-be pre-scans a file for information used by
) other ideas, and I'm wondering: in this condition, which produces better
) results, regular Huffman or Adaptive Huffman?  Or is another variant
) better?

That depends on how variable the symbol distribution is through the file.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

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

#2068

On Tuesday, November 5, 2013 12:47:58 PM UTC-5, Willem wrote:
> That depends on how variable the symbol distribution is through the file.

The technique is supposed to be general-purpose--the symbol distribution variability may be different depending on the file.  Since the compressor pre-scans first, maybe it's possible to determine the best way without interfering much with speed.  (?)  I'm basically looking for maximum compressibility.

BTW, I've been thinking about scrapping the technique hinted-at above other than Huffman. 

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

#2069

On 05.11.2013 17:24, Harry Potter wrote:
> My compression technique-to-be pre-scans a file for information used by other ideas, and I'm wondering: in this condition, which produces better results, regular Huffman or Adaptive Huffman?  Or is another variant better?

How can one tell? Both methods impose different models for the same 
input file, and whatever model fits the data better produces better 
results. Typically, adaptive Huffman is needlessly complex, and I would 
rather use adaptive arithmetic coding. But again, which adaption 
strategy works best (including the case of "no adaption strategy" = 
"static coding") is source dependent.

The art of compression is not to find a bit representation method. They 
are known: Arithmetic coding, and its special case, Huffman coding. The 
art is to find good models, or suitable models given an input file.

Greetings,
	Thomas

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

#2070

On Tuesday, November 5, 2013 2:01:34 PM UTC-5, Thomas Richter wrote:
> How can one tell? Both methods impose different models for the same 
> input file, and whatever model fits the data better produces better 
> results. Typically, adaptive Huffman is needlessly complex, and I would 
> rather use adaptive arithmetic coding. But again, which adaption 
> strategy works best (including the case of "no adaption strategy" = 
> "static coding") is source dependent.
> 
I'll just go with Adaptive, then.  I'm pretty far into it right now, anyway.

> The art of compression is not to find a bit representation method. They 
> are known: Arithmetic coding, and its special case, Huffman coding. The 
> art is to find good models, or suitable models given an input file.
> 
In that case, I may do well.  Most of my method involves doing such methods *better* :) along with furthering them.

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

#2071

On 11/5/2013 10:24 AM, Harry Potter wrote:
> My compression technique-to-be pre-scans a file for information used by other ideas, and I'm wondering: in this condition, which produces better results, regular Huffman or Adaptive Huffman?  Or is another variant better?
>

IME:

Static Huffman:
fast encoding/decoding (masking, shifts, and tables), but largely 
non-viable for higher order context models (beyond order-0);
a higher-order context-adaptive transform can be used, but kills much of 
the speed advantage, and a Huffman table beyond order-0 tends to be too 
large and eats any compression advantage.

use of multiple context-dependent tables can be used to good effect though.


Adaptive Huffman:
overly complex with lackluster speed and worse compression than 
(Adaptive) Arithmetic or Range coding.

Arithmetic and Range coding (Static):
slower than Huffman with few real advantages, efficiently storing 
context models is non-trivial and may kill any compression advantage.

Arithmetic and Range coding (Adaptive):
good compression at some cost to the speed (vs Static Huffman), more 
easily handles higher-order contexts.
probably a good choice for non-speed-critical compression tasks (such as 
file compression, but has been successfully used in video compression, *1).


*1: dunno, speed is hard in video compression so I am not entirely 
really sure how they make it fast enough. though, OTOH, most of my 
codecs end up spending most of their time in the color transform (so it 
is possible that the added cost of the AC isn't too bad in comparison).


some codecs (VP8 and VP9) seem to use Huffman for the first-pass 
compression, and use arithmetic coding as a secondary stage, so it is 
possible that this is acceptable (*2).

I once tried doing similar with M-JPEG with a modest decoding cost (in 
my tests it could squeeze another about 10-15% out of a JPEG, with a 
minor reduction in decoding speed), but at the time tried similar (with 
much less impressive results) at compressing DXTn images (both the 
decompression speed and compression ratio were somewhat worse than that 
of the JPEG images).

some of my current "fast" codecs combine block-based VQ with the use of 
Deflate, which offers a more reasonable compromise, and one offered 
Deflate+Arithmetic as an option (first Deflate the VQ data, then feed 
this through an arithmetic coder). though, at the time, this still 
wasn't particularly speed or size competitive with JPEG (whereas VQ + 
Deflate at least goes moderately fast).

this was with a bit-at-a-time arithmetic coder (transforming a series of 
input bits to a series of output bits), generally matching the bit-order 
used by the Huffman-coding stage.

*2: in this scenario, the Huffman compression does most of the "dirty 
work", with a comparably smaller amount of "fine tuning" being done by 
the arithmetic coder. as a result, the arithmetic coder doesn't have to 
have as much data fed through it, and as a result has less of a 
performance impact.

less certain is how the compression compares with straight AC, but I 
suspect it may be a compromise.


or such...

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

#2073

On Tuesday, November 5, 2013 9:36:37 PM UTC-5, BGB wrote:
> Static Huffman:
> fast encoding/decoding (masking, shifts, and tables), but largely 
> non-viable for higher order context models (beyond order-0);
> a higher-order context-adaptive transform can be used, but kills much of 
> the speed advantage, and a Huffman table beyond order-0 tends to be too 
> large and eats any compression advantage.
> 
I assume that order-0 means that the lowest value compressed is 0.  I was working on Static Huffman, and you're right: the table of a test text file was ~80 bytes.  Again, I developed a way to shrink the size of a value by at least one bit.  If I also alphabetize the values, I might be able to shorten some values to an offset from the previous.

> use of multiple context-dependent tables can be used to good effect though.
> 
I don't understand multiple context-dependent tables.  :(  Can you explain it for me please?

> Adaptive Huffman:
> overly complex with lackluster speed and worse compression than 
> (Adaptive) Arithmetic or Range coding.
> 
I have a way that can minimize the number of bits per byte in an Adaptive Huffman NYT.  However, it will only save a few bytes per file.

And as for arithmetic coding, I am currently not doing it because I am working on the 8- and 16-bit versions of my codec.  I will work on 32-bit versions later.

James Dow Allen:

Right now, I'm doing *everything* to create the best technique, so any idea would be useful.  BTW, I'll look at Golomb run coding now.

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

#2074

On Wednesday, November 6, 2013 9:12:52 AM UTC-5, Harry Potter wrote:
> BTW, I'll look at Golomb run coding now.

I looked.  It might be useful for text files but not other files.  After I figure it out and am ready to use it, I may try it.

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

#2075

On 11/6/2013 8:12 AM, Harry Potter wrote:
> On Tuesday, November 5, 2013 9:36:37 PM UTC-5, BGB wrote:
>> Static Huffman:
>> fast encoding/decoding (masking, shifts, and tables), but largely
>> non-viable for higher order context models (beyond order-0);
>> a higher-order context-adaptive transform can be used, but kills much of
>> the speed advantage, and a Huffman table beyond order-0 tends to be too
>> large and eats any compression advantage.
>>
> I assume that order-0 means that the lowest value compressed is 0.  I was working on Static Huffman, and you're right: the table of a test text file was ~80 bytes.  Again, I developed a way to shrink the size of a value by at least one bit.  If I also alphabetize the values, I might be able to shorten some values to an offset from the previous.
>

order-0: each symbol is encoded independently, for example, if you have 
256 possible byte values, each will have a certain probability 
regardless of what precedes them.

order-1: one prior symbol is taken into account, so for 256 symbols you 
have 65536 possible probabilities (every symbols' probability is 
relative to the symbol that preceded it).

order-2: two prior symbols are taken into account, so for 256 symbols 
you have 16777216 possible probabilities.

...


>> use of multiple context-dependent tables can be used to good effect though.
>>
> I don't understand multiple context-dependent tables.  :(  Can you explain it for me please?
>

usually, the entropy coding stage will be designed for a specific data 
format.

in this case, one can use different tables for different symbol types.

for example, you could have different tables for commands vs literal 
byte values vs distance values.

or, say you are developing a format which encodes 8x8 blocks of numbers:
the DC value (item 0) might be special and encoded with its own table;
the normal AC values (items 1-63) might have their own table (or 
possibly even subdivided, noting that 1-23 may have different 
probabilities than 24-63, etc);
escape-coded cases might also be given another table (say, if you have 
smaller items which might be encoded directly in a single symbol, and 
larger items which may require multiple symbols).


>> Adaptive Huffman:
>> overly complex with lackluster speed and worse compression than
>> (Adaptive) Arithmetic or Range coding.
>>
> I have a way that can minimize the number of bits per byte in an Adaptive Huffman NYT.  However, it will only save a few bytes per file.
>
> And as for arithmetic coding, I am currently not doing it because I am working on the 8- and 16-bit versions of my codec.  I will work on 32-bit versions later.
>
> James Dow Allen:
>
> Right now, I'm doing *everything* to create the best technique, so any idea would be useful.  BTW, I'll look at Golomb run coding now.
>

looking up Golomb-run and similar, found some interesting results.

in a lot of my formats, I have often used Rice coding for things like 
tables (Huffman and Quantization), as this tends to be simpler and 
cheaper (*) than using Huffman-coded tables, and more compact than naive 
byte-based tables.


*: it kind of a waste to set up a Huffman table only to use it to decode 
a small number of items, namely, another Huffman table.

actually, for the most part (in past format), I had been using a fairly 
direct adaptation of Deflate's Huffman table design over to using Rice 
coding. could probably consider a simpler (and "more elegant") design 
(Difference+RLE+Rice, or maybe MTF+RLE+Rice).


or such...

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

#2078

On Wednesday, November 6, 2013 1:57:34 PM UTC-5, BGB wrote:
> order-0: each symbol is encoded independently, for example, if you have 
> 256 possible byte values, each will have a certain probability 
> regardless of what precedes them.
> 
> order-1: one prior symbol is taken into account, so for 256 symbols you 
> have 65536 possible probabilities (every symbols' probability is 
> relative to the symbol that preceded it).
> 
> order-2: two prior symbols are taken into account, so for 256 symbols 
> you have 16777216 possible probabilities.
> 
I could use order-1 and order-2 on a 32-bit technique.  Thank you!

> usually, the entropy coding stage will be designed for a specific data 
> format.
> in this case, one can use different tables for different symbol types.
> 
I am using it for binary/general-purpose information, although text and multi-media would be nice.  :)

> for example, you could have different tables for commands vs literal 
> byte values vs distance values.
> 
I've seen that in the Deflate technique, but I didn't understand it.  :(

> or, say you are developing a format which encodes 8x8 blocks of numbers:
> the DC value (item 0) might be special and encoded with its own table;
> the normal AC values (items 1-63) might have their own table (or 
> possibly even subdivided, noting that 1-23 may have different 
> probabilities than 24-63, etc);
> escape-coded cases might also be given another table (say, if you have 
> smaller items which might be encoded directly in a single symbol, and 
> larger items which may require multiple symbols).
> 
This could be useful on Multi-Media files.

> looking up Golomb-run and similar, found some interesting results.
> 
> in a lot of my formats, I have often used Rice coding for things like 
> tables (Huffman and Quantization), as this tends to be simpler and 
> cheaper (*) than using Huffman-coded tables, and more compact than naive 
> byte-based tables.
> 
> *: it kind of a waste to set up a Huffman table only to use it to decode 
> a small number of items, namely, another Huffman table.
> 
Is rice format both faster and smaller than Huffman and Adaptive Huffman?

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

#2072

Typically, arithmetic codes encode *2-way* decisions while Huffman codes 
are best for *n-way* decisions with largish n.  (Obviously there are ways 
to convert n-way decisions into 2-way decisions and vice versa.)

Note that Huffman (static or adaptive) and Arithmetic (static or adaptive) 
are NOT the only good statistical bit coding methods, although the 
alternatives I'll mention have no advantage over Arithmetic coding except 
speed and simplicity.

There are the so-called "quasi-arithmetic" codes (with Howard-Vitter the 
most famous authors).

There is Golomb run coding or adaptive Golomb run coding (e.g. Generalized 
Langdon-Golomb coding).  The big disadvantage of Golomb run coding compared 
with arithmetic or quasi-arithmetic coding is that the coding assumes a 
single context.  However it is possible (see U.S. Patent 5583500(?)) to 
interleave Golomb code tokens from multiple contexts.

James Dow Allen

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

#2076

Am 06.11.2013 07:54, schrieb James Dow Allen:
> 
> There is Golomb run coding or adaptive Golomb run coding (e.g. Generalized 
> Langdon-Golomb coding).  The big disadvantage of Golomb run coding compared 
> with arithmetic or quasi-arithmetic coding is that the coding assumes a 
> single context.  However it is possible (see U.S. Patent 5583500(?)) to 
> interleave Golomb code tokens from multiple contexts.

Thanks for pointing out that this technique is patented.  I hate when
that happens, when you think of something by yourself and later notice
that somebody patented it already.

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

#2077

sg wrote:

> Am 06.11.2013 07:54, schrieb James Dow Allen:
>>
>> There is Golomb run coding or adaptive Golomb run coding (e.g. Generalized 
>> Langdon-Golomb coding).  The big disadvantage of Golomb run coding compared 
>> with arithmetic or quasi-arithmetic coding is that the coding assumes a 
>> single context.  However it is possible (see U.S. Patent 5583500(?)) to 
>> interleave Golomb code tokens from multiple contexts.
> 
> Thanks for pointing out that this technique is patented.  I hate when
> that happens, when you think of something by yourself and later notice
> that somebody patented it already.

If an "invention" is "obvious to a person skilled in the art"
then it is not patentable.

https://en.wikipedia.org/wiki/Inventive_step_and_non-obviousness

If I find an algorithm to solve a given problem after thinking
about it for a few hours, or even a few days, I would consider it
obvious to experts in that field. And that's not even considering
the problem with patenting algorithms.

Regards.

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

#2085

Noob <root@127.0.0.1> might have writ, in
news:l5fsb6$poc$2@dont-email.me: 
> sg wrote:
> 
>> Am 06.11.2013 07:54, schrieb James Dow Allen:
>>> ... it is possible
>>> (see U.S. Patent 5583500(?)) to interleave Golomb code tokens from
>>> multiple contexts. 
>> 
>> Thanks for pointing out that this technique is patented.  I hate when
>> that happens, when you think of something by yourself and later
>> notice that somebody patented it already.

My attitude is rather opposite.  At Slobodan Labs, colleagues often 
asked "Perhaps someone's already thought of that?" as though that should 
be a deterrant.  With so many researchers at work worldwide, my concern 
was more that if nobody had pursued an idea, it might just be that that 
idea was crackpottery!!

> If an "invention" is "obvious to a person skilled in the art"
> then it is not patentable.

AFAIK examiners focus on prior art and not on the ill-defined concept of 
"obviousness."

> If I find an algorithm to solve a given problem after thinking
> about it for a few hours, or even a few days, I would consider it
> obvious to experts in that field.

If "obviousness" is described in terms of *how long* it takes to come up 
with an idea, I'd think *minutes* would be more appropriate than *days.*  
Days may be needed for fleshing out details, but not the essential 
inspiration.

In the specific case of interleaving Golomb codes, I don't remember 
details and I'm not going to try to read the patent -- they were all 
written by a lawyer and seem garbled to me.  I do recall, however, that 
the task was non-trivial and the details indeed non-obvious.  (I do also 
believe I was "skilled in the relevant art," though that may remain "my 
word against yours.")

James Dow Allen

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

#2097

On 11/8/2013 2:46 AM, James Dow Allen wrote:
> Noob <root@127.0.0.1> might have writ, in
> news:l5fsb6$poc$2@dont-email.me:
>> sg wrote:
>>
>>> Am 06.11.2013 07:54, schrieb James Dow Allen:
>>>> ... it is possible
>>>> (see U.S. Patent 5583500(?)) to interleave Golomb code tokens from
>>>> multiple contexts.
>>>
>>> Thanks for pointing out that this technique is patented.  I hate when
>>> that happens, when you think of something by yourself and later
>>> notice that somebody patented it already.
>
> My attitude is rather opposite.  At Slobodan Labs, colleagues often
> asked "Perhaps someone's already thought of that?" as though that should
> be a deterrant.  With so many researchers at work worldwide, my concern
> was more that if nobody had pursued an idea, it might just be that that
> idea was crackpottery!!
>

pretty much.

lots of information, lots of ideas, sometimes it isn't so much work with 
creativity, as much as the mental equivalent of using a shovel, or maybe 
trying to classify and categorize things.


though, even as such, there is often not anything with the specific 
combination of desired features, so this doesn't mean usable preexisting 
solutions always necessarily exist either.


>> If an "invention" is "obvious to a person skilled in the art"
>> then it is not patentable.
>
> AFAIK examiners focus on prior art and not on the ill-defined concept of
> "obviousness."
>

sadly, though, neither seems to really prevent the issue of 
proliferation of random pointless patents.

best I can really hope sometimes as "this thing is pretty much the same 
as whatever existed prior to the patent in question, and thus the patent 
should not apply".


like, if someone went and tried to claim that RPZA violates the S3TC 
patent or similar (with RPZA being many years older, and both being 
based on "Color Cell Compression"). (and, for that matter, does it also 
apply to things like the graphics hardware in the Sega Genesis, ... ?).


likewise, someone also goes and claims to have ownership over 
compressing into DXTn via unpacking it via using indices into a table, 
but it is debatable if it applies to using LZ77 to unpack the DXTn, or 
going indirectly via transcoding from RPZA blocks (*2).

*2: actually, taken literally, it would also seemingly sidestep S3TC 
itself, but it isn't entirely clear what exactly is being protected by 
S3TC (literally, it shouldn't apply either to decoders or to encoders 
which work via feeding data through lookup tables in-general, or what 
part exactly isn't already covered under prior art, ...).


>> If I find an algorithm to solve a given problem after thinking
>> about it for a few hours, or even a few days, I would consider it
>> obvious to experts in that field.
>
> If "obviousness" is described in terms of *how long* it takes to come up
> with an idea, I'd think *minutes* would be more appropriate than *days.*
> Days may be needed for fleshing out details, but not the essential
> inspiration.
>

yeah, probably.

too much "pointlessly malevolent" stuff around IMO, so it is mostly a 
risk of accidentally stepping on things just randomly swapping out parts 
and similar.

"well, you went from MSB-first to LSB first bit-ordering and flipped the 
sign on this other value, thus, infringement!".


> In the specific case of interleaving Golomb codes, I don't remember
> details and I'm not going to try to read the patent -- they were all
> written by a lawyer and seem garbled to me.  I do recall, however, that
> the task was non-trivial and the details indeed non-obvious.  (I do also
> believe I was "skilled in the relevant art," though that may remain "my
> word against yours.")
>
> James Dow Allen
>

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

#2080

sg wrote:
> Am 06.11.2013 07:54, schrieb James Dow Allen:
>>
>> There is Golomb run coding or adaptive Golomb run coding (e.g. Generalized
>> Langdon-Golomb coding).  The big disadvantage of Golomb run coding compared
>> with arithmetic or quasi-arithmetic coding is that the coding assumes a
>> single context.  However it is possible (see U.S. Patent 5583500(?)) to
>> interleave Golomb code tokens from multiple contexts.
>
> Thanks for pointing out that this technique is patented.  I hate when
> that happens, when you think of something by yourself and later notice
> that somebody patented it already.
>
It will expire on December 10th this year.

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

#2082

On Tuesday, November 5, 2013 10:24:40 AM UTC-6, Harry Potter wrote:
> My compression technique-to-be pre-scans a file for information used by other ideas, and I'm wondering: in this condition, which produces better results, regular Huffman or Adaptive Huffman?  Or is another variant better?

If you're familiar with C++, you might check out the library that I put together a while back (https://github.com/SebastianGarth/The-Generic-Huffman-Compression-Library). It's static Huffman, but the overhead is quite optimal (maximum storage overhead in all cases never exceeds like ~320 bytes, and for the general case (ie: text files) that goes down to around 40-75 bytes, files with just one or two types of unique symbols require far less than a dozen bytes). Best of all, it's open-source, so you're welcome to modify it as you see fit.

Cheers!

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

#2088

On Friday, November 8, 2013 2:10:57 AM UTC-5, Sebastian Garth wrote:

> If you're familiar with C++, you might check out the library that I put together a while back (https://github.com/SebastianGarth/The-Generic-Huffman-Compression-Library). It's static Huffman, but the overhead is quite optimal (maximum storage overhead in all cases never exceeds like ~320 bytes, and for the general case (ie: text files) that goes down to around 40-75 bytes, files with just one or two types of unique symbols require far less than a dozen bytes). Best of all, it's open-source, so you're welcome to modify it as you see fit.
> 

I hazard a guess that a static Huffman technique I once tried should do slightly better than yours in the worst-case scenario.  However, my tests at the time showed ~80 bytes on a given text file.  I haven't been able to work on file compression lately--I goofed up my main working camputers at a day program; I haven't been able to go to my mother's house lately, and I haven't gotten to use my computer at home.  I will try the site now, but I won't be able to use the technique yet.

BTW, Have you tried some technique to sort the symbols yet?  Doing this may allow you to at times shorten a value to an offset from the previous?  If so,  can you tell me about it?

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

#2090

On Friday, November 8, 2013 8:12:21 AM UTC-6, Harry Potter wrote:
> On Friday, November 8, 2013 2:10:57 AM UTC-5, Sebastian Garth wrote:
> 
> 
> 
> > If you're familiar with C++, you might check out the library that I put together a while back (https://github.com/SebastianGarth/The-Generic-Huffman-Compression-Library). It's static Huffman, but the overhead is quite optimal (maximum storage overhead in all cases never exceeds like ~320 bytes, and for the general case (ie: text files) that goes down to around 40-75 bytes, files with just one or two types of unique symbols require far less than a dozen bytes). Best of all, it's open-source, so you're welcome to modify it as you see fit.
> 
> > 
> 
> 
> 
> I hazard a guess that a static Huffman technique I once tried should do slightly better than yours in the worst-case scenario.  However, my tests at the time showed ~80 bytes on a given text file.  I haven't been able to work on file compression lately--I goofed up my main working camputers at a day program; I haven't been able to go to my mother's house lately, and I haven't gotten to use my computer at home.  I will try the site now, but I won't be able to use the technique yet.
> 
> 
> 
> BTW, Have you tried some technique to sort the symbols yet?  Doing this may allow you to at times shorten a value to an offset from the previous?  If so,  can you tell me about it?

The technique I use doesn't require that the symbols be sorted; the actual Huffman tree is transmitted in it's entirety along with the the data and it's size is completely dependent upon the number of unique symbols used. So for example, a file that contains say 26 unique symbols requires something like 40 bytes overhead (26 bytes to store the actual symbols, the rest for the "tree bits"). Moreover the specific number of excess bits required is dependent upon the tree structure generated by that particular file.

On Friday, November 8, 2013 8:12:21 AM UTC-6, Harry Potter wrote:
> I looked at your source code but have been unable to find the encoder class.

The encoder class is contained within the ghcl.hpp header file (the demo program ghcl_test_suite.cpp was out of date, by the way, but that's been since fixed).

Just compile and run the test program to see how it works...

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

#2094

On Friday, November 8, 2013 11:39:54 AM UTC-5, Sebastian Garth wrote:
> Just compile and run the test program to see how it works...

I'll try to download, compile and test the program at the earliest opportunity.  Again, I don't have access to a usable computer for the task right now.  :(

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.compression

csiph-web