精华内容
下载资源
问答
  • 哈夫曼编码

    2018-08-07 09:21:14
    哈夫曼编码的目的是得到平均长度最短的编码,对一棵具有n个叶子的哈夫曼树,若对树中的每个分支赋予0分支赋予1(也可调换顺序),则从根到每个叶子的通路上,各分支的赋值分别构成一个二进制串,该二进制串就...

    一、哈夫曼编码的特性及作用
    哈夫曼编码的目的是得到平均长度最短的编码,对一棵具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1(也可调换顺序),则从根到每个叶子的通路上,各分支的赋值分别构成一个二进制串,该二进制串就称为哈夫曼编码。哈夫曼编码是前缀编码,因为在所以叶子所构成的二进制串中,任一编码都不是其他编码的前缀,哈夫曼编码是最优前缀编码,使用频度较高的字符对应的编码较短。
    利用哈夫曼树可以的到平均长度最短的编码,研究操作码的优化问题主要是为了缩短指令字的长度,减少程序的总长度以及增加指令所能表示的操作信息和地址信息。
    二、哈夫曼编码的算法实现
    typedef char * HuffmanCode[N+1];//存放哈夫曼编码串的头指针数组
    由于每个哈夫曼编码是变长编码,因此使用指针数组存放每个编码串的头指针
    void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n)
    //从叶子结点到根,逆向求每个叶子结点对应的哈夫曼编码
    {
    char *cd;
    int i,start,c,p,j,k;
    cd=(char *)malloc(n*sizeof(char));//分配求当前编码的工作空间
    cd[n-1]=’\0’;//从右向左逐位存放编码,首先存放编码结束符
    for(i=1;i<=n;i++) //求n个叶子结点对应的哈夫曼编码
    {
    start=n-1;//初始化编码起始指针
    c=i;
    p=ht[i].parent;//从叶子结点开始往上倒推
    while(p!=0)
    {
    –start;
    if(ht[p].LChild==c) cd[start]=’0’;
    else cd[start]=’1’;
    c=p;
    p=ht[p].parent;
    }
    hc[i]=(char *)malloc((n-start)*sizeof(char));//为第i个编码分配空间
    k=n-start;
    for(j=0;j

    展开全文
  • 基本概念 哈夫曼树:给定N个权值作为N个叶子结点,构造...哈夫曼编码,即将字符出现概率当成叶子结点权值,进行构造哈夫曼树,而后所有父结点的子树为0子树为1,对字符进行编码的方法,称之为哈夫曼编码 哈夫曼

    基本概念

    哈夫曼树:给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)

    哈夫曼编码:依据字符出现概率来构造异字头的平均长度最短的码字的编码方法,称之为哈夫曼编码

    理解:

    哈夫曼树,即该二叉树满足所有叶子结点的带权路径(路径长度与结点权值的乘积)之和最小

    哈夫曼编码,即将字符出现概率当成叶子结点权值,进行构造哈夫曼树,而后所有父结点的左子树为0,右子树为1,对字符进行编码的方法,称之为哈夫曼编码

    哈夫曼树

    如何构建哈夫曼树 重点

    假设我们要将 7 19 2 6 32 3 21 10这8个叶子结点构造二叉树,如下

    一般二叉树,构建完成如下:

    权值计算:(7+19+2+6+32+3+21+10)*3= 300

    哈夫曼树构造过程

    1.取最小的两个叶子结点构成二叉树

    2.将生成的父结点放入原来的叶子结点集,继续构建(取最小的两个叶子结点构成二叉树)

    3.继续构建,但是我们发现此时最小的两个结点分别为7和10,均小于新增的叶子结点11,这是我们需要重新进行构建,即当我们取两个最小值时,如果不包括新增的叶子结点,我们需要新建一个二叉树,如下

    4.重复上述步骤

    权值计算:2*5 + 3*5 + 7*4 + 10*4 + 6*4 + 32*2 + 19*2 + 21*2 = 261

    实际权值最小,可以再自行构建其他二叉树进行验证

    哈夫曼编码 

    如果需传送的电文为 ‘ABACCDA’,即:A, B, C, D 的频率(即权值)分别为 0.43, 0.14, 0.29, 0.14,试构造哈夫曼编码

    转为上述哈夫曼二叉树,即为 四个结点 43 14 29 14 进行构建二叉树

    此时则 A的编码为0 ,B的编码为110,C的编码为10,D的编码为111

    实际问题

    1.一般给出叶子结点求哈夫曼树

    2.根据字符出现频率求哈夫曼编码

    解题思路:

    1.依次取最小的两个结点进行构建

    2.注意新二叉树的构建和连接

    展开全文
  • 哈夫曼编码方法,把各个字符作为结点,权值是字符出现的频率,构造出哈夫曼树,各个字符最终都出现在叶子节点上,然后从根节点到某字符的路径,向0,向1,得到哈夫曼编码 E为00 B为010 ...

    哈夫曼树构造方法,把一开始的各个点看作一颗颗树,取权值最小的两棵树组成一颗新二叉树,新树权值为两点之和,放入森林中取代原来的两个结点。一直重复直至只剩最后一颗树

    哈夫曼编码方法,把各个字符作为结点,权值是字符出现的频率,构造出哈夫曼树,各个字符最终都出现在叶子节点上,然后从根节点到某字符的路径,向左为0,向右为1,得到哈夫曼编码
    在这里插入图片描述
    E为00
    B为010

    展开全文
  • 算法_哈夫曼编码

    2020-06-27 14:47:08
    一、 什么是哈夫曼编码 计算机中使用二进制编码字符...从根开始, 遇到分支编码为0, 遇到分支编码为1; 对于同一个编码, 哈夫曼编码不唯一,但是都能正常工作; 哈夫曼编码是一种变长编码,权值越大的字符,其编

    一、 什么是哈夫曼编码

    计算机中使用二进制编码字符;
    哈夫曼编码是通过构造哈夫曼树得到的, 哈夫曼树是通过贪心算法得到的;

    贪心算法构造哈夫曼树:
    字符出现的次数作为哈夫曼树的权值,按照贪心算法,选择权值最小的两个结点,成为一个数的左右结点;左右子结点的权值变为子树根的权值;然后在余下的结点中递归选用最小的两个结点;
    在这里插入图片描述
    根据哈夫曼树得到哈夫曼编码:
    从根开始, 遇到左分支编码为0, 遇到右分支编码为1;

    对于同一个编码, 哈夫曼编码不唯一,但是都能正常工作;

    哈夫曼编码是一种变长编码,权值越大的字符,其编码越小;可变长编码要比固定长度编码好很多,其特点是对频度高的字符以短编码,对频度低的字符以长编码;

    哈夫曼编码,不存在一个字符编码是另一个编码的一部分,因为哈夫曼编码是前缀码, 从根节点到叶节点A的路径, 不可能是根节点到叶节点B的一部分;
    任何一颗二叉树的编码都是前缀码;哈夫曼编码不仅仅是前缀码,还是带权路径最小的;

    二、构造哈夫曼编码

    贪心算法的正确性依赖于贪心选择性质和最优子结构。
    构造哈夫曼树的思路如下:
    1) 已知一个需要编码的字符序列,将这个序列按照字符出现频率为权值压入优先队列中(小根堆);
    2) 从优先队列中取出两个节点, 这两个节点称为新建节点的左右子树, 新建节点的权值等于左右子树权值之和,再将新建节点压回优先队列;
    3) 反复执行步骤2, 直到优先队列中只有一个节点, 这个节点就是哈夫曼树的根节点;

    对哈夫曼使用贪心算法的正确性解释:
    需要证明最优前缀编码的问题具有贪心选择性质和最优子结构性质

    引理:设C是一个字母表, 其中每个字符c都具有频度f©。 设x 和y是C中具有最低频度的两个字符,则存在一种最优前缀编码, 其中x和y的编码长度相同但是最后一位不同;这个引理说明了哈夫曼树具有贪心选择性质
    这相当于x和y是兄弟节点, 即对于字母表C中, 其频度最低的两个节点肯定是兄弟节点;
    因此, 通过合并来构造一棵最优树的过程,可以贪心选择两个频度最低的字符开始。这为什么是一个贪心选择呢?我们可以认为一次合并的代价就是被合并的两个字符的频度之和。选择频度最低的两个字符合并,使得最终哈夫曼树的合并代价最低;

    引理:设C是一个给定的字母表, 其中每个字母c都定义了频度f©, 其中x和y是C中最低频度的两个字母;假设C’是C-x-y+z的字母表(其中z是由x和y合成的节点)f(z) = f(x)+f(y);假设T’是C’的最优前缀编码的任意一颗树。那么可以将T’中的叶子节点替换成具有x和y孩子的内部节点, 也就得到了树T, 表示的是字母表C的一个最优前缀编码;
    因此, 求解问题C的哈夫曼编码 = 求解C’的哈夫曼编码 + 将C’中的z替换成x和y

    展开全文
  • C++ 哈夫曼树和哈夫曼编码 哈夫曼树又称最优二叉树是树的结构应用之一。 哈夫曼树的构建: ...从结点开始,分支路径记0分支路径记1,从根结点到目标叶结点路径上的编号序列就是哈夫曼编码 ...
  • 哈夫曼编码详解

    千次阅读 2020-06-02 14:47:42
    哈夫曼编码,则是从根节点开始,节点标记为0节点标记为1. 例: **a,b,c,d,e 对应出现的频率为4,6,11,13,15,则a,b,c,e,d的哈夫曼编码是? 先把出现频率当成权重,选出权重最低了两个相加。 a和b相加,4+...
  • 哈夫曼树的主要用途就是来生成字符对应的哈夫曼编码以达到压缩文件的...我们设向走为1, 向走为 0。那么我们可以这样表示字符: 则a表示为0。我们从下向上来构建这棵树的话。有2种思路,你可以构建成这样 这
  • 哈夫曼编码测试

    2019-09-29 14:47:15
    哈夫曼树 定义 哈夫曼树,又称最优树,是一类带权路径长度最短的树 创建哈夫曼1)从F中选取两棵根结点权值最小的树作为左右子树构造一棵新...约定分支表示字符'0',分支表示字符'1',在哈夫曼树中从根结点开...
  • 哈夫曼编码算法--我只想简单点

    万次阅读 多人点赞 2019-01-02 13:12:38
    孩子路径编码为 0, 孩子路径编码为 1 图解 即 A 的编码: 0 D 的编码: 10 B 的编码: 110 C 的编码: 111 哈夫曼编码算法的实现 定义一个哈夫曼树 //定义一个哈夫曼树 typedef struct { //定义权值 un...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 234
精华内容 93
关键字:

哈夫曼编码左1右0