Huffman Coding Tree
Please read the
remarks about programming problems for
this course.
Section 5.6 in your textbook introduces Huffman coding trees.
In this assignment you will construct a Huffman coding tree from
English text and produce codes for letters of the alphabet.
Write a C++ program that reads in text from the standard input
stream. Use may use command line redirection or copy and paste
from a text file and into a console window to test your program.
A sample text is provided in
declaration.text (the US
Declaration of Independence).
You program must perform as follows:
- read in the contents of the text file, one character at a
time
- echo to the console each character as it is read from the
file (do this for all characters: alphabetic,
punctutation, whitespace, etc.)
- ignore all non-alphabetic characters (spaces, punctuation,
etc.) for the purpose of building the Huffman tree and
generating Huffman codes
- capitalize all lower-case letters (thus A and
a are both counted as just A)
- compute the frequencies of all the alphabetic letters within the
document
- build a Huffman tree from the letters and their associated
frequencies
- draw the Huffman tree in the sideways,
right-subtree-node-left-subtree manner as we did for our
other binary trees
- print a table in alphabetical order containing each letter with its associated
Huffman encoding derived from your tree.
The following shows a sample run against
declaration.text:
C:\Users\rick\Documents\Huffman\>huffman.exe < declaration.text
When in the Course of human events, it becomes necessary for one people to dissolve the political
bands which have connected them with another, and to assume among the powers of the earth, the
separate and equal station to which the Laws of Nature and of Nature's God entitle them, a decent
respect to the opinions of mankind requires that they should declare the causes which impel them
to the separation.
We hold these truths to be self-evident, that all men are created equal, that they are endowed by
their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit
of Happiness. --That to secure these rights, Governments are instituted among Men, deriving their
just powers from the consent of the governed, --That whenever any Form of Government becomes
destructive of these ends, it is the Right of the People to alter or to abolish it, and to institute
new Government, laying its foundation on such principles and organizing its powers in such form, as
to them shall seem most likely to effect their Safety and Happiness. Prudence, indeed, will dictate
that Governments long established should not be changed for light and transient causes; and
accordingly all experience hath shewn, that mankind are more disposed to suffer, while evils are
sufferable, than to right themselves by abolishing the forms to which they are accustomed. But when
a long train of abuses and usurpations, pursuing invariably the same Object evinces a design to
reduce them under absolute Despotism, it is their right, it is their duty, to throw off such
Government, and to provide new Guards for their future security. --Such has been the patient
sufferance of these Colonies; and such is now the necessity which constrains them to alter their
former Systems of Government. The history of the present King of Great Britain [George III] is a
history of repeated injuries and usurpations, all having in direct object the establishment of an
absolute Tyranny over these States. To prove this, let Facts be submitted to a candid world.
He has refused his Assent to Laws, the most wholesome and necessary for the public good.
He has forbidden his Governors to pass Laws of immediate and pressing importance, unless suspended
in their operation till his Assent should be obtained; and when so suspended, he has utterly
neglected to attend to them.
He has refused to pass other Laws for the accommodation of large districts of people, unless those
people would relinquish the right of Representation in the Legislature, a right inestimable to them
and formidable to tyrants only.
He has called together legislative bodies at places unusual, uncomfortable, and distant from the
depository of their public Records, for the sole purpose of fatiguing them into compliance with his
measures.
He has dissolved Representative Houses repeatedly, for opposing with manly firmness his invasions
on the rights of the people.
He has refused for a long time, after such dissolutions, to cause others to be elected; whereby
the Legislative powers, incapable of Annihilation, have returned to the People at large for their
exercise; the State remaining in the mean time exposed to all the dangers of invasion from without,
and convulsions within.
He has endeavoured to prevent the population of these States; for that purpose obstructing the Laws
for Naturalization of Foreigners; refusing to pass others to encourage their migrations hither,
and raising the conditions of new Appropriations of Lands.
He has obstructed the Administration of Justice, by refusing his Assent to Laws for establishing
Judiciary powers.
He has made Judges dependent on his Will alone, for the tenure of their offices, and the amount and
payment of their salaries.
He has erected a multitude of New Offices, and sent hither swarms of Officers to harass our people,
and eat out their substance.
He has kept among us, in times of peace, Standing Armies without the consent of our legislatures.
He has affected to render the Military independent of and superior to the Civil power.
He has combined with others to subject us to a jurisdiction foreign to our constitution and
unacknowledged by our laws; giving his Assent to their Acts of pretended Legislation:
For Quartering large bodies of armed troops among us:
For protecting them, by a mock Trial, from punishment for any Murders which they should commit on
the Inhabitants of these States:
For cutting off our Trade with all parts of the world:
For imposing Taxes on us without our Consent:
For depriving us, in many cases, of the benefits of Trial by Jury:
For transporting us beyond Seas to be tried for pretended offences:
For abolishing the free System of English Laws in a neighbouring Province, establishing therein
an Arbitrary government, and enlarging its Boundaries so as to render it at once an example and
fit instrument for introducing the same absolute rule into these Colonies:
For taking away our Charters, abolishing our most valuable Laws, and altering fundamentally the
Forms of our Governments:
For suspending our own Legislatures, and declaring themselves invested with power to legislate
for us in all cases whatsoever.
He has abdicated Government here, by declaring us out of his Protection and waging War against us.
He has plundered our seas, ravaged our Coasts, burnt our towns, and destroyed the lives of our people.
He is at this time transporting large Armies of foreign Mercenaries to compleat the works of death,
desolation and tyranny, already begun with circumstances of Cruelty and perfidy scarcely paralleled
in the most barbarous ages, and totally unworthy the Head of a civilized nation.
He has constrained our fellow Citizens taken Captive on the high Seas to bear Arms against their
Country, to become the executioners of their friends and Brethren, or to fall themselves by their
Hands.
He has excited domestic insurrections amongst us, and has endeavoured to bring on the inhabitants
of our frontiers, the merciless Indian Savages, whose known rule of warfare, is an undistinguished
destruction of all ages, sexes and conditions.
In every stage of these Oppressions We have Petitioned for Redress in the most humble terms: Our
repeated Petitions have been answered only by repeated injury. A Prince whose character is thus
marked by every act which may define a Tyrant, is unfit to be the ruler of a free people.
Nor have We been wanting in attentions to our British brethren. We have warned them from time to
time of attempts by their legislature to extend an unwarrantable jurisdiction over us. We have
reminded them of the circumstances of our emigration and settlement here. We have appealed to
their native justice and magnanimity, and we have conjured them by the ties of our common kindred
to disavow these usurpations, which, would inevitably interrupt our connections and correspondence.
They too have been deaf to the voice of justice and of consanguinity. We must, therefore, acquiesce
in the necessity, which denounces our Separation, and hold them, as we hold the rest of mankind,
Enemies in War, in Peace Friends.
We, therefore, the Representatives of the united States of America, in General Congress, Assembled,
appealing to the Supreme Judge of the world for the rectitude of our intentions, do, in the Name,
and by the Authority of the good People of these Colonies, solemnly publish and declare, That these
United Colonies are, and of Right ought to be Free and Independent States; that they are Absolved
from all Allegiance to the British Crown, and that all political connection between them and the
State of Great Britain, is and ought to be totally dissolved; and that as Free and Independent
States, they have full Power to levy War, conclude Peace, contract Alliances, establish Commerce,
and to do all other Acts and Things which Independent States may of right do. And for the support
of this Declaration, with a firm reliance on the protection of divine Providence, we mutually
pledge to each other our Lives, our Fortunes and our sacred Honor.
Counts:
-------
A: 478
B: 95
C: 184
D: 253
E: 862
F: 180
G: 132
H: 350
I: 452
J: 16
K: 14
L: 228
M: 144
N: 484
O: 514
P: 138
Q: 6
R: 425
S: 478
T: 640
U: 209
V: 74
W: 97
X: 9
Y: 81
Z: 4
Total = 6547
---------------------------------
/ [O:0.078509]
/ (0.152436)
\ [N:0.073927]
/ (0.298916)
/ [D:0.038644]
/ (0.073469)
\ [L:0.034825]
\ (0.146479)
\ [A:0.073011]
/ (0.572629)
/ [S:0.073011]
/ (0.142050)
\ [I:0.069039]
\ (0.273713)
\ [E:0.131663]
- (1.000000)
/ [V:0.011303]
/ (0.018787)
/ [J:0.002444]
/ (0.004582)
\ [K:0.002138]
\ (0.007484)
/ [Q:0.000916]
/ (0.001527)
\ [Z:0.000611]
\ (0.002902)
\ [X:0.001375]
/ (0.033603)
\ [W:0.014816]
/ (0.065526)
\ [U:0.031923]
/ (0.130441)
\ [R:0.064915]
/ (0.239499)
/ [C:0.028104]
/ (0.055598)
\ [F:0.027494]
\ (0.109058)
\ [H:0.053460]
\ (0.427371)
/ [T:0.097755]
\ (0.187872)
/ [B:0.014510]
/ (0.026883)
\ [Y:0.012372]
/ (0.048877)
\ [M:0.021995]
\ (0.090118)
/ [P:0.021078]
\ (0.041240)
\ [G:0.020162]
---------------------------------
A: 1100
B: 000111
C: 01011
D: 11011
E: 100
F: 01010
G: 00000
H: 0100
I: 1010
J: 011111011
K: 011111010
L: 11010
M: 00010
N: 1110
O: 1111
P: 00001
Q: 0111110011
R: 0110
S: 1011
T: 001
U: 01110
V: 0111111
W: 011110
X: 011111000
Y: 000110
Z: 0111110010
There be some slight
differences in your output due to ties for some frequencies, but if
you implement the Huffman tree building algorithm carefully, your
program's encodings should be very close to those shown above.
Your program will be tested
against other documents to verify its correctness.
Place all your code within a single file named
huffman.cpp. When you are finished submit your
huffman.cpp file to
eclass.e.southern.edu.