1.1编码方案二进制Huffman编码三进制Huffman编码1.编码方案2.例子及伪代码二叉树三叉树3.正确性证明4.推广Vn≥2（nEN），都可按照huffman方法构造出满二叉树那么对于三叉树呢？？？每次将3个结点合并成1个，相当于减少了两个，则我们可以得出n=2k+1（k是合并的次数）可见只有奇数才可以这样合并成满三叉树。那么对于偶数怎么办？
1. 编码方案 2. 例子及伪代码 3. 正确性证明 4. 推广 1.1 编码方案 二进制Huffman编码 三进制Huffman编码 二叉树 三叉树 ∀𝑛 ≥ 2 𝑛 ∈ 𝑁 ，都可按照huffman方法构造出满二叉树 那么对于三叉树呢？？？ 每次将3个结点合并成1个，相当于减少了两个，则我们可 以得出𝑛 = 2k + 1(𝑘是合并的次数),可见只有奇数才可以这样合 并成满三叉树。那么对于偶数怎么办？
1.1编码方案编码方案1.方法：添加一个结点，并将这个结点的出现频率设为0.很显然总的代2.例子及伪代码价没有变化。则仿照二进制Huffman编码的编码方案，我们可以得到三进制编码方3.正确性证明案：①选取字母表中出现频率最低的三个结点。4.推广②将这三个结点合并成一个结点，其出现频率为三个结点出现频率之和。③重复上述步骤，直到构建出一棵满三叉树
1. 编码方案 2. 例子及伪代码 3. 正确性证明 4. 推广 1.1 编码方案 方法：添加一个结点，并将这个结点的出现频率设为0. 很显然总的代 价没有变化。 则仿照二进制Huffman编码的编码方案，我们可以得到三进制编码方 案： ① 选取字母表中出现频率最低的三个结点。 ② 将这三个结点合并成一个结点，其出现频率为三个结点出现 频率之和。 ③ 重复上述步骤，直到构建出一棵满三叉树
2.1例子c:13d:12b:16编码方案[a]2.例子及伪代码b:16c:13d:12a:423.正确性证明d:12b:16c13e:9f:5g:34.推广b[a]d:12C:13[e]
1. 编码方案 2. 例子及伪代码 3. 正确性证明 4. 推广 2.1例子
2.2伪代码HUFFMAN(C)1n=|Cl1.编码方案2Q=C2.例子及伪代码for i=1 to n-l34allocatea new nodea3.正确性证明5Q.left=x=EXTRACT-MIN(Q)4推广6α.middle=y=EXTRACT-MIN(Q)7α.right=z=EXTRACT-MIN(Q)8Q.freq=x.freq+y.freq+z.freq9INSERT(Q,α)10return EXTRACT-MIN(Q)
1. 编码方案 2. 例子及伪代码 3. 正确性证明 4. 推广 2.2伪代码
3，1贪心选择性质的证明仿照TC上（装模作样）给出一个命题：令c为一个字母表，其中每个字符cEC都有一个频率c.freq。令x，y和z是c频率最低的三个字符1.编码方案那么存在c的一个最优前缀码，xyz的码字长度相同，且只有最后一个三进制位不同。2.例子及伪代码证明：令a，b，c是T（任意一个最优前缀码所对应的编码树）深度最大的兄弟叶结点，不失一般性，我们3.正确性证明不妨假设a.freq≤b.freq≤c.freq且x.freq≤y.freq≤z.freq。由于xy,z是叶结点中出现频率最低的三个字符，而a,b,c是任意的三个字符，因此我们有x.freq≤a.freq、y.freq≤4.推广b.freq和z.freq≤c.freq。如果有x.freq=c.freq，那么会出现x.freq=y.freq=z.freq=a.freq=b.freqc.freq。此时显然成立。所以我们假定x丰c。②如果x.freq=b.freq，那么会出现x.freq=y.freq=a.freq=b.freq，此时我们用x,y交换a,b,形成T'，显然T和T两个树的效果等价，均为最优前缀编码对应的树，我们在T中用z交换c形成一个新树T”那么在T"中x,y,z是深度最深的三个兄弟叶结点，根据公式我们得到T和T"代价之差为B(T") -B(T') = Zcec c. freq * dr-(c) -Ecec c. freq * dr,(c)= (c. freq - z. freq) * (dr(z) -dr'(c)) ≤ 0.其中c.freq一z.freq)非负，（d(z)一d(c))非正
1. 编码方案 2. 例子及伪代码 3. 正确性证明 4. 推广 3.1贪心选择性质的证明 仿照TC上（装模作样）给出一个命题： 令C为一个字母表，其中每个字符 c ∈ 𝐶都有一个频率c.freq。令x , y和z是C频率最低的三个字符， 那么存在C的一个最优前缀码，x,y,z的码字长度相同，且只有最后一个三进制位不同。 证明： 令a,b,c是T（任意一个最优前缀码所对应的编码树）深度最大的兄弟叶结点，不失一般性，我们 不妨假设a. 𝑓𝑟𝑒𝑞 ≤ 𝑏. 𝑓𝑟𝑒𝑞 ≤ 𝑐. 𝑓𝑟𝑒𝑞且𝑥. 𝑓𝑟𝑒𝑞 ≤ 𝑦. 𝑓𝑟𝑒𝑞 ≤ 𝑧. 𝑓𝑟𝑒𝑞。由于x, 𝑦, 𝑧是叶结点中出现频率 最低的三个字符，而a,b,c是任意的三个字符，因此我们有𝑥. 𝑓𝑟𝑒𝑞 ≤ 𝑎. 𝑓𝑟𝑒𝑞、𝑦. 𝑓𝑟𝑒𝑞 ≤ 𝑏. 𝑓𝑟𝑒𝑞和𝑧. 𝑓𝑟𝑒𝑞 ≤ 𝑐. 𝑓𝑟𝑒𝑞。 ①如果有x. 𝑓𝑟𝑒𝑞 = 𝑐. 𝑓𝑟𝑒𝑞，那么会出现𝑥. 𝑓𝑟𝑒𝑞 = 𝑦. 𝑓𝑟𝑒𝑞 = 𝑧. 𝑓𝑟𝑒𝑞 = 𝑎. 𝑓𝑟𝑒𝑞 = 𝑏. 𝑓𝑟𝑒𝑞 = 𝑐. 𝑓𝑟𝑒𝑞。此时显然成立。所以我们假定𝑥 ≠ 𝑐。 ②如果𝑥. 𝑓𝑟𝑒𝑞 = 𝑏. 𝑓𝑟𝑒𝑞，那么会出现𝑥. 𝑓𝑟𝑒𝑞 = 𝑦. 𝑓𝑟𝑒𝑞 = 𝑎. 𝑓𝑟𝑒𝑞 = 𝑏. 𝑓𝑟𝑒𝑞，此时我们用 𝑥, 𝑦交换𝑎, b, 形成𝑇 ′ , 显然T和T‘两个树的效果等价，均为最优前缀编码对应的树，我们在T’中用z交 换c形成一个新树T”,那么在T”中x,y,z是深度最深的三个兄弟叶结点，根据公式我们得到T’和T”代价之 差为 B(𝑇") − 𝐵(𝑇′) = σ𝑐∈𝐶 𝑐. 𝑓𝑟𝑒𝑞 ∗ 𝑑𝑇"(𝑐) − σ𝑐∈𝐶 𝑐. 𝑓𝑟𝑒𝑞 ∗ 𝑑𝑇′ (𝑐) = 𝑐. 𝑓𝑟𝑒𝑞 − 𝑧. 𝑓𝑟𝑒𝑞 ∗ 𝑑𝑇 ′ 𝑧 − 𝑑𝑇 ′ 𝑐 ≤ 0. 其中(𝑐. 𝑓𝑟𝑒𝑞 − 𝑧. 𝑓𝑟𝑒𝑞)非负， 𝑑𝑇 ′ 𝑧 − 𝑑𝑇 ′ 𝑐 非正