Proof of the Optimality of Huffman Code

웹에 있는 것들 중에 http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L9.pdf 파일이 가장 쉬운 것 같다.

Lemma 1. 가장 작은 두 글자가 가장 long leaf에 sibling으로 있는 것이 optimal 하다.

직관적으로도 그렇고, 계산도 pdf에 있다.

Lemma 2. optimal한 tree를 통해 (longer or original) optimal한 tree를 얻는다. 다시말해,
x,y를 합해서 z라는 노드를 만들었다면, [z를 포함하면서 optimal한 tree]에서 z만 x,y로 바꿔 [x,y를 포함하는 optimal tree]를 얻는다.

 contradiction으로 증명. 이하 [x를 포함하는 optimal tree]를 \(T_x\)로 줄여 표시함.
\(T_z\)에서 z만 x,y로 나눈 트리를 \(T_{x,y}\)라 하고, \(T_{x,y}\)와 다른 optimal tree(물론 이때 Lemma 1을 만족해야 한다)의 존재 \(T_{x,y} '\)을 가정한다. \(T_{x,y} '\)을 통해 \(T_z '\)을 얻을 수 있는데, \(T_z '\)의 비용이 \(T_z\)보다 작음을 계산을 통해(pdf에 나옴) 보일 수 있다. 이는 \(T_z\)가 optimal하다는 가정에 위배.

위 두 Lemma를 통해 증명 끝.




I think http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L9.pdf \(\leftarrow\) this file is most understandable.

Lemma 1. Let the most frequent two letters are, then the two letters must be at the longest leaf as a sibling. That's optimal.
 Reference that pdf file, which shows concrete calcuation.

Lemma 2. We can get a longer optimal tree by using a smaller optimal tree. For example, if a node z is got by x, y node, we can get [the optimal tree including x, y] from [the optimal tree including z] by only substituting z by x, y.
 Let's say [the optimal tree including x] as \(T_x\), and \(T_{x,y}\) is the tree including x, y which are split from z. And assume the optimal tree \(T_{x,y} '\) that is not equal to \(T_{x,y}\). Surely \(T_{x,y} '\) must be subject to Lemma 1. Then we can get \(T_z '\) from \(T_{x,y} '\), and show cost of \(T_z '\) is smaller then the cost of \(T_z\). See the pdf file for precise calculation. This is contradictory.


From these, proof is done immediately.