WHITE SPACES ARE NOT COUNTED!!!!! WHITE SPACES ARE NOT COUNTED!!!!! WHITE SPACES
ID: 3820086 • Letter: W
Question
WHITE SPACES ARE NOT COUNTED!!!!!
WHITE SPACES ARE NOT COUNTED!!!!!
WHITE SPACES ARE NOT COUNTED!!!!!
WHITE SPACES ARE NOT COUNTED!!!!!
WHITE SPACES ARE NOT COUNTED!!!!!
Consider the sentence, "DOGS DO NOT SPOTHOT POTS OR CATS." Draw the frequency table and Huffman tree, using the algorithm in the supplementary lecture notes, for the letters in the sentence. The table should have three columns: letter, frequency and code. For the initial contents of the priority queue, when letters have the same frequency, they are enqueued in lexicographical order.Explanation / Answer
"DOGS DO NOT SPOT HOT POTS OR CATS"
Distinct Letters S = {A, C, D, G, H,N,O,P,R,S,T}
Table:
Letter - Frequency - Bits
A - 1 - 111110
C - 1 - 1111110
D - 2 - 1110
G - 1 - 11111110
H - 1 - 111111110
N - 1 - 1111111111
O - 7 - 0
P - 2 - 11110
R - 1 - 1111111110
S - 4 - 110
T - 5 - 10
Huffman Algorithm:
Arrange the letters in the decreasing order of their frequency
0, T, S, D, P, A, C, G, H, N, R
Tree: (left child = 0 , right child: 1)
26
O:7 19
T:5 14
S:4 10
D:2 8
P:2 6
A:1 5
C:1 4
G:1 3
H:1 2
R:1 N:1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.