Dear Student, In order to prove the correctness of Huffman Encoding, you have to show that any tree that differs from the one constructed by Huffman algorithm can be transformed into one that is equal to tree without increasing its costs. Huffman’s The cost of any encoding tree is T Where, is any optimal prefix code tree with two siblings and at the maximum depth of the T b c tree. (See Figure 7.2 on handouts page 102) The cost of encoding tree T/ is: B(T/) is the Huffman tree that is transformed by exchanging position of x and b, y and c are left intact. (See Figure 7.3 on handouts page 103) B(T/) p(b)d(b) + p(b)d(x) = B(T) − p(x)d(x) + p(x)d(b) − (px)d(x) is the term showing the position of x in BT in which positions were not swapped. As this term does not appear in new tree, so you will subtract this term. P(x)d(b) is term in which position of x is exchanged with b but its probability remains the same. This term is belonging to transformed tree so you will add this term. As b has also changed its position, so you will subtract term p(b)d(b). p(b)d(x) is the term after swapped position. So, you will add this term here. After solving this expression you get B(T/) < = B(T) which means cost does not increase, so we can say T/ is optimal tree. If you still face any difficulty, feel free to ask. Regards,
Dear Student, In order to prove the correctness of Huffman Encoding, you have to show that any tree that differs from the one constructed by Huffman algorithm can be transformed into one that is equal to Huffman’s tree without increasing its costs. The cost of any encoding tree T is Where, T is any optimal prefix code tree with two siblings b and c at the maximum depth of the tree. (See Figure 7.2 on handouts page 102) The cost of encoding tree T/ is: B(T/) is the Huffman tree that is transformed by exchanging position of x and b, y and c are left intact. (See Figure 7.3 on handouts page 103) B(T/) = B(T) − p(x)d(x) + p(x)d(b) − p(b)d(b) + p(b)d(x) (px)d(x) is the term showing the position of x in BT in which positions were not swapped. As this term does not appear in new tree, so you will subtract this term. P(x)d(b) is term in which position of x is exchanged with b but its probability remains the same. This term is belonging to transformed tree so you will add this term. As b has also changed its position, so you will subtract term p(b)d(b). p(b)d(x) is the term after swapped position. So, you will add this term here. After solving this expression you get B(T/) < = B(T) which means cost does not increase, so we can say T/ is optimal tree. If you still face any difficulty, feel free to ask. Regards,
Huffman%20Encoding%20Correctness.docx