Hauffman practice
Java代写 | 算法代写 | 数据结构代写 – 这个题目属于一个java的代写任务, 是比较典型的java等代写方向，涉及了算法和数据结构等方面的内容
####### 16.5. PROBLEM SET
16.5 Problem set
####### Problem 16.5.1. Write a class called Hauffman as explained in figures below.
HauffmanTest.java
######## 1 /**
2 * File Name: HauffmanTest.java
3 * Test Hauffman encode and decode algorithms
4 *
5 * @author Jagadeesh Vasudevamurthy
6 * @year 2016
7 */
8
9 public class HauffmanTest{
10 private static final IntUtil u = new IntUtil();
11
12 public static void test1(String s, boolean show, String dotfilename) {
13 Hauffman h = new Hauffman(s,show,dotfilename);
14 String d = h.decode();
15 String f = h.encode();
16 u .myassert(s.equals(f)) ;
17 double sl = s.length() * 7 ;
18 double dl = d.length();
19 System. out .println("Original string cost = " + sl) ;
20 System. out .println("Decoded string cost = " + dl) ;
21 double r = ((dl - sl)/sl) * 100 ;
22 System. out .println("% reduction = " + (-r)) ;
23 }
24
25 public static void testbed() {
26 boolean show = true ;
27 test1 ("a",show,"C:\\work\\java\\fig\\1.dot");
28 test1 ("aba",show,"C:\\work\\java\\fig\\2.dot");
29 test1 ("aaabbggggghhhhaaaggggaaaaa_+@#",show,"C:\\work\\java\\fig\\3.dot");
30 test1 ("A quick brown fox jumps over the lazy dog",show,"C:\\work\\java\\fig\\4.dot");
31 test1 ("Pack my box with five dozen liquor jugs",show,"C:\\work\\java\\fig\\5.dot");
32 test1 ("Long years ago we made a tryst with destiny, and now the time comes when we shall
redeem our pledge, not wholly or in full measure, but very substantially.At the stroke of the
midnight hour, when the world sleeps, India will awake to life and freedom. A moment comes,
which comes but rarely in history, when we step out from the old to the new, when an age ends,
and when the soul of a nation, long suppressed, finds utterance.",show,"C:\\work\\java\\fig\
\6.dot");
33 test1 ("Baa, baa, black sheep, have you any wool?",show,"C:\\work\\java\\fig\\7.dot") ;
34
35 if (show) {
36 System. out .println("=============== Done with Test1 ==================") ;
37 }
38 }
39
40 public static void main(String[] args) {
41 System. out .println("HauffmanTest.java");
42 testbed () ;
43 System. out .println(" All Hauffman Test passed. You are great. You should get an award");
44 }
45
46 }
Page 1
####### 447
####### 16.5. PROBLEM SET
####### ============ Baa, baa, black sheep, have you any wool? +++++++++++++++
####### occurs 7 times
####### a occurs 7 times
####### B occurs 1 times
####### b occurs 2 times
####### c occurs 1 times
####### e occurs 3 times
####### h occurs 2 times
####### k occurs 1 times
####### , occurs 3 times
####### l occurs 2 times
####### n occurs 1 times
####### o occurs 3 times
####### p occurs 1 times
####### s occurs 1 times
####### u occurs 1 times
####### v occurs 1 times
####### w occurs 1 times
####### y occurs 2 times
####### ? occurs 1 times
####### ==== Tree built in this order===============
####### Leaf node 1 Character is Weight is 7
####### Leaf node 2 Character is a Weight is 7
####### Leaf node 3 Character is B Weight is 1
####### Leaf node 4 Character is b Weight is 2
####### Leaf node 5 Character is c Weight is 1
####### Leaf node 6 Character is e Weight is 3
####### Leaf node 7 Character is h Weight is 2
####### Leaf node 8 Character is k Weight is 1
####### Leaf node 9 Character is , Weight is 3
####### Leaf node 10 Character is l Weight is 2
####### Leaf node 11 Character is n Weight is 1
####### Leaf node 12 Character is o Weight is 3
####### Leaf node 13 Character is p Weight is 1
####### Leaf node 14 Character is s Weight is 1
####### Leaf node 15 Character is u Weight is 1
####### Leaf node 16 Character is v Weight is 1
####### Leaf node 17 Character is w Weight is 1
####### Leaf node 18 Character is y Weight is 2
####### Leaf node 19 Character is? Weight is 1
STEP 1
STEP 2
####### Figure 16.4: Step 1 and Step 2 of the Hauffman algorithm
####### CHAPTER 16. GREEDY ALGORITHMS
Programmer's Notepad - t.dot
!"""##"-DJDGHHVK"9DVXGHYDPXUWK\"####
2"""##"GRW"47SGI"&9?ZRUN?MDYD?ILJ?W?GRW"4R"&9?ZRUN?MDYD?ILJ?W?GRW?SGI
@"""GLJUDSK"J"^
B""""ODEHO" "F"%DDH"EDDH"EODFN"VKHHSH"KDYH"\RX"DQ\"ZRRO""F
L""""F@M?QB!F"4!F@L?Q!OF">FRORU UHG@
O""""F@M?QB!F"4!F@O?Q2LF">FRORU EOXH@
M""""F@L?Q!OF"4!F@!?QRF">FRORU UHG@
R""""F@L?Q!OF"4!F@2?QRF">FRORU EOXH@
S""""F@O?Q2LF"4!F@@?Q!!F">FRORU UHG@
!T""""F@O?Q2LF"4!F@B?Q!BF">FRORU EOXH@
!!""""F@!?QRF"4!F2L?QBF">FRORU UHG@
!2""""F@!?QRF"4!F2R?QBF">FRORU EOXH@
!@""""F@2?QRF"4!F2M?QBF">FRORU UHG@
!B""""F@2?QRF"4!F2O?QBF">FRORU EOXH@
!L""""F@@?Q!!F"4!F2S?QLF">FRORU UHG@
!O""""F@@?Q!!F"4!F@T?QOF">FRORU EOXH@
!M""""F@B?Q!BF"4!F2?QM?Q"DF">FRORU UHG@
!R""""F@B?Q!BF"4!F!?QM?Q"EODQNF">FRORU EOXH@
!S""""F2L?QBF"4!F!R?Q2?Q"\F">FRORU UHG@
2T""""F2L?QBF"4!F2B?Q2F">FRORU EOXH@
2!""""F2R?QBF"4!FB?Q2?Q"EF">FRORU UHG@
22""""F2R?QBF"4!FM?Q2?Q"KF">FRORU EOXH@
2@""""F2M?QBF"4!F2T?Q2F">FRORU UHG@
2B""""F2M?QBF"4!F!T?Q2?Q"OF">FRORU EOXH@
2L""""F2O?QBF"4!F2!?Q2F">FRORU UHG@
2O""""F2O?QBF"4!F22?Q2F">FRORU EOXH@
2M""""F2S?QLF"4!F2@?Q2F">FRORU UHG@
2R""""F2S?QLF"4!F!2?Q@?Q"RF">FRORU EOXH@
2S""""F@T?QOF"4!FS?Q@?Q"HF">FRORU UHG@
@T""""F@T?QOF"4!FO?Q@?Q"HF">FRORU EOXH@
@!""""F2B?Q2F"4!F!B?Q!?Q"VF">FRORU UHG@
@2""""F2B?Q2F"4!F!L?Q!?Q"XF">FRORU EOXH@
@@""""F2T?Q2F"4!F@?Q!?Q"%F">FRORU UHG@
@B""""F2T?Q2F"4!FL?Q!?Q"FF">FRORU EOXH@
@L""""F2!?Q2F"4!FR?Q!?Q"NF">FRORU UHG@
@O""""F2!?Q2F"4!F!O?Q!?Q"YF">FRORU EOXH@
@M""""F22?Q2F"4!F!M?Q!?Q"ZF">FRORU UHG@
@R""""F22?Q2F"4!F!S?Q!?Q""F">FRORU EOXH@
@S""""F2@?Q2F"4!F!!?Q!?Q"QF">FRORU UHG@
BT""""F2@?Q2F"4!F!@?Q!?Q"SF">FRORU EOXH@
B!"""`
B2"""
Page 1, 8/10/2016 - 4:15:09 PM
####### Figure 16.5: Step 3 of the Hauffman algorithm
####### Copyright c Jagadeesh Vasudevamurthy – Do not photocopy. 449
####### 16.5. PROBLEM SET
Unique name
Weight
character
"37\n41" ->"35\n16" [color=red]
"37\n41" ->"36\n25" [color=blue]
"23\n2" ->"13\n1\n p" [color=blue]
"23\n2" ->"11\n1\n n" [color=red]
####### Figure 16.6: Binary tree created by Hauffman algorithm
####### CHAPTER 16. GREEDY ALGORITHMS
============Code for each character in Baa, baa, black sheep, have you any wool? ===============
Has Code 111
a Has Code 110
b Has Code 0010
B Has Code 01000
c Has Code 01001
e Has Code 1011
h Has Code 0011
k Has Code 01100
l Has Code 0101
, Has Code 1010
n Has Code 10000
o Has Code 1001
p Has Code 10001
s Has Code 00010
u Has Code 00011
v Has Code 01101
w Has Code 01110
y Has Code 0000
? Has Code 01111
======= Original String========
Baa, baa, black sheep, have you any wool?
======= Decoded String========
01000110110101011100101101101010111001001011100100101100111000
10001110111011100011010111001111001101101111100001001000111111
101000000001110111010011001010101111
======= Recovered String========
Baa, baa, black sheep, have you any wool?
Original string cost = 287.
Decoded string cost = 160.
% reduction = 44.
public static void test1(String s, boolean show, String dotfilename) {
Hauffman h = new Hauffman(s,show,dotfilename);
String d = h.encode();
String f = h.decode();
u.myassert(s.equals(f)) ;
double sl = s.length() * 7 ;
double dl = d.length();
System.out.println("Original string cost = " + sl) ;
System.out.println("Decoded string cost = " + dl) ;
double r = ((dl - sl)/sl) * 100 ;
System.out.println("% reduction = " + (-r)) ;
}
boolean show = true ;
test1("Baa, baa, black sheep, have you any wool?",show,"7.dot") ;
HauffmanTest.java
email only
1.Hauffman.java
2.dotfile.pdf
3.Screen shot
Cannot change anything
Hauffmantest.java
All tests must pass
STEP 4
Step 5
Step 6
You are free to use any object
from java library
####### Figure 16.7: Step 4 and Step 5 of the Hauffman algorithm