网站广告收费标准,网页搜索引擎优化技术,模版做网站多少钱,平度网站建设ld4哈夫曼编码
在说哈夫曼编码之前#xff0c;先要讲清楚编码集是什么东西。相信写过代码的人#xff0c;一定听说过ASCII、 UTF-8、GBK 这些编码集。这些编码集合#xff0c;本质上都是一个二进制和字符之间映射关系#xff0c;拿最简单的 ASCII 来说吧#xff0c;使用 0x3…哈夫曼编码
在说哈夫曼编码之前先要讲清楚编码集是什么东西。相信写过代码的人一定听说过ASCII、 UTF-8、GBK 这些编码集。这些编码集合本质上都是一个二进制和字符之间映射关系拿最简单的 ASCII 来说吧使用 0x30 代表字符 0 0x31 代表字符 1当打印设备看到 0x30 后就打印出字符 0 了。ASCII 最初是由美国弄出来他们使用的英文所以只考虑了英文中的字符那还有很多字符比如阿拉伯文字、俄文这些文字怎么表示于是就有了 UTF-8 这些。
讲了半天哈夫曼编码和字符集有什么关系呢大家都知道在计算机刚诞生的时候其内存是非常小的所以希望能设计出一个字符集这个字符集提高单位内存保存数据信息量。以 ASCII 码为例它使用 1 个字节保存来保存如果一封 e-mail 有 150 个字符则需要 150 个字节来存储。那么有没有办法减少一些呢大家仔细观察英文的字符有的使用比较多有的比较少能不能使用比较短的比特为表示比较常用的字符呢比如a 比 z 使用的比较多我们可以使用两个比特位来表示z 可以使用三个表示。这样的话在越长的文本中使用这种方式保存数据是不是越能节省内存。
哈夫曼编码就是生成这样自定义字符集的算法。
上代码
哈弗树 /**输入一个字符串计算出各个字符出现的次数出现的次数作为 Node 中的权重。然后在将 Node 放入到小根堆中。*/public static PriorityQueueNode getQueue(String input){MapCharacter , Integer cha new HashMap();for (char c : input.toCharArray()) {cha.computeIfPresent(c , (key , oldValue)-{return oldValue 1;});cha.computeIfAbsent(c , x - {return 1;});}PriorityQueueNode nodes new PriorityQueue(cha.size());cha.forEach((key , value) - {nodes.add(new Node(key , null , null , value));});return nodes ;}/**根据小根堆生成 Huffman 树。*/public static Node huffmanTree(PriorityQueueNode queue){Node head null ;Node first null ;Node second null ;Node h null ;while(!queue.isEmpty()){first queue.poll();second queue.poll();if(null second){break ;}h new Node(null , first , second , first.weight second.weight);head h ;queue.add(h);}return head ;}public static class Node implements ComparableNode{public Node left ;public Node right ;public int weight ;public Character c ;public Node(Character c , Node l , Node r , int w){left l ;right r ;weight w ;this.c c ;}Overridepublic int compareTo(Node o) {return this.weight - o.weight;}} /**返回字符对应的 Huffman 编码*/public static MapCharacter , String huffmanCode(Node head){MapCharacter , String rs new HashMap();maxLevel process2(head, , 0, rs);return rs ;}/**递归的找到 Huffman 编码*/public static int process2(Node head , String binaryStr , int value , MapCharacter , String map){if(head.c ! null){map.put(head.c , binaryStr value);int p 1 binaryStr.length();return p;}int p1 process2(head.left , binaryStr 1 , 1 , map);int p2 process2(head.right , binaryStr 0 , 0 , map);return Math.max(p1 , p2);} 转码码和解码
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;import java.util.Iterator;
import java.util.Map;
import java.util.BitSet;
public class HuffmanEncoder {private static Logger logger LoggerFactory.getLogger(HuffmanEncoder.class);/**使用 BitSet 保存 Huffman 编码*/public static Info encode(String input , MapCharacter , String mapping){BitSet bs new BitSet();int idx 0 ;for(char c : input.toCharArray()){String code mapping.get(c);char[] charArray code.toCharArray();for(int i charArray.length - 1 ; i 0 ; i-- ){bs.set(idx , charArray[i] 1);}}IteratorMap.EntryCharacter, String iterator mapping.entrySet().iterator();// max 的作用是保存 Huffman 编码的最大长度使用 max 1 长度的连续为 1 的比特位作为结尾int max 0 ;while (iterator.hasNext()) {Map.EntryCharacter, String next iterator.next();if(max next.getValue().length()){max next.getValue().length();}}// 设置结尾字符for (int i 0; i max1; i) {bs.set(idx , true);}return new Info(max1 , bs) ;}// 返回的信息体max 是结束比特位的长度。// BitSet 是字符串转码后的比特数据public static class Info{public int max ;public BitSet bs ;public Info(int m , BitSet b){max m ;bs b ;}}
}
解码
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;import java.util.BitSet;
import java.util.Map;public class HuffmanDecoder {private static Logger logger LoggerFactory.getLogger(HuffmanDecoder.class);public static String decode(HuffmanEncoder.Info info, MapInteger, Character mapping){StringBuilder sb new StringBuilder();int sum 0 ;int i 0 ;int j 0 ;int end 0 ;for (int k 0; k info.max; k) {end (1 k);}while(i info.bs.length()) {sum (info.bs.get(i)? 1j : 0);j;// j 表示了当前比特的位数当 max -1 的时候才能解码// 避免混淆例如111 和 011 当读完 11 后第三个 1 没读取此时转化为 10 进制为 3 正好和 011 相等// 这种情况就出现问题所以一定要判断一下是否大于 info.max -1 if(mapping.containsKey(sum) j info.max-1){sb.append(mapping.get(sum));sum 0 ;j 0 ;}// 判断是否等于结束字符。if(sum end){break ;}i;}return sb.toString();}
}
