|
|
|
动态哈夫曼编码的改进
|
| |
该文所附的动态哈夫曼编码数据压缩与解压源程序中的update函数是动态修改哈夫曼树的关键部分，该函数对动态哈夫曼树的一种可能情况无法正确修改，针对这一点，本文附上对该函数的一个修正定义，以使该压缩与解压程序更加完善。
以下就举例说明原update函数无法正确修改的一种哈夫曼树。例如若要压缩“tthhis”字符串，则在压缩完“tth”之后的动态哈夫曼树为图所示(设根结点序号为1000)：
@@04a07700.gif;图 压缩完“tth”之后的动态哈夫曼树@@
此时若再将字符h进行压缩编码，则在输出h的编码“01”后需调整哈夫曼树，以997号叶结点为当前结点，则与当前结点具有同样重量的且序号最大的结点为998号结点，而该结点是997号结点的父结点，对二者按原文所提供的update函数进行交换，则将导致998号结点变成叶结点，996号结点变成997号结点的左孩子，997号结点则既为自己的父结点又是自己的右孩子，这样在对后继字符i进行压缩编码时，首先就无法输出996号空结点的编码了，此时压缩程序陷入死循环。
显然这时可以简单地将998和997号结点的重量加1，然后以998号结点的父结点为当前结点进行调整，根据这种思想对原文提供的update函数进行修正所得新的update函数附后。
|
|
|
|
|
|
|
|
|
| 广告载入中... |
| 广告载入中... |
| 广告载入中... |
|
|
|
|
|
教育论文中心