g Suppose we want to compress a text consisting of 6 characters,a, b, c, d, e, fusingthe Huffman Algorithm. Give an example for
which the algorithm produces at least onecodeword of length 5. In other words, you are being asked to give a set of the characterfrequencies that results in the deepest tree.
1 answer:
Answer:
e(a) = 0
e(b) = 10
e(c) = 110
e(d) = 1110
Explanation:
The Worst case will happen when f(a) > 2*f(b) ; f(b) > 2*f(c) ; f(c) > 2*f(d) ; f(d) > 2*f(e) and f(e) > 2*f(f).
Where f(x) is frequency of character x.
Lets consider the scenario when
f(a) = 0.555, f(b) = 0.25, f(c) = 0.12, f(d) = 0.05, f(e) = 0.02 and f(f) = 0.005
Please see attachment for image showing the steps of construction of Huffman tree:- see attachment
From the Huffman tree created, we can see that endcoding e() of each character are as follows:-
e(a) = 0
e(b) = 10
e(c) = 110
e(d) = 1110
e(e) = 11110
e(f) = 11111
So we can see that maximum length of encoding is 5 in this case.
You might be interested in
Answer:
User Datagram Protocol (UDP) , transport-layer segment.
Explanation:
The User Datagram Protocol is popularly known as UDP. It is defined as the communication protocol which is used across the internet for any time sensitive transmission like the DNS lookup or the video playback.
The UDP provides a unreliable and connectionless service to a invoking application.
The transport layers on sending side converts the application messages which it
from the
into a transport layer segment called as the transport layer segments. This is achieved by breaking down the application messages into a smaller chunks and then adding the transport layer header into each chunk so as to create a transport layer segment.