PS：本文为转载文章，原文可读性会更好，文末有原文链接通信领域的信息处理方法1,2,1定长编码1,2,2变长编码1,2,3哈夫曼编码1,哈夫曼树编码1,1哈夫曼编码基本介绍哈夫曼编码是一种编码方式和程序算法；哈夫曼编码是哈夫曼树在电信领域的经典应用之一；霍夫曼编码广泛应用于数据文件压缩，其压缩率一般在20%~90%之间；霍夫曼码是一种可变字长编码。霍夫曼于1952年提出了一种编码方法，称为最优编码。1,2通信领域的信息处理方式1,2,1定长编码我们列举通信领域的信息处理方式-定长编码，假设我要给别人发一句话“病毒变异了，becameweakerandweaker”，按照定长编码的方法，这句话转为二进制编码后的长度是多少？我们先给出一个Ascill码表，如图1所示；图1中空格（图1中未显示空格）的十进制Ascill码为32，二进制Ascill码为00100000；见图1，a的十进制Ascill码为97，二进制Ascill码为01100001；看懂了图1中字符a的Ascill码，应该就能看懂其他字符的Ascill码了吧？图1中其他字符的Ascill码我就不一一描述了，但是不管你怎么看图1中的字符，它们的二进制Ascill码都是8位的。我们把上面要发送的句子放到记事本里，统计字符数，如图2；图2见图2，发送的句子长度为46个字符；再看图1中的二进制AscillCode，一个字符占8位，所以发送的句子转为二进制，长度为46X8=368。1,2,2变长编码假设我要给别人发一句话是“病毒变异了，越来越弱”。传输的过程必须转换成二进制编码，可以采用变长编码。减少bytes占用的内存；好了，下面开始变长编码分析。我们先把“thevirusmutatedandbecameweakerandweaker”这句话中每个字符出现的次数列在一个表格中，如下表1；图片好了，我们现在对表1中的字符进行二进制编码，原则上出现次数越多编码越小；比如字符e出现次数最多，我们把它编码成0，那么，现在我们也对表1中的字符做一个编码表，如表2；图中，我们将“病毒变异，变得越来越弱”这句话转换成表2中的所有字符二进制代码表示，得到表3；图片表3中的字符装不下那么多，我就省略了；”thevirusmutatedandbecameweakerandweaker”这句话按照表2的规则转换成二进制编码就是1001101011011110011111111011000111100101000101110110101111110100001010000110010101010011110110101110010101010011；把Putthisstringofbinarycodesintothenotepadtototalitslength,andgetthelengthstatisticsasshowninFigure3;图3中图片的二进制长度为112，相对于定长码，“病毒变异了，变得越来越弱”这句话的压缩率为(368-112)/368X100%=70%，但是解码的时候就麻烦了。比如一开始的编码是解码成10还是101，解码成10就变成字母a了。解码错了。1、2、3哈夫曼编码哈夫曼编码利用了定长编码和变长编码的一些优点，例如，它使用十进制的Ascill码和字符出现的次数作为二进制编码，这样就可以做压缩字节码可以无损解码。好，我们先用哈夫曼编码画一棵树，这样下面描述的内容就容易理解了，如图3；图片见图3，节点左边的路径用0表示，右边的路径用1表示表示一个字符的编码为10。我们继续用“病毒变异了”这句话andbecomeweakerandweaker”进行传输，这次我们使用哈夫曼编码，步骤如下；(1)仍然使用表1中的字符。(2)以表1中字符出现的次数作为权重构造哈夫曼树（哈夫曼树的构建过程见Java版哈夫曼树).(3)根据哈夫曼树，向左的路径为0，向右的路径为1。我们要发送的字符串中字符的二进制编码如表2所示。(4)使用十进制Ascill码作为叶节点的数据值，利用节点的权重将其转换为二进制码。(5)哈夫曼代码内置的树必须是哈夫曼树。最后，根据哈夫曼编码，将“病毒变异，变得越来越弱”这句话转化为二进制码：100010111100110001110111010110110000010000100100010101000101001010111现在代码实现了；(1)创建节点类Node:/**NodeimplementsComparable让Node对象可以连续排序Collections集合排序*/publicclassNodeimplementsComparable{privateBytedata;//存储十进制如果Ascill码更大比'a'字符，则Ascill码为97从小到大返回this.weight-arg0.weight;}publicNode(Bytedata,intweight){super();this.data=data;this.weight=weight;}publicBytegetData(){返回数据;}publicNodegetLeft(){returnleft;}publicvoidsetLeft(Nodeleft){this.left=left;}publicNodegetRight(){returnright;}publicvoidsetRight(Noderight){this.right=right;}publicintgetWeight(){returnweight;}}(2)创建生成霍夫曼码的类Test：publicclassTest{Noderoot;publicstaticvoidmain(String[]args){Strings="病毒变异，越来越弱";byte[]bs=s.getBytes();System.out.println("s的长度为："+s.length());Testtest=newTest();Listlist=test.getNode(bs);test.root=test.createHuffmanTree(list);//生成哈夫曼码表并将哈夫曼码表存入huffumanCodestest.getCodes(test.root,"",test.sb);s="";for(Map.Entrymap:test.huffumanCodes.entrySet()){s=s+map.getValue();}System.out.println("s根据哈夫曼编码生成的对应二进制码为"+s);}//拼接哈夫曼树的节点路径，节点左路径为"0”表示，正确的路径用“1”表示StringBuildersb=newStringBuilder();MaphuffmanCodes=newHashMap();//生成霍夫曼码表/**@paramnode传入的节点@paramcode节点左边路径用“0”表示，右边路径用“1”表示@paramsbsplicingcode@return*/privatevoidgetCodes(Nodenode,Stringcode,StringBuildersb){StringBuildersb2=newStringBuilder(sb);//给sb2添加代码sb2.append(code);if(node!=null){//非叶子节点if(node.getData()==null){//左递归处理getCodes(node.getLeft(),"0",sb2);//右递归处理getCodes(node.getRight(),"1",sb2);//它是一个叶子节点}else{huffhumanCodes.put(node.getData(),sb2.toString());}}}privateListgetNode(byte[]bs){ArrayListlist=newArrayList();//统计byte出现次数Mapmap=newHashMap();for(inti=0;ientry:map.entrySet()){字节数据=entry.getKey();intweight=entry.getValue();节点node=newNode(data,weight);list.add(node);}returnlist;}//创建哈夫曼树privateNodecreateHuffmanTree(Listlist){while(list.size()>1){//从小到大排序Collections.sort(列表）;//System.out.println("list="+list);/***这必须是权重最小的节点*/NodeminNode=list.get(0);/***除了minNode节点，这个节点是权重最小的节点，但是节点比minNode节点大，比minNode节点大，其他节点都小*/NodesecondMinNode=list.get(1);/***构建一个新的二叉树*/NodeparentNode=newNode(null,minNode.getWeight()+secondMinNode.getWeight());父节点.setLeft(minNode);parentNode.setRight(secondMinNode);/***从list集合中删除2个已经构建成二叉树的节点*/list.remove(minNode);list.remove(secondMinNode);/***将新二叉树的父节点添加到链表集合中*/list.add(parentNode);}/***建立哈夫曼树后，list集合中的第一个节点必须是根节点*/returnlist.get(0);}}日志打印如下：从日志中可以看到图片，也就是我们上面说的结果，按照霍夫曼编码转换成二进制码；哈夫曼编码，下篇文章会写哈夫曼解码，敬请期待
