哈夫曼编码实践
实践要求
- 设有字符集：S={a,b,c,d,e，f,g,h,i,j,k,l,m,n.o.p.q,r,s,t,u,v,w,x,y,z}。 给定一个包含26个英文字母的文件，统计每个字符出现的概率，根据计算的概率构造一颗哈夫曼树。 并完成对英文文件的编码和解码。
- 要求： （1）准备一个包含26个英文字母的英文文件（可以不包含标点符号等），统计各个字符的概率 （2）构造哈夫曼树 （3）对英文文件进行编码，输出一个编码后的文件 （4）对编码文件进行解码，输出一个解码后的文件
哈夫曼编码
- 一种编码方式，可以通过其算法来减小数据的存储空间，从而达到压缩文件的目的。
- 主要原理：
-
- 计算各个元素出现的频率也就是每个元素所占总元素的权重。根据权重的大小来进行后续的处理。
-
- 哈夫曼树，通过树的数据结构来存储数据。哈夫曼树可以不为完全树，其度为2。特点在于，父结点总是给左子树为0，右子树为1。
-
- 哈夫曼树的构造。对于所有元素，首先求出其所有的权重。对于这些森林，每次选出权重最小的两棵树，求其和，作为这两棵树的父结点。最终构造出哈夫曼树。根据其构造方法，我们可以发现，权重越大的结点，也就是其对应的元素越靠上，这样做的原因是因为权重越大，出现的愈加频繁，所以，以较短长度来替换出现次数最多的元素。从而使得存储空间得以减少。
-
- 广度优先遍历，在得到各个结点的编码时，我们使用广度优先遍历来根据每层来增加一个0或1。不过，哈夫曼树是个树，也就是使用层序遍历来得到每个结点的编码。
代码实现
- 在将对一个个的字符转换时，我想到计算机中每个元素都对应着一个ASCII码表值，所以，将其转化为ASCII值后，统计将变得较为便利。同时，为了存储数据方便，我使用了线性表来存储每一个结点。
- 广度优先遍历，之前学习过这种遍历方法，也就是使用队列和列表来得到相应的结点，并在此时得出对应的哈夫曼码。先将父结点存入队列，再将其孩子结点存入队列，再将其弹出，弹出的进入列表。这样，这个列表就存储着所有的带着霍夫曼码的结点。
public Node createTreee(Listnodes){ while (nodes.size()>1){ Collections.sort(nodes); Node left = nodes.get(nodes.size()-1); Node right = nodes.get(nodes.size()-2); Node parent = new Node(null,left.getWeight()+right.getWeight()); parent.setLeft(left); parent.setRight(right); nodes.remove(nodes.size()-1); nodes.remove(nodes.size()-1); nodes.add(parent); } return nodes.get(0); } //广度遍历 public static List levelTraverse(Node root){ List list = new ArrayList (); Queue queue = new ArrayDeque (); if (root != null) { queue.offer(root); root.getLeft().setCode(root.getCode() + "0"); root.getRight().setCode(root.getCode() + "1"); } while (!queue.isEmpty()) { list.add(queue.peek()); Node node = queue.poll(); if (node.getLeft() != null) node.getLeft().setCode(node.getCode() + "0"); if (node.getRight() != null) node.getRight().setCode(node.getCode() + "1"); if (node.getLeft() != null) { queue.offer(node.getLeft()); } if (node.getRight() != null) { queue.offer(node.getRight()); } } return list; }
结点实现类
public Node(T data,double weight){ this.data = data; this.weight = weight; this.code=""; } public Node(T data, double weight, String code){ this.data = data; this.weight = weight; this.code = code; } 运行结果
出现的问题
- 出现了比较多的问题有类转化问题。
- 因为使用了ASCII值，所以在使用诸如Long.parseLong()方法时，就会出现错误，因为char值不能使用String值进行强制类型转化，所以，在得到一个char值后，如果我们想使其变为String型时，最简单的方法就是给它加一个空字符串也就是“”，就可以了。
- 同时，这次在读取文本时也出现了问题。往往最后一位的空格可能导致出错，因为其不可见，我们往往可能忽视这一细节。在写入时也可能导致出现这种错误。