- 浏览: 23297 次
- 性别:
文章分类
最新评论
-
stevenjohn:
楼主,好文
JAVA线程模型 -
GLC:
操作系统的正好还没考、这个让我好好复习了很多啊。
JAVA线程模型 -
wanghengxian:
somefuture 写道单线程该用双线程后,能节省一半时间吗 ...
Java多线程 -
wanghengxian:
都是来看妹子的吗
Java多线程 -
tingle:
ThreadPoolExecutor这个更好
Java多线程
哈夫曼与压缩
带权路径长度(WPL):
二叉树的带权(外部)路径长度是树的各叶结点所带的权值wi与该结点到根的路径长度li的乘积之和。
一、哈夫曼树
哈夫曼树又称“最优树”,是带权路径长度达到最小的二叉树。
特点:在哈夫曼树中,权值越大的结点离根越近。
构建哈夫曼树:
1、由给定的n个权值,构造具有n棵二叉树的森林,其中每棵二叉树值有一个带权值的根结点其左右子树为空;
2、重复(直到森林中仅剩下一棵树):
1)在森林中选取两棵根结点权值最小的二叉树,作为左右子树构造一棵新的二叉树。设置新的二叉树的根节点的权值为其左右字数上根节点的权值之和;
2)在森林中删去这两棵二叉树;
3)把新的二叉树加入到森林中。
(该步骤重复次数为n-1,最终形成的哈夫曼树中共有2n-1个节点,起哄叶节点个数为n,度为2的结点个数为n-1个,没有度为1的结点。——严格二叉树/正则二叉树)
二、哈夫曼编码
以一段报文中出现的字符作为结点,各字符出现的次数作为权值,构建哈夫曼树,从根节点开始,对左子树分配代码0,右子树分配代码1,一直到达叶子结点为止,然后从根节点开始到每个叶子结点的路径上的代码连接起来,构成了哈夫曼编码。
因为哈夫曼树的带权路径长度是最小的,所以每个字符的编码长度乘以出现的次数的综合也是最小的,这样利用哈夫曼树构造的编码可以减少总编码的长度。
哈夫曼编码是一种无前缀编码(都由叶结点组成,路径不会重复)。解码时不会混淆。
三、压缩与解压缩
哈夫曼压缩时一种无损压缩方法,在压缩过程中不会丢失信息熵,而且在无损压缩算法中是最优的。对应用程序、重要资料等绝对不允许信息丢失的压缩场合,哈夫曼算法是非常好的选择。
计算机中存储一个字节型数据占用8个01位,因为计算机中所有数据都是转化为二进制位去存储的。所以我们就讲编码按照计算机的存储规则用为的方法写入进去就实现压缩。
压缩总体思路:
1、读文件,统计各字符的出现次数,并记录字符ASCII码的下标
2、对字符按照出现次数从小到大排序(优先队列)
3、构建哈夫曼树
4、遍历树,生成码表
5、写文件:
1)头信息:出现的字符种类总数;
字符ASCII码,补了几个0,编码占几个byte,补零后的编码;
文件末尾补零的个数;
2)写内容:每个字符不考虑补零,按照码表中的原始编码写入,
如果编码不够8位就读取下个字符将编码连接起来,
够8位就写入,剩下的编码再凑够8位写入,直到文件末尾补零。
压缩用到的其他类:
解压缩总体思路:(怎么写进去的就要怎么读出来)
1、读取文件头信息:1)字符种类总数;
2)各字符信息:字符ASCII码,补零个数,占用byte数,编码
(在这过程中,需要把读到的编码转换成与码表中相同的编码)
3)文件末尾补零个数。
2、读取文件信息:读取每个字节转换成01串,前面补零成8位,
加到等待匹配的字符串后,与码表中的编码匹配,写入。
读到文件末尾将加上去的0去掉。
解压缩用到的其他类
据我测试,简单的英文压缩和解压缩应该没有问题,可能还有很多不足的地方,欢迎指正!
带权路径长度(WPL):
二叉树的带权(外部)路径长度是树的各叶结点所带的权值wi与该结点到根的路径长度li的乘积之和。
一、哈夫曼树
哈夫曼树又称“最优树”,是带权路径长度达到最小的二叉树。
特点:在哈夫曼树中,权值越大的结点离根越近。
构建哈夫曼树:
1、由给定的n个权值,构造具有n棵二叉树的森林,其中每棵二叉树值有一个带权值的根结点其左右子树为空;
2、重复(直到森林中仅剩下一棵树):
1)在森林中选取两棵根结点权值最小的二叉树,作为左右子树构造一棵新的二叉树。设置新的二叉树的根节点的权值为其左右字数上根节点的权值之和;
2)在森林中删去这两棵二叉树;
3)把新的二叉树加入到森林中。
(该步骤重复次数为n-1,最终形成的哈夫曼树中共有2n-1个节点,起哄叶节点个数为n,度为2的结点个数为n-1个,没有度为1的结点。——严格二叉树/正则二叉树)
二、哈夫曼编码
以一段报文中出现的字符作为结点,各字符出现的次数作为权值,构建哈夫曼树,从根节点开始,对左子树分配代码0,右子树分配代码1,一直到达叶子结点为止,然后从根节点开始到每个叶子结点的路径上的代码连接起来,构成了哈夫曼编码。
因为哈夫曼树的带权路径长度是最小的,所以每个字符的编码长度乘以出现的次数的综合也是最小的,这样利用哈夫曼树构造的编码可以减少总编码的长度。
哈夫曼编码是一种无前缀编码(都由叶结点组成,路径不会重复)。解码时不会混淆。
三、压缩与解压缩
哈夫曼压缩时一种无损压缩方法,在压缩过程中不会丢失信息熵,而且在无损压缩算法中是最优的。对应用程序、重要资料等绝对不允许信息丢失的压缩场合,哈夫曼算法是非常好的选择。
计算机中存储一个字节型数据占用8个01位,因为计算机中所有数据都是转化为二进制位去存储的。所以我们就讲编码按照计算机的存储规则用为的方法写入进去就实现压缩。
压缩总体思路:
1、读文件,统计各字符的出现次数,并记录字符ASCII码的下标
2、对字符按照出现次数从小到大排序(优先队列)
3、构建哈夫曼树
4、遍历树,生成码表
5、写文件:
1)头信息:出现的字符种类总数;
字符ASCII码,补了几个0,编码占几个byte,补零后的编码;
文件末尾补零的个数;
2)写内容:每个字符不考虑补零,按照码表中的原始编码写入,
如果编码不够8位就读取下个字符将编码连接起来,
够8位就写入,剩下的编码再凑够8位写入,直到文件末尾补零。
import java.awt.BorderLayout; import java.awt.Color; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.util.PriorityQueue; import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.JPanel; import javax.swing.JTextField; /** * 哈夫曼压缩主类,实现压缩(英文可压缩) * @author 客 * */ public class HuffmanTest extends JFrame{ //压缩文章的路径 static String path = "src\\lwq\\java\\HuffmanCode0729\\Untitled 1"; //压缩到的路径 static String newPath = "src\\lwq\\java\\HuffmanCode0729\\Untitled 2"; //记录文章中字符和频率的数组,下标表示字符的ASCII码,数组内容表示该字符的出现次数 int[] byteCount = new int[256]; //哈夫曼树的根节点 static hfmNode root; //传入“给叶子节点设置编码的方法”中 static String s = ""; //存储ascii为下标值的字符的编码对象,它是码表,是初始的编码,不补0的 static Code SaveCode[] = new Code[256]; //存储ascii为下标值的字符的编码需要的补0数 int zeroCount[] = new int[256]; FileInputStream fis; FileOutputStream fos; //记录文件内容所有的原始编码的字符串,用以统计文件末尾的补零个数 int allString = 0; //文件末尾补零的个数 int fileAddZero; /** * 程序入口,主方法 * @param args * @throws IOException */ public static void main(String[] args) throws IOException{ HuffmanTest huffmantest = new HuffmanTest(); //遍历文件统计每个字符的出现次数,并且记录字符的ASCII码 huffmantest.countWeight(path); //根据字符出现次数,建立哈夫曼树,方法末尾得到树的根节点 huffmantest.createTree(); //给叶子节点设置编码 huffmantest.setCode(root, s); //写入文件头信息 huffmantest.writeHead(newPath); //写入文件 huffmantest.writeFile(path); } /** * 读取文件统计字符和字符的出现频率 * @param path 要压缩的文件路径 * @throws IOException */ public void countWeight(String path) throws IOException{ fis = new FileInputStream(path); while(fis.available()>0){ int i = fis.read(); byteCount[i]++;//i是字符的ASCII码,数组内容是该字符的出现次数 } } /** * 根据字符频率,将字符创建成结点加入到优先队列中,建立哈夫曼树 */ public void createTree(){ //使用优先队列 PriorityQueue<hfmNode> nodeQueue = new PriorityQueue<hfmNode>(); for(int i=0;i<byteCount.length;i++){ // System.out.println(byteCount[i]); if(byteCount[i]!=0){//文件中出现次数不为0的字符,建立哈夫曼结点,存入队列 hfmNode node = new hfmNode(i,byteCount[i]); nodeQueue.add(node); } } //根据优先队列的排序,构建哈夫曼树 while(nodeQueue.size()>1){//当队列中的元素个数大于1 //取得最小的两个,并删除掉 hfmNode min1 = nodeQueue.poll(); hfmNode min2 = nodeQueue.poll(); //建立新的结点 hfmNode result = new hfmNode(0,min1.getTimes()+min2.getTimes()); //设置新结点的左右子结点 result.setlChild(min1); result.setrChild(min2); //新结点加入到优先队列中 nodeQueue.add(result); } //循环结束后队列中只有一个元素,该元素就是根节点,获取到但不删除 root = nodeQueue.peek(); System.out.println("根!"+root.toString()); } /** * 给叶子节点设置编码 * @param root * @param s */ public void setCode(hfmNode root,String s){ //如果左右子结点都为空,即为叶子节点 if(root.getlChild()==null&&root.getrChild()==null){ //实例化一个code对象,设置编码和长度 Code huffman_code = new Code(); huffman_code.setCode(s); //把编码code对象放到SaveCode数组中下标为字符ascii值 SaveCode[root.getAscii()] = huffman_code; //输出编码信息 // System.out.println(SaveCode[root.getAscii()].toString()); } //如果左子结点不为空,递归 if(root.getlChild()!=null){ setCode(root.getlChild(),s+'0'); } //如果右子结点不为空,递归 if(root.getrChild()!=null){ setCode(root.getrChild(),s+'1'); } } /** * 写入文件头信息,写入的编码是补零后的编码 * 然后把码表写入文件头信息 * @throws IOException */ public void writeHead(String newPath) throws IOException{ fos = new FileOutputStream(newPath); //统计文件总共用到的字符总数,即编码个数 int codeNum = 0; for(int i=0;i<256;i++){ if(SaveCode[i]!=null){ codeNum++; allString += byteCount[i]*SaveCode[i].getCode().length(); } } //写入总文件中总共有多少个用到的字符 fos.write(codeNum); System.out.println(codeNum); //循环输出码表,包括(按顺序):字符、补了几个0、编码含有的byte个数、编码(整型)。 for(int i=0;i<256;i++){ //如果该字符在文件中出现过,即编码不为空 if(SaveCode[i]!=null){ //写入:字符的ASCII码值 fos.write(i); System.out.print(i+"\t"+(char)i); //第i个字符的补零数 if(SaveCode[i].getCode().length()%8!=0){//如果编码字符串程度不是8的整倍数 zeroCount[i] = 8-SaveCode[i].getCode().length()%8;//设置补零的个数 }else{//如果是8的整倍数 zeroCount[i] = 0; } //写入:每个编码末尾补了几个0 fos.write(zeroCount[i]); //补零后的编码,写入头信息 String addZero = SaveCode[i].getCode(); System.out.println(SaveCode[i].getCode()+"需要补零的个数"+zeroCount[i]); for(int j=0;j<zeroCount[i];j++){//循环次数为:需要补零的个数 //每次在编码后补一个0 // SaveCode[i].setCode(SaveCode[i].getCode()+'0'); addZero = addZero+'0'; } //在补0完成后,写入:编码有几个byte fos.write(addZero.length()/8); // System.out.print(addZero.length()/8+"\t"); //对于补齐0的编码,每次取出一个字节 for(int j=0;j<addZero.length()/8;j++){ String subString = ""; //取出一个字节中的8位赋值给codeString for(int k=j*8;k<(j+1)*8;k++){ subString = subString+addZero.charAt(k); } //读取每个字节,将01串转化成整型数 int cs = changeString(subString); fos.write(cs); // System.out.print(cs+" "); }//每个字符读取完毕 // System.out.println("\t"+zeroCount[i]); } } if(allString%8==0){ fos.write(0); }else{ fileAddZero = 8-allString%8; fos.write(fileAddZero); System.out.println("文章末尾补零"+fileAddZero); } } /** * 读文件并写入内容 * @throws IOException */ public void writeFile(String path) throws IOException{ System.out.println("xxxxxxx"); //等待中的编码字符串 String str = ""; fis = new FileInputStream(path); //如果文件可读内容大于0 while(fis.available()>0){ //读取一个字节字符 int i = fis.read(); //得到该字符的码表中的编码----没有补零的,加入到等待中的字符串后 str = str+SaveCode[i].getCode(); System.out.println("!!~~!!"+str); //如果该编码长度大于等于8 while(str.length()>=8){ //截取8位编码的字符串 String subString = ""; for(int j=0;j<8;j++){ subString = subString+str.charAt(j); } //读取每个字节,将01串转化成整型数 int cs = changeString(subString); fos.write(cs); //删除str的前八位 String tranString = str; str = ""; for(int j=8;j<tranString.length();j++){ str = str+tranString.charAt(j); } } // System.out.println("sssssssssssssssssssss"+str); } //文件末尾最后的字符串 System.out.println("mm"+str); for(int t=0;t<fileAddZero;t++){ str = str+'0'; } System.out.println(str); //写入文件 int cs = changeString(str); fos.write(cs); } /** * 将8个字符的字符串转换成01串对应的整数 * @param s * @return */ private int changeString(String s) { return ((int)s.charAt(0)-48)*128+((int)s.charAt(1)-48)*64 +((int)s.charAt(2)-48)*32+((int)s.charAt(3)-48)*16 +((int)s.charAt(4)-48)*8+((int)s.charAt(5)-48)*4 +((int)s.charAt(6)-48)*2+((int)s.charAt(7)-48); } }
压缩用到的其他类:
/** * 哈夫曼树中给叶子节点设置的编码类 * @author 客 * */ public class Code { //哈夫曼编码 private String code = ""; /** * 输出Code类对象的方法 */ public String toString(){ return "编码:"+code+" 长度:"+code.length(); } /** * 得到编码内容 * @return */ public String getCode() { return code; } /** * 设置编码内容 * @param code */ public void setCode(String code) { this.code = code; } }
/** * 哈夫曼树结点类 * @author 客 * */ public class hfmNode implements Comparable<hfmNode>{ //字符的ASCII码值 private int ascii; //字符的出现次数 private int times; //当前结点的左子结点 private hfmNode lChild; //当前结点的右子结点 private hfmNode rChild; /** * 构造方法 * @param i ASCII的值 * @param times 文件中的出现次数 */ public hfmNode(int ascii,int times){ this.ascii = ascii; this.setTimes(times); } /** * 得到结点字符ASCII值得方法 * @return ASCII码值 */ public int getAscii() { return ascii; } /** * 设置结点字符的ASCII值 * @param ascii */ public void setAscii(int ascii) { this.ascii = ascii; } /** * 得到当前结点字符出现次数的方法 * @return */ public int getTimes() { return times; } /** * 设置当前结点字符出现次数的方法 * @param times */ public void setTimes(int times) { this.times = times; } /** * 得到当前结点左孩子的方法 * @return 左子结点 */ public hfmNode getlChild() { return lChild; } /** * 设置当前结点左孩子的方法 * @param lChild */ public void setlChild(hfmNode lChild) { this.lChild = lChild; } /** * 得到当前结点右孩子的方法 * @return 右子结点 */ public hfmNode getrChild() { return rChild; } /** * 设置当前结点右孩子的方法 * @param rChild */ public void setrChild(hfmNode rChild) { this.rChild = rChild; } /** * 输出hfmNode类对象--哈夫曼结点的方法 */ public String toString(){ return "ascii="+(char)ascii+" times="+times; } /** * 定义在队列中进行排序比较的属性 */ public int compareTo(hfmNode o) { return times-o.getTimes(); } }
解压缩总体思路:(怎么写进去的就要怎么读出来)
1、读取文件头信息:1)字符种类总数;
2)各字符信息:字符ASCII码,补零个数,占用byte数,编码
(在这过程中,需要把读到的编码转换成与码表中相同的编码)
3)文件末尾补零个数。
2、读取文件信息:读取每个字节转换成01串,前面补零成8位,
加到等待匹配的字符串后,与码表中的编码匹配,写入。
读到文件末尾将加上去的0去掉。
import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; /** * 实现文件解压缩 * @author 客 * */ public class OpenTest { //文件输入输出流 FileInputStream fis; FileOutputStream fos; //被解压缩文件路径 static String path = "src\\lwq\\java\\HuffmanCode0729\\Untitled 2"; //解压缩后的文件路径 static String newPath = "src\\lwq\\java\\HuffmanCode0729\\Untitled 3"; //存储文件头信息--即各个字符信息的数组 HeadInfo[] head; //文件末尾补零的数 int fileAddZero; //记录总共有多少个字符 int codeNum; public static void main(String[] args) throws IOException{ OpenTest opentest = new OpenTest(); //读取文件头信息 opentest.readHead(path); //读取文件内容并输出 opentest.readFile(path,newPath); } /** * 读取文件头信息,按写入的顺序依次读出: * 1、字符种类总数, * 2、字符ASCII码,编码末尾补零数,字符占字节数,编码 * 3、文件末尾补零数 * * @throws IOException */ public void readHead(String path) throws IOException{ fis = new FileInputStream(path); //读取字符种类总数 codeNum = fis.read(); System.out.println(codeNum); //实例化记录文件头信息的数组,数组长度为字符种类总数 head = new HeadInfo[codeNum]; System.out.println("ascii\t字节数\t补零数\t编码"); //以字符种类总数作为循环限制条件,读取每个字符的编码细则 for(int i=0;i<codeNum;i++){ //创建文件头信息对象 HeadInfo info = new HeadInfo(); //读取字符ASCII码,给对象设置ASCII码 info.setAscii(fis.read()); System.out.print(info.getAscii()+"\t"+(char)info.getAscii()+" "); //读取编码末尾补零数,并给对象设置 info.setZeroNum(fis.read()); //读取编码所占字节数,给对象设置 info.setByteNum(fis.read()); System.out.print(info.getByteNum()+"\t"); //读取当前编码的每个字节 for(int j=0;j<info.getByteNum();j++){ int code_int = fis.read(); //读取到的整数转换成String---0,1串,该01串不会以0开头 String code_string = Integer.toBinaryString(code_int); // System.out.println("s++"+code_string); int length = code_string.length(); //01串不足8位的在前面补零 if(length%8!=0){ for(int k=0;k<8-length;k++){ code_string = '0'+code_string; } } //给info对象设置编码,含补零,每个字节的前面补零的01串相加 info.setCode(info.getCode()+code_string); } //得到完整的补零后的01串,即文件头信息存储的编码 System.out.print(info.getZeroNum()+"\t"); //根据编码末尾补零个数,恢复编码不补零的编码,即码表中存储的编码, for(int t=0;t<info.getZeroNum();t++){ info.setCode(info.getCode().substring(0, info.getCode().length()-1)); } System.out.println("去0后 "+info.getCode()); //将info对象添加到数组中 head[i] = info; } //读取头信息的最后一个内容:文章末尾的补零的个数 fileAddZero = fis.read(); System.out.println("文件末尾补零"+fileAddZero); } /** * 读取文件内容,写入新文件,完成解压缩 * @throws IOException */ public void readFile(String path,String newPath) throws IOException{ fos = new FileOutputStream(newPath); //等待转换的字符串 String str = ""; //当文件可读信息大于零时 while(fis.available()>0){ //读取一个字节,赋值给整数txt int txt = fis.read(); //将该整数转换成01串,该字符串不会以0开头 String temp = Integer.toBinaryString(txt); System.out.println(temp+" nnnn"); //给转换成的01串,前面补零成完整的8位的字符串 int frontAddZero = temp.length()%8; if(frontAddZero!=0){ for(int i=0;i<8-frontAddZero;i++){ temp = '0'+temp; } } System.out.println(temp+">>>>>>>>>>>>"); //加到等待转换的字符串后,等待转换 str = str+temp; System.out.println(str+" !!!!等待转换!!!!"); for(int j=0;j<codeNum;j++){ //判断当前等待转换的字符串,是否以码表中的某个编码开头 if(str.startsWith((head[j].getCode()))){ //如果是,写入这个编码对应的字符 System.out.println(str+" ======== "+head[j].getCode()); // System.out.println("qqqq"+i); System.out.println((char)head[j].getAscii()); fos.write(head[j].getAscii()); // //将等待转换的字符串去掉已经写入的编码部分 String tran = str; str = ""; for(int k=head[j].getCode().length();k<tran.length();k++){ str = str+tran.charAt(k); } //设置循环从头开始判断现在的str是否以某编码开头 j = -1; //如果此时已经没有可读的文件信息了 if(fis.available()==0){ //将文件末尾添加的0的个数,在str中删去 String tra = str; str = ""; for(int t=0;t<tra.length()-fileAddZero;t++){ str = str+tra.charAt(t); } //如果删去之后字符串空了,那么跳出循环,文件读取完毕 if(str==""){ break; } //如果str不为空,那么继续j=-1的地方循环判断是否以某编码开头 } } }//for循环 }//while循环 //确认文件读取完毕 System.out.println(str.length()+" 最后str的长度"); } }
解压缩用到的其他类
/** * 文件解压缩时用到的文件头信息中每个字符的信息类 * @author 客 * */ public class HeadInfo { //字符ASCII码 private int ascii; //字符编码占用字节数 private int byteNum; //编码末尾补零数 private int zeroNum; //编码 private String code = ""; /** * 得到ASCII码 * @return */ public int getAscii() { return ascii; } /** * 设置ASCII码 * @param ascii */ public void setAscii(int ascii) { this.ascii = ascii; } /** * 得到编码占字节数 * @return */ public int getByteNum() { return byteNum; } /** * 设置编码占字节数 * @param byteNum */ public void setByteNum(int byteNum) { this.byteNum = byteNum; } /** * 得到编码 * @return */ public String getCode() { return code; } /** * 设置编码 * @param code */ public void setCode(String code) { this.code = code; } /** * 得到编码末尾补零个数 * @return */ public int getZeroNum() { return zeroNum; } /** * 设置编码末尾补零个数 * @param zeroNum */ public void setZeroNum(int zeroNum) { this.zeroNum = zeroNum; } }
据我测试,简单的英文压缩和解压缩应该没有问题,可能还有很多不足的地方,欢迎指正!
相关推荐
在实现哈夫曼树压缩算法的过程中,通常包括以下几个步骤: 1. **频率统计**:首先,对输入的数据流进行频率统计,得到每个符号(如字符)出现的次数。这一步骤有助于了解哪些符号更常见,哪些更不常见。 2. **构建...
在C++中实现哈夫曼树压缩与解压涉及到几个主要步骤,包括构建哈夫曼树、生成哈夫曼编码、编码数据以及解码数据。 1. **哈夫曼树的构建** - 首先,统计输入文本中每个字符出现的频率,形成一个频率列表。 - 接着,...
《基于哈夫曼树的文件压缩与解压技术在QT可视化界面中的实现》 哈夫曼编码是一种数据压缩算法,其核心是构建哈夫曼树,通过对数据出现频率的统计,构建出一棵特殊的二叉树——哈夫曼树,使得出现频率高的字符具有较...
本文将深入解析一个利用哈夫曼树进行文件压缩与解压的具体实现案例。本程序通过C语言编写,并在VC++6.0环境中进行编译测试。它能够处理任意单个文件的压缩与解压,且能够生成压缩过程中使用的哈夫曼树和相应的哈夫曼...
在8.3版本的压缩包中,可能包含了一个实现哈夫曼树压缩和解压缩的程序。这个程序可能包括了对文件进行读取、频率统计、哈夫曼树构建、编码生成、编码文件写入、解码以及哈夫曼树重建等功能。通过学习和理解这个程序...
基于哈夫曼树的压缩软件 C++ 知识点一:哈夫曼编码原理 哈夫曼编码是一种_variable-length prefix code_,它的主要思想是将频繁出现的字符编码短,较少出现的字符编码长,以此来减少所占用的空间。哈夫曼编码的主要...
哈夫曼树与哈夫曼编码是数据结构和算法领域中的一个重要概念,广泛应用于数据压缩、文本编码以及优先队列等场景。哈夫曼编码是一种特殊的前缀编码方法,能够为字符提供一种高效的二进制表示,使得频繁出现的字符具有...
将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint 中。 3. 测试数据 用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:...
本文将详细探讨如何利用哈夫曼树对文本进行压缩与解压缩的过程,以及它在文本处理中的核心原理。 哈夫曼树是一种带权路径长度最短的二叉树,它的构建基于频率优先的原则。在对文本进行压缩前,我们首先要对文本中的...
哈夫曼树实现压缩解压 哈夫曼树是一种基于Variable-Length Prefix Codes(变长前缀码)的压缩算法,通过构建哈夫曼树来实现压缩和解压缩。下面是该算法的详细知识点: 1. 哈夫曼树的构建: 哈夫曼树是一棵二叉树...
6. **解压缩**:解压缩的过程与压缩相反,首先需要根据哈夫曼树的编码生成原始的哈夫曼树,然后读取二进制流,按照哈夫曼编码解码,恢复出原始文本。 在NetBeans环境中,你可以创建一个新的Java项目,将上述逻辑...
哈夫曼树的构建与C语言实现 哈夫曼树是一种特殊的二叉树,它的权值越小,越靠近根节点。哈夫曼树的构建是数据压缩和编码的重要组件。下面是哈夫曼树的构建与C语言实现的相关知识点: 一、哈夫曼树的定义 哈夫曼...
功能要求 1. 针对一幅BMP格式的图片文件,统计...2. 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 3. 压缩后的文件与原图片文件同名,加上后缀.huf(保留原后缀),如pic.bmp 压缩后pic.bmp.huf 4. 解压缩
哈夫曼树是一种在计算机科学中广泛使用的数据结构,尤其在数据压缩领域有着重要的应用。本实验报告主要探讨了如何运用哈夫曼树对文本文件进行编码和解压缩,以实现无损数据压缩。 首先,我们需要理解哈夫曼树的基本...
#### 五、哈夫曼树与哈夫曼编码 哈夫曼树是一种特殊的二叉树,具有最小的带权路径长度。在汉字压缩中,哈夫曼树的应用主要体现在生成哈夫曼编码上,从而实现高效的汉字点阵字形压缩。 **哈夫曼树构建算法**: 1. *...
哈夫曼树源代码,不同于流行的算法。数据结构课程相关。