适应性哈夫曼编码

答：在哈夫曼编码中，有个缺点是除了压缩后的资料外，它还得传送机率表给解码端，否则解码端无法正确地做解码的工作。 如果想要压缩好一点，必须有更多的统计资料，但同时必须要送出更多的统计资料到解压缩端。 而适应性编码可以利用已经读过的资料机动的调整哈夫曼树。 适应性哈夫曼编码中，算法FGK的基本原则是根据兄弟性质（Sibling Property），由Gallager定义。 一颗哈夫曼树只是一棵在每个节点，包括树叶与内节点，加上加权值得二叉树，除了树根外，每一个节点都有一个兄弟节点与其共有一个父亲节点。 如果每一个节点可以按照加权值从小排列到大且每个节点又再自己的兄弟相邻，称为兄弟性质。 修改、或更新一棵哈夫曼树包括两个步骤。

答：赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。 每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。 a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001… 可以算出本例的信源熵为2.61bit，二者已经是很接近了。

答：由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者 香农 共同研究过类似编码的导师。 哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。