- 浏览: 18313 次
- 性别:
- 来自: 湖南常德
最新评论
一、哈弗曼树,又称最优树,是一种带权路径长度最短的树。
路径长度: 两个节点之间的路径上的分支数目
数的带权路劲长度:树中所有叶子节点的带权路径长度之和(WPL值,其中WPL最小的就叫最优二叉树或者哈弗曼树)。
二、哈弗曼树的建立
哈弗曼树也算二叉树的一种,所以哈弗曼树的建立和二叉树类似,只是多了个参数--权值。
基本步骤:
一.读取文件,将读取的信息转化为ASCII码,建立数组以ASCII码为下标,记录字符出现的次数
二.生成节点,根据节点的权值排序(使用优先队列) 三.构建哈夫曼树,生成码表根据权值进行排序,根据权值排好序以后,去前两个节点也就是最小的节点,取出后删除节点,两个节点形成一个新的节点,权值小的为新节点的左子节点,权值大的为右子节点。(同时给节点赋值,左子节点为“0”,右子节点为“1”。这就是哈弗曼编码,我们在递归的时候让子节点不断加上父节点的哈弗曼编码就能得到该节点的哈弗曼编码。)我们再将新节点加入优先队列重复以上步骤
HuffmanNode node1 = nodeQueue.poll();
HuffmanNode node2 = nodeQueue.poll(); HuffmanNode parent_node = new HuffmanNode(0, node1.getCount()+ node2.getCount()); parent_node.setLeftChild(node1); node1.setHuffmanCode("0"); parent_node.setRightChild(node2); node2.setHuffmanCode("1"); nodeQueue.add(parent_node);
三、得到哈弗曼编码
哈弗曼树构建好了以后我们开始遍历这棵树,得到他的哈弗曼编码,首先该节点的左右字数是否为空,是则得到其哈弗曼编码,反之则遍历,将子节点的编码加上父节点的编码
if (root.getLeftChild() == null && root.getRightChild() == null) {
// 把叶子节点添加到节点数组里 leafNode[counter] = root; counter++; } else { // 获取当前节点的哈夫曼编码值 String str = root.getHuffmanCode(); // 左节点的编码值加上当前节点的编码值 str += root.getLeftChild().getHuffmanCode(); // 把加后的编码值赋值给左节点 root.getLeftChild().setHuffmanCode(str); // 递归左节点 printHuffmanCode(root.getLeftChild()); // 获取当前节点的编码值 String str1 = root.getHuffmanCode(); // 右节点的编码值加上当前节点的编码值 str1 += root.getRightChild().getHuffmanCode(); // 把加后的编码值赋值给右节点 root.getRightChild().setHuffmanCode(str1); // 递归右节点 printHuffmanCode(root.getRightChild()); }
四、文件的写入
将所有的哈弗曼编码不够八位的补满八位,超过八位补成整数个八位,同时记录补零的个数
for (int i = 0; i < leafNode.length; i++) {
allhfmCode[i] = leafNode[i].getHuffmanCode(); } for (int i = 0; i < leafNode.length; i++) { int zeroCount = 0; String presentCode = leafNode[i].getHuffmanCode(); while (presentCode.length() % 8 != 0) { zeroCount++; presentCode += "0"; } int bytesize = presentCode.length() / 8; leafNode[i].setByteSize(bytesize); leafNode[i].setHuffmanCode(presentCode); leafNode[i].setZeroCount(zeroCount); allString += leafNode[i].getHuffmanCode(); }
将头文件信息写完后,用一串字符进行标记,将头信息和文件体信息隔开解压文件时可以进行判断。文件写入时每八位写入,没有八位的补零满八,写入,同时写入补零个数
for (int i = 0; i < allString.length(); i++) {
// 一个一个的读取给中转字符 writes += allString.charAt(i); // 当读满八位时执行 if (i % 8 == 7) { if (byteCount1 == byteCount2) { // 写入该字符占有几个位置 byteCount2 = leafNode[nodeCount].getByteSize(); bos.write(leafNode[nodeCount].getByteSize()); // 写入字符 bos.write(leafNode[nodeCount].getASCII()); // 写入补了多少个0 String str_zerocount = Integer.toString(leafNode[nodeCount] .getZeroCount()); bos.write((int) str_zerocount.charAt(0)); nodeCount++; byteCount1 = 0; } // 把这8位字符串转化成整形 if (byteCount1 < byteCount2) { int x = ChangeString(writes); // 写入转换后的整型 bos.write(x); // 中转字符串归零 writes = ""; byteCount1++; } } } for (int i = 0; i < 5; i++) { bos.write(97 + i); } // 定义计数器,记录的是内容的补零个数 int zeroCount = 0; // 定义一个存储内容编码的字符串 String content = ""; // 定义一个中转字符串 String tranString = ""; // 遍历读取文件内容,并写入文件 for (int i = 0; i < length; i++) { // 读取文件 int x = bis.read(); // 循环判断该字符所对应的编码 for (int j = 0; j < allhfmCode.length; j++) { if (x == leafNode[j].getASCII()) { // 把编码赋值给字符串中存储 content += allhfmCode[j]; } } // 如果此时的字符串位数大于等于8 if (content.length() >= 8) { // 循环获得前八位 for (int j = 0; j < 8; j++) { tranString += content.charAt(j); } // 把这8位字符串转化成整形 int a = ChangeString(tranString); // 写入转换后的整型 bos.write(a); // 清空转换字符串 tranString = ""; // 循环获得除去前八位后剩下的字符 for (int j = 8; j < content.length(); j++) { tranString += content.charAt(j); } // 把原先的字符串覆盖掉 content = tranString; // 清空转换字符串 tranString = ""; } } // 如果没有满八位,则补上0 while (content.length() % 8 != 0) { zeroCount++; content += "0"; } // 把这8位字符串转化成整形 if (content.equals("")) { } // 把这8位字符串转化成整形 else { int b = ChangeString(content); // 写入转换后的整型 bos.write(b); } // 写入补零计数器 String so = Integer.toString(zeroCount); bos.write((int) so.charAt(0));
五、文件解压
解压可以算是压缩的逆过程
按照自己写入的规律读取文件形成新的文件
发表评论
-
git入门
2015-02-11 11:02 0git入门 -
JVM内存结构浅谈
2013-05-19 14:47 659Java程序的运行过程: ... -
菜鸟入门之网页数据抓取
2013-05-04 21:53 5526有时候需要从网页上获取数据,比如别一些网页上的新闻获取到放 ... -
动态编译
2013-03-01 22:33 583前几天谈论了关于动 ... -
位映射
2013-03-01 22:33 917前些天讨论了位映射的内容,一个具体的例子就对于M个int ... -
线程同步
2013-03-01 22:34 7131,为什么要有线程同 ... -
生产消费模型
2013-03-01 22:34 678当遇到一个线程要产生数据而另一个线程要处理数据时,这就是生 ... -
设计模式之单例模式
2012-12-02 23:02 0单例模式又叫单台模式或者单例模式 -
数据结构之Hash
2012-11-19 21:45 858数据结构之hash 首先介绍两种非常重要的数据结构。数组,为 ... -
数据结构之Hash
2012-11-18 14:47 0数据结构之hash 首先介 ... -
网络通信总结
2012-10-28 15:33 820网络通信:一句话说,用网络传输数据(各种数据) 。进行通讯那 ... -
链表总结
2012-08-03 11:43 784首先,链表是一种顺 ... -
线程及线程应用总结
2012-08-03 11:44 729一、什么是线程 每个java程序都至少有一个线程 ... -
树二叉树总结
2012-08-03 11:45 835一、数的相关 节点: 节点是树的基本组成单 ... -
java集合框架
2012-07-16 21:21 723java集合框架总结 主要由以下三部分组成: ... -
I/O体系结构总结
2012-07-16 21:22 883I/O体系结构总结 流的概念和分类: ... -
File相关类总结
2012-07-16 21:22 892File是java中的与文件相关的类,可以对进行创建、删 ... -
java异常机制
2012-07-11 13:01 691JAVA异常机制 一、异常的基本概念 简单的说 ... -
总结20120705
2012-07-05 10:07 650一、类与对象 1. ... -
java关键字总结
2012-05-20 13:31 705常用关键字: 访问修饰符关键字: public: 是最为公 ...
相关推荐
哈弗曼压缩编码
自适应哈弗曼压缩编码VC源码 VS2010工程 自适应哈弗曼压缩编码VC源码 VS2010工程 自适应哈弗曼压缩编码VC源码 VS2010工程
哈弗曼压缩解压算法代码
实现哈弗曼压缩及解压缩功能,并计算压缩前后文件占用空间比 模型建立与题目分析 压缩: 以二机制可读形式打开源文件,以二进制可写形式打开压缩目标文件。每次从源文件读取八个比特(一字节),作为一个ASCII码...
huffmanCompress哈弗曼压缩与解压缩,一个压缩工具
哈弗曼压缩软件(数据结构试验报告附源程序).docx哈弗曼压缩软件(数据结构试验报告附源程序).docx
哈弗曼压缩软件(数据结构试验报告附源程序).pdf哈弗曼压缩软件(数据结构试验报告附源程序).pdf
数据结构 哈弗曼实现压缩算法 数据结构 哈弗曼实现压缩算法 数据结构 哈弗曼实现压缩算法
课程实习时做的哈弗曼压缩程序,效率不是很好,还望大家指点
本文件里含有哈弗曼压缩文件和解压文件程序 另外还有多项式的简单运算 哈弗曼采用了MFC界面来编写,简洁美观!
2 个文件,一个是MATLAB哈弗曼压缩纯英文文本;一个是图像Huffman编码;都是MATLAB程序。
哈弗曼编码技术来实现文件的压缩和解压缩。
NULL 博文链接:https://qc-aion.iteye.com/blog/903422
用MATLAB实现用哈弗曼编码压缩纯英文文本文件,并能解压缩。
这是大二数据结构课程的大project,主要实现了用哈弗曼不等长编码对文件的压缩。
利用哈弗曼原理实现压缩解压文件,其语言是利用Java实现,
哈夫曼压缩编码
using namespace std; /***********************************************/ struct HTNode{/*Huffman Tree 的结构定义*/ long long weight; int parent, lchild, rchild; char chr; }; class Huffman{ ...
哈夫曼是一种常用的压缩方法。是1952年为文本文件建立的,其基本原理是频繁使用的数据用较短的代码代替,很少使用的数据用较长的代码代替,每个数据的代码各不相同。这些代码都是二进制码,且码的长度是可变的。如: ...
VC++基于哈弗曼算法的一个压缩和解压的VC例子,可视界面操作,可方便运用到程序里面。