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:
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.