5 votes 5 votes 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} Algorithms huffman-code + – Pooja Palod asked Dec 3, 2015 • retagged Jun 17, 2022 by makhdoom ghaya Pooja Palod 2.9k views answer comment Share Follow See 1 comment See all 1 1 comment reply Himanshu1 commented Dec 17, 2015 reply Follow Share only code 1 possible. 0 votes 0 votes Please log in or register to add a comment.
4 votes 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 !) Akash Kanase answered Dec 17, 2015 Akash Kanase comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes b is not posiible try to make tree like huffman algo quetion. http://www.cs.umd.edu/class/fall2012/cmsc132h/Projects/P7/project7.html Prashant. answered Dec 3, 2015 • edited Dec 3, 2015 by Prashant. Prashant. comment Share Follow See all 2 Comments See all 2 2 Comments reply minal commented Dec 3, 2015 reply Follow Share 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 ? 5 votes 5 votes Prashant. commented Dec 6, 2015 reply Follow Share wrong here weight not given... so u can take any element as ur requirment. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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/ minal answered Dec 5, 2015 • edited Dec 17, 2015 by minal minal comment Share Follow See all 2 Comments See all 2 2 Comments reply Himanshu1 commented Dec 17, 2015 reply Follow Share Sonam, Huffman coding is minimal , so option 3 also not possible. 0 votes 0 votes minal commented Dec 17, 2015 reply Follow Share yes code 3 is also not possible ... 0 votes 0 votes Please log in or register to add a comment.
0 votes 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 srestha answered Dec 3, 2015 srestha comment Share Follow See all 2 Comments See all 2 2 Comments reply Prashant. commented Dec 3, 2015 reply Follow Share just flip the above tree u got code 3 0 votes 0 votes अनुराग पाण्डेय commented Dec 5, 2015 i edited by अनुराग पाण्डेय Dec 5, 2015 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.