做招聘网站,呼和浩特网站建设价格,抖音开放平台是干嘛的,新乡市置顶网络技术有限公司哈夫曼树
Huffman 编码问题
问题引入
什么是编码#xff1f;
简单说就是建立【字符】到【数字】的对应关系#xff0c;如下面大家熟知的 ASC II 编码表#xff0c;例如#xff0c;可以查表得知字符【a】对应的数字是十六进制数【0x61】
\000102030405060708090a0b0c0d…哈夫曼树
Huffman 编码问题
问题引入
什么是编码
简单说就是建立【字符】到【数字】的对应关系如下面大家熟知的 ASC II 编码表例如可以查表得知字符【a】对应的数字是十六进制数【0x61】
\000102030405060708090a0b0c0d0e0f0000000102030405060708090a0b0c0d0e0f0010101112131415161718191a1b1c1d1e1f002020!#$%’()*,-./00300123456789:;?0040ABCDEFGHIJKLMNO0050PQRSTUVWXYZ[\]^_0060abcdefghijklmno0070pqrstuvwxyz{|}~7f 注一些直接以十六进制数字标识的是那些不可打印字符 传输时的编码
java 中每个 char 对应的数字会占用固定长度 2 个字节如果在传输中仍采用上述规则传递 abbccccccc 这 10 个字符 实际的字节为 006100620062006300630063006300630063006316进制表示总共 20 个字节不经济
现在希望找到一种最节省字节的传输方式怎么办
假设传输的字符中只包含 abc 这 3 个字符有同学重新设计一张二进制编码表见下图
0 表示 a1 表示 b10 表示 c
现在还是传递 abbccccccc 这 10 个字符
实际的字节为 01110101010101010 二进制表示总共需要 17 bits也就是 2 个字节多一点行不行
不行因为解码会出现问题因为 10 会被错误的解码成 ba而不是 c
解码后结果为 abbbababababababa是错误的
怎么解决必须保证编码后的二进制数字要能区分它们的前缀prefix-free
用满二叉树结构编码可以确保前缀不重复 向左走 0向右走 1走到叶子字符累计起来的 0 和 1 就是该字符的二进制编码
再来试一遍
a 的编码 0b 的编码 10c 的编码 11
现在还是传递 abbccccccc 这 10 个字符
实际的字节为 0101011111111111111二进制表示总共需要 19 bits也是 2 个字节多一点并且解码没有问题了行不行
这回解码没问题了但并非最少字节因为 c 的出现频率高7 次a 的出现频率低1 次因此出现频率高的字符编码成短数字更经济
考察下面的树 00 表示 a01 表示 b1 表示 c
现在还是传递 abbccccccc 这 10 个字符
实际的字节为 000101 1111111 二进制表示总共需要 13 bits这棵树就称之为 Huffman 树根据 Huffman 树对字符和数字进行编解码就是 Huffman 编解码
Huffman 树
public class HuffmanTree {Node root;String code;private static class Node{char ch;int freq;String code;Node left;Node right;public Node(char ch) {this.ch ch;}public Node(char ch, int freq) {this.ch ch;this.freq freq;}public Node(int freq, Node left, Node right) {this.freq freq;this.left left;this.right right;}public boolean isLeaf(){return this.left null this.right null;}}public HuffmanTree(String s){char[] charArray s.toCharArray();MapString,Integer map new HashMap();for (char c : charArray) {Integer i map.getOrDefault(String.valueOf(c),0);map.put(String.valueOf(c),i1);}PriorityQueueNode queue new PriorityQueue(Comparator.comparingInt(v - v.freq));for (String string : map.keySet()) {Node node new Node(string.charAt(0), map.get(string));queue.add(node);}while(queue.size() 1){Node n1 queue.poll();Node n2 queue.poll();Node node new Node(n1.freq n2.freq, n1, n2);queue.add(node);}root queue.peek();s doEncode(root,new StringBuilder(),s);code s;}
}Huffman 编解码
补充两个方法注意为了简单期间用了编解码都用字符串演示实际应该按 bits 编解码
public class HuffmanTree {// ...// 编码private String doEncode(Node node,StringBuilder sb,String s){if(!node.isLeaf()){s doEncode(node.left,sb.append(0),s);sb.deleteCharAt(sb.length()-1);s doEncode(node.right,sb.append(1),s);sb.deleteCharAt(sb.length()-1);}else{node.code sb.toString();while(s.contains(String.valueOf(node.ch))){s s.replace(String.valueOf(node.ch), node.code);}}return s;}public String encode(){return code;}public String decode(String code){Node node root;StringBuilder sb new StringBuilder();char[] charArray code.toCharArray();for (int i 0; i charArray.length; i) {if(charArray[i] 0){node node.left;}else {node node.right;}if(node.isLeaf()){sb.append(node.ch);node root;}}return sb.toString();}public static void main(String[] args) {HuffmanTree tree new HuffmanTree(aabcccccc);String encode tree.encode();System.out.println(encode);String decode tree.decode(encode);System.out.println(decode);}
}
