哈夫曼树算法

题目的阐述：　以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格式的图像，使用颜色数量有限的颜色空间，其压缩就采用了两种算法的灵活变形应用。

关于哈夫曼算法和哈夫曼算法的优点的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。