🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.compression.research
Article #83

how Huffman tree can be stored efficiently ?

#83
From: Jerzy Tarasiuk
Date: Wed, 30 Sep 1992 17:48
14 lines
1247 bytes
Hello,
Most efficient algorithm to store information necessary to re-build
Huffman decoding tree is put 256 bytes each specifying code size
used to encode byte value which is index to the table, for exmple
if use for 'a', 'b' and 'c' codes of lengths 4, 7 and 6, respectively
then bytes at positions 97,98 and 99 should be 4,7,6; if '@' is not
used in text which is compressed, then at position 64 can be 0.
This information is not sufficient to rebuild original tree but is
sufficient to build tree giving max compression (as original gives)
so can put same algorithm for rebuilding in both comp and decomp.
If there are no many long codes can think about using less then 8-bit
bytes for this information (but is possible worst case when code
sizes have range from 1 to 255 and such a packing is not possible...).
Jerzy Tarasiuk
Technical Details
Message-ID: <JT.92Sep30184832@fizyk1.fuw.edu.pl>
Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!sunic!fuw.edu.pl!cocos!jt

Show Full Headers
Complete Article Headers
Newsgroups: comp.compression.research
Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!sunic!fuw.edu.pl!cocos!jt
From: jt@fuw.edu.pl (Jerzy Tarasiuk)
Subject: how Huffman tree can be stored efficiently ?
Message-ID: <JT.92Sep30184832@fizyk1.fuw.edu.pl>
Sender: news@fuw.edu.pl
Nntp-Posting-Host: fizyk1
Organization: Warsaw University Physics Dept.
Distribution: comp
Date: Wed, 30 Sep 1992 17:48:32 GMT
Lines: 14