ppt做书模板下载网站有哪些,免费app制作平台有哪些,成都需要网站制作,templates怎么读这是我们的课程中布置的作业。找一些资料将作业完毕#xff0c;顺便将其写到博客#xff0c;以后看起来也方便。原理介绍什么是Huffman压缩Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了#xff0c;它是一种无损压缩方法#xff0c;在压缩过程中不会丢失信息熵。并且能…这是我们的课程中布置的作业。找一些资料将作业完毕顺便将其写到博客以后看起来也方便。原理介绍什么是Huffman压缩Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了它是一种无损压缩方法在压缩过程中不会丢失信息熵。并且能够证明 Huffman 算法在无损压缩算法中是最优的。Huffman 原理简单实现起来也不困难在如今的主流压缩软件得到了广泛的应用。相应用程序、重要资料等绝对不同意信息丢失的压缩场合 Huffman 算法是非常好的选择。怎么实现Huffman压缩哈夫曼压缩是个无损的压缩算法一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(比如文本文件里的字符)用一个特定长度的位序列替代。因此。在文件里出现频率高的符号使用短的位序列。而那些非常少出现的符号。则用较长的位序列。二叉树在计算机科学中。二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作 “ 左子树 ” ( left subtree )和 “ 右子树 ” ( right subtree )。哈夫曼编码 (Huffman Coding)哈夫曼编码是一种编码方式哈夫曼编码是可变字长编码 (VLC) 的一种。 uffman 于 1952 年提出一种编码方法。该方法全然依据字符出现概率来构造异字头的平均长 度最短的码字有时称之为最佳编码一般就叫作 Huffman 编码。Huffman编码生成步骤扫描要压缩的文件对字符出现的频率进行计算。把字符按出现的频率进行排序组成一个队列。把出现频率最低(权值)的两个字符作为叶子节点。它们的权值之和为根节点组成一棵树。把上面叶子节点的两个字符从队列中移除并把它们组成的根节点增加到队列。把队列又一次进行排序。反复步骤 3、4、5 直到队列中仅仅有一个节点为止。把这棵树上的根节点定义为 0 (可自行定义 0 或 1 )左边为 0 。右边为 1 。这样就能够得到每个叶子节点的哈夫曼编码了。如 (a) 、 (b) 、 (c) 、 (d) 几个图就能够将离散型的数据转化为树型的了。假设假设树的左边用0 表示右边用 1 表示。则每个数能够用一个 01 串表示出来。则能够得到相应的编码例如以下1–1102–1113–104–0每个01 串既为每个数字的哈弗曼编码。为什么能压缩压缩的时候当我们遇到了文本中的1 、 2 、 3 、 4 几个字符的时候我们不用原来的存储而是转化为用它们的 01 串来存储不久是能减小了空间占用了吗。(什么 01 串不是比原来的字符还多了吗怎么降低)大家应该知道的。计算机中我们存储一个 int 型数据的时候一般式占用了 2^32-1 个 01 位由于计算机中全部的数据都是最后转化为二进制位去存储的。所以。想想我们的编码不就是仅仅含有 0 和 1 嘛因此我们就直接将编码依照计算机的存储规则用位的方法写入进去就能实现压缩了。比方1这个数字。用整数写进计算机硬盘去存储占用了 2^32-1 个二进制位而假设用它的哈弗曼编码去存储仅仅有110 三个二进制位。效果显而易见。编码实现流程图编码流程Created with Raphaël 2.1.0開始读入待压缩文件计算文件里各字符的权重依据权重构建Huffman树依据Huffman树获得各个字符的HUffman编码并建立Huffman编码的HashTable将字符总数、字符种数以及Huffman树写入压缩文件文件头再次读入待压缩文件。依据其内容和coding hash table 将压缩后的数据写入文件结束数据结构CharacterWeight记录字符值。以及其在待压缩文件里的权重。public class CharacterCode {private int weight;//字符值private char character;//字符值private String code;//其相应huffman编码}HuffmanNodehuffman树中的节点信息。public class HuffmanNode {private int parent;//父节点private int lChild;//左子private int rChild;//右子private int weight;//权重}程序关键步骤Huffman树的构建Huffman树的变量ArrayList list流程图Created with Raphaël 2.1.0開始i0n字符的种数循环遍历查找列表中权重最小的两个node创建一个新的节点作为找到的两个权重最小的节点的父节点并将该父节点的权重置为权重最小的两节点的权重和。将该节点增加数组中。ii代码for(int i0;i//w1 : the first min weight w2: the second min weight//i1 : the first min weight index, i2: the second min weight indexint w1 MAX_VALUE, w2MAX_VALUE;int i1 0, i2 0;// find the two node with the minimum weightfor(int j0;jHuffmanNode node tree.get(j);if(node.getWeight() w1 node.getParent()-1){w2 w1;w1 node.getWeight();i2 i1;i1 j;}else if(node.getWeight()w2 node.getWeight();i2 j;}}//set the two node to be the children of a new node, and add the new node to the treeHuffmanNode pNode new HuffmanNode(w1w2);pNode.setlChild(i1);pNode.setrChild(i2);tree.add(pNode);tree.get(i1).setParent(tree.indexOf(pNode));tree.get(i2).setParent(tree.indexOf(pNode));}依据Huffman 树获得Huffman编码从叶子节点開始网上遍历Huffman树直到到达根节点依据当前节点为其父节点的左儿子还是右儿子确定这一位值是0还是1。最后将依次获得的0,1字符串反转获得Huffman编码。for(int i0;iHuffmanNode node tree.get(i);HuffmanNode pNode tree.get(node.getParent());String code ;while(true){if(pNode.getlChild()tree.indexOf(node)){code 0code;}else if(pNode.getrChild() tree.indexOf(node)){code 1code;}else {System.out.println(Tree Node Error!!!);return null;}nodepNode;if(node.getParent()!-1)pNodetree.get(node.getParent());elsebreak;}list.get(i).setCode(new String(code));}头文件设计编码类型字节数字符总数Int4字符种类数Short2叶子节点char字符 short 父节点3非叶子节点Short 左儿子 short 右儿子 short父节点6文件头长度(单位 byte)l 9n当中n 为字符种类数。文件内容的编码和写入Created with Raphaël 2.1.0開始将待压缩文件读入字符数组依据coding hash table 获得huffman编码字符串,并将该字符串增加到buff中查看buff假设字符数大于8则将字符串转换为Short类型变量并写入文件将写入的字符从buff中删除是否到达文件尾结束yesno代码while((tempreader.read())!-1){//! EOF// get the code from the code tableString code codeTable.get((char)temp);c;if(ccount/96){System.out.print();c0;}try{StringBuilder codeString new StringBuilder(code);outputStringBuffer.append(codeString);while(outputStringBuffer.length()8){out.write(Short.parseShort(outputStringBuffer.substring(0, 8),2));outputStringBuffer.delete(0, 8);}} catch(Exception e){e.printStackTrace();}}解码实现流程图Created with Raphaël 2.1.0開始读压缩文件。读入文件头获得字符总数。字符种数以及huffman表信息。重建huffman树读入正文依据重建得到的huffman树获得原本的字符。将字符写入解压缩后的文件是否到达文件尾部结束yesno数据结构HuffmanNodehuffman树中的节点信息。public class HuffmanNode {private int parent;//父节点private int lChild;//左子private int rChild;//右子private int weight;//权重}程序关键步骤重建Huffman树。在文件头中存放的原本就是Huffman树的节点信息。in new DataInputStream(new FileInputStream(file));count in.readInt();charNum in.readShort();nodeNum 2*charNum -1;//rebuild the huffman treefor(int i0;iHuffmanNode node new HuffmanNode((char)in.readByte());int parent in.readShort();node.setParent(parent);tree.add(node);}for(int icharNum;iHuffmanNode node new HuffmanNode( );int l in.readShort();int r in.readShort();int p in.readShort();node.setlChild(l);node.setrChild(r);node.setParent(p);tree.add(node);}解码流程图Created with Raphaël 2.1.0開始Buff.length32从文件里读入整数将读入的整数转为二进制字符串并将其加到buff中依据buff中的01字符从顶向下遍历huffman树。得到叶子节点、其相应的解码值将其写入文件从buff中遍历删去已经遍历过的字符字符数是否达到总数处理buff中剩余内容结束yesnoyesno代码while(true){while(buff.length()32){temp in.readInt();String codeString Integer.toBinaryString(temp);while(codeString.length()32){codeString0codeString;}buff.append(codeString);}node tree.get(tree.size()-1);dep 0;while(!(node.getlChild()-1node.getrChild()-1)){if(depbuff.length()){System.out.println( Buff overflow);}if(buff.charAt(dep)0){node tree.get(node.getlChild());}else if(buff.charAt(dep)1){node tree.get(node.getrChild());}else{System.out.println(Coding error);}dep;}char c node.getCH();num;if(numn/99){System.out.print();num0;}count;if(countn){break;}charBuffc;if(charBuff.length()256){writer.write(charBuff);charBuff;}buff.delete(0, dep);}} catch(EOFException e){//just do nothing}catch(Exception e){e.printStackTrace();} finally{//there may be data released in the buff and charbuff, so we need to process themwhile(buff.length()0){node tree.get(tree.size()-1);dep 0;while(!(node.getlChild()-1node.getrChild()-1)){if(depbuff.length()){break;}if(buff.charAt(dep)0){node tree.get(node.getlChild());}else if(buff.charAt(dep)1){node tree.get(node.getrChild());}else{System.out.println(Coding error);//return;}dep;}char c node.getCH();num;if(numn/99){System.out.print();num0;}count;if(countn){break;}charBuffc;if(charBuff.length()256){try {writer.write(charBuff);} catch (IOException e1) {// TODO Auto-generated catch blocke1.printStackTrace();}charBuff;}buff.delete(0, dep);}try {writer.write(charBuff);writer.close();} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();}}try{writer.close();} catch(IOException e){throw e;}项目源代码留坑回头放上
