压缩程序(哈弗曼编码算法).ppt

压缩程序 哈弗曼编码算法 谢涛 需求分析 1 写一个对txt文件压缩和解压的程序 使用动态编码 2 使用Huffman编码压缩和解压时 Huffman树的存储可以直接存储树结构 也可以存储所有字符的频度或权值 然后读取时建立Huffman树 3 使用Huffman编码压缩和解压时 注意定义压缩码的结束标记 可以使用一个特殊的字符作为结束标记 也可以在压缩码之前存储其比特长度 如果使用一个特殊字符作为结束标记 则其频度为1 需要在建立Huffman树时把它看作一个独立的字符进行建树 4 使用Huffman编码压缩和解压时 在一个缓冲区里面收集压缩码比特流 每当收集的比特数满8时 可以把这8比特通过位操作合并成一个字节写入文件 当然也可以收集满一定数目的字节后再写入文件 写入文件的最小信息单位为字节 概要分析 采用顺序表实现对Huffman树的存储 Huffman树存储结构 typedefstruct intweight intlchild rchild parent HuffmanTree typedefHuffmanTreeHTree m weight域存有该节点字符的权值 lchild rchild parent分别存放该节点的左孩子 右孩子和双亲节点在顺序表中的位置 采用顺序表实现对Huffman编码的存储 Huffman编码存储结构 typedefstruct charch intstart charbits n 1 HuffmanCode typedefHuffmanCodeHCode n ch存放对应的字符 start存放Huffman编码在字符数组bits 中开始的位置 抽象数据 抽象数据类型定义 ADT 数据对象 txt文档基本操作 FileRead intcount chars charfilename 初始条件 压缩文档存在 操作结果 对该文档进行读取 求其所有出现的字符和字符的权值 CreateHuffmanTree HTreeT intN intcount chars 初始条件 以求得该文档的字符和权值 操作结果 建立Huffman树 HuffmanCoding HTreeT HCodeH intN chars 初始条件 Huffman树 操作结果 求各个字符的Huffman编码 FilePrint HTreeT HCodeH intN 初始条件 求得Huffman编码以及各节点的权值 操作结果 将求得的数据分别存放在HuffmanCode txt Char txt Weight txt中 FileWrite HCodeH intN charfilename 初始条件 求得Huffman编码以及各节点的权值 操作结果 将文档翻译成Huffman编码以字符形式存放在File txt中 FileConvert void 初始条件 File txt存在 操作结果 将字符形式的Huffman编码翻译成二进制形式 每首季8比特就通过位操作合并成一个字节写入文件code txt中 最后不足8位时将最后的几位存放在Tail txt中 FileRead HTreeT HCodeH 初始条件 压缩生成的HuffmanCode txt Char txt Weight txt存在 操作结果 读取字符及其权值和其Huffman编码 FileExtract void 初始条件 压缩结果文件Code txt和tail txt存在 操作结果 将code txt和tail txt中的字符写成编码的二进制字符形式 写进file00 txt FileTrans HTreeT HCodeH intN 初始条件 已生成File00 txt并已求得各个字符的Huffman编码 Huffman树已建立 操作结果 将Huffman编码翻译成原文件 写入translated txt ADT还需要包含调用若干库文件 stdio h malloc h string h 采用C语言的编程方法在VC 6 0环境下实现本题目的要求 主程序流程图 压缩部分 include include include defineMAX SIZE1000000 definen150 definem2 n 1typedefstruct charch intweight intlchild rchild parent HuffmanTree typedefHuffmanTreeHTree m typedefstruct charch charbits n 1 HuffmanCode typedefHuffmanCodeHCode n 一 宏定义及节点定义 由于文档限于英文文章 所以字符的ASCII码限于0 150 依次读取文档的各个字符 计算每个字符出现的次数为权值 再将数组压缩 没有出现的字符从数组中删去 返回文档出现不同字符的个数算法如下 1 统计字符出现的频率 即权值的函数intapprate char s intcnt charstr 方法具体实现如下 定义两个数组 分别存放大写和小写英文字母 a 将两个数组初始化都为0 b 如果取出的字符是小写字母 则将小写字母转换为数字 每一个字符对应一个数字 同一个字符出现一次频率就加1 直到全部统计出为止 如果取出的是大写字母 方法如小写字母的实现方法 c 再将转换都的数字再转换为相应的字符 以便为下面的建树方便调用 具体代码如下 二读取原文档函数 intFileRead intcount chars charfilename inti 0 N 0 k 0 temp n charc FILE rf rf fopen filename r if rf NULL printf cannotopenfile n exit 0 for i 0 i n i temp i 0 count i 0 while feof rf c fgetc rf k c temp k i fclose rf for i 0 i n i if temp i 0 s N i count N temp i N returnN FileRead 三生成Huffman树函数 选取字符中权值最小的两个节点建树 将权值相加放在根节点中 将原节点删除 新节点放入数组 递归进行上述操作直到数组中只有一个节点为止 算法如下 2 建立哈夫曼树构造哈夫曼数时 首先将n个权值的叶子结点存放到数组huffTree 2 num 的前n个分量中 然后不断的将两棵子树合并为一棵子树 并将新子树的根结点顺序存放到数组huffTree 2 num 的前n个分量的后面 设n个叶子的权值保存在数组cnt n 中 哈夫曼树的存储主要是利用数组存储 例如将已知字符窜s为abcdeacedaeadcedabadadaead统计出的字符频率分别为a 9 b 2 c 3 d 7 e 5则构造哈夫曼树的存储空间的初始状态最后状态如图 伪代码描述为 1 数组哈夫曼树HuffmanTree初始化 所有元素结点的双亲 左右孩子都置为0 2 数组哈夫曼树HuffmanTree的前n个元素的权值给定权值cnt n 3 进行n 1次合并c 1 在二叉树集合中选取两个权值最小的根结点 其下标分别为i1和i2 c 2 将二叉树i1和i2合并为一棵新的二叉树k voidCreateHuffmanTree HTreeT intN intcount chars inti j p1 0 p2 0 l1 l2 for i 0 i 2 N 1 i T i lchild 0 T i rchild 0 T i parent 0 for i 0 i N i T i weight count i for i N i 2 N 1 i l1 l2 1000000 for j 0 j i j if T j parent 0 if T j weight l1 l1 T j weight p1 j for j 0 j i j if T j parent 0 if T j weight l2 CreateHuffmanTree 四求Huffman编码函数 从叶子节点找到根节点 若该节点是双亲节点的左孩子为1 反之为0 直到根节点为止求得该节点Huffman编码的逆序列 1 对哈夫曼树进行编码函数voidHuffmancoding elementhuffTree CodeCodeNode charstr intn 主要思想 规定哈夫曼编码树的左分支代表0 右分支代表1 则从根结点对应的字符的编码 称为哈夫曼编码 例如上面所举例子的哈夫曼编码构造树及哈夫曼编码 对每个叶子结点进行编码 a 1初始化编码深度为0 将孩子结点的双亲结点付给一个变量 双亲结点不为空时 深度加1 继续向上查找 这时该双亲结点已变成孩子结点 循环知道双亲结点为空 求出每一个叶子结点的深度 a 2将编码初始结点初始化为深度 1 将孩子结点的双亲结点付给一个变量 双亲结点不为空时 初始结点 1 如果此孩子为双亲的左孩子 则置为0 否则置为1 循环知道双亲结点为空 编码完毕 函数C代码 voidHuffmanCoding HTreeT HCodeH intN chars intc p i start charcd n 1 cd N 1 0 for i 0 i N i H i ch s i start N c i p T c parent while p if T p lchild c cd start 0 elsecd start 1 c p p T p parent H i start start strcpy H i bits cd HuffmanCoding 五 输出解压信息函数 将求得的数据分别存放在HuffmanCode txt Char txt Weight txt中函数C代码 voidFilePrint HTreeT HCodeH intN inti j 0 FILE rf fp rp rf fopen HuffmanCode txt w fp fopen Char txt w rp fopen Weight txt w while j N for i H j start i N i fprintf rf c H j bits i fprintf rf n j for i 0 i N i fputc H i ch fp for i 0 i N i fprintf rp d n T i weight fclose rf fclose fp fclose rp FilePrint 六 翻译成Huffman编码函数 读取原文件 将每个字符翻译成Huffman编码 以字符形式输导File txt中 读取原文件 将每个字符翻译成Huffman编码 以字符形式输导File txt中 函数C代码 voidFileWrite HCodeH intN charfilename inti k p 0 charc FILE rf fp rf fopen filename r fp fopen File txt w if rf NULL printf cannotopenfile n n exit 0 while feof rf c fgetc rf for i 0 i N i if H i ch c for k H i start k N k fputc H i bits k fp p if p 8 fprintf fp p 0 fclose rf fclose fp FileWrite 七 压缩函数函数 读取File txt文档 每8位子符翻译成二进制 在转化成十进制在翻译成字符 输出到Code txt中 最后不足8位的部分不翻译 直接写入Tail txt中 最后将中间文档File txt删除 主要思想 主要采用二进制转换为十进制的方法进行解压处理 代码如下 voidFileConvert void inti 0 k 0 temp 0 l charst 10 FILE rf fp rp rf fopen File txt r fp fopen Code txt wb rp fopen Tail txt w if rf NULL printf cannotopenfile n n exit 0 while feof rf st i fgetc rf switch st i case 0 k 2 k 0 i break case 1 k 2 k 1 i break case fwrite FileConvert 八压缩程序main函数部分 代码如下 voidmain HTreeT HCodeH ntN intcount n chars n filename 10 printf n printf InputFilename n scanf s filename printf n printf Encoding n N FileRead count s filename printf CharacterIn Char txt n printf CharacterWeightIn Weight txt n CreateHuffmanTree T N count s HuffmanCoding T H N s FilePrint T H N printf HuffmanCodeIn HuffmanCode txt n FileWrite H N filename FileConvert printf CodeFileIn Code txt n printf TailFileIn Tail txt n 压缩部分 主要思想为 对字符窜编码的解码是将编码窜从左到右逐为判别 直到确定一个字符 这可以用生成哈夫曼的逆过程实现 从根结点开始 根据每一位的值是0还是1确定选择左分支还是右分支 直到到达一个叶子结点 然后再从根结点出发 开始下一个字符的翻译 如根据上面的 a 哈夫曼编码树对生成的 b 字符编码表进行解码 从根结点开始 由于第一位是1 所以选择右分支 下一位又是1 又选择右分支 到达叶子结点对应的字符a 再从根结点出发 下一位是0 选择左分支 再下一位是1 则选择右分支 再下一结点为0 选择左分支 到达叶子结点对应的字符c 同理 知道所有的字符都被解出伪代码如下 创建新的文本文档b 读取压缩的二进制文件 按照编码的先后顺序进行读取编码 当文件没结束时 读取编码 从根结点开始 如果此结点有子结点 如果读取的编码为0并且是根结点的左孩子 则将此左孩子置为根结点 如果读取的编码为1并且是根结点的右孩子 则将此右孩子置为根结点 否则的话说明已经有一个字符和编码对应了 输出 再从根结点开始 重复上述过程 知道读取的文件为空 解码完毕 c 关闭文件 include 预处理及相关结构变量声明部分 include include defineMAX SIZE1000000 definen150 definem2 n 1typedefstruct charch intweight intlchild rchild parent HuffmanTree typedefHuffmanTreeHTree m typedefstruct charch charbits n 1 HuffmanCode typedefHuffmanCodeHCode n 一 读取解压信息函数 读取字符及其权值和其Huffman编码 函数C代码 inti 0 j 0 N 0 charc p charstr MAX SIZE FILE rf fp rp rf fopen Char txt r fp fopen HuffmanCode txt r rp fopen Weight txt r if rf NULL printf cannotopenfile n exit 0 if fp NULL printf cannotopenfile n exit 0 if rp NULL printf cannotopenfile n exit 0 while feof rf H N ch fgetc rf T N ch H N ch N while feof fp c fgetc fp switch c case n i j 0 break default H i bits j c j H i bits j 0 break for i 0 i N i T i weight 0 i 0 j 0 while feof rp c fgetc rp switch c case n for p str p 0 p T i weight T i weight 10 p 48 i j 0 break default str j c j str j 0 break fclose rf fclose fp fclose rp returnN 1 FileRead 二翻译为Huffman编译文档函数 将Code txt重新翻译成二进制 在以字符形式输入到File00 txt中 再将Tail txt中的最后编码复制到File txt的最后 函数C代码 intFileExtract void inti j 0 k 0 t temp 0 unsignedcharc chars 8 FILE rf fp rp rf fopen Tail txt r fp fopen File00 txt w rp fopen File00 txt a if rf NULL printf cannotopenfile n exit 0 fscanf rf d s while j 0 i t c t i t FileExtract 三 翻译Huffman编译文档函数 读取二进制文档 从根节点开始找叶子节点 遇到1找左节点 遇到0找右节点 直到为叶子节点为止