Java Reference
In-Depth Information
Most systems come with a compression program. Compress several
types of files to determine the typical compression rate on your sys-
tem. How large do the files have to be to make compression worth-
while? Compare their performance with the Huffman coding program
( Hzip ) provided in the online source code.
12.2
What happens if a file compressed with Huffman's algorithm is used
to transmit data over a phone line and a single bit is accidentally lost?
What can be done in this situation?
12.3
IN THEORY
12.4
Prove the correctness of Huffman's algorithm by expanding the fol-
lowing steps.
a.
Show that no node has only one child.
b.
Show that the two least frequent characters must be the two deep-
est nodes in the tree.
c.
Show that the characters in any two nodes at the same depth can
be swapped without affecting optimality.
d.
Use induction: As trees are merged, consider the new character
set to be the characters in the tree roots.
Under what circumstances could a Huffman tree of ASCII characters
generate a 2-bit code for some character? Under what circumstances
could it generate a 20-bit code?
12.5
Show that, if the symbols have already been sorted by frequency,
Huffman's algorithm can be implemented in linear time.
12.6
Huffman's algorithm occasionally generates compressed files that
are not smaller than the original. Prove that all compression algo-
rithms must have this property (i.e., no matter what compression
algorithm you design, some input files must always exist for which
the algorithm generates compressed files that are not smaller than
the originals).
12.7
IN PRACTICE
12.8
In the cross-reference generator, store the line numbers in a
LinkedList instead of an ArrayList and compare performance.
If a word occurs twice on a line, the cross-reference generator will list
it twice. Modify the algorithm so that duplicates are only listed once.
12.9
Modify the algorithm so that, if a word appears on consecutive lines,
a range is indicated. For example,
12.10
if: 2, 4, 6-9, 11
Search WWH ::




Custom Search