🚀 go-pugleaf

robert@solan.unit.no (Robert Schmidt) writes:

>Hi!
>
>As a part of my Data structures and Algorithms course, I came across
>the Huffman algorithm for finding an optimal, variable-length coding tree,
>for compressing data.
>
>I implemented this using C++ classes (a heap and a binary tree), and although
>it was fast, the compression ratio didn't impress me much, as you can
>well imagine.

	Maybe I missed the clue boat.   I thought that the optimal
	code for compressing a data set also produced the optimal
	compressed data set.  Is this not true?  I understand that
	in some cases there would be a more optimal algorithm than
	Huffman's, such as a variation of Huffman's that used
	samples of different lengths.  How could you NOT be impressed
	by its compression ratio, though?  The first thing that
	I imagine is that you didn't compress the coded bits into
	packed bytes, but saved them as their ascii values, '0',
	and '1'.  If that's the case, packing the bits would produce
	a coded file 1/8 of its current size, depending on the size
	of the original data set.  Was that your problem?  

>
>I was wondering if anyone have assembler, pascal, c or c++ sources for
>compression.  I'll appreciate anything, even if it doesn't compress
>very good, or is very slow.  I've used run-length encoding before, and have
>glanced at LZ coding.
>
>If I get enough nice replies, I'll collect them and send them to some binary
>archives or ftp sites (if such collections doesn't exist already, of course).
>
>And one more thing:  Please reply via e-mail!
>

	I would honor your request to reply via e-mail, but I
	wanted to ask everyone else out there the same question:
	Is there a more optimal coding algorithm?

						Don Kauffman

In article <kauffman.16.717709476@slab.unt.edu>, kauffman@slab.unt.edu (DON KAUFFMAN) writes:

 > 	Maybe I missed the clue boat.   I thought that the optimal
 > 	code for compressing a data set also produced the optimal
 > 	compressed data set.  Is this not true?  I understand that
 > 	in some cases there would be a more optimal algorithm than
 > 	Huffman's, such as a variation of Huffman's that used
 > 	samples of different lengths.  How could you NOT be impressed
 > 	by its compression ratio, though?  The first thing that
 > 	I imagine is that you didn't compress the coded bits into
 > 	packed bytes, but saved them as their ascii values, '0',
 > 	and '1'.  If that's the case, packing the bits would produce
 > 	a coded file 1/8 of its current size, depending on the size
 > 	of the original data set.  Was that your problem?  

Heh, what do you take me for?  :-)

Actually I ran the Huffman cost analysis on my HUFFMAN.CPP source file.
The size went from about 9100 bytes to 5800 bytes.  That's good, and pretty
near usable!  I tried it again on the 23000 byte HUFFMAN.EXE
file, which was reduced to nearly 21500 bytes.  That was what didn't impress
me.

I have long experience in using programs like PKZIP, LHA and ARJ, and I am
perhaps expecting too much of a simple algorithm like Huffman's.  But the
fact is that all those programs compressed the above files to approx. 50-65
percent of the original sizes.
 
I guess combining Huffman coding with LZ coding would be a good idea, and
I have heard that that's what's been done in LHA.  I think that boils
down to what you refer to as variable-sample Huffman.

-- 
Cheers from Robert Schmidt, aka Ztiff Zox, aka Buuud (IRC).  E-mail to 
robert@solan.unit.no, snail-mail to Stud.techn. Robert Schmidt, Stud.post 170,
Norwegian Institute of Technology, 7034 Trondheim, NORWAY          

Warlords: Now do you think my .sig is boring enough?

|> Actually I ran the Huffman cost analysis on my HUFFMAN.CPP source file.
|> The size went from about 9100 bytes to 5800 bytes.  That's good, and pretty
|> near usable!  I tried it again on the 23000 byte HUFFMAN.EXE
|> file, which was reduced to nearly 21500 bytes.  That was what didn't impress
|> me.
|> 

Just a comment on compressing executables. Most microprocessors (well
CISCs anyway) have their instruction set optimized just like Huffman
coding (the most common instructions have the shortest instruction
length) and that is why it gives you bad results when compressing
executables.

Marius (mariusk@lise.unit.no)..