自适应Ｈｕｆｆｍａｎ压缩码的生成
发布时间：2015-07-04 20:28
摘要:随着现代社会信息量的增加,对数据进行压缩越来越有它的必要性。其中，huffman编码作为一种高效的数据编码方法在文本、图象、音频等压缩有着广泛的应用。本文中，笔者根据huffman编码的原理，实现对文本进行压缩与解压的功能。
关键词：huffman编码；数据压缩；解压；文本；自适应编码
huffman编码压缩是一种无损压缩技术。利用huffman编码原理进行压缩的主要问题包括压缩的算法设计及程序实现、解压算法及程序实现。
一、huffman编码介绍
huffman于1952年提出一种编码的方法，它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做huffman编码。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。
二、自适应huffman编码原理
基于静态huffman编码算法对输入的符号流进行编码，必须进行两次扫描，第一次扫描统计字符出现的概率，并创建huffman树；第二次扫描是按照huffman树的字符进行编码。并且在存储和传输huffman编码时，必须先存储和传送huffman树。这些问题使的静态huffman编码在实际应用用的的较少。为了解决静态huffman编码的缺点，产生了自适应huffman编码，它只需要对输入的符号流进行一次扫描即可。它不仅涉及到编码树的构造过程，还与编码和解码有关。
自适应huffman编码过程
初始化huffman树
对每个输入符号
{对符号编码；
更新huffman树；
}
初始化huffman树时，由于对字符流进行一次扫描，因此，不能预先知道各字符的概率，为了对所以字符一致对待，在这里使用符号为nyt，权值为0作为初始的huffman树。nyt不同于任何一个将要传送的符号，在这里作为一个逸出码。nyt有两种作用：一是在编码时，当有一个还没在编码树出现的字符需要编码时，系统就输出nyt编码，然后跟着字符的原始表达；在解码时，当解码器读出nyt时，就知道下面的内容暂不是huffman编码，而是一个从没在编码数据流出现的原始字符；二是作为新字符的插入点，在需要插入一个新字符时，总是构造一个新子树，子树包括nyt符号和新符号两个叶结点，然后将旧的nyt结点用新子树代替，并使原nyt和新符号结点的权值赋一。对符号编码与静态的一样。在每次编码完成之后，需要试图对包含的结点进行权值加一操作，为此在这里需要介绍两个概念：结点编号和所属块。结点编号是一个全局唯一的的值，不同的结点有不同的结点编号，它具有如下特性：
(一)权值越大的结点，结点编号越大。
(二)父结点的编号总是大于子结点的编号。
以上两点称为兄弟属性，在每次调整结点权值时，都需要调整结点的编号，以避免兄弟属性破坏。在本课程设计中用数组来表示结点编号，根结点在数组的最大位置。所属块指权值相同的一组结点。在对每个结点进行权值加一时，首先检查该结点是否是所在块的最大结点，如果不是，将该结点与所在块的最大结点交换位置，在对该结点的权值加一，这样保证了结点的兄弟属性，由于结点的权值发生变化，必须递归对结点的夫结点执行加一操作。
三、自适应huffman压缩编码算法
（一）判断字符在文本中是否出现
由于自适应huffman编码只对字符流扫描一次，因此，就需要判断该字符在前面的字符流是否出现过。
（二）判断该字符是否是所属块的最大结点
为了保证其兄弟属性不破坏，在进行加一操作时，必须判断该结点是否是所属快的最大结点，不是就必须交换当前结点与最大结点。
（三）交换当前结点与所属块的最大结点
当highinblock函数返回的不是-1就必须交换当前结点与所属块的最大结点，保证兄弟属性。
（四）对当前字符进行编码
从输入流中得到一个字符，若以前出现过该字符，则对该字符进行编码，并判断该字符是否是所属块的最大结点，否就交换当前结点与最大结点；若以前没有出现该字符，则生成两个结点，一个结点用于保存该字符，另一个用做逸出码结点nyt，并这两个结点的父结点为原逸出码结点nyt，输出逸出码及原字符。在这里我们用了code这个结构来保存一个字符的编码。
程序流程过程如下：
1、从字符输入流中，取出一个字符；
2、判断该字符以前是否出现过？
3、否，用新的nyt及字符结点代替原nyt，输出逸出码及原字符，并使原nyt及字符结点的权值赋为一，改变当前结点为原nyt结点；
4、是，输出该字符的编码，判断该字符是否是所属块的最大结点？否，交换该字符结点与最大结点，改变当前结点为最大结点，并是当前结点的权值加一。
（五）更新huffman树结构
当从输入流中取出一个字符并对其编码后，huffman树的权值发生了变化，这就要更新huffman树，在程序实现上用了变量newplace保存了需要更新结点权值的位置，当该结点不是根结点就递归是其父结点的权值加一。
程序流程如下：
1、当前结点是否为根结点？是，结束；否，转2；
2、改变当前结点为其父结点；
3、判断该结点是所属块的最大结点？是，转4；否，交换当前结点与最大结点；
4、当前结点的权值加一，转1。
四、对输入字符流进行压缩
对字符进行压缩，实际上对字符编码和更新huffman树的过程。
程序流程如下：
（一）初始化huffman树；
（二）是否遇到结束符’\0’，否，转3；否则就结束；
（三）对字符进行编码；
（四）更新huffman树；
（五）读下一个字符，转2。
{
//原文本编辑框的内容赋给sadaporiginaltext
getdlgitemtext(idc_adap_originaltext,sadaporiginaltext);
charm_sadaporiginaltext[32767];
//sadaporiginaltext的内容赋给m_sadaporiginaltext
strcpy(m_sadaporiginaltext,(lpstr)(lpctstr)sadaporiginaltext);
intc=0;
charch;
ch=m_sadaporiginaltext[c];
("");
inithuffman();//初始化huffman树
while(ch!=’\0’)//判断文本是否结束
{
encode(ch);//对字符ch编码
updatetree();更新huffman树
c++;
ch=m_sadaporiginaltext[c];
}
setdlgitemtext(idc_adap_compresstext,adapstr);//在二进制编辑框显示压缩流
huffman_information();
setdlgitemtext(idc_adap_information,information);
checkcompressbutton=true;//按下压缩按钮，把它赋为true
cbutton*pbtn;
//屏蔽压缩按钮
pbtn=(cbutton*)getdlgitem(idc_compress);
pbtn->enablewindow(false);
//激活huffman树按钮和解压按钮
pbtn=(cbutton*)getdlgitem(idc_decompress);
pbtn->enablewindow(true);
pbtn=(cbutton*)getdlgitem(idc_huffmantree);
pbtn->enablewindow(true);
}
五、自适应huffman压缩效果分析
一个压缩器的好坏，取决于它的压缩参数值：主要包括压缩比、平均代码长度、熵、冗余度。
压缩比=输出流/输入流=(length+chlength×8)÷(p×8)压缩比>1，压缩器做无效的压缩；压缩比=1，压缩器没起作用；压缩比<1压缩器起到压缩作用。
平均代码长度=((length+chlength×8)÷p),文本中每个字符huffman代码的平均长度越小，压缩效果越好。
熵值=－∑(log2(w[i]/p)×w[i])(0＜i＜129)
其中length存储0-1串的长度，chlength存储字符的种类；w[i]存储为i字符权值，p为字符总数。
参考文献：
[1]王京.quake3自适应huffman编码[j].v0.96.2006.12.
[2]吴乐南.数据压缩(第一版)[m].北京:电子工业出版社,2000:1-118
[3]冯斐玲.数据压缩技术的一般方法[j].计算机世界报,1994,15:58-65
关键词：huffman编码；数据压缩；解压；文本；自适应编码
huffman编码压缩是一种无损压缩技术。利用huffman编码原理进行压缩的主要问题包括压缩的算法设计及程序实现、解压算法及程序实现。
一、huffman编码介绍
huffman于1952年提出一种编码的方法，它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做huffman编码。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。
二、自适应huffman编码原理
基于静态huffman编码算法对输入的符号流进行编码，必须进行两次扫描，第一次扫描统计字符出现的概率，并创建huffman树；第二次扫描是按照huffman树的字符进行编码。并且在存储和传输huffman编码时，必须先存储和传送huffman树。这些问题使的静态huffman编码在实际应用用的的较少。为了解决静态huffman编码的缺点，产生了自适应huffman编码，它只需要对输入的符号流进行一次扫描即可。它不仅涉及到编码树的构造过程，还与编码和解码有关。
自适应huffman编码过程
初始化huffman树
对每个输入符号
{对符号编码；
更新huffman树；
}
初始化huffman树时，由于对字符流进行一次扫描，因此，不能预先知道各字符的概率，为了对所以字符一致对待，在这里使用符号为nyt，权值为0作为初始的huffman树。nyt不同于任何一个将要传送的符号，在这里作为一个逸出码。nyt有两种作用：一是在编码时，当有一个还没在编码树出现的字符需要编码时，系统就输出nyt编码，然后跟着字符的原始表达；在解码时，当解码器读出nyt时，就知道下面的内容暂不是huffman编码，而是一个从没在编码数据流出现的原始字符；二是作为新字符的插入点，在需要插入一个新字符时，总是构造一个新子树，子树包括nyt符号和新符号两个叶结点，然后将旧的nyt结点用新子树代替，并使原nyt和新符号结点的权值赋一。对符号编码与静态的一样。在每次编码完成之后，需要试图对包含的结点进行权值加一操作，为此在这里需要介绍两个概念：结点编号和所属块。结点编号是一个全局唯一的的值，不同的结点有不同的结点编号，它具有如下特性：
(一)权值越大的结点，结点编号越大。
(二)父结点的编号总是大于子结点的编号。
以上两点称为兄弟属性，在每次调整结点权值时，都需要调整结点的编号，以避免兄弟属性破坏。在本课程设计中用数组来表示结点编号，根结点在数组的最大位置。所属块指权值相同的一组结点。在对每个结点进行权值加一时，首先检查该结点是否是所在块的最大结点，如果不是，将该结点与所在块的最大结点交换位置，在对该结点的权值加一，这样保证了结点的兄弟属性，由于结点的权值发生变化，必须递归对结点的夫结点执行加一操作。
三、自适应huffman压缩编码算法
（一）判断字符在文本中是否出现
由于自适应huffman编码只对字符流扫描一次，因此，就需要判断该字符在前面的字符流是否出现过。
（二）判断该字符是否是所属块的最大结点
为了保证其兄弟属性不破坏，在进行加一操作时，必须判断该结点是否是所属快的最大结点，不是就必须交换当前结点与最大结点。
（三）交换当前结点与所属块的最大结点
当highinblock函数返回的不是-1就必须交换当前结点与所属块的最大结点，保证兄弟属性。
（四）对当前字符进行编码
从输入流中得到一个字符，若以前出现过该字符，则对该字符进行编码，并判断该字符是否是所属块的最大结点，否就交换当前结点与最大结点；若以前没有出现该字符，则生成两个结点，一个结点用于保存该字符，另一个用做逸出码结点nyt，并这两个结点的父结点为原逸出码结点nyt，输出逸出码及原字符。在这里我们用了code这个结构来保存一个字符的编码。
程序流程过程如下：
1、从字符输入流中，取出一个字符；
2、判断该字符以前是否出现过？
3、否，用新的nyt及字符结点代替原nyt，输出逸出码及原字符，并使原nyt及字符结点的权值赋为一，改变当前结点为原nyt结点；
4、是，输出该字符的编码，判断该字符是否是所属块的最大结点？否，交换该字符结点与最大结点，改变当前结点为最大结点，并是当前结点的权值加一。
（五）更新huffman树结构
当从输入流中取出一个字符并对其编码后，huffman树的权值发生了变化，这就要更新huffman树，在程序实现上用了变量newplace保存了需要更新结点权值的位置，当该结点不是根结点就递归是其父结点的权值加一。
程序流程如下：
1、当前结点是否为根结点？是，结束；否，转2；
2、改变当前结点为其父结点；
3、判断该结点是所属块的最大结点？是，转4；否，交换当前结点与最大结点；
4、当前结点的权值加一，转1。
四、对输入字符流进行压缩
对字符进行压缩，实际上对字符编码和更新huffman树的过程。
程序流程如下：
（一）初始化huffman树；
（二）是否遇到结束符’\0’，否，转3；否则就结束；
（三）对字符进行编码；
（四）更新huffman树；
（五）读下一个字符，转2。
voidcadaptivehuffman::oncompress()
{
//原文本编辑框的内容赋给sadaporiginaltext
getdlgitemtext(idc_adap_originaltext,sadaporiginaltext);
charm_sadaporiginaltext[32767];
//sadaporiginaltext的内容赋给m_sadaporiginaltext
strcpy(m_sadaporiginaltext,(lpstr)(lpctstr)sadaporiginaltext);
intc=0;
charch;
ch=m_sadaporiginaltext[c];
("");
inithuffman();//初始化huffman树
while(ch!=’\0’)//判断文本是否结束
{
encode(ch);//对字符ch编码
updatetree();更新huffman树
c++;
ch=m_sadaporiginaltext[c];
}
setdlgitemtext(idc_adap_compresstext,adapstr);//在二进制编辑框显示压缩流
huffman_information();
setdlgitemtext(idc_adap_information,information);
checkcompressbutton=true;//按下压缩按钮，把它赋为true
cbutton*pbtn;
//屏蔽压缩按钮
pbtn=(cbutton*)getdlgitem(idc_compress);
pbtn->enablewindow(false);
//激活huffman树按钮和解压按钮
pbtn=(cbutton*)getdlgitem(idc_decompress);
pbtn->enablewindow(true);
pbtn=(cbutton*)getdlgitem(idc_huffmantree);
pbtn->enablewindow(true);
}
五、自适应huffman压缩效果分析
一个压缩器的好坏，取决于它的压缩参数值：主要包括压缩比、平均代码长度、熵、冗余度。
压缩比=输出流/输入流=(length+chlength×8)÷(p×8)压缩比>1，压缩器做无效的压缩；压缩比=1，压缩器没起作用；压缩比<1压缩器起到压缩作用。
平均代码长度=((length+chlength×8)÷p),文本中每个字符huffman代码的平均长度越小，压缩效果越好。
熵值=－∑(log2(w[i]/p)×w[i])(0＜i＜129)
其中length存储0-1串的长度，chlength存储字符的种类；w[i]存储为i字符权值，p为字符总数。
参考文献：
[1]王京.quake3自适应huffman编码[j].v0.96.2006.12.
[2]吴乐南.数据压缩(第一版)[m].北京:电子工业出版社,2000:1-118
[3]冯斐玲.数据压缩技术的一般方法[j].计算机世界报,1994,15:58-65