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:

  1. read in the contents of the text file, one character at a time
  2. echo to the console each character as it is read from the file (do this for all characters: alphabetic, punctutation, whitespace, etc.)
  3. ignore all non-alphabetic characters (spaces, punctuation, etc.) for the purpose of building the Huffman tree and generating Huffman codes
  4. capitalize all lower-case letters (thus A and a are both counted as just A)
  5. compute the frequencies of all the alphabetic letters within the document
  6. build a Huffman tree from the letters and their associated frequencies
  7. draw the Huffman tree in the sideways, right-subtree-node-left-subtree manner as we did for our binary search trees
  8. print a table 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]

---------------------------------

G : 00000
P : 00001
M : 00010
Y : 000110
B : 000111
T : 001
H : 0100
F : 01010
C : 01011
R : 0110
U : 01110
W : 011110
X : 011111000
Z : 0111110010
Q : 0111110011
K : 011111010
J : 011111011
V : 0111111
E : 100
I : 1010
S : 1011
A : 1100
L : 11010
D : 11011
N : 1110
O : 1111

The actual bit patterns for each letter may vary from those shown above depending on your exact algorithm for constructing the Huffman tree, but the lengths of the bitstrings for each letter produced by your program should match those above.

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.