Length-Limited Huffman Coding

Length-Limited Huffman Coding

[gautier_niouzes]

Hello,

Does someone here knows of an Ada implementation of length-limited Huffman coding ? Basically it is the construction of a Huffman tree with a constraint of a limited tree depth (or code length, if you consider the code formed by walking through the tree). References seem to point to two algorithms [1] and [2] which reduces the memory space needed, compared to [1]. Actually [1] would already be OK for my needs ("Dynamic Deflate" compression in Zip-Ada). 

TIA
_________________________ 
Gautier's Ada programming 
http://sf.net/users/gdemont/


[1] A Fast Algorithm for Optimal Length-Limited Huffman Codes
Larmore & Hirschberg

[2] A Fast and Space-Economical Algorithm for Length-Limited Coding
Katajainen, Moffat & Turpin

Re: Length-Limited Huffman Coding

[gautier_niouzes]

No need to search, there is an implementation now, translated from katajainen.c (Zopfli project):
http://sf.net/p/unzip-ada/code/HEAD/tree/zip_lib/length_limited_huffman_code_lengths.ads
http://sf.net/p/unzip-ada/code/HEAD/tree/zip_lib/length_limited_huffman_code_lengths.adb

There is an independent test procedure:

http://sf.net/p/unzip-ada/code/HEAD/tree/test/test_llhc.adb

and a minor sighting (so far...) in Zip.Compress.Deflate.
Cheers
G.

Re: Length-Limited Huffman Coding

[gautier_niouzes]

> http://sf.net/p/unzip-ada/code/HEAD/tree/zip_lib/length_limited_huffman_code_lengths.ads
> http://sf.net/p/unzip-ada/code/HEAD/tree/zip_lib/length_limited_huffman_code_lengths.adb
> http://sf.net/p/unzip-ada/code/HEAD/tree/test/test_llhc.adb

For the fun of it, test_llhc (which with'es only package length_limited_huffman_code_lengths) builds on GNAT with the -gnat83 switch, so *perhaps* with all Ada compilers!...
_________________________ 
Gautier's Ada programming 
http://sf.net/users/gdemont/ 

Re: Length-Limited Huffman Coding

[Randy Brukardt]

<gautier_niouzes@hotmail.com> wrote in message 
news:3353c34e-b11d-42fe-83d2-85781276c0e2@googlegroups.com...
>> http://sf.net/p/unzip-ada/code/HEAD/tree/zip_lib/length_limited_huffman_code_lengths.ads
>> http://sf.net/p/unzip-ada/code/HEAD/tree/zip_lib/length_limited_huffman_code_lengths.adb
>> http://sf.net/p/unzip-ada/code/HEAD/tree/test/test_llhc.adb
>
> For the fun of it, test_llhc (which with'es only package 
> length_limited_huffman_code_lengths)
> builds on GNAT with the -gnat83 switch, so *perhaps* with all Ada 
> compilers!...

Careful! You might talk me into digging out an old Janus/Ada 83 for MS-DOS. 
:-)

                             Randy.

Re: Length-Limited Huffman Coding

[gautier_niouzes]

> > builds on GNAT with the -gnat83 switch, so *perhaps* with all Ada 
> > compilers!...

Randy:

> Careful! You might talk me into digging out an old Janus/Ada 83 for MS-DOS. 
> :-)

Teasing, isn't it ? Will you resist ?

_________________________ 
Gautier's Ada programming 
http://www.openhub.net/accounts/gautier_bd

Re: Length-Limited Huffman Coding

[Tero Koskinen]

11.2.2016, 11.48, gautier_niouzes@hotmail.com wrote:
>>> builds on GNAT with the -gnat83 switch, so *perhaps* with all Ada
>>> compilers!...
>
> Randy:
>
>> Careful! You might talk me into digging out an old Janus/Ada 83 for MS-DOS.
>> :-)
>
> Teasing, isn't it ? Will you resist ?

I am not Randy, but I tested the code with Janus/Ada 3.1.2c
(on Windows 10) and it compiled and ran fine:

 > test_llh
Maximum Huffman code length (constraint):  4 bits
------------------------------------
     a freq = 10 length =  4
     b freq = 30 length =  2
     c freq = 12 length =  4
     d freq =  5 length =  4
     e freq = 17 length =  3
     f freq = 20 length =  3
     g freq = 17 length =  3
     h freq =  0 length =  0
     i freq = 20 length =  3
     j freq =  0 length =  0
     k freq = 15 length =  4
Maximum Huffman code length (constraint):  5 bits
------------------------------------
     a freq = 10 length =  5
     b freq = 30 length =  2
     c freq = 12 length =  4
     d freq =  5 length =  5
     e freq = 17 length =  3
     f freq = 20 length =  3
     g freq = 17 length =  3
     h freq =  0 length =  0
     i freq = 20 length =  3
     j freq =  0 length =  0
     k freq = 15 length =  3

 >

Although, Janus/Ada gave one warning:
In File C:\Work\gautier\llhc\LENGTH_LIMITED_HUFFMAN_CODE_LENGTHS.ADB at 
line 54
--------------
    53:    type Index_pair is array(Index_type'(0)..1) of Index_type;
    54:    lists: array(0..Index_type(max_bits-1)) of Index_pair;
-----------------------------------------------------^
*WARNING* This component has a non-simple type (6.5.2)
%%%%%%%


Yours,
  Tero

Re: Length-Limited Huffman Coding

[Randy Brukardt]

"Tero Koskinen" <tero.koskinen@iki.fi> wrote in message 
news:n9ikpb$ma8$1@loke.gir.dk...
> 11.2.2016, 11.48, gautier_niouzes@hotmail.com wrote:
...
> I am not Randy, but I tested the code with Janus/Ada 3.1.2c
> (on Windows 10) and it compiled and ran fine:

Thanks. Of course, the MS-DOS Ada 83 compiler, with the 640K memory limit 
and weaker representation clause support, might be a different story.

...
> Although, Janus/Ada gave one warning:
> In File C:\Work\gautier\llhc\LENGTH_LIMITED_HUFFMAN_CODE_LENGTHS.ADB at 
> line 54
> --------------
>    53:    type Index_pair is array(Index_type'(0)..1) of Index_type;
>    54:    lists: array(0..Index_type(max_bits-1)) of Index_pair;
> -----------------------------------------------------^
> *WARNING* This component has a non-simple type (6.5.2)

That just means that the implementation of that type is likely to be 
expensive. It should work (as it does), but if you have a performance 
concern you, one might want to try to get rid of the warning. I presume this 
is in a generic unit, though, so that's probably impossible. (This is one of 
the warnings that I'm contemplating moving to a new category of 
"informations", which could then be turned on/off separately; leaving 
warnings for things that a programmer really ought to consider changing.)

                         Randy.