精明的巨人源代码实验报告
实验1 :精明巨人源代码综合设计【实验目的】通过本专题设计，掌握精明巨人代码的原理和实现方法，熟悉c语言编程，对典型文本数据和图像数据进行精明巨人编解码器。 【预备知识】1、熵的概念、精明巨人编码原则2、数据结构与算法设计3、c (或c )编程语言【实验环境】1、设备：计算机一台2、软件： c程序编译器【 用c语言设计和实现精明的巨人队编码和解码程序，需要对给定的典型文本数据和图像数据进行精明的巨人队编码编解码器【实验原理】霍夫曼编码是熵编码的方法之一，源符号中的Huffman编码的主要思想是：出现概率高的码由长码字表示； 相反，出现概率小的代码用短码字表示。 Huffman编码过程说明：1.将初始化：源符号按出现频率升序排列，输入集合l； 2 .重复以下操作，直到l中的仅一个节点：(a )从l获得具有最低频率的两个节点并且创建其父节点为止； (b )分配给它们的频率和父节点，并将其插入到l中； 3 .进行编码：从根节点开始，赋予左子节点1，右节点0，直至叶节点。 2【基本定义】1 .熵和平均码长熵是信息量的测量方法，一个事件出现的概率越低，表示该事件包含的信息越多。 根据Shannon理论，源s的熵被定义为符号2 () log (1/) IIhspIp信号出现在s中的概率； 如果将包含在其中的信息量、即编码所需的Is2log(1/) i p i S i S的比特数设为编码后的长度lI ) I=1，n，则平均编码长度l为IsIIIlpl2。 压缩率将原始字符串的全长设为L orig位。 设编码后的全长为L coded位，则压缩率r以符号a、b、c、d、e表示，40个像素中出现灰度a的像素数为15个，出现灰度b的像素表1符号在图像中出现的数符号A B C D E出现的次数15 7 7 6 5根据Shannon理论，该图像的熵为h(s )=) 15/40 ) (( (40/15 ) )7/40 ) (40/5 ) 40 ) *1)的表2精明的巨人队的代码例符号的出现次数log2(1/PI ) 2.736900118 E5 )，指示分配的代码所需的位数a15(0.375 ) 1.4150115b7 ) 0.175 ) 01121c7 ) 0.175 ) 2.514501021d6 ) 0.150 ) 精明巨人代码的代码长度可变，但不需要另外添加同步代码。 例如，如果代码串的第一位是0，则它无疑是代码a。 因为没有一个符号以0开头，表示其他符号，所以下一位表示下一个符号的第一位。 同样，如果出现“110”，它表示3符号d。 制作一个“词典”，解释各种代码的含义——码本，就可以根据码本一个个地按顺序对代码进行解码。 【实验步骤】(16学时)根据提供的样例Huffman编解码源程序，用VC 6.0编译生成可执行文件，读取程序运行。 1、在Microsoft Office Vision中分别绘制Huffman编码和解码程序流程图，并写出使用的主要数据结构进行说明。
2、在Huffman编码器的适当位置加入calcProbability、calcEntropy、calcAvgSymbolLength、calcCompressionRatio个函数，分别出现源的各个符号的概率(自定义函数参数) 3、分析精明巨人编译代码的计算复杂性，定量说明Huffman编码还是解码操作更费时间。 4、设计中遇到的问题，是如何解决的？ 设计过程中的心得体会。 考题： 1、精明的巨人代码有唯一性吗？ 2、关于精明巨人队编码方式不足的个人想法，以及在进行压缩时避免这些问题的方法。 3、分析精明巨人队编码对文本数据和图像数据的编码效率，观察其与相应源概率分布的关系。 4、参考静态图像压缩编码国际标准JPEG，为了提高图像编码效率，通常在精明的巨人编码之前做什么操作？ 5、 【实验结果】1 .解码和编码流程图如下。 1 .解码流程图4否否否2 .编码
流程图 程序初始化 主程序 调用图像库数据 接收到有效指 令？ 图像显示指令？ 字符显示指令？ 图像像素数据？ 返回主程序 显示图像 显示字符 JPEG 格式图像解码 调用字符库数据5 否 是 是 否 是 否 否 是 二．四个部分的程序 1.计算每个个符号出现的概率 void calcProbability(int total, SymbolFrequencies *pSF) { 程序初始化 主程序 调用图像库数据 接收到有效指 令？ 图像显示指令？ 字符显示指令？ 图像像素数据？ 返回主程序 显示图像编码 显示字符编码 JPEG 格式图像编码 调用字符库数据6 int i; float prob[MAX_SYMBOLS]; memset(prob, 0, sizeof(prob)); for(i = 0; i count / total; printf(“%c, %fn“, (*pSF)[i]->symbol, prob[i]); } } } 2.计算熵 void calcEntrop(SymbolFrequencies *pSF) { int i; float prob[MAX_SYMBOLS]; double entropy; double difference; double difference1; double difference2; entropy = 0; for(i = 0; i < MAX_SYMBOLS; ++i) { difference1 = log(prob[i]); difference2 = log(2); difference = difference1/difference2; entropy = entropy - prob[i]*difference; } printf(