数据结构试验报告霍夫曼编码.doc

数据结构实验报告 （三） 学院 自动化学院学号 姓名 日期 2014-12-09实验目的1、 掌握哈夫曼编码原理；2、熟练掌握哈夫曼树的生成方法；3、理解数据编码压缩和译码输出编码的实现；4、掌握二叉树的基本3操作。实验内容利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。 实验要求1） 初始化（Initialzation）。利用下表给出的字符集和频度的=;实际统计数据建立哈夫曼树，并将它存于文件hfmTree中；字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161 2） 编码（EnCoding）。利用已建好的哈夫曼树（若不在内存中，则从文件hfmTree中读入），对以下报文进行编码，结果存入文件CodeFile中；报文内容：THIS PROGRAM IS MY FAVORITE 3） 译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile中编码后的报文进行解码，结果存入文件Textfile中； 4） 输出（Output）。输出字符集中每个字符的哈夫曼编码；输出原始报文，及其编码文件CodeFile和解码文件Textfile的内容。 扩展要求：将2）的编码结果以二进制形式存入CodeFile中，输出原始报文长度和编码后的报文长度。1 需求分析 （1） 将实验要求中的表格写在文件“HfmTree.txt”中，程序初始化时从该文件中读取字符及其频度，并据此建立Hfm树，生成编码表，打印出编码表；（2） 编码：用上一步生成的编码表，对报文进行编码，考虑到数据压缩性，这一步将编码结果以二进制文件进行存储，文件名为CodeFile；（3） 解码：从文件CodeFile中读入编码后的报文，利用建立好的Hfm树对其进行一一解码，输出解码结果，同时将结果存入Textfile.txt中；2 概要设计因本次实验涉及许多字符串的操作，文件读写，并且除了霍夫曼树外，还用到了许多其他数据结构，而本次实验重点在霍夫曼树上，为了省去编写其他数据结构的时间，本次实验选用了C#语言和 .NetFrameWork 4.0来实现。自定义数据结构和类： 2.1 Node类：表示霍夫曼树的一个节点，在C#结构体是值类型，类是引用类型，故必须将结点定义成类;成员变量：public char data = 0; /该结点对应的欲编码的字符public double probability; /频度，出现概率，即结点的权重public Node left = null; /左子结点public Node right = null;/右子结点public bool isAccess = false;/用于标记是否已被访问过public int id = 0; /独一无二的id，用于唯一标识一个结点static int curId = 0;/每创建一个新Node时，都自动分配给其一个id，这个id逐个加1，防止出现完全相同的节点导致无法比较大小方法：此外为了排序方便，实现了IComparable接口的CompareTo函数，定义结点之间的比较大小规则，根据实际需求，首先比较频度（权值），如果一样则通过唯一标识的id加以区分。2.2 HfmTree类：表示一颗Hfm树成员：public Node root = null;/树的根结点方法：public HfmTree(Node nodes) /根据结点数据构造Hfm树 public HfmTree(string fileName) /根据文件里的数据构造Hfm树 public Dictionary CreateCodeTable()/创建编码表，为每个字符创建一个编码 public string DeCode(string code) /根据输入的二进制编码进行解码，还原文本2.3 用到的.Net里的数据结构Dictionary：字典类，由键和值组成的集合，键、值可为任意类型，在 本作业中适合于存储编码表；Stack ：用于存储结点的栈，在遍历Hfm树的时候需要用于回到父结点；SortedSet：这是个结点的集合，而且里面的结点是自动排好序的，在建立霍夫曼树时寻找最小权值结点时要用到；List ：这是Byte型数据的链表，在创建二进制编码文件时用于组织文件的组成字节，该类型提供了函数可直接转成数组，非常方便；2.4 全局函数static void CreateBinaryFile(string code, string filename)根据编码字符串code创建二进制文件static string ReadCodeFromBinaryFile(string filename)读取二进制文件还原成编码字符串2.5 Main函数流程a.读取文件HfmTree，根据文件里的内容创建结点，进而构建霍夫曼树，文件HfmTree的形式如下：每行表示一条记录，先是字符，然后隔一个空格写上其频度；b. 根据生成的树，遍历树，生成编码表并输出；c. 输出原始报文，并对其进行编码，编码结果输出到终端；d. 将编码结果以二进制形式保存成文件Codefile，其中Codefile的前四个字节用于标识编码的总长度，从第五个字节开始按位存储0和1的编码（从高位到低位填充），最后一个字节如果填不满默认为0；e. 读入Codefile文件，将内容还原成string形式的编码结果，并将此结果送至HfmTree进行解码得到原文，输出解码原文，并将结果存入Textfile.txt 中。3 详细设计public HfmTree(string fileName) /根据文件里的数据构造Hfm树 SortedSet sortedNodes = new SortedSet();/按序存储所有节点集 sortedNodes.Clear(); StreamReader reader = File.OpenText(fileName);/读入文件 string curLine = ; char split=new char1; split0= ; while (true) curLine=reader.ReadLine(); string data=curLine.Split(split); if (data.Length 2) break; char charData = data00; if (charData = 0) charData = ; double prob = Convert.ToDouble(data1); sortedNodes.Add(new Node(charData, prob);/创建新结点加入有序结点集 if (reader.EndOfStream) break; reader.Close(); Node min = null; /当前结点集最小的元素 Node min2 = null;/当前结点集次小的元素 Node parent = null; /用于产生合并子结点的父结点 while (true) min = sortedNodes.ElementAt(0); min2 = sortedNodes.ElementAt(1);/首先取出权值最小的两个结点 sortedNodes.Remove(min); sortedNodes.Remove(min2);/最小的两个从结点集中去除 parent = new Node(0, bability + bability);/创建一个父结点连接最小的两个结点 parent.left = min; parent.right = min2; sortedNodes.Add(parent);/将合并后的结点加入结点集 if (sortedNodes.Count 2)/如果结点集中只剩一个元素，则构建完毕，跳出循环 break; root = parent;/设置根结点 public Dictionary CreateCodeTable()/创建编码表，为每个字符创建一个编码 Dictionary codeTable = new Dictionary();/创建空字典 Stack nodeStack = new Stack();/创建结点栈 string curCode = ;/当前编码字符串 Node curNode = root;/当前访问的结点 while (true) curNode.isAccess = true;/将当前结点标记为已访问过 if (curNode.left = null)/如果当前结点没有子节点，将curCode作为当前结点的data的编码，加入字典 codeTable.Add(curNode.data, curCode); /Console.WriteLine(curNode.data.ToString(); curNode = nodeStack.Pop();/返回上一个结点 curCode = curCode.Remove(curCode.Length - 1);/curCode去掉最新的一位 continue; else if (!curNode.left.isAccess)/如果左结点未访问过，跳至左子结点 nodeStack.Push(curNode); curCode = curCode + 0; curNode = curNode.left; continue; else if (!curNode.right.isAccess)/如果右结点未访问过，跳至左子结点 nodeStack.Push(curNode); curCode = curCode + 1; curNode = curNode.right; continue; else/如果左右都已访问过，则需要返回上一结点 if (nodeStack.Count 0)/如果栈未空，则返回上一结点 curNode = nodeStack.Pop(); curCode = curCode.Remove(curCode.Length - 1); continue; else /如果栈已空，说明已经遍历完毕，退出循环 break; return codeTable; /根据输入的二进制编码进行解码，还原文本 public string DeCode(string code) Node cur=root; string output = ; foreach (char x in code) if (x = 0)/若是0，则进入左子树 cur = cur.left; if (cur.left = null)/成功解出一个字符，加入输出字符串 output = output + cur.data.ToString(); cur = root;/返回根结点 else if (x = 1)/若是1，则进入右子树 cur = cur.right; if (cur.left = null) output = output + cur.data.ToString(); cur = root; else return ; return output; 4 调试分析调试过程中遇到了一点问题。最初结点node类是没有唯一id去标识的，导致在比较大小时出现相等（权值和相等，又不是原始的子结点）的情况，sortedSet无法处理这种情况，所以编码表里重复的几项就被遗漏了。后来想到用流水方式分配给每个新建的Node一个独一无二的id，这样用id来做第二排序关键字，于是就不会出现无法排序的情况。最终运行时也不会遗漏了。5 测试结果从输出的编码表可看出，频度越小的字母编码越长，越大的编码越短，而且具有前缀性，不会产生歧义，这说明hfm树构建正确。然后输出了原始报文，长度为27，编码后输出了编码字符串，后将此字符串打包成二进制文件长度变为19（文件头占了4字节），可见数据已经被压缩了。最后从文件读取二进制编码并进行了解码，可看出解码后结果完全正确。之后我们通过winhex检查了Codefile里的内容，03字节表示了实际编码位数，第四字节D1变为二进制为11010001，第五字节为01100011可见二进制