The Gateway to Computer Science Excellence
+5 votes
829 views
we use huffman encoding to encode a b c with frequency fa fb fc.Which of the following code sequence is not possible?

code 1={0,10,11}

code 2={0,00,1}

code 3={10,00,01}
in Algorithms by Boss (31.4k points) | 829 views
0
only code 1 possible.

4 Answers

+4 votes
Only code 1  is possible

Code 2 and code 3 is not possible.

Code 2 => 0 & 00. Here give 000, we can not distinguish 0 00 and 00 0 and 0 0 0.

Code 3 => Here issue is that this code can not be generated by Huffman algorithm in first place. It is simply not possible. (Try to take any example you can see you can not generate this. You can generate (00,01,10,11) but not just 3 of those !)
by Boss (41.9k points)
+1 vote
b is not posiible

try to make tree like huffman algo quetion.

http://www.cs.umd.edu/class/fall2012/cmsc132h/Projects/P7/project7.html
by Veteran (63k points)
edited by
+5
3rd one also , we just take two minimum frequency and add them and again repeat this , so here only 3 a,b,c so first we take 2 minimum add them and take last remaining one , so after root 1st level only one (aor b or c) which will be encoded by only 1 bit  and last level only 2(ab or bc or ca ) they will be encoded by 2 bits ... so only 1 is possible , 2 and 3 rd both are not possible  rt ?
0
wrong here weight not given...

so u can take any element as ur requirment.
+1 vote

Huffman coding makes sure that there is no ambiguity when we decode the bit stream code .so the The variable-length codes assigned to input characters are Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character.

so code 1 which is possible ...this follow the prefix property ... ( no prefix is otherone prefix)..

code 2 which is not possible ... bcoz 00 does not follow the prefix property , 0 is code 00 also contain 0 as prefix , 

code 3  it follows prefix property  but one of them should be only one bit code ....so its not possible..

ref :http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

 

by Boss (17.1k points)
edited by
0
Sonam, Huffman coding is minimal , so option 3 also not possible.
0
yes code 3 is also not possible ...
0 votes

I think code2 and code3 are not possible

Code2 = last level of code should be 1 bit. 0 and 1 in the same huffman tree and then 2 bit code 00 not possible.If the tree at the last level ended with 0 , the extended part will be 10 and 11.(See pic)

Code3= not possible as all 2 bit code. As we know last level of code of huffman tree must be 1 bit

by Veteran (119k points)
0
just flip the above tree u got code 3
0

In huffman encoding symbols being encoded must be at the leaves of the huffman tree & not in the inner nodes.So code 2 is impossible for sure 

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,388 answers
198,575 comments
105,413 users