Subject: Re: improvements to lha

From: [email-masked] (Jean-loup Gailly)
Date: 18 Jan 93 14:59:32 GMT

jonathan forbes <[email-masked]> writes:

> Well, AR's method of creating a Huffman tree from a statistics table is
> rather complex; if there is a faster way of doing it, I'd love to know.

zip 1.9 spends a negligible portion of its time in the Huffman tree
construction. Most of the time is spent in the string matching.
Concerning the complexity of Huffman tree construction, see the FAQ
for textbooks.

> I thought AR002 used a digital hash trie.  I was thinking about having a
> 256*256 "perfect" hash table for the first occurance of two adjacent
> characters in a buffer, and then a separate array of size BUFLENGTH of
> the previous occurance of those two characters.  Brute force could be
> used to match lengths > 2.

This is close to what I'm doing in zip 1.9. I am however using a
smaller hash table, because my experiments showed that a 256*256 hash
table did not improve the speed. I am also using linked lists instead
of an array for the hash chains, because this uses less memory and
also because Robert Jung has patented (5,140,321) the lzrw3a algorithm
which uses arrays instead of linked lists. (If you want to argue about
the value of such a patent, please followup to misc.legal.computing,
not comp.compression.research.)

> What is lazy evaluation anyway? I did look at the ZIP 1.9 source a
> while ago, but it really didn't explain anything

Did you look at algorithm.doc in the zip 1.9 sources? (See the FAQ
for ftp sites.)

> and the match location routines simply weren't
> separable from the rest of the program.

Agreed. Restructuring the code to build a general purpose compression
library is on my list of things to do.

Jean-loup Gailly
info-zip

---

From: [email-masked] (Nico E de Vries)
Date: 13 Jan 93 23:57:25 GMT

In <1993Jan12.2816.1018@dosgate> [email-masked] (jonathan forbes) writes:

>-> By the way, the basic algorithm of LHA is in my public-domain pre-LHA
>-> experimental archiver ar002 (which I wrote when I was a high-school
>-> teacher).  It's in CompuServe's IBMPRO Library and also on the disk

>What do you think programs such as ARJ are doing to get compression
>improvements over LHA?  Simply increasing the buffer size from 8K to 24K
>can't be all it is.  Perhaps there is a better way of encoding the

Actually buffer size is the most major factor. This is not unlimited
BTW. Making in 300k doesn't improve it on 200k.

>huffman tree and outputting it - there may also be a faster way of
>generating the huffman tree.

That is less interesting. Most time is soend looking for matches.

>Also, do you know of a faster way to locate matches (than the digital
>hash trie used in AR002)?  It doesn't matter if it takes more memory;
>I'm just looking for speed improvements in the match finding process.

The digital trie is nice from a theoretic viewpoint but useless in
practice. The overhead is too high. Simply brute force searching
with hashing  to speed it up is sufficient. (some small tricks
like lazy evaluation are needed of cource but those are already
available in AR002). Look at the ZIP 1.9 source to see excactly
what I mean.

>AR002 is a great program!

It is the best. ARJ, PKZIP and LHA are all derived from it. All faster
but essential no better compression.

Nico de Vries  "Personal opinion, 'AS IS', no waranties, bad grammar" etc.
    InterNet: [email-masked]   CompuServe: 100115,2303

To get (many) ==> LOSSLESS DATA COMPRESSION SOURCES <== get lds_10.zip at 
garbo.uwasa.fi /pc/programming. Make files for Borland C are included.

---

From: [email-masked] (Jean-loup Gailly)
Date: 19 Jan 93 09:16:56 GMT

jonathan forbes <[email-masked]> writes:

> The ZIP 1.9 source appears to used arrays for the hash chains (#ifndef
> DYN_ALLOC... Pos far prev[WSIZE]) just like I do.  That's not what
> you're referring to as being patented is it?

The prev[] array implements a linked list. This is the straightforward
implementation of external chaining in hash tables.  lzrw3a (ftp
location in FAQ item 5) uses a two dimensional array as the hash
table. All elements hashing to the same value are contiguous, so lzrw3a
has no need for a prev[] array. This is what Jung patented. (Yes, it is
pathetic that such things are patentable. Even run length encoding is
patented, see the FAQ item 8. But this subject is not appropriate for
comp.compression.research.)

> I wonder ifone can output matches in some way other than the standard
> LZ77 "Position,Length"... [while still using a sliding window type of
> algorithm]

Yes, you can. See for example the series of lzrw* algorithms and the Fiala and
Greene algorithm (also patented, see the FAQ for references). You can
use a hash index or a position in a trie instead of the usual distance.

> Also, did the use of dynamic Huffman trees improve compression any (in
> ZIP) or do they come out to about the same as static Huffman trees
> (which are, of course, much faster to use)?

There may be a problem of terminology here. zip uses static Huffman
coding, as opposed to adaptive Huffman coding, for which the tree is
changed after each input byte. (The review paper in ACM Computing
Surveys, 19,3, recommends the term 'adaptive coding' instead of the
more ambiguous 'dynamic coding').  As I mentioned in my previous
reply, building the tree takes negligible time, so it is not 'of
course much faster' to use a unique built-in tree for all files (as in
pkzip -es). This degrades compression significantly.

Jean-loup Gailly
[email-masked]