huffman coding

Question

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}

Comments

only code 1 possible.

Answer 1

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 !)

Answer 2

b is not posiible

try to make tree like huffman algo quetion.

http://www.cs.umd.edu/class/fall2012/cmsc132h/Projects/P7/project7.html

Comments

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 ?

---

wrong here weight not given...

so u can take any element as ur requirment.

Answer 3

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/

 

Comments

Sonam, Huffman coding is minimal , so option 3 also not possible.

---

yes code 3 is also not possible ...

Answer 4

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

Comments

just flip the above tree u got code 3

---

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