2●算法伪码

设C是字符集，任意一个字符c的频率为f(c)；x、y是C中具有最小频率的两个字符。

(1) 贪心选择性质——存在从贪心选择开始的最优解。

需证明存在字符集C的一个最优前缀码方案T，使得x、y具有相同的码长，且最后一位编码不同。

如果T中，x、y是最深的叶子且互为兄弟，那么T就是贪心选择开始的最优前缀码； 

如果T中，x、y不是最深的叶子，也不是兄弟，那么设T中字符b、c是最深的叶子且互为兄弟，如图1所示。

由于x,y是字符集C中频率最小的两个字符，所以有f(x)≤f(b)、f(x)≤f(c)、f(y)≤f(b)、f(y)≤f(c)，交换树T中的字符x和字符b得到树T′，如图2所示。

■ 图1 树T结构示意图      ■ 图2 树T′结构示意

又f(x)-f(b)≤0，d_T(x)-d_T(b)≤0，

故B(T)-B(T′)≥0，B(T)≥B(T′)。

再交换字符y和字符a，得到树T″，如图3所示。

■ 图3  树T″结构示意

同理可以证明B(T′)≥B(T″)，由此B(T)≥B(T″)。

又因为T是字符集C的最优前缀码，所以B(T)≤B(T″)。所以B(T)=B(T″)，T″中，x、y字符处于最深处且互为兄弟，是从贪心选择开始的最优解。

（2) 最优子结构性质——整体最优解一定包含子问题的最优解。

设T是字符集C的最优前缀码，令f(z)=f(x)+f(y)，则T′是字符集C′=C-{x,y}+{z}的最优前缀码。

需要证明T′是字符集C′=C-{x,y}+{z}的最优前缀码。

证明： 假设T′不是字符集C′的最优前缀码，则设T″是字符集C′的最优前缀码，B(T′)>B(T″)。

将字符x、y加入到T″中，作为字符z的孩子，构成的树为T"'，则有T"'是字符集C的一种编码方案。

对任意字符c∈C-{x,y}，有d_T(c)=d_T′(c)，故f(c)d_T(c)=f(c)d_T′(c)，另一方面d_T(x)=d_T(y)=d_T(z)+1。

则

由此，可以知道，B(T)=B(T′)+f(x)+f(y)，同理有B(T'″)=B(T″)+f(x)+f(y)。

由于B(T′)>B(T″)，所以B(T)>B(T'″)。

这说明T不是字符集C的最优前缀码，这与T是字符集C的最优前缀码矛盾，假设不真，得证。