本文共 6449 字,大约阅读时间需要 21 分钟。
既然是学习哈夫曼编码,我们首先需要知道什么是哈夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
在日常计算机的使用中,我们一定会出现下面这种情况:假如给定a、b、c、d、e五个字符,它们在文本中出现的概率如下图所示:
字符 | 概率 |
---|---|
a | 0.12 |
b | 0.40 |
c | 0.15 |
d | 0.05 |
e | 0.25 |
我们现在要将文本编码成0/1序列从而使得计算机能够进行读取和计算。为了保证每个字符的独一性,所以我们给予不同的的字符以不同的编码。如果给每个字符赋予等长的编码的话,会使得平均的编码长度过长,影响计算时的性能,浪费计算机的资源(定长编码的缺点)。这时我们就想到了变长编码,理所当然的,给出现概率较大的字符赋予较短的编码,概率较小的字符赋予较长的编码,这样在计算的时候不就可以节省很多时间了吗?可这样我们又面临到了一个巨大的问题,我们来看下面这种情况,我们对字符进行编码:
字符 | 概率 | 编码 |
---|---|---|
a | 0.12 | 01 |
b | 0.40 | 0 |
c | 0.15 | 00 |
d | 0.05 | 10 |
e | 0.25 | 1 |
假设现在文本中的字符是bcd,转换之后的0/1序列为00010,可我们要在转换成文本的时候究竟是把第一位的0读作b还是把前两位的00读作c呢?为了解决这个问题,就又有了前缀码的概念。顾名思义,前缀码的含义就是任意字符的编码都不是其他字符编码的前缀。那么该如何形成前缀码呢?首先我们要构造一棵二叉树,指向左孩子的"边"记作0,指向右孩子的点记作“1”,叶子节点为代编码的字符,出现概率越大的字符离根的距离就越近。
字符 | 概率 | 编码 |
---|---|---|
a | 0.12 | 0100 |
b | 0.40 | 1 |
c | 0.15 | 0101 |
d | 0.05 | 011 |
e | 0.25 | 00 |
我们在前面提到:哈夫曼树的带权路径最小,所以有哈夫曼树构成的前缀码记作哈夫曼编码。哈夫曼作为已知的最佳无损压缩算法,满足前缀码的性质,可以即时解码。
哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。
实现哈夫曼编码的主要思路为从指定的文件中读出文本,首先通过遍历获得各个字符出现的概率,根据出现概率的大小构造二叉树,在此基础上进行编码解码。
public class Nodeimplements Comparable > { private T data; private double weight; private Node left; private Node right; String code; public Node(T data, double weight){ this.data = data; this.weight = weight; this.code = ""; } public T getData() { return data; } public void setData(T data) { this.data = data; } public double getWeight() { return weight; } public void setWeight(double weight) { this.weight = weight; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } public String getCode(){ return code; } public void setCode(String str){ code = str; } @Override public String toString(){ return "data:"+this.data+";weight:"+this.weight+";code: "+this.code; } @Override public int compareTo(Node other) { if(other.getWeight() > this.getWeight()){ return 1; } if(other.getWeight() < this.getWeight()){ return -1; } return 0; }}
public NodecreateTree(List > nodes) { while (nodes.size() > 1) { Collections.sort(nodes); Node left = nodes.get(nodes.size() - 2); left.setCode(0 + ""); Node right = nodes.get(nodes.size() - 1); right.setCode(1 + ""); Node parent = new Node (null, left.getWeight() + right.getWeight()); parent.setLeft(left); parent.setRight(right); nodes.remove(left); nodes.remove(right); nodes.add(parent); } return nodes.get(0); }
public List> breadth(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; }
File file = new File("G:/usually/input/input1.txt");
public class readtxt { char[] chars = new char[]{'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',' '}; int[] number = new int[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; public String txtString(File file){ StringBuilder result = new StringBuilder(); try{ BufferedReader br = new BufferedReader(new FileReader(file));//构造一个BufferedReader类来读取文件 String s = null; while((s = br.readLine())!=null){//使用readLine方法,一次读一行 result.append(System.lineSeparator()+s); num(s); } br.close(); }catch(Exception e){ e.printStackTrace(); } return result.toString(); } public void num(String string){ for(int i = 0;i<27;i++){ int temp = 0; for(int j = 0;j
readtxt read = new readtxt(); String temp = read.txtString(file); int[] num = read.getNumber(); char[] chars = read.getChars();
for(int i = 0;i<27;i++){ System.out.print(chars[i]+":"+num[i]+" "); list.add(new Node(chars[i]+"",num[i])); }
HuffmanTree huffmanTree = new HuffmanTree(); Noderoot = huffmanTree.createTree(list);
list2=huffmanTree.breadth(root); for(int i = 0;i
for(int i = 0;i
for(int i = 0;i0){ temp2 = temp2+"" +list5.get(0); list5.remove(0); for(int i=0;i
File file2 =new File("G:/usually/input/input2.txt"); Writer out =new FileWriter(file2); out.write(temp3); out.close();
最后得到的结果:
我有一个微信公众号,经常会分享一些Java技术相关的干货;如果你喜欢我的分享,可以用微信搜索“Java团长”或者“javatuanzhang”关注。
转载地址:http://zzgbi.baihongyu.com/