Article View: comp.compression.research
Article #83how Huffman tree can be stored efficiently ?
From: Jerzy Tarasiuk
Date: Wed, 30 Sep 1992 17:48
Date: Wed, 30 Sep 1992 17:48
14 lines
1247 bytes
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!jtShow 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