word2vec中关于霍夫曼树的应用原理
霍夫曼编码的原理
2013年末，Google发布的word2vec引起了一帮人的热捧，各种兴奋。时至今日，各地讨论的也不似如此频繁，也是时候写一下个人对它的理解，亦可避免被真正的有识之士鄙视。在大量赞叹word2vec的微博或者短文中，几乎都认为它是深度学习在自然语言领域的一项了不起的应用，各种欢呼“深度学习在自然语言领域开始发力了”。但实际上，简单看看代码就知道它实际上只是一个三层网络，压根算不上所谓的深层网络，学习过程也很简单，并未用太玄妙的东西，以至于在了解完整以后对它的简单叹为观止。
笔者其实也是门外汉，幸好周围有一些高人，几经指点，自认为大体了解，作此鄙文，记录一下。
首先，它的结构就是一个三层网络——输入层、隐层（也可称为映射层），输出层。
其次，代码中让人费解（没学过神经网络，是以费解）的主要是hierarchical softmax。得同事J指导，和同事S讨论，终于弄明白其网络结果，如下图所示：
word2vec层次softmax网络示意图
输入层读入窗口内的词，将它们的向量（K维，初始随机）加和在一起，形成隐藏层K个节点。输出层是一个巨大的二叉树，叶节点代表语料里所有的词（语料含有V个独立的词，则二叉树有|V|个叶节点）。而这整颗二叉树构建的算法就是Huffman树。这样，对于叶节点的每一个词，就会有一个全局唯一的编码，形如"010011"。我们可以记左子树为1，右子树为0。接下来，隐层的每一个节点都会跟二叉树的内节点有连边，于是对于二叉树的每一个内节点都会有K条连边，每条边上也会有权值。
这样，整体的结构就清晰了。在训练阶段，当给定一个上下文，要预测后面的词(Wn)的时
候（word2vec的CBOW和Skip-gram都不是预测后面的词，都是在中间的词上做文章，但是本文这么写并不影响理解），实际上我们知道要的是哪个词(Wn)，而Wn是肯定存在于二叉树的叶子节点的，因此它必然有一个二进制编号，如"010011"，那么接下来我们就从二叉树的根节点一个个地去便利，而这里的目标就是预测这个词的二进制编号的每一位！即对于给定的上下文，我们的目标是使得预测词的二进制编码概率最大。形象地说，我们希望在根节点，词向量和与根节点相连经过logistic计算得到的概率尽量接近0（即预测目标是bit=1）；在第二层，希望其bit是1，即概率尽量接近1……这么一直下去，我们把一路上计算得到的概率相乘，即得到目标词Wn在当前网络下的概率(P(Wn))，那么对于当前这个sample的残差就是1-P(Wn)。于是就可以SGD优化各种权值了。
那么hs(hierarchical softmax)如何保证叶节点输出的概率值（即我们一路沿二进制编号乘下去的概率）是归一化的呢（否则，所谓的残差1-P(Wn)就没什么意义了）？这点其实很简单，请看下图：
hierarchical softmax说明
从根节点开始，对于一个sample而言，目标词是W2，二进制编码是"110"。我们在根节点计算得到它的第一位是'1'的概率是P，那么它第一位是'0'的概率就是1-P；在左子树里，第二位是"1"的概率是P'，那么第二位是"0"的概率就是1-P'，而在右子树里，第二位是"1"的概率是P''，那么第二位是"0"的概率就是1-P''；第三位亦如此。为方便表示记，我们只写到第二层。这样，在第二层，整个概率之和就是
(P*(P') + P*(1-P')) + ((1-P)*(P'') + (1-P)*(1-P'')) = P + (1-P) = 1
即按照目标词的二进制编码计算到最后的概率值就是归一化的，这也是为啥它被称作hierarchical softmax的原因。
如果没有使用这种二叉树，而是直接从隐层直接计算每一个输出的概率——即传统的softmax，就需要对|V|中的每一个词都算一遍，这个过程时间复杂度是O(|V|)的。而使用了二叉树（如word2vec中的Huffman树），其时间复杂度就降到了O(log2(|V|))，速度大大地加快了。
不过虽然hierarchical softmax一般被认为只是用于加速，但是仍然可以感性地理解一下为啥它会奏效：二叉树里面的每一个内节点实际上是一种隐含概念的分类器（二元分类器，因为二进制编码就是0/1），它的输出值的大小预示着当前上下文能够表达该隐含概念的概率，而一个词的编码实际上是一堆隐含概念的表达（注意，这个隐含概念的表达和词向量的维度所表达的隐含概念是不一样的）。我们的目标就在于找到这些当前上下文对于这些概念分类的最准确的那个表达（即目标词向量）。由于概念之间实际上是有互斥关系的（二叉树保证），即在根节点如果是"1"，即可以表达某一概念，那么该上下文是绝对不会再有表达根节点是"0"的其他情况的概念了，因此就不需要继续考虑根节点是"0"的情况了。因此，整个hierarchical softmax可以被看作完全不同于传统softmax的一套。
写到这里，感觉没有想象的那么明白。sigh，果然下笔难成书。再慢慢润色吧。
word2vec 阅读笔记
1一个输入层；1 个隐含层；1个输出层
syn0 input -> hidden 的 weights 在code中是一个1维数组，但是应该按照二维数组来理解。
访问时实际上可以看成 syn0[i, j] i为第i个单词，j为第j个隐含单元。
大小：词典大小* 隐含层大小
syn1 hidden->output 的weights
neu1 浮点型数组，隐含层神经的值
大小：隐含层大小
neu1e 隐含层误差量
大小：隐含层大小
vocab_size 不同单词个数，也就是词典大小。
layer1_size 向量长度，实际上就是隐含层的大小。
分析完其实就是一个BP网络，不过还是不知道为啥要将前后几个词和当前词联系起来，要完全理解此场景的模型思想，看来还是得看论文了。
1. TrainModelThread
while （1）
1. 打印训练的进度情况
2. （while）从输入文件中读入1000个单词组成一个句子，存入sen，sen[i]
= word_index, 也就是sen数组里的顺序与单词在原文中的顺序一致，而
sen存放的值为词典中该单词的位置。
sentence_length - 该sen数组的长度
sentence_position - 为最外层while循环遍历该句子时，对记录当前单词在
此句子中的位置。
3. 如果处理的单词个数超出了分配给当前线程的个数，则结束。
4. 获取当前单词。从句子sen中取出 word_index = sen[sentence_position];
5. 初始化隐含层神经neu1 、隐含层误差neu1e 为0
6. b 产生随机数b，取值目前为0~4之间。窗口值window默认为5
7. cbow
1. in -> hidden （正向传播, 得到隐含层）
for (遍历左右窗口词，c从sentence_position - (window
-b) 到 sentence_position + (window -b) ，且
c != sentence_position
1. 得到c处存放的单词索引last_word = sen[c];
2. 将该词对应到的每一个in->hidden的网络权重系数syn0 累
加到隐含层单元neu1中
for (c = 0; c < layer1_size; c++) neu1[c] += syn0[c +
last_word * layer1_size];
2. HIERARCHICAL SOFTMAX 目前默认hs为1的。
for (遍历该词的huffman编码串)
1. f = 0
2. 计算出该词在hidden-output 网络中的权重存储位置l2 =
vocab_[word_index].point[d] * layer1_size;
这里的point[d]有疑问？？是否有可能超出vocab_size呢
3. hidden -> output （正向传播，得到该编码单元对应的
output 值f）
for (c = 0; c < layer1_size; c++) f += neu1[c] * syn1[c + l2];
4. 对f 进行Sigmoid变换（这里是预先存放在了expTable
表中）
5. 计算下降的梯度g （乘了学习率alpha）
g = (1 - vocab_[word_index].code[d] - f) * alpha;
6. output - > hidden （反向传播得到隐含层误差）
for (c = 0; c < layer1_size; c++) neu1e[c] += g * syn1[c +
l2];
7. 学习权重hidden-output
for (c = 0; c < layer1_size; c++) syn1[c + l2] += g * neu1[c];
3. NEGATIVE SAMPLING 目前运行时默认未走此步
4. hidden -> in （反向传递，更新in-hidden网络权重）
for (遍历左右窗口词，c从sentence_position - (window
-b) 到 sentence_position + (window -b) ，且
c != sentence_position
1. 得到c处存放的单词索引last_word = sen[c];
2. 学习权重input-hidden 将隐含层单元误差量neu1e 加
到该词对应到的每一个in->hidden的网络权重系数syn0
上
for (c = 0; c < layer1_size; c++) syn0[c + last_word *
layer1_size] += neu1e[c];
8. skip-gram
这里居然没有隐含神经元的概念，也就是无neu1；
计算输出值f的时候，直接用的是两层网络的权重syn0与syn1;
第1层网络权重用的是窗口词的，第2层网络权重用的是当前词的;
其余部分和cbow模型类似。
2. 保存结果
将input-hidden网络权重（syn0）作为了词向量保存，不知为何这个就是词向量了。
一、k-means算法
算法描述
输入：簇的数目k；包含n个对象的数据集D。
输出：k个簇的集合。
方法：
1.从D中任意选择k个对象作为初始簇中心；
2.repeat;
3.根据簇中对象的均值，将每个对象指派到最相似的簇；
4.更新簇均值，即计算每个簇中对象的均值；
5.计算准则函数；
6.until准则函数不在发生变化
二、Machine Learning(Ng)算法笔记
算法主要思想：
1）首先根据你要聚类的个数（假设为k），选择k个中心u，可以挑选k个样本作为中心。
2）根据挑选出的k个中心，将每个样本（一共m个）贴上特定的标签。
3）根据新贴的标签，更新样本的中心。
三、word2vec中k-means实现
1int clusterCount = classses;
2int iter = 10;
3
4int *centcn = (int *)malloc(clusterCount * sizeof(int)); //属于每个中心的单词个数
5int *cluster = (int *)calloc(vocab_size, sizeof(int)); // 存放每个单词指派的
中心id
6
7 real *cent = (real *)calloc(clusterCount * layer1_size, sizeof(reall)); //存放每个中心的向量表示
8
9for (a=0; a 10 cluster[a] = a % clusterCount; //随机指派每个单词的中心 11 12for (a=0; a < iter; a++) { //一共迭代iter轮 13for(b = 0; b < clusterCount * layer1_size; ++b) 14 cent[b] = 0; 15 16for(b=0; b < clusterCount; ++b) 17 centcn[b] = 1; 18 19for(c=0; c < vocab_size; ++c) { 20for(d=0; d < layer1_size; ++d) { 21 cent[layer1_size * cluster[c]+d] += syn0[c*layer1_size+d]; // 将属于每个中心的点的每个坐标相加 22 centcn[cluster[c]]++; // 分别计算属于每个中心的点个数 23 } 24 } 25 26for(b=0; b < clusterCount; ++b) { //更新每个中心的向量表示 27 closeV = 0; 28for (c=0; c 29 cent[layer1_size*b+c] /= centcn[b]; 30 closeV += cent[layer1_size*b+c] * cent[layer1_size*b+c]; 31 } 32 closeV = sqrt(closeV); 33for (c=0; c 34 } 35 36//更新每个样本的中心 37for(c=0; c < vocab_size; ++c) { 38 closev= -10; 39 closeid = 0; 40for (d=0; d < clusterCount; ++d) { 41 x = 0; 42for(b=0; b < layer1_size; ++b) { 43 x += cent[layer1_size*d+b] * syn0[c*layer1_size+b] 44 } 45if (x > closev) { //选出与单词表示最相近的中心 46 closeid = d; 47 closev = x; 48 } 49 } 50 cluster[c] = closeid; 51 } 52 } 附录二 表1. 传真用的修正霍夫曼编码表 构造码 64 11011 0000001111 960 011010100 0000001110011 128 10010 000011001000 1024 011010101 0000001110100 192 010111 000011001001 1088 011010110 0000001110101 256 0110111 000001011011 1152 011010111 0000001110110 320 00110110 000000110011 1216 011011000 0000001110111 384 00110111 000000110100 1280 011011001 0000001010010 448 01100100 000000110101 1344 011011010 0000001010011 512 01100101 0000001101100 1448 011011011 0000001010100 576 01101000 0000001101101 1472 010011000 0000001010101 640 01100111 0000001001010 1536 010011001 0000001011010 704 011001100 0000001001011 1600 010011010 0000001011011 768 011001101 0000001001100 1664 011000 0000001100100 832 011010010 0000001001101 1728 010011011 0000001100101 896 011010011 0000001110010 EOL 000000000001 000000000001 结尾码 游程长度 白游程编码 黑游程编码 游程长度白游程编码 黑游程编码 0 00110101 0000110111 32 000111011 000001101010 1 000111 010 33 00010010 000001101011 2 0111 11 34 00010011 000011010010 3 1000 10 35 00010100 000011010011 4 1011 011 36 00010101 000011010100 5 1100 0011 37 00010110 000011010101 6 1110 0010 38 00010111 000011010110 7 1111 00011 39 00101000 000011010111 8 10011 000101 40 00101001 000001101100 9 10100 000100 41 00101010 000001101101 10 00111 0000100 42 00101011 000011011010 11 01000 0000101 43 00101100 000011011011 12 001000 0000111 44 00101101 000001010100 13 000011 00000100 45 00000100 000001010101 14 110100 00000111 46 00000101 000001010110 15 110101 000011000 47 00001010 000001010111 16 101010 0000010111 48 00001011 000001100100 17 101011 0000011000 49 01010010 000001100101 18 0100111 0000001000 50 01010011 000001010010 19 0001100 00001100111 51 01010100 000001010011 20 0001000 00001101000 52 01010101 000000100100 21 0010111 00001101100 53 00100100 000000110111 22 0000011 00000110111 54 00100101 000000111000 23 0000100 00000101000 55 01011000 000000100111 24 0101000 00000010111 56 01011001 000000101000 25 0101011 00000011000 57 01011010 000001011000 26 0010011 000011001010 58 01011011 000001011001 27 0100100 000011001011 59 01001010 000000101011 28 0011000 000011001100 60 01001011 000000101100 29 00000010 000011001101 61 00110010 000001011010 30 00000011 000001101000 62 00110011 000001100110 31 00011010 000001101001 63 00110100 000001100111 205 目录 一、摘要 (3) 二、题目 (3) 三、实验目的 (3) 四、实验原理 (3) 五、需求分析 (4) 5.1实验要求 (4) 5.2实验内容 (4) 六、概要设计 (4) 6.1所实现的功能函数 (4) 6.2主函数 (5) 6.3 系统结构图 (6) 七、详细设计和编码 (6) 八、运行结果 (12) 九、总结 (15) 9.1调试分析 (15) 9.2 心得体会 (15) 参考文献 (16) 一、摘要 二、题目 哈夫曼树的编码与译码 三、实验目的 （1）熟悉对哈夫曼的应用以及构造方法，熟悉对树的构造方式的应用； （2）进一步掌握哈夫曼树的含义； （3）掌握哈夫曼树的结构特征，以及各种存储结构的特点以及使用范围； （4）熟练掌握哈夫曼树的建立和哈夫曼编码方法； （5）提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法； （6）掌握一种计算机语言，可以进行数据算法的设计。 四、实验原理 哈夫曼（Huffman）编码属于长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下： （1）初始化，根据富豪概率的大小按由大到小顺序对符号进行排序； （2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和； （3）重复第（2）步，直到形成一个符号为止（树），其概率最后等于1； （4）从编码树的根开始回溯到原始的符号，并将每一下分支赋值1，上分支赋值0； 译码的过程是分解电文中字符串，从根出发，按字符“0”或者“1”确定找做孩 子或右孩子，直至叶子节点，便求得该子串相应的字符。 中国矿业大学2015-2016学年第二学期 《数字视频技术》课程小设计考核 图像的Huffman编码研究 专业班级：信息13-04班 学生姓名：王振宇、龙航、王一鸣 学生学号：04131407、04131403、04131406 本人郑重声明：本人认真、独立完成了查找资料、完成作业、编写程序等考核任务，无抄袭行为。 签字： 日期：2016.05.17 1.引言 1.1图像数据压缩的目的 数字图像通常要求很大的比特数，这给图像的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。一般原始图像存在很大的冗余度。所以，对图像数据压缩显得非常重要。 1.2图像数据压缩的原理 对数字图像压缩主要运用两个基本原理：一是图像的相关性。在图像同一相邻像素之间，活动图像的相邻帧的对应像素之间往往存在很强的相关性，去除或减少这些相关性，也就除去或减少图像信息中的冗余度，继而实现对数字图像的压缩。二是人的视觉心理特征，人的视觉对于边缘急剧变化不敏感，对颜色分辨力弱，利用这些特征在相应部分降低编码精度而使人从视觉上感觉不到图像质量的下降，从而达到对数字图像压缩的目的。 1.3Huffman编码 Huffman编码是一种编码方式，是一种用于无损数据压缩的熵编码算法。它是Huffman 在1952年根据Shannon在1948年和Fano在1949年阐述的这种编码思想下提出的一种不定长编码的方法，有时也称之为最佳编码。依据信源数据中各信号出现的频率分配不同长度的编码。其基本思想是在编码过程中，对出现频率越高的值，分配越短的编码长度，相应地对出现频率越低的值则分配较长的编码长度，完全依据字符出现概率来构造异字头的平均长度最短的码字。哈夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。 2.设计任务 2.1设计任务 研究实现灰度图像的Huffman编码和解码恢复。 2.2设计目的 (1)了解Huffman编码的基本原理及其特点； (2)理解并熟练对图像进行哈夫曼编码的算法； (3)学习和熟悉MA TLAB图像处理工具箱； (4)熟悉和掌握MA TLAB程序设计方法； 2.3设计要求 现灰度图像的Huffman编码和解码恢复图像；处理结果要求最终图像显示，且计算图像的信息熵，平均码字长度，编码效率，压缩比。 3.总体设计方案 3.1系统运行环境 Windows 8.1/10系统 3.2编程软件平台 MATLAB R2013a/R2014a 3.3Huffman编码算法原理 哈夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的哈夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。 (1)计算信源符号出现的概率； (2)将信源符号按其出现的概率，由小到大顺序排列，并从左至右排列为叶节点[1]； 三进制霍夫曼编码 Prepared on 22 November 2020 题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。 ※将霍夫曼编码推广至三进制编码 设一个数据文件包含Q个字符：A1，A2，……，Aq，每个字符出现的频度对应为P：P1，P2，……，Pq。 1.将字符按频度从大到小顺序排列，记此时的排列为排列1。 2.用一个新的符号(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符，记为排列2。(注：若Q-2k=0，则取其值为2，若Q-2k=1，则取其值为 3.) 3.对排列2重复上述步骤2，直至最后剩下3个概率值。 4.从最后一个排列开始编码，根据3个概率大小，分别赋予与3个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。 5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。 6.如此一直往前，直到排列1所有的频度值都被编码为止。 举例说明如下（假设Q=9）： 频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1~A9的码字依次为：2,00,02,10,11,12,010,011,012。 构造三进制霍夫曼编码伪码程序如下： HUFFMAN(C) 1 n ←∣C ∣ 2 Q ← C 3 for i ← 1 to n-1 4 do allocate a new node s 5 left[s] ← x ← EXTRACT-MIN(Q) 6 middle[s] ← y ← EXTRACT-MIN(Q) 7 right[s] ← z ← EXTRACT-MIN(Q) 8 f[s] ← f[x]+f[y]+f[z] 9 INSERT(Q，z) 10 return EXTRACT-MIN(Q) ※霍夫曼编码（三进制）最优性证明 在二进制霍夫曼编码中，文件的最优编码由一棵满二叉树表示，树中每个非叶子结点都有两个子结点。在此与之相对应，构造一棵满三叉树来表示三进制的霍夫曼编码，树中每个非叶子结点都有三个子结点。对文件中A中的每个字符a，设f(a)表示a在文件中出现的频度，d T(a)表示字符a的编码长度，亦即a 的叶子在树中的深度。这样，编码一个文件所需的位数就是 B(T)=∑f(a)d T(a) 设A为一给定文件，其中每个字符都定义有频度f[a]。设x，y和z是A中具有最低频度的两个字符。并设A'为文件A中移去x，y和z，再加上新的字符s后的文件，亦即A'=A-{x,y,z}∪{s}；如A一样为A'定义f，其中f[s]=f[x]+f[y]+f[z]。设T'为文件A'上最优 #include 图像压缩编码实验报告 一、实验目的 1.了解有关数字图像压缩的基本概念，了解几种常用的图像压缩编码方式； 2.进一步熟悉JPEG编码与离散余弦变换（DCT）变换的原理及含义； 3.掌握编程实现离散余弦变换（DCT）变换及JPEG编码的方法； 4.对重建图像的质量进行评价。 二、实验原理 1、图像压缩基本概念及原理 图像压缩主要目的是为了节省存储空间，增加传输速度。图像压缩的理想标准是信息丢失最少，压缩比例最大。不损失图像质量的压缩称为无损压缩，无损压缩不可能达到很高的压缩比；损失图像质量的压缩称为有损压缩，高的压缩比是以牺牲图像质量为代价的。压缩的实现方法是对图像重新进行编码，希望用更少的数据表示图像。应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分为以下3类： （1）无损压缩编码种类 哈夫曼（Huffman）编码，算术编码，行程（RLE）编码，Lempel zev编码。（2）有损压缩编码种类 预测编码，DPCM，运动补偿； 频率域方法：正交变换编码(如DCT)，子带编码； 空间域方法：统计分块编码； 模型方法：分形编码，模型基编码； 基于重要性：滤波，子采样，比特分配，向量量化； （3）混合编码 JBIG，H.261，JPEG，MPEG等技术标准。 2、JPEG 压缩编码原理 JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。其中最常用的是基于DCT变换的顺序式模式，又称为基本系统。JPEG 的压缩编码大致分 霍夫曼编码 霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。1952年，David A. Huffman在麻省理工攻读博士时所提出一种编码方法，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 该方法完全依据字符出现概率来构造异字头的平均长度最短的 码字，有时称之为最佳编码，一般就叫作Huffman编码。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他 在MIT信息论的同学需要选择是完成学期报告还是期末考试。 导师Robert M. Fano给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 霍夫曼（Huffman）编码是一种统计编码。属于无损（lossless）压缩编码。 以霍夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 ←根据给定数据集中各元素所出现的频率来压缩数据的 一种统计压缩编码方法。这些元素(如字母)出现的次数越 多，其编码的位数就越少。 ←广泛用在JPEG, MPEG, H.2X等各种信息编码标准中。霍夫曼编码的步骤 霍夫曼编码的具体步骤如下： １）将信源符号的概率按减小的顺序排队。 ２）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在上部，直到最后变成概率１。 3）将每对组合的上边一个指定为1，下边一个指定为0（或相反）。４）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。 信源熵的定义： 概率空间中每个事件所含有的自信息量的数学期望称信源熵或简称熵(entropy)，记为： 例：现有一个由5个不同符号组成的30个符号的字 符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 哈夫曼树描述文档 一、思路 通过一个argv[]数组存储从test文件中读取字母，然后利用ascal 码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。 二、截图 三、代码 #include intrchild; }HTNode; typedefstruct { char cd[50]; int start; }HCode; using namespace std; int enter(char argv[])//进行读入操作 { fstream in; ofstream out; char c; int number=0;//字母个数置为0 in.open("test.txt",ios::in); //打开文件test.txt out.open ("code.txt",ios::trunc); //打开文件code.txt，如果不存在就新建一个，如果存在就清空 if(!in.eof()) in>>c; //从test.txt中读取一个字符存入c printf("原文本是:\n"); while(! in.eof()){ //文件不为空，循环读取一个字符 cout< clear X=imread('lena512.bmp'); data=uint8(X); [zipped,info]=huffencode(data); %调用Huffman编码程序进行压缩 unzipped=huffdecode(zipped,info,data); %调用Huffman编码程序进行解码 %显示原始图像和经编码后的图像，显示压缩比，并计算均方根误差得erms=0，表示是Huffman是无失真编码 subplot(121);imshow(data); subplot(122);imshow(unzipped); %erms=compare(data(:),unzipped(:)) cr=info.ratio whos data unzipped zipped function [zipped, info] = huffencode(vector) % 输入和输出都是uint8 格式 % info 返回解码需要的结构信息 % info.pad 是添加的比特数 % info.huffcodes 是Huffman 码字 % info.rows 是原始图像行数 % info.cols 是原始图像列数 % info.length 是原始图像数据长度 % info.maxcodelen 是最大码长 if ~isa(vector, 'uint8') error('input argument must be a uint8 vector'); end [m, n] = size(vector); vector = vector(:)'; f = frequency(vector); %计算各符号出现的概率 symbols = find(f~=0); f = f(symbols); [f, sortindex] = sort(f); %将符号按照出现的概率大小排列 symbols = symbols(sortindex); len = length(symbols); symbols_index = num2cell(1:len); codeword_tmp = cell(len, 1); % 生成Huffman 树，得到码字编码表 while length(f)>1 index1 = symbols_index{1}; index2 = symbols_index{2}; codeword_tmp(index1) = addnode(codeword_tmp(index1), uint8(0)); codeword_tmp(index2) = addnode(codeword_tmp(index2), uint8(1)); #include"stdafx.h" #include"stdio.h" #include"conio.h" #include 实验四哈夫曼树与哈夫曼编码 一、实验内容 [问题描述] 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求] 1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法6.12） 2. 编码：根据建立的Huffman树，求每个字符的Huffman 编码。 对给定的待编码字符序列进行编码。 二、概要设计 算法设计： 要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。 流程图： 算法： 模块： 在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下： 首先建立一个哈夫曼树和哈夫曼编码的存储表示： typedef struct { int weight; int parent,lchild,rchild; char elem; }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树 typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。 构造哈夫曼树： for(i=n+1;i<=m;++i) {//在HT[1……i]选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2); 实验四图像压缩 姓名：学号：邮箱： 一、实验目的 1.掌握DCT变换的原理 2.了解DCT变化在图像压缩中的应用 3.掌握图像压缩的基本原理及方法 4.了解霍夫曼编码原理 5.熟悉图像压缩的MATLAB编程 二、实验原理 DCT是目前比较好的图像变换，它有很多优点。DCT是正交变换，它可以将8x8图像空间表达式转换为频率域，只需要用少量的数据点表示图像；DCT产生的系数很容易被量化，因此能获得好的块压缩；DCT算法的性能很好，它有快速算法，如采用快速傅立叶变换可以进行高效的运算，因此它在硬件和软件中都容易实现；而且DCT算法是对称的，所以利用逆DCT算法可以用来解压缩图像。 由于DCT主要应用在数据和图像的压缩，因此希望原信号的能量在变换后能尽量集中在少数系数上，且这些大能量的系数能处在相对集中的位置，这将有利于进一步的量化和编码。但是如果对整段的数据或整幅图像来做DCT，那就很难保证大能量的系数能处在相对集中的位置。因此，在实际应用中，一般都是将数据分成一段一段来做，一般分成8x8或16x16的方块来做。 二维DCT正交变换的公式为： 二维DCT逆变换公式： 其中 三、实验要求 利用DCT变换对图像进行压缩，对比不同压缩比下的结果，对比不同压缩比下图像大小的变化。压缩过程如下图所示： 四、实验过程与结果 实验程序如下：（先给出主程序，然后给出各功能子函数的程序） 主程序： clear load('')%调入170*170大小的一幅彩色lena图像 l=imresize(lena,[256 256]);%将图像变换为8的整数倍大小 X=rgb2gray(l); Y1=double(X);%读入图像数据lianghua=[16 11 10 16 24 40 51 61;%量化矩阵，量化的程度序决定压缩比 12 12 14 19 26 58 60 55; 14 13 16 24 40 57 69 56; 14 17 22 29 51 87 80 62; 18 22 37 56 68 109 103 77; DCT变换 量化huffman编码 哈夫曼树编码 #include } if (j==t->total) { t->arr[t->total].ch = text[i]; t->arr[t->total].weight = 1; t->total ++; } } printf("char frequence\n"); for (i=0; i 霍夫曼编码的matlab实现 一、实验内容： 用Matlab语言编程实现霍夫曼（Huffman）编码。 二、实验原理及编码步骤： 霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。以本教材P74例题3-18信源为例： 信源： X x1 x2 x3 x4 x5 q(X) = 0.4 0.2 0.2 0.1 0.1 解： 通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。 特点：霍夫曼编码在三种编码方法中编码效率最高 基本步骤：p72 三、实验程序及运行结果 （见附录6） 程序流程图：XXXXXXXXXXXX 四 分析结果 由程序运行结果可知： 方法一（概率之和往上排）： 码字：11 01 00 101 100 编码效率： %4.962 .212 .21log 2 .22.038.0212 .2)(log ) (log )(log n 5 11≈= ==?+?==-= = ∑ηη所以：） （D n X H D n xm q xm q D X H 码长均值：2.22.038.02n 1=?+?= 码长均方差：{}16.02.0)2.23(8.0)2.22()2221=?-+?-=-n n E （ 方法二（概率之和往下排）： 码字：0 10 111 1101 1100 编码效率： %4.962 .212 .21log 2.22.042.032.024.0112.2)(log ) (log )(log n 5 12≈= ==?+?+?+?==-= =∑ηη所以：） （D n X H D n xm q xm q D X H 码长均值：2.22.042.032.024.01n 2=?+?+?+?= 码长均方差： { }36 .12.02.2-42.02.2-32.0)2.22(4.0)2.21()2 2222 22=?+?+?-+?-=-）（）（（n n E 比较方法一和方法二可知：两张编码方法平均码长相等，但方法二均方差较大，一般取均方 差小的编码方法，这样译码会更简单。 1．哈夫曼编码的方法 编码过程如下: (1) 将信源符号按概率递减顺序排列; (2) 把两个最小的概率加起来, 作为新符号的概率; (3) 重复步骤(1) 、(2), 直到概率和达到1 为止; (4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出"1"、"0"序列（从码数的根到终节点）。 2．哈夫曼编码的特点 ①哈夫曼方法构造出来的码不是唯一的。 原因 ·在给两个分支赋值时, 可以是左支( 或上支) 为0, 也可以是右支( 或下支) 为0, 造成编码的不唯一。 ·当两个消息的概率相等时, 谁前谁后也是随机的, 构造出来的码字就不是唯一的。 ②哈夫曼编码码字字长参差不齐, 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。 ·当信源概率是2 的负幂时, 哈夫曼码的编码效率达到100%; ·当信源概率相等时, 其编码效率最低。 ·只有在概率分布很不均匀时, 哈夫曼编码才会收到显著的效果, 而在信源分布均匀的情况下, 一般不使用哈夫曼编码。 ④对信源进行哈夫曼编码后, 形成了一个哈夫曼编码表。解码时, 必须参照这一哈夫编码表才能正确译码。 ·在信源的存储与传输过程中必须首先存储或传输这一哈夫曼编码表在实际计算压缩效果时, 必须考虑哈夫曼编码表占有的比特数。在某些应用场合, 信源概率服从于某一分布或存在一定规律 使用缺省的哈夫曼编码表有 解：为了进行哈夫曼编码, 先把这组数据由大到小排列, 再按上方法处理 （1）将信源符号按概率递减顺序排列。 （2）首先将概率最小的两个符号的概率相加，合成一个新的数值。 （3）把合成的数值看成是一个新的组合符号概率，重复上述操作，直到剩下最后两个符号。 5．4．2 Shannon-Famo编码 Shannon-Famo(S-F) 编码方法与Huffman 的编码方法略有区别, 但有时也能编 出最佳码。 1．S－F码主要准则 符合即时码条件; 在码字中,1 和0 是独立的, 而且是( 或差不多是)等概率的。 这样的准则一方面能保证无需用间隔区分码字,同时又保证每一位码字几乎有 1位的信息量。 2．S－F码的编码过程 信源符号按概率递减顺序排列; 把符号集分成两个子集, 每个子集的概率和相等或近似相等; 霍夫曼编码 四川大学计算机学院2009级戚辅光 【关键字】 霍夫曼编码原理霍夫曼译码原理霍夫曼树霍夫曼编码源代码霍夫曼编码分析霍夫曼编码的优化霍夫曼编码的应用 【摘要】 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman 编码。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。它属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 【正文】 引言 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 霍夫曼编码原理： 霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[]，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个操作2*n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantree[i].parent，如果i是myHuffmantree[i].parent 的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了。 霍夫曼树： 题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。 ※将霍夫曼编码推广至三进制编码 设一个数据文件包含Q个字符：A1，A2，……，Aq，每个字符出现的频度对应为P：P1，P2，……，Pq。 1.将字符按频度从大到小顺序排列，记此时的排列为排列1。 2.用一个新的符号(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符，记为排列2。(注：若Q-2k=0，则取其值为2，若Q-2k=1，则取其值为 3.) 3.对排列2重复上述步骤2，直至最后剩下3个概率值。 4.从最后一个排列开始编码，根据3个概率大小，分别赋予与3个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。 5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。 6.如此一直往前，直到排列1所有的频度值都被编码为止。 举例说明如下（假设Q=9）： 字符A1 A2 A3 A4 A5 A6 A7 A8 A9 频度0.22 0.18 0.15 0.13 0.10 0.07 0.07 0.05 0.03 字符频度编码频度编码频度编码频度编码A1 0.22 2 0.22 2 0.30 1 0.480 A2 0.18 00 0.18 00 0.22 2 0.30 1 A3 0.15 02 0.1501 0.18 00 0.22 2 A4 0.13 10 0.15 02 0.15 01 A5 0.10 11 0.13 10 0.15 02 A6 0.07 12 0.10 11 A7 0.07 010 0.07 12 A8 0.05 011 A9 0.03 012 频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1~A9的码字依次为：2,00,02,10,11,12,010,011,012。 构造三进制霍夫曼编码伪码程序如下： HUFFMAN(C) 1 n ←∣C ∣ 2 Q ← C 3for i ←1 to n-1 4 do allocate a new node s 哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路霍夫曼编码表
哈夫曼树的编码与译码
基于MATLAB的图像Huffman编码研究.docx
三进制霍夫曼编码
实验六 哈夫曼树及哈夫曼编码
图像压缩编码实验报告
霍夫曼编码
构建哈夫曼树及输出哈夫曼代码及算法思想
霍夫曼图像压缩编码源程序
哈夫曼树的编码和译码
实验四 哈夫曼树与哈夫曼编码
实验四dct变换huffman编码图像压缩
哈夫曼树编码
霍夫曼编码
哈夫曼编码的方法
霍夫曼编码原理
三进制霍夫曼编码
哈夫曼树实验报告