546
Graphs and Trees
Because B′ was optimal, it cannot be the case that E(T ′) < E(B′), so E(T ′) = E(B′),
and T ′ is optimal.
Finally, a tree with a single node whose frequency is the sum of all the frequencies is trivially optimal for that sum. We can repeatedly split up this sum
and drop down children in such a way that we end up with the Huffman tree.
By the preceding paragraph, each such tree, including the final Huffman tree, is
optimal.
example 40
If we applied the process that preserves optimality to the tree of Figure 6.57, we
would begin with a single node with frequency 100 and “grow” that tree downward, as shown in Figure 6.60.
100
52
48
100
52
48
30
22
100
52
48
30
22
17
13
100
52
48
30
22
13
10
17
4
9
12
100
52
48
30
22
10
17
12
13
100
Figure 6.60
application of huffman codes
The cost of data storage has certainly declined in recent years, and the relatively low
cost makes it seem as if practically unlimited storage should be available to all. But
“relatively inexpensive” doesn’t mean “free,” and during the same period in which
data storage costs have decreased, the legal requirements on many businesses and
other organizations to keep electronic records have increased. Much of this information is archival in nature and suitable for data compression. As just one example,
the Sarbanes–Oxley Act became United States federal law in 2002. This law was
enacted as a reaction to a series of high-profile scandals about accounting irregularities and irresponsible corporate governance that shook financial markets and public
trust. Congress authorized the Securities and Exchange Commission (SEC) to set up
rules regarding retention of documents concerned with financial audits or reviews.
The final SEC rule requires that all publicly traded companies must retain electronic
records of all financial transactions for seven years. These records are to include not
just formal documents but any e-mail, memos, working papers, and so forth, sent or
received, that contain opinions, conclusions, analyses, or financial data.
Graphs and Trees
Because B′ was optimal, it cannot be the case that E(T ′) < E(B′), so E(T ′) = E(B′),
and T ′ is optimal.
Finally, a tree with a single node whose frequency is the sum of all the frequencies is trivially optimal for that sum. We can repeatedly split up this sum
and drop down children in such a way that we end up with the Huffman tree.
By the preceding paragraph, each such tree, including the final Huffman tree, is
optimal.
example 40
If we applied the process that preserves optimality to the tree of Figure 6.57, we
would begin with a single node with frequency 100 and “grow” that tree downward, as shown in Figure 6.60.
100
52
48
100
52
48
30
22
100
52
48
30
22
17
13
100
52
48
30
22
13
10
17
4
9
12
100
52
48
30
22
10
17
12
13
100
Figure 6.60
application of huffman codes
The cost of data storage has certainly declined in recent years, and the relatively low
cost makes it seem as if practically unlimited storage should be available to all. But
“relatively inexpensive” doesn’t mean “free,” and during the same period in which
data storage costs have decreased, the legal requirements on many businesses and
other organizations to keep electronic records have increased. Much of this information is archival in nature and suitable for data compression. As just one example,
the Sarbanes–Oxley Act became United States federal law in 2002. This law was
enacted as a reaction to a series of high-profile scandals about accounting irregularities and irresponsible corporate governance that shook financial markets and public
trust. Congress authorized the Securities and Exchange Commission (SEC) to set up
rules regarding retention of documents concerned with financial audits or reviews.
The final SEC rule requires that all publicly traded companies must retain electronic
records of all financial transactions for seven years. These records are to include not
just formal documents but any e-mail, memos, working papers, and so forth, sent or
received, that contain opinions, conclusions, analyses, or financial data.