Guide
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 7
lab_huffman
Hazardous Huffman Codes
!"#$%&'(%)*+%,*-./%0&
!1234#5 6'7%8'591":
Assignment Description
;5%:8<=%>'7+%31"%?<>>%7#%#2@>1(<54%'%9<AA#(#5:%:(##%'@@><B':<15%CD"AAE'5%F(##=G+%?8<B8%'>>1?%A1(%#AA<B<#5:%>1==>#==
B1E@(#==<15%1A%A<>#=H%F8#(#%'(#%'%>1:%1A%A<>#=%<5%:8<=%>'7+%7":%31"%?<>>%15>3%7#%E19<A3<54%huffman_tree.cppH
Lab Insight
D"AAE'5%#5B19<54%<=%'%A"59'E#5:'>%B1E@(#==<15%'>41(<:8E=%A1(%9':'H%I1E@(#==<54%9':'%<=%'%J#(3%@1?#(A">
:11>%:8':%B'5%(#@(#=#5:%'%4<J#5%=#:%1A%<5A1(E':<15%<5%>#==%=@'B#+%:8"=%'>>1?<54%:8#%9':'%:1%7#%:('5=A#((#9%E1(#
#AA<B<#5:>3H%!<AA#(#5:%:3@#=%1A%B1E@(#==<15%B'5%7#%=##5%?<:8<5%<E'4#=%A1(E':=%><K#%L0MC>1==3G%1(%0NMC>1==>#==GH
;:%B'5%'>=1%7#%=##5%<5%O;0%A<>#=%A1(%B1E@(#==<54%E">:<@>#%A<>#=H%F8#%B15B#@:%1A%#5B19<54%9':'%B'5%7#%=##5%<5
A":"(#%B1"(=#=%IP%Q*R+%I1EE"5<B':<15%N#:?1(K=+%9#'><54%?<:8%:('5=A#((<54%>'(4#%'E1"5:=%1A%9':'+%'59%IP
QST+%I1E@":#(%P#B"(<:3+%?8<B8%9#'>=%?<:8%#5B19<54%9':'%A1(%'%>'3#(%1A%@(<J'B3H
Getting Set Up
U(1E%31"(%IP%,,.%4<:%9<(#B:1(3+%("5%:8#%A1>>1?<54%15%VWP$
git fetch release
git merge release/lab_huffman -m "Merging initial lab_huffman files"
;A%31"X(#%15%31"(%1?5%E'B8<5#+%31"%E'3%5##9%:1%("5$
git fetch release
git merge --allow-unrelated-histories release/lab_huffman -m "Merging initial lab_huffman
files"
Y@15%'%="BB#==A">%E#(4#+%31"(%>'7Z8"AAE'5%A<>#=%'(#%51?%<5%31"(%lab_huffman%9<(#B:1(3H
F8#%B19#%A1(%:8<=%'B:<J<:3%(#=<9#=%<5%:8#%lab_huffman/%9<(#B:1(3H%M#:%:8#(#%73%:3@<54%:8<=%<5%31"(%?1(K<54
9<(#B:1(3$
cd lab_huffman/
Video Intro
F8#(#%<=%'%J<9#1%<5:(19"B:<15%A1(%:8<=%>'7[%;A%31"%'(#%<5:#(#=:#9%<5%=##<54%'%=:#@\73\=:#@%#2#B":<15%1A%:8#
D"AAE'5%F(##%'>41(<:8E=+%@>#'=#%?':B8%<:$
!%F8#%A1>>1?<54%<=%E#'5:%:1%8#>@%31"%"59#(=:'59%:8#%:'=K%A1(%:8<=%>'7H%;:%<=%=:(154>3%(#B1EE#59#9%:8':
31"%?':B8%:8#%J<9#1%:1%"59#(=:'59%:8#%E1:<J':<15%A1(%?83%?#X(#%:'>K<54%'71":%D"AAE'5%V5B19<54%'=%?#>>
'=%81?%:8#%'>41(<:8E%?1(K=H
Assignment
Description
Lab Insight
Getting Set Up
Video Intro
The Huffman
Encoding
Implement
buildTree()
and
removeSmallest()
Implement
decode()
Implement
writeTree()
and readTree()
Testing Your
Code!
Submitting
Your Work
Good luck!
CS 225 Huffman Encoding
The Huffman Encoding
;5%T/.T+%?8<>#%:'K<54%'5%;5A1(E':<15%F8#1(3%B>'==%'=%'%=:"9#5:%':%&;F+%!'J<9%]H%D"AAE'5%'59%8<=%B>'==E':#=
?#(#%4<J#5%'%B81<B#%73%:8#%@(1A#==1(%^17#(:%&H%U'51$%:8#3%B'5%#<:8#(%:'K#%:8#%A<5'>%#2'E+%1(%<A%:8#3%?'5:%:1%1@:
1":%1A%<:%:8#3%5##9%:1%A<59%:8#%E1=:%#AA<B<#5:%7<5'(3%B19#H%D"AAE'5%:11K%:8#%(1'9%>#==%:('J#>#9%'59%:8#%(#=:
:8#3%='3%<=%8<=:1(3H
0":%=<E@>3+%D"AAE'5%#5B19<54%:'K#=%<5%'%:#2:%<5@":%'59%4#5#(':#=%'%7<5'(3%B19#%C'%=:(<54%1A%)X=%'59%TX=G%:8':
(#@(#=#5:=%:8':%:#2:H%6#:X=%>11K%':%'5%#2'E@>#$%;5@":%E#=='4#$%_A##9%E#%E1(#%A119`
Building the Huffman tree
Input:%_A##9%E#%E1(#%A119`
Step 1:%I'>B">':#%A(#a"#5B3%1A%#J#(3%B8'('B:#(%<5%:8#%:#2:+%'59%1(9#(%73%<5B(#'=<54%A(#a"#5B3H%P:1(#%<5%'
a"#"#H
r : 1 | d : 2 | f : 2 | m : 2 | o : 3 | 'SPACE' : 3 | e : 4
Step 2:%b"<>9%:8#%:(##%A(1E%:8#%71::1E%"@H%P:'(:%73%:'K<54%:8#%:?1%>#'=:%A(#a"#5:%B8'('B:#(=%'59%E#(4<54%:8#E
CB(#':#%'%@'(#5:%519#%A1(%:8#EGH%P:1(#%:8#%E#(4#9%B8'('B:#(=%<5%'%5#?%a"#"#$
rd:3
r:1 d:2
SINGLE: f : 2 | m : 2 | o : 3 | 'SPACE' : 3 | e : 4
MERGED: rd : 3
Step 3:%^#@#':%P:#@%,%:8<=%:<E#%'>=1%B15=<9#(<54%:8#%#>#E#5:=%<5%:8#%5#?%a"#"#H%cAX%'59%cEX%:8<=%:<E#%'(#%:8#
:?1%#>#E#5:=%?<:8%:8#%>#'=:%A(#a"#5B3+%=1%?#%E#(4#%:8#E$
rd:3
r:1 d:2
fm:4
f:2 m:2
SINGLE: o : 3 | 'SPACE' : 3 | e : 4
MERGED: rd : 3 | fm : 4
Step 4:%^#@#':%P:#@%*%"5:<>%:8#(#%'(#%51%E1(#%#>#E#5:=%<5%:8#%P;NM6V%a"#"#+%'59%15>3%15#%#>#E#5:%<5%:8#
&V^MV!%a"#"#$
rd:3
r:1 d:2
fm:4
f:2 m:2
o+SPACE:6
o:3 SPACE:3
SINGLE: e : 4
MERGED: rd : 3 | fm : 4 | o+SPACE : 6
rd:3
r:1 d:2
fm:4
f:2 m:2
o+SPACE:6
o:3 SPACE:3
rde:7
e:4
SINGLE:
MERGED: fm : 4 | o+SPACE : 6 | rde: 7
rd:3
r:1 d:2
fm:4
f:2 m:2
o+SPACE:6
o:3 SPACE:3
rde:7
e:4
fmo+SPACE:10
SINGLE:
MERGED: rde: 7 | fmo+SPACE: 10
rd:3
r:1 d:2
fm:4
f:2 m:2
o+SPACE:6
o:3 SPACE:3
rde:7
e:4
fmo+SPACE:10
rdefmo+SPACE:17
SINGLE:
MERGED: rdefmo+SPACE: 17
From Text to Binary
N1?%:8':%?#%7"<>:%1"(%D"AAE'5%:(##+%<:=%:<E#%:1%=##%81?%:1%#5B19#%1"(%1(<4<5'>%E#=='4#%_A##9%E#%E1(#%A119`
<5:1%7<5'(3%B19#H
Step 1:%6'7#>%:8#%7('5B8#=%1A%:8#%D"AAE'5%:(##%?<:8%'%c)X%1(%cTXH%bV%IdNP;PFVNF$%<5%:8<=%#2'E@>#%?#%B81=#%:1
>'7#>%'>>%>#A:%7('5B8#=%?<:8%c)X%'59%'>>%(<48:%7('5B8#=%?<:8%cTXH
Step 2:%F'K<54%15#%B8'('B:#(%':%'%:<E#%A(1E%1"(%E#=='4#+%:('J#(=#%:8#%D"AAE'5%:(##%:1%A<59%:8#%>#'A%519#%A1(
:8':%B8'('B:#(H%F8#%7<5'(3%B19#%A1(%:8#%B8'('B:#(%<=%:8#%=:(<54%1A%)X=%'59%TX=%<5%:8#%@':8%A(1E%:8#%(11:%:1%:8#
>#'A%519#%A1(%:8':%B8'('B:#(H%U1(%#2'E@>#$%cAX%8'=%:8#%7<5'(3%B19#$%100
P1%1"(%E#=='4#%_A##9%E#%E1(#%A119`%7#B1E#=%10000000111111010011110111001000111100110110011
From Binary Code to Text
W#%B'5%'>=1%9#B19#%=:(<54=%1A%)X=%'59%TX=%<5:1%:#2:%"=<54%1"(%D"AAE'5%:(##H%W8':%?1(9%91#=%:8#%B19#
01000011%:('5=>':#%:1e
What About the Rest of the Alphabet?
N1:<B#%:8':%<5%1"(%#2'E@>#%'71J#+%:8#%D"AAE'5%:(##%:8':%?#%7"<>:%91#=%51:%8'J#%'>>%:8#%'>@8'7#:X=%>#::#(=f%=1
?8<>#%?#%B'5%#5B19#%1"(%E#=='4#%'59%=1E#%1:8#(%?1(9=%><K#%_911(`%1(%_9##(`+%<:%?15X:%8#>@%"=%<A%?#%5##9%:1
=#59%'%E#=='4#%B15:'<5<54%'%>#::#(%:8':X=%51:%<5%:8#%:(##H%U1(%1"(%D"AAE'5%#5B19<54%:1%7#%'@@><B'7>#%<5%:8#%(#'>
?1(>9%?#%5##9%:1%7"<>9%'%8"AAE'5%:(##%:8':%B15:'<5=%'>>%:8#%>#::#(=%1A%:8#%'>@8'7#:f%?8<B8%E#'5=%<5=:#'9%1A
"%Efficiency of Huffman Encoding%N1:<B#%:8':%<5%1"(%D"AAE'5%:(##+%:8#%E1(#%A(#a"#5:%'%B8'('B:#(%<=+
:8#%B>1=#(%<:%<=%:1%:8#%(11:+%'59%'=%'%(#=">:%:8#%=81(:#(%<:=%7<5'(3%B19#%<=H%I'5%31"%=##%81?%:8<=%?<>>%(#=">:
<5%B1E@(#==<54%:8#%#5B19#9%:#2:e
"=<54%_A##9%E#%E1(#%A119`%:1%7"<>9%1"(%:(##+%?#%=81">9%"=#%'%:#2:%91B"E#5:%:8':%B15:'<5=%'>>%>#::#(=%1A%:8#
'>@8'7#:%:1%7"<>9%1"(%D"AAE'5%:(##H%]=%'%A"5%#2'E@>#+%8#(#%<=%:8#%D"AAE'5%:(##%:8':%(#=">:=%?8#5%?#%"=#%:8#
:#2:%1A%:8#%!#B>'(':<15%1A%;59#@#59#5B#%:1%7"<>9%<:H
D#(#%<=%:8#%!1234#5%4#5#(':#9%><=:%1A%A<>#=%'59%:8#<(%"=#=H
Implement buildTree() and removeSmallest()
g1"(%A<(=:%:'=K%?<>>%7#%:1%<E@>#E#5:%:8#%buildTree()%A"5B:<15%15%'%HuffmanTreeH%F8<=%A"5B:<15%7"<>9=%'
HuffmanTree%7'=#9%15%'%B1>>#B:<15%1A%=1(:#9%Frequency%17h#B:=H%0>#'=#%=##%:8#%!1234#5%A1(%buildTree()%A1(
9#:'<>=%15%:8#%'>41(<:8EH%g1"%'>=1%?<>>%@(17'7>3%?'5:%:1%B15=">:%:8#%><=:%1A%B15=:("B:1(=%A1(%TreeNode=H
g1"%=81">9%<E@>#E#5:%removeSmallest()%A<(=:%'=%<:%?<>>%8#>@%31"%<5%?(<:<54%buildTree()[
Implement decode()
g1"(%5#2:%:'=K%?<>>%7#%"=<54%'5%#2<=:<54%HuffmanTree%:1%9#B19#%'%4<J#5%7<5'(3%A<>#H%g1"%=81">9%=:'(:%':%:8#%(11:
'59%:('J#(=#%:8#%:(##%"=<54%:8#%9#=B(<@:<15%4<J#5%<5%:8#%!1234#5H%D#(#%<=%:8#%!1234#5%A1(%decode()H
g1"%?<>>%@(17'7>3%A<59%:8#%!1234#5%A1(%BinaryFileReader%"=#A">%8#(#H
W#X(#%"=<54%'%=:'59'(9%stringstream%8#(#%:1%7"<>9%"@%1"(%1":@":H%F1%'@@#59%B8'('B:#(=%:1%<:+%"=#%:8#
A1>>1?<54%=35:'2$
ss << myChar;
Implement writeTree() and readTree()
U<5'>>3+%31"%?<>>%?(<:#%'%A"5B:<15%"=#9%A1(%?(<:<54%HuffmanTrees%:1%A<>#=%<5%'5%#AA<B<#5:%?'3+%'59%'%A"5B:<15%:1
(#'9%:8<=%#AA<B<#5:>3%=:1(#9%A<>#\7'=#9%(#@(#=#5:':<15%1A%'%HuffmanTreeH
D#(#%<=%:8#%!1234#5%A1(%writeTree()%'59%:8#%!1234#5%A1(%readTree()H
g1"%?<>>%@(17'7>3%A<59%:8#%!1234#5%A1(%BinaryFileWriter%"=#A">%8#(#H
Testing Your Code!
W#XJ#%@(1J<9#9%31"%?<:8%'%B1>>#B:<15%1A%9':'%A<>#=%:1%8#>@%31"%#2@>1(#%D"AAE'5%#5B19<54H%^"5%:8#%A1>>1?<54
B1EE'59%:1%91?5>1'9%'59%#2:('B:%:8#%A<>#=H%F8#3%?<>>%7#%<5%'%5#?>3\B(#':#9%data%9<(#B:1(3H
"%Static Keyword%F8#%=:':<B%K#3?1(9%E#'5=%:8':%:8#%J'(<'7>#%1(%A"5B:<15%<=%=8'(#9%73%'>>%<5=:'5B#=%1A
:8#%B>'==H%F8<=%E#'5=%:8':%<A%'%=:':<B%A"5B:<15%<=%"=#9%:8':%<5=<9#%:8#%A"5B:<15+%51%(#A#(#5B#=%:1%:8#
A"5B:<15=%E#E7#(%J'(<'7>#=%E'3%7#%"=#9%C51%'BB#==%:1%this%@1<5:#(GH%P:':<B%A"5B:<15=%B'5%7#%7#5#A<B<'>
?8#5%<:%<=%<5B15J<#5:%:1%E'K#%'%5#?%<5=:'5B#%1A%'%B>'==+%7":%<:%?1">9%7#%5<B#%:1%"=#%:8#%E#E7#(%A"5B:<15H
U1(%#2'E@>#+%<A%31"X(#%<5=<9#%'%E#E7#(%A"5B:<15%'59%?'5:%:1%B'>>%'%=:':<B%A"5B:<15%1A%:8':%B>'==%31"%B'5
91%myStaticHelper(args)%:8#%='E#%?'3%31"X9%B'>>%'51:8#(%E#E7#(%A"5B:<15H
"%Tie Breaking%F1%A'B<><:':#%4('9<54+%E'K#%="(#%:8':%?8#5%7"<>9<54%<5:#(5'>%519#=+%:8#%>#A:%B8<>9%8'=%:8#
=E'>>#=:%A(#a"#5B3H
;5%removeSmallest()+%break ties by taking the front of the singleQueue[
wget
https://courses.engr.illinois.edu/cs225/sp2019/assets/assignments/labs/huffman/lab_huffman_data.tar
&& tar -xf lab_huffman_data.tar && rm lab_huffman_data.tar
W8#5%31"%("5%make+%:?1%@(14('E=%=81">9%7#%4#5#(':#9$%encoder%'59%decoder+%?<:8%:8#%A1>>1?<54%"='4#=$
$ ./encoder
Usage:
./encoder input output treefile
input: file to be encoded
output: encoded output
treefile: compressed huffman tree for decoding
$ ./decoder
Usage:
./decoder input treefile output
input: file to be decoded
treefile: compressed huffman tree to use for decoding
output: decompressed file
Y=#%31"(%encoder%:1%#5B19#%'%A<>#%<5%:8#%9':'%9<(#B:1(3+%'59%:8#5%"=#%31"(%B1E@(#==#9%A<>#%'5%:8#%8"AAE'5
:(##%<:%7"<>:%:1%decode%<:%'4'<5%"=<54%:8#%9#B19#(H%;A%diff\<54%:8#%A<>#=%@(19"B#=%51%1":@":+%31"(%HuffmanTree
=81">9%7#%?1(K<54[
W8#5%:#=:<54+%:(3%"=<54%=E'>>%A<>#=%':%A<(=:%="B8%'=%data/small.txtH%d@#5%<:%"@%'59%>11K%<5=<9#H%;E'4<5#%?8':
:8#%:(##%=81">9%>11K%><K#+%'59%=##%?8':X=%8'@@#5<54%?8#5%31"%("5%31"(%B19#H
N1?%:(3%("55<54%31"(%B19#$
$ ./encoder data/small.txt output.dat treefile.tree
Printing generated HuffmanTree...
______________ 28 _____________
______________/ \______________
______ 11 _____ ______ 17 _____
______/ \______ ______/
\______
s:5 __ 6 __ __ 8 __
__ 9 __
__/ \__ __/ \__
__/ \__
y:3 3 l:4 i:4 4
:5
/ \ /
\
h:1 t:2 2
2
/ \
/ \
\n:1 r:1
o:1 a:1
Saving HuffmanTree to file...
"%Differing Output%;:%<=%@1==<7>#%:1%4#:%9<AA#(#5:%1":@":%:8'5%:8<=%:(##%'59%=:<>>%@'==%B':B8H%Use the
provided test cases on catch to see if your code is passing.
g1"%B'5%'>=1%:#=:%"59#(%B':B8%'=%"="'>%73%("55<54$
make test && ./test
Submitting Your Work
F8#%A1>>1?<54%A<>#=%'(#%"=#9%:1%4('9#%:8<=%'==<45E#5:$
huffman_tree.cpp
huffman_tree.h
partners.txt
]>>%1:8#(%A<>#=%<5B>"9<54%'53%:#=:<54%A<>#=%31"%8'J#%'99#9%?<>>%51:%7#%"=#9%A1(%4('9<54H
Good luck!
#%M"<9#$%D1?%:1%="7E<:%IP%,,.%?1(K%"=<54%4<:
