在离散数学中就看到了哈弗曼编码这个东西....但是当时没有比较具体的思考....当数据结构到来时才选择了这个课程设计...(采用 java 实现)
实现这个程序有几个核心(实现算法方法有多种):
1 : 建树
2 : 查找数据节点(分编码、译码两种)
3 : 将编码用二进制数据写入
这个我总共修改了 n 遍, 第一版本是采用 char (java 的char是 16位 ) 是为了压缩文本数据.但是这个的速度确实有点慢(因为全部都是无序链表形式),但是文本压缩率约 58%,之后为了可以压缩所有文件采用了 byte (压缩率有所下降) 进行压缩.这样也减少了内存使用后来使用.后来进行了新的统计查找算法(采用哈希表),极大提高了压缩执行速度..
压缩char 的程序做了比较美观的界面,可以显示文本内容,界面比较完善.(课程设计嘛).byte 的界面十分简单 ,只是为了实现我的想法.提高可应用性.但是一开始采用的还是链表的方法,执行速度还是有点慢.暑假回家后没事就顺便修改了一下.某天突然来了灵感就改成哈希表形式(压缩速度大大提高).但是这个已经不可能再作为课程设计上交了(小小郁闷一下) ...后来也完善了大文件(2G内)的压缩算法(其实没什么.这里不介绍,下面是界面)
/* 先介绍一下节点类*/
class ByteHfmNode {
byte data; int weight; long code; int deep; ByteHfmNode rchild; ByteHfmNode lchild; ByteHfmNode next; private boolean isleaf;
ByteHfmNode(); // 无参数构造器 由于构造 树的根
ByteHfmNode(byte); //通过 数据 构造节点
ByteHfmNode(byte,int); //通过 数据和其权 构造叶子节点
ByteHfmNdoe(ByteHfmNode,ByteHfmNode); //通过两个孩子节点 构造新节点
boolean isLeaf(); // 检验叶子节点
boolean isRoot(); // 检验根节点
}
/*********************** 在介绍主要实现功能的 方法*************************************/
/************************ 1： 用于统计字符的方法:************************************/
/**
* 编码过程添加数据记录(用于统计)
* @param data 字符
*/
void append(byte data){
pos = data+128;
if(appendArray[pos] == null){
appendArray[pos] = new ByteHfmNode(data);
this.LEAFS ++;
}else{
appendArray[pos].weight ++;
}
}
/**
* 解码过程添加数据(用于统计)
* @param data 字符
* @param weight 权
*/
void append(byte data,int weight){
unCodeappendTmp.next = new ByteHfmNode(data,weight);
unCodeappendTmp = unCodeappendTmp.next;
}
/*********************** 2 用于建树的方法 ***************************/
/**
* 建立哈弗曼编码树
* @throws Exception
*/
void createTree()throws Exception {
/*根据编码译码进行建树前初始化*/
if(Coding){
this.initSortArray(); //更加原来的统计数组生成 可以排序的数据
this.sort(); // 排序
this.arrrayToLink(); //将数组转换为链表(这样方便于建树)
}else{
//译码不需要进行初始化;
}
ByteHfmNode tmp = head;
ByteHfmNode stmp = head;
while(head.next.next != null){
stmp = head;
tmp = new ByteHfmNode(head.next,head.next.next);
head.next = head.next.next.next;
while(stmp.next != null&&stmp.next.weight < tmp.weight){
stmp = stmp.next;
}
if(stmp.next == null){
stmp.next = tmp;
//stmp = head;
}else{
tmp.next = stmp.next;
stmp.next = tmp;
}
}
head.rchild = head.lchild = head.next;
/* 解码时候需要先进行初始化搜索缓存节点*/
if(!Coding){
searchTmp = head.lchild;
}
}
/****** 建树使用到的方法 *****/
/**
* 对编码树进行编码
* @throws Exception
*/
void codeTree()throws Exception{
if(head.lchild.isRoot()){
this.CODETREE(head.lchild, 0, 0);
}else{
CODETREE(head.lchild,1,1);
}
}
/**
* 对哈弗曼数组进行排序（按权值升序排序）
*/
private void sort(){
int i=0,j=0;
int length = sortArray.length;
ByteHfmNode temp;
for(int gap = length>>1; gap>0;gap = gap==2?1:(int )(gap/2.2)){
for( i = gap;i<length;i++){
temp = sortArray[i];
j=i;
for(;j>= gap && temp.weight < sortArray[j - gap].weight ;j-= gap){
sortArray[j] = sortArray[j - gap];
}
sortArray[j] = temp;
}
}
for( i=0;i<sortArray.length;i++){
}
}
/**
* 将排好序的数组转换为链表同时记录下字符及其权值
*/
private void arrrayToLink(){
head.next = sortArray[0];
datas = null;
weights = null;
datas = new byte[sortArray.length];
weights = new int[sortArray.length];
datas[0] = sortArray[0].data;
weights[0] = sortArray[0].weight;
//System.out.println("Length:"+sortArray.length);
/******** 现在需要先将排序号的数据保存下来 这样解码才有数据 ****/
for(int i = sortArray.length - 1;i>0;i--){
sortArray[ i-1 ].next = sortArray[i];
datas[i] = sortArray[i].data;
weights[i] = sortArray[i].weight;
}
}
/******************************** 移位写入文件 ****************************************/
/** 在这里必须先介绍我的文件结构:
* 文件结构：
* 文件头： ‘B’0xff 2 byte
* 文件长度： count 4 byte
* 字符种类： data.length 1 byte
* 最大权值： weightSize 1 byte
* 间隔符 ： 0xff 0xff 2 byte
* 权表：{ 字符，对应的权，下一字符，对应权 ..... }
* 间隔符 ： 0xff 0xff 2 byte
* 编码数据： 二进制文件
*/
public byte[] getHuffmanByteArray()throws Exception{
if (lastCount == count) {
return hfmOutput.toByteArray();
}
int lastSize = 0;
if(hfmOutput!=null){
lastSize = hfmOutput.size();
}
hfmOutput = null;
hfmOutput = new ByteArrayOutputStream();
//******************************************************************
bhm.createTree();
bhm.codeTree();
byte [] datas = bhm.getDatas();
int [] weights = bhm.getWeight();
/* 文件头标志位 byte 哈弗曼编码文件 */
byte[] fileHead = {'B',(byte)0xff};
/* 文件内部间隔符 */
byte[] mark = {(byte)0xff,(byte)0xff};
int weightSize = weights[weights.length-1];
/* 根据本次编码最大权值占用 byte 数控制写入权值的位数 */
if(weightSize<0xff){
weightSize = 1;
}else{
if(weightSize<0xffff){
weightSize = 2;
}else{
if(weightSize<0xffffff){
weightSize = 3;
}else{
weightSize = 4;
}
}
}
hfmOutput.write(fileHead);
hfmOutput.write(intToBytes(count));
hfmOutput.write(datas.length);
hfmOutput.write(weightSize);
hfmOutput.write(mark);
byte wtmp[] = new byte[4];
for(int i = 0 ;i<datas.length;i++){
hfmOutput.write(datas[i]);
wtmp = intToBytes(weights[i]);
hfmOutput.write(wtmp,0,weightSize);
}
hfmOutput.write(mark);
/* 权表保存完毕,下面写入数据*/
/* 临时缓存变量*/
byte ct =0;
/* 记录上次写入剩余数据*/
byte buffer = 0;
/* 记录本次写入开始位*/
int nowPos = 0;
/* 记录本字符编码*/
long code = 0;
/* 记录本字符编码长度*/
int deep = 0;
/* 计数器*/
int k = 0 ;
ByteHfmNode hfmTmp;
// System.out.println(count);
int bit =0;
int i = 0;
int writeTime = 0;
for( i=0;i<count;i++){
hfmTmp = bhm.getNode(buf[i]);
code = hfmTmp.code;
deep = hfmTmp.deep;
bit+=deep;
if(nowPos+deep>8){
/* 编码已经超过一个字节 先写入*/
ct = (byte)((code>>(deep - ( 8 - nowPos)))&0xff);
ct = (byte)((ct)|(buffer));
hfmOutput.write(ct);
writeTime++;
for(k = 1; deep -(k<<3) + nowPos >8; ){
ct = (byte) ( (code>>( deep - ((++k)<<3) +nowPos ) )& 0xff );
hfmOutput.write(ct);
//writeTime++;
}
nowPos = (deep+nowPos)- (k<<3) ;
buffer = (byte)((code<<(8-nowPos ))&0xff);
}else{
/*添加后编码不够一个字节长度 */
if(nowPos+deep ==
{
ct = (byte)code;
ct = (byte)((ct)|(buffer));
hfmOutput.write(ct);
writeTime++;
nowPos = 0;
buffer =0;
}else{
nowPos += deep;
ct = (byte)((code<<(8 - nowPos))& 0xff);
buffer =(byte)(ct|buffer);
}
}
}
/*如果还有剩余数据写入*/
if(nowPos >0){
hfmOutput.write(buffer);
}
//System.out.println("\nOK!"+hfmOutput.size()+" bit"+bit + " i:"+i+" writeTimt:"+writeTime);
return hfmOutput.toByteArray();
}
/************************* 最后介绍一下解码过程吧 *************************/
public byte[] getunCodeBytes()throws Exception{
if(this.buf[0] != 'B'||this.buf[1]!=-1 ||this.count<12||buf[8] != -1 || buf[9] != -1 ){
throw new UnsupportedEncodingException();
}
int nowPos = 10;
int contentLength;
int dataLength = buf[6]&0x000000ff;
int weightSize = buf[7];
if(dataLength == 0& weightSize!= 0){
dataLength = 256;
}
int i,j,k;
int intTmp;
byte byteTmp;
byte[] bytesTmp = new byte[4];
bytesTmp[0] = buf[2];
bytesTmp[1] = buf[3];
bytesTmp[2] = buf[4];
bytesTmp[3] = buf[5];
contentLength = bytesToInt(bytesTmp);
for(i=0;i<4;i++){
bytesTmp[i] = 0;
}
/*读取权表*/
for(i=0;i<dataLength;i++){
byteTmp = buf[nowPos++];
for(j =0 ;j<weightSize;j++){
bytesTmp[j] = buf[nowPos++];
}
intTmp = bytesToInt(bytesTmp);
bhm.append(byteTmp, intTmp);
}
if(buf[nowPos++] != -1|| buf[nowPos++]!= -1){
throw new UnsupportedEncodingException();
}
/* 建树编码*/
bhm.createTree();
//bhm.codeTree();
boolean rchild;
int time = 0;
ByteHfmNode tmp;
/*权表读取完毕，开始解码*/
while(nowPos<count){
byteTmp = buf[nowPos++];
for(j = 7;j>=0;j--){
intTmp = (byteTmp>>j);
intTmp = intTmp&0x1;
rchild = (intTmp == 1 );
if(bhm.searchNode(rchild)){
time++;
tmp =bhm.getSearchNode();
bos.write(tmp.data);
if(time >= contentLength){
//System.out.println(time+" "+contentLength);
break;
}
}
}
byteTmp = 0;
}
return bos.toByteArray();
}
使用大文件压缩器时间
(压缩一个 2.09m 的exe文件 时间: 273 ms 压缩后 1.71m ,
一个 61.3m 的exe 时间:2723ms 压缩后文件大小基本没变 )
压缩率跟哈弗曼算法有关
添加一个C#移植版，需要.net framework
- 大小: 71.7 KB
分享到：
相关推荐
哈弗曼编码是一种高效...总之，这个基于C++的哈弗曼编/译码器项目涉及到了数据压缩的基础理论，二叉树的构建，编码和解码算法的实现，以及C++的文件处理等多个方面的知识，对于理解和应用哈弗曼编码有很好的实践价值。
哈弗曼编码是一种高效的数据压缩方法，它基于一种特殊的二叉树——哈弗曼树（Huffman Tree），也称为最优二叉树。这种编码技术在信息传输和存储中发挥着重要作用，特别是在图像处理（如JPEG）、文本压缩等领域广泛...
哈弗曼编码是一种高效的数据压缩方法，通过构建哈弗曼树来实现。在给定的题目中，我们看到两个不同的构建哈弗曼树的方法：方案1是直接输入字符及其权值，而方案2是根据文档中字符的频率来构建。 在哈弗曼树的结构中...
根据给定文件的信息，我们可以提炼出关于“C++语言实现的哈夫曼编码/译码器”的关键知识点，包括但不限于： ### 哈夫曼编码原理 哈夫曼编码是一种可变长度的前缀编码技术，它根据字符出现频率来构建一棵哈夫曼树，...
### 哈弗曼编码译码器：Huffman译码器 #### 一、概述 哈弗曼编码（Huffman Coding）是一种广泛应用于数据压缩领域的编码方式，它是由David A. Huffman在1952年提出的。哈弗曼编码的核心思想是通过构建一棵特殊的...
这个压缩文件包含了实现哈弗曼编码译码的完整代码，适用于数据结构课程设计。学生可以从中学习到如何运用链表、树等数据结构以及算法来实现这一过程。同时，此项目还可以帮助学生理解数据压缩的基本原理和实际应用，...
5. **哈弗曼译码器**：译码器主要包括： - 读取比特流：`Read()`函数用于从压缩文件中读取比特。 - 重建哈弗曼树：`CreateFromCodeFile()`或`CreateFromSourceFile()`函数根据编码文件或原始文件头重建哈弗曼树。 ...
通过对哈弗曼编码/译码器的设计和实现，学生能够全面掌握数据结构和算法在实际问题中的应用，同时提升编程实践能力。这个过程不仅是对专业知识的巩固，也是对个人解决问题能力的锻炼。通过课程设计，学生将能够更好...
请设计一个哈夫曼编码器/译码器。 【基本要求】 （1）初始化：键盘输入n个字符和n个权值，建立哈夫曼树； （2）编码：利用已建立的huffman树生成huffman编码 ； （3）译码：利用已建立的哈夫曼树对一段代码进行译码...
总的来说，哈弗曼编码译码器是实现数据压缩的重要工具，它的C++实现涉及数据结构、算法和文件操作等多个方面的知识。理解和掌握哈弗曼编码不仅可以提高数据压缩的效率，也是深入理解计算机科学和信息处理的关键一步...
4. **译码功能**：译码是哈夫曼编码的逆过程。给定一个编码，需要按照哈夫曼树的结构，从根节点开始，根据0和1的序列决定向左还是向右移动，直至到达叶节点，这样就可以确定原始字符。 5. **数据结构设计**：在C++...
在C++中实现哈弗曼编码译码器，我们需要理解以下几个关键步骤： 1. **构建哈弗曼树**： - 首先，统计输入字符的频率，创建一个频率列表。 - 使用优先队列（通常用最小堆实现）存储哈弗曼树节点，其中包含字符及其...
这个Java版的哈弗曼编码译码器是一个很好的学习资源，适合加深对数据结构和算法的理解，特别是对于那些希望掌握数据压缩技术的学生或开发者。通过阅读和分析源代码，你可以了解到如何将理论知识应用于实际编程中，...
哈夫曼译码流程图，数据结构课程设计需要，用visio画的
《哈弗曼编码译码器实现详解》 哈弗曼编码是一种有效的数据压缩方法，它通过构建哈弗曼树来生成具有最短路径长度的编码，使得频度高的字符拥有较短的编码，从而提高编码效率。在哈弗曼编码器中，主要涉及以下几个...
哈夫曼编/译码器 问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）...
### 哈弗曼编码译码器C++代码解析与知识点总结 #### 一、哈弗曼编码原理 哈弗曼编码（Huffman Coding）是一种广泛应用于数据压缩领域的编码技术，它采用一种自底向上的贪心算法来构建最优前缀码。这种编码方式能够...