* Length-Limited Huffman Coding
@ 2016-02-06 20:57 gautier_niouzes
2016-02-08 21:20 ` gautier_niouzes
0 siblings, 1 reply; 7+ messages in thread
From: gautier_niouzes @ 2016-02-06 20:57 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Length-Limited Huffman Coding
2016-02-06 20:57 Length-Limited Huffman Coding gautier_niouzes
@ 2016-02-08 21:20 ` gautier_niouzes
2016-02-10 11:29 ` gautier_niouzes
0 siblings, 1 reply; 7+ messages in thread
From: gautier_niouzes @ 2016-02-08 21:20 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Length-Limited Huffman Coding
2016-02-08 21:20 ` gautier_niouzes
@ 2016-02-10 11:29 ` gautier_niouzes
2016-02-11 1:59 ` Randy Brukardt
0 siblings, 1 reply; 7+ messages in thread
From: gautier_niouzes @ 2016-02-10 11:29 UTC (permalink / raw)
> 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/
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Length-Limited Huffman Coding
2016-02-10 11:29 ` gautier_niouzes
@ 2016-02-11 1:59 ` Randy Brukardt
2016-02-11 9:48 ` gautier_niouzes
0 siblings, 1 reply; 7+ messages in thread
From: Randy Brukardt @ 2016-02-11 1:59 UTC (permalink / raw)
<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.
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Length-Limited Huffman Coding
2016-02-11 1:59 ` Randy Brukardt
@ 2016-02-11 9:48 ` gautier_niouzes
2016-02-11 18:44 ` Tero Koskinen
0 siblings, 1 reply; 7+ messages in thread
From: gautier_niouzes @ 2016-02-11 9:48 UTC (permalink / raw)
> > 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Length-Limited Huffman Coding
2016-02-11 9:48 ` gautier_niouzes
@ 2016-02-11 18:44 ` Tero Koskinen
2016-02-11 22:08 ` Randy Brukardt
0 siblings, 1 reply; 7+ messages in thread
From: Tero Koskinen @ 2016-02-11 18:44 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Length-Limited Huffman Coding
2016-02-11 18:44 ` Tero Koskinen
@ 2016-02-11 22:08 ` Randy Brukardt
0 siblings, 0 replies; 7+ messages in thread
From: Randy Brukardt @ 2016-02-11 22:08 UTC (permalink / raw)
"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.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2016-02-11 22:08 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-02-06 20:57 Length-Limited Huffman Coding gautier_niouzes
2016-02-08 21:20 ` gautier_niouzes
2016-02-10 11:29 ` gautier_niouzes
2016-02-11 1:59 ` Randy Brukardt
2016-02-11 9:48 ` gautier_niouzes
2016-02-11 18:44 ` Tero Koskinen
2016-02-11 22:08 ` Randy Brukardt
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox