Java Reference
In-Depth Information
binary trie
A data structure in which a left branch represents 0 and a right
branch represents 1. The path to a node indicates its representation. (475)
compression
The act of reducing the number of bits required for data repre-
sentation, which actually has two phases: the encoding phase (compres-
sion) and the decoding phase (uncompression). (474)
cross-reference generator
A program that lists identifiers and their line numbers.
It is a common application because it is similar to creating an index. (495)
full tree
A tree whose nodes either are leaves or have two children. (475)
Huffman's algorithm
An algorithm that constructs an optimal prefix code by
repeatedly merging the two minimum weight trees. (477)
prefix code
Code in which no character code is a prefix of another character
code. This condition is guaranteed in a trie if the characters are only in
leaves. A prefix code can be decoded unambiguously. (476)
When working with character I/O, you often need to use an
int
to store
the characters because of the additional
EOF
symbol. There are several
other tricky coding issues.
1.
Using too much memory to store the compression table is a common mis-
take. Doing so limits the amount of compression that can be achieved.
2.
The compression program and cross-reference generator is available.
Hzip.java
Contains the source for the Huffman coding compression and
uncompression program. See also
HZIPInputStream.java
,
HZIPOutputStream.java
, and
Tokenizer.java
.
Xref.java
Contains the source for the cross-reference generator.
IN SHORT
12.1
Show the Huffman tree that results from the following distribution
of punctuation characters and digits: colon (100), space (605), new-
line (100), comma (705), 0 (431), 1 (242), 2 (176), 3 (59), 4 (185),
5 (250), 6 (174), 7 (199), 8 (205), and 9 (217).
Search WWH ::
Custom Search