Consider the following seemingly meaningless sentence: MAT CAT MAN MITTEN MAM ME
ID: 3206272 • Letter: C
Question
Consider the following seemingly meaningless sentence: MAT CAT MAN MITTEN MAM MEN EATEN. Estimate the probabilities of each of the symbols in the sentence by computing the relative frequency of the symbols. You may ignore spaces. Compute the average information for the sentence. Obtain the Huffman code for each of the symbols in the sentence. Determine the average length of the code words. HUFFMAN ALGORITHM Arrange the symbols in order of decreasing probability. If the probabilities are equal, break the tie randomly. Combine the two smallest values in the list to form a new entry whose probability is the sum of the two original entries. Continue combining two smallest values in the modified list (original untouched values and the new entry) until the root of the tree is reached. Assign bits from left to right on the tree: at each branch, assign a 0 to the higher valued branch and a 1 to the other. Form the code words by reading from the root to the node of the symbol.Explanation / Answer
Frequency of M=6
Frequency of A=5
Total count= 26
Frequency of N=4, probability = 4/26
Frequency of E=4,probability = 4/26
Frequency of C=1,probability = 1/26
Frequency of T=5,probability = 5/26
Frequency of I=1,probability = 1/26