3) Reverse the order of all the bits in the above ShannonCode()
vector, so that the most significant bit becomes the least
significant bit. For example, the value 0x1234 (hex) would
become 0x2C48 (hex).
4) Restore the order of Shannon-Fano codes as originally stored
within the file.
Example:
This example will show the encoding of a Shannon-Fano tree
of size 8. Notice that the actual Shannon-Fano trees used
for Imploding are either 64 or 256 entries in size.
Example: 0x02, 0x42, 0x01, 0x13
The first byte indicates 3 values in this table. Decoding the
bytes:
0x42 = 5 codes of 3 bits long
0x01 = 1 code of 2 bits long
0x13 = 2 codes of 4 bits long
This would generate the original bit length array of:
(3, 3, 3, 3, 3, 2, 4, 4)
There are 8 codes in this table for the values 0 thru 7. Using
the algorithm to obtain the Shannon-Fano codes produces:
Reversed Order Original
Val Sorted Constructed Code Value Restored Length
--- ------ ----------------- -------- -------- ------
0: 2 1100000000000000 11 101 3
1: 3 1010000000000000 101 001 3
2: 3 1000000000000000 001 110 3
3: 3 0110000000000000 110 010 3
4: 3 0100000000000000 010 100 3
5: 3 0010000000000000 100 11 2
6: 4 0001000000000000 1000 1000 4
7: 4 0000000000000000 0000 0000 4
The values in the Val, Order Restored and Original Length columns
now represent the Shannon-Fano encoding tree that can be used for
decoding the Shannon-Fano encoded data. How to parse the
variable length Shannon-Fano values from the data stream is beyond
the scope of this document. (See the references listed at the end of
this document for more information.) However, traditional decoding
schemes used for Huffman variable length decoding, such as the
Greenlaw algorithm, can be successfully applied.
The compressed data stream begins immediately after the
compressed Shannon-Fano data. The compressed data stream can be
interpreted as follows:
loop until done
read 1 bit from input stream.
if this bit is non-zero then (encoded data is literal data)
if Literal Shannon-Fano tree is present
read and decode character using Literal Shannon-Fano tree.
otherwise
read 8 bits from input stream.
copy character to the output stream.
otherwise (encoded data is sliding dictionary match)
if 8K dictionary size
read 7 bits for offset Distance (lower 7 bits of offset).
otherwise
read 6 bits for offset Distance (lower 6 bits of offset).
using the Distance Shannon-Fano tree, read and decode the
upper 6 bits of the Distance value.
