哈夫曼树算法
题目的阐述： 以N进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入0，1，2，．．．，N－1构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．如： N＝3 英文原串为 ABBCBADDACE其对应的一种编码方式为A：00B：01C：020D：021E：022原串对译后的编码为000101020010002102100020022其码长为27若输入编码串0102002200则对应的英文原串为 BCEA 分 析： 假设英文原串中的字符存放于字符集S中，‖S‖＝ X，每个字符在字串中出现的概率为W［i］，L［i］为字符i的编码长．依题意得，对S集合中的不同字符进行N进制编码后要求1）新字串的码长最短WPL＝∑W［i］＊L［i］
（i∈1．．X）使得在WPL是所有编码方式中的最小值2）编码无二义性任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的．N为此哈夫曼树的分叉数，S字符集里的元素即为此N叉哈夫曼树的叶子，概率W［i］即为叶子结点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长L［i］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．但具体应该怎样建立起此N叉哈夫曼树呢？我们首先以N＝2为例 ：S＝｛A，B，C，D｝W＝［3，1，2，1］ 首先从W中选出两个最小权，1，1，将其删去，并以2（即1＋1）替代W＝［3，2，2］；再从新的W中取出两个最小权，2，2，将其删去，并以4（即2＋2）替代W＝［3，4］；依此类推，直到W中只一个值时合并结束，此时 W＝［7］以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下： m0åæ1m m A0åæ1 mm C0åæ1m m BD MIN－WPL＝3＊1＋1＊3＋2＊2＋1＊3＝13 从某一根结点出发走向其左子树标记为0，走向其右子树标记为1，则可以得到以下编码 A，B，C，D对应的编码为 A：0 B：110 C：10 D：111
N＝3时又是怎样一种情况呢？设 S＝｛A，B，C，D，E｝W＝［7，4，2，5，3｝则按权重排序可得S＝｛D，B，E，C，A｝ W＝［7，5，4，3，2］那么此哈夫曼树的树形应为怎样呢？是以下的左图，还是右图，或是两者均不是 m måâ æ å æ m m llmå æå æC A å æ ll lllm AD BED å æ
l mBå æ l l E C 显然，要带权路径长WPL最短，那么，此树的高度就应尽可能的小，由此可知将此树建成丰满N叉树是最合理的，于是我们尽量使树每一层都为N个分枝．对于这道题的情况，我们具体来分析．按照哈夫曼树的思想，首先从W中取出权最小的三个值，即2，3，4，并以9（2＋3＋4）来代替，得到新的W＝［9，7，5］；再将这三个值合并成9＋7＋5＝21这个结点．于是得到三叉哈夫曼树如下：m åâæl l mD B å â æl l lE C AWPL＝1＊7＋1＊5＋2＊2＋2＊3＋2＊4＝30以0．．N－1依次标记每个根结点的N个分枝，则可以得到每个字符相对应的编码：A：22B：1C：21D：0E：20我们发现对于这种情况恰巧每层均为N个分枝，但事实上并非所有的N叉哈夫曼树都可得到每层N个分枝．例于当N＝3，‖S‖＝6时就不可能构成一棵每层都为三个分枝的三叉树．如何来处理这种情况呢？最简单的处理方式就是添加若干出现概率为0的空字符填补在N叉树的最下一层，这些权为0的虚结点并无实际意义但却非常方全便于这棵N叉树的建立．空字符的添加个数add的计算如下：Y＝‖S‖ mod （n－1）add＝0 （Y＝1） add＝1 （Y＝0）add＝N－Y （Y＞1） 虚结点的加入使得权重最小的N－add个字符构成了距根结点最远的分枝，使其它字符构成的N叉树保持了丰满的N叉结构．例： N＝3S＝｛A，B，C，D，E，F｝ W＝［1，2，3，4，5，6｝则 y：＝6 mod （3－1）＝0add＝1于是构成N叉树如下： 为虚结点¡åâæl lmF E åâæll mDC å â æ B A WPL＝1＊6＋1＊5＋2＊4＋2＊3＋3＊2＋3＊1＋3＊0＝33对应编码为：A：221B：220C：21D：20E：1F：0
哈夫曼算法简介
看官们建议在看我的这篇文章之前，先看一下RlE算法 这个是计算机压缩算法的入门级，如果连这个算法的思想都不清楚的，请私聊我，单独讲解
简单说一下rle=字符乘以重复数量
举个例子，aaaaaa*********的rlu就是a6b6
说回哈夫曼算法
*** 统计每个字符出现的次数
第二 将出现次数最少的字符连线并求数量和
第三 重复第二步完成哈夫曼树
第四 将哈夫曼树的左边的边写上0，右边的边也写上 1
第五 从根节点开始沿着边去将数字写在对应的字符下面
这样一个哈夫曼编码就完成了
#include iostream
#include iomanip
using namespace std;
//哈夫曼树的存储表示
typedef struct
{
int weight; // 权值
int parent, lChild, rChild; // 双亲及左右孩子的下标
}HTNode, *HuffmanTree;
// 选择权值最小的两颗树
void SelectMin(HuffmanTree hT, int n, int s1, int s2)
{
s1 = s2 = 0;
int i;
for(i = 1; i n; ++ i){
if(0 == hT[i].parent){
if(0 == s1){
s1 = i;
}
else{
s2 = i;
break;
}
}
}
if(hT[s1].weight hT[s2].weight){
int t = s1;
s1 = s2;
s2 = t;
}
for(i += 1; i n; ++ i){
if(0 == hT[i].parent){
if(hT[i].weight hT[s1].weight){
s2 = s1;
s1 = i;
}else if(hT[i].weight hT[s2].weight){
s2 = i;
}
}
}
}
// 构造有n个权值（叶子节点）的哈夫曼树
void CreateHufmanTree(HuffmanTree hT)
{
int n, m;
cin n;
m = 2*n - 1;
hT = new HTNode[m + 1]; // 0号节点不使用
for(int i = 1; i = m; ++ i){
hT[i].parent = hT[i].lChild = hT[i].rChild = 0;
}
for(int i = 1; i = n; ++ i){
cin hT[i].weight; // 输入权值
}
hT[0].weight = m; // 用0号节点保存节点数量
for(int i = n + 1; i = m; ++ i){
int s1, s2;
SelectMin(hT, i, s1, s2);
hT[s1].parent = hT[s2].parent = i;
hT[i].lChild = s1; hT[i].rChild = s2; // 作为新节点的孩子
hT[i].weight = hT[s1].weight + hT[s2].weight; // 新节点为左右孩子节点权值之和
}
}
int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)
{
if(hT[i].lChild == 0 hT[i].rChild == 0){
return hT[i].weight * deepth;
}
else{
return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);
}
}
// 计算WPL（带权路径长度）
int HuffmanTreeWPL(HuffmanTree hT)
{
return HuffmanTreeWPL_(hT, hT[0].weight, 0);
}
// 输出哈夫曼树各节点的状态
void Print(HuffmanTree hT)
{
cout "index weight parent lChild rChild" endl;
cout left; // 左对齐输出
for(int i = 1, m = hT[0].weight; i = m; ++ i){
cout setw(5) i " ";
cout setw(6) hT[i].weight " ";
cout setw(6) hT[i].parent " ";
cout setw(6) hT[i].lChild " ";
cout setw(6) hT[i].rChild endl;
}
}
// 销毁哈夫曼树
void DestoryHuffmanTree(HuffmanTree hT)
{
delete[] hT;
hT = NULL;
}
int main()
{
HuffmanTree hT;
CreateHufmanTree(hT);
Print(hT);
cout "WPL = " HuffmanTreeWPL(hT) endl;
DestoryHuffmanTree(hT);
return 0;
}
请描述哈夫曼算法，并用图描述构造哈夫曼树的过程。
这个讲的相当清楚。
首先介绍什么是哈夫曼树。哈夫曼树又称***二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）
然而怎样构造一棵哈夫曼树呢？***有一般规律的构造方法就是哈夫曼算法。一般的数据结构的书中都可以找到其描述：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{
float weight;
union{
char leaf;
struct tree *left;
};
struct tree *right;
};
struct forest{
struct tree *ti;
struct forest *next;
};
例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为***或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。
这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：***遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据***遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。 静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。
因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。
C语言都有哪些经典的无损压缩算法
C语言经典的无损压缩算法有：哈夫曼算法、LZ。
哈夫曼算法：
哈夫曼编码是David A. Huffman于1952年发明的一种满足对编码算法要求的一种编码算法。
哈夫曼算法是利用频率信息构造一棵二叉树，频率高的离根节点近（编码长度短），频率低的离根节点远（编码长度长），手动构造方法是先将字母按照频率从小到大排序，然后不断选择当前还没有父节点的节点中权值最小的两个，构造新的父节点，父节点的值为这两个节点值的和，直到构造成一棵二叉树。
LZ算法：
LZ算法及其衍生变形算法是压缩算法的一个系列。LZ77和LZ78算法分别在1977年和1978年被创造出来。虽然他们名字差不多，但是算法方法完全不同。这一系列算法主要适用于字母数量有限的信息，比如文字、源码等。流行的GIF和PNG格式的图像，使用颜色数量有限的颜色空间，其压缩就采用了两种算法的灵活变形应用。
关于哈夫曼算法和哈夫曼算法的优点的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。