Talk:Huffman coding: Difference between revisions

Line 215:

''Important : This method does not generate the optimal Huffman tree for any given string; it suffers from a serious flaw because of the fact that elements in a c++ priority queue are ordered according to strict weak ordering. To see why, please check out [http://www.google.co.in/url?sa=t&rct=j&q=huffman%20coding&source=web&cd=2&ved=0CC0QFjAB&url=http%3A%2F%2Fcs.nyu.edu%2F~melamed%2Fcourses%2F102%2Flectures%2Fhuffman.ppt&ei=wS7zTo2qJIesrAeHgoniDw&usg=AFQjCNEmui64FKCEKp21t08xAh_satIlkw&sig2=jebypPEfbn0G4VdWcrlV3A&cad=rja this example]. It shows that the optimal huffman tree for the given line of text will have no code longer than 4 bits. This piece of code generates huffman codes which are 5 bits in size. Try running it with the same line of text as input and you can verify this.''

I dispute these statements. First of all, the linked PowerPoint presentation incorrectly encodes the text in their example given their own encoding they generated. It says that it takes 73 bits; however, the correct ~~encoding~~ is <tt>000010110000011001110001010110101111011010111001111101011111100011001111110100100101</tt>, which is 84 bits. Secondly, nowhere in the PowerPoint does it "show that the optimal huffman tree ... will have no code longer than 4 bits". It merely shows that that particular optimal Huffman coding (one of many possible ones which are equally optimal) has no code longer than 4 bits. In fact, if you take the C++ code and run the same example string, you will get an encoding which, although it uses 5-bit codes for some characters, still encodes the string in 84 bits, so is equally optimal. Finally, the PowerPoint does not mention any "serious flaw because of the fact that elements in a c++ priority queue are ordered according to strict weak ordering", and I can't seem to make sense of this statement. --[[User:Spoon!|Spoon!]] 11:21, 26 December 2011 (UTC)

I dispute these statements. First of all, the linked PowerPoint presentation incorrectly encodes the text in their example given their own encoding they generated. It says that it takes 73 bits; however, the correct encoded string is <tt>000010110000011001110001010110101111011010111001111101011111100011001111110100100101</tt>, which is 84 bits. Secondly, nowhere in the PowerPoint does it "show that the optimal huffman tree ... will have no code longer than 4 bits". It merely shows that that particular optimal Huffman coding (one of many possible ones which are equally optimal) has no code longer than 4 bits. In fact, if you take the C++ code and run the same example string, you will get an encoding which, although it uses 5-bit codes for some characters, still encodes the string in 84 bits, so is equally optimal. Finally, the PowerPoint does not mention any "serious flaw because of the fact that elements in a c++ priority queue are ordered according to strict weak ordering", and I can't seem to make sense of this statement. --[[User:Spoon!|Spoon!]] 11:21, 26 December 2011 (UTC)