哈夫曼压缩

1. 哈夫曼实现压缩

我的作业，哈弗曼树的建立，不过那个字符的频率要自己编的。
//main.cpp
#include"HuffmanTree.h"
#include<string.h>
#include<stdlib.h>
//#include<iostream>

//using namespace std;

int main(){

HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n\n**********************欢迎使用哈夫曼编码/译码系统**********************\n"<<endl<<endl;
cout<<" 您可以进行以下操作:\n";
cout<<" 1 建立哈夫曼树\n";
cout<<" 2 编码(源文已在文件ToBeTran中，或键盘输入)\n";
cout<<" 3 译码(码文已在文件CodeFile中)\n";
cout<<" 4 显示码文\n";
cout<<" 5 显示哈夫曼树\n";
cout<<" 6 退出\n\n";

cout<<" 请选择一个操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感谢使用本系统!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main

//Huffmannode.h
#ifndef _HuffmanNode_
#define _HuffmanNode_
struct HuffmanNode
{
int weight; //存放结点的权值，假设只考虑处理权值为整数的情况
int parent; //-1表示为根结点，否则表示为非根结点
int lchild,rchild; //分别存放该结点的左右孩子的所在单元的编号
};
#endif

//huffmantree.h
#ifndef _HuffmanTree_
#define _HuffmanTree_
#include"HuffmanNode.h"
#include<iostream>
#include<fstream>
#include<string>
using namespace std;

class HuffmanTree //哈夫曼树
{
public:
struct HuffmanNode *Node; //Node[]存放哈夫曼树
char *Info; //Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放
int LeafNum; //哈夫曼树的叶子个数，也是源码个数
public:
HuffmanTree();
~HuffmanTree();
void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node[]中。 让用户从两种建立哈夫曼树的方法中选择：
1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，
并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/
void CreateHuffmanTreeFromKeyboard();
void CreateHuffmanTreeFromFile();
void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），
对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。
ToBeTran的内容可以用记事本等程序编辑产生。*/
void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，
则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，
得到的源文写入文件TextFile中，并同时输出到屏幕上。*/
void PrintCodeFile(); /*将码文文件CodeFile显示在屏幕上*/
void PrintHuffmanTree(); /*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，
同时写入文件TreePrintFile中*/
void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/
};
#endif

//huffmantree.cpp
#include"HuffmanTree.h"
#include<string>
#include<limits> //为使用整型最大值

//#include<iostream>
using namespace std;

//******************************************************
HuffmanTree::HuffmanTree()
{
LeafNum=0;
Node=NULL;
Info+NULL;

}
//******************************************************
HuffmanTree::~HuffmanTree()
{
delete []Node;
Node=NULL;
delete []Info;
Info=NULL;

}
//******************************************************
void HuffmanTree::CreateHuffmanTree()
{
char Choose;
cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";
cin>>Choose;
if(Choose=='2') {//键盘输入建立哈夫曼树
CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile();
}
}
//******************************************************
void HuffmanTree::CreateHuffmanTreeFromKeyboard()
{
int Num;
int i,j,pos1,pos2,max1,max2;
cout<<"\n请输入源码字符集个数：";
cin>>Num;
if (Num<=1)
{
cout<<"无法建立少于2个叶子结点的哈夫曼树。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
Info=new char[2*Num-1];
for( i=0;i<Num;i++) {//读入哈夫曼树的叶子结点信息
cout<<"请输入第"<<i+1<<"个字符值";
getchar();
Info[i]=getchar(); //源文的字符存入字符数组Info[]
getchar();
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //源文的字符权重存入Node[].weight
Node[i].parent=-1; //为根结点
Node[i].lchild=-1; //无左孩子
Node[i].rchild=-1; //无右孩子
}

for( i=Num;i<2*Num-1;i++) //循环建立哈夫曼树内部结点 表示需做Num-1次合并
{
pos1=-1;pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
max1=32767; max2=32767; //32767为整形数的最大值 分别用来存放当前找到的最小值和次小值
for(j=0;j<i;j++) //在根结点中选出权值最小的两个
{
if(Node[j].parent==-1) //是否为根结点
if(Node[j].weight<max1) //是否比最小值要小
{
max2=max1; //原最小值变为次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在的单元编号
pos1=j; //修改最小值所在的单元编号
}
else
if(Node[j].weight<max2) //比原最小值大但比原此小值小
{
max2=Node[j].weight;
pos2=j;
}
}
Node[pos1].parent=i;
Node[pos2].parent=i;
Node[i].lchild=pos1;
Node[i].rchild=pos2;
Node[i].parent=-1;
Node[i].weight=Node[pos1].weight+Node[pos2].weight;

} //for

LeafNum=Num;
cout<<"哈夫曼树已成功构造完成。\n";

//把建立好的哈夫曼树写入文件hfmTree.dat
char ch;
cout<<"是否要替换原来的哈夫曼树文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打开文件
if(fop.fail()) {
cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先写入哈夫曼树的叶子结点个数
for( i=0;i<Num;i++) { //再写入源文字符集的所有字符（存储在Info[]中）
fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for( i=0;i<2*Num-1;i++) { //最后写入哈夫曼树的各个结点（存储在Node[]中）
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close(); //关闭文件
cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n";
}

//******************************************************
void HuffmanTree::CreateHuffmanTreeFromFile()
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。\n";
fip.close();
return;
}
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for( int i=0;i<LeafNum;i++)
fip.read((char*)&Info[i],sizeof(Info[i]));
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼树已成功构造完成。\n";
}

//******************************************************
void HuffmanTree::Encoder()
{
if(Node==NULL) //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}//if

char *SourceText; //字符串数组，用于存放源文
//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入
char Choose;
cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？";
cin>>Choose;
if(Choose=='1')
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail())
{
cout<<"源文文件打开失败!无法继续执行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入k
fip1.close();

SourceText=new char[k+1]; //申请存放源文的字符数组空间
ifstream fip2("ToBeTran.txt");//第二次读源文文件，把内容写入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
cout<<"需编码的源文为：";
cout<<SourceText<<endl;
}
else { //从键盘输入源文
string SourceBuff;
cin.ignore();
cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}

ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件
char *code;
code=new char[LeafNum]; //存放一个源文字符的编码
int k=0;
int i,j,start;
while(SourceText[k]!='\0') //源文串中从第一个字符开始逐个编码
{
start=0;
for(i=0;i<LeafNum;i++)
if(Info[i]==SourceText[k]) //求出该文字所在单元的编号
break;
j=i;
while(Node[j].parent!=-1) //结点j非根
{
j=Node[j].parent; //求结点j的双亲结点
if(Node[j].lchild==i) //是左子树，则生成代码0
code[start++]='0';
else
code[start++]='1'; //是右子树，则生成代码1
i=j;
}
code[start]='\0'; //置串结束符
for(i=0;i<start/2;i++)
{
j=code[i];
code[i]=code[start-1-i];
code[start-1-i]=j;
}
i=0; //将源文的当前字符的对应编码写入码文文件
while(code[i]!='\0')
{
fop<<code[i];
i++;
}
k++; //源文串中的字符后移一个

}
fop.close();
cout<<"已完成编码，码文已写入文件CodeFile.dat中。\n\n";
}

//******************************************************
void HuffmanTree::Decoder()
{

//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}

//将码文从文件CodeFile.dat中读入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail())
{
cout<<"没有码文，无法译码。\n";
return;
}

char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch))
{
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';

cout<<"经译码得到的源文为：";
ofstream fop("TextFile.dat");

int j=(LeafNum-1)*2; //j指向哈夫曼树的根

int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子
while(CodeStr[i]!='\0') //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符
{
if(CodeStr[i]=='0')
j=Node[j].lchild; //往左走
else
j=Node[j].rchild; //往右走
if(Node[j].rchild==-1) //到达叶子结点
{
cout<<Info[j]; //输出叶子结点对应的字符
j=LeafNum*2-1-1; //表示重新从根结点开始往下搜索
}
i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中。\n\n";
}
//******************************************************
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"没有码文文件，无法显示码文文件内容。\n";
return;
}
while(fip.get(ch))
{
cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
//******************************************************
void HuffmanTree::PrintHuffmanTree()
{
//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}

ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
//******************************************************
void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer)//凹入表示法
{
if(Node[T].lchild!=-1)
PrintHuffmanTree_aoru(Node[T].lchild,layer+1);//左子树
for(int i=1;i<=layer;i++)// 根
cout<<'\0'<<'\0'<<'\0';
cout<<Node[T].weight<<endl;
if(Node[T].rchild!=-1)
PrintHuffmanTree_aoru(Node[T].rchild,layer+1); // 右子树

}

2. 哈夫曼压缩算法的内容是什么

注:哈夫曼和lzss算法不是同一种算法,先用哈夫曼再用lzss算法压缩后会发现经哈夫曼压缩后再用lzss压缩文件会变大,具体原因不明
lzss原理:
把编码位置置于输入数据流的开始位置。
在前向缓冲器中查找窗口中最长的匹配串
①
pointer
：=匹配串指针。
②
length
：=匹配串长度。
判断匹配串长度length是否大于等于最小匹配串长度(min_length)
，
如果“是”：输出指针，然后把编码位置向前移动length个字符。
如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。
如果前向缓冲器不是空的，就返回到步骤2。
例：编码字符串如表03-05-3所示，编码过程如表03-05-4所示。现说明如下：
“步骤”栏表示编码步骤。
“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。
“匹配”栏表示窗口中找到的最长的匹配串。
“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
“输出”栏的输出为：
①
如果匹配串本身的长度length
>=
min_length，输出指向匹配串的指针，格式为(back_chars，
chars_length)。该指针告诉译码器“在这个窗口中向后退back_chars个字符然后拷贝chars_length个字符到输出”。
②
如果匹配串本身的长度length
>=
min_length，则输出真实的匹配串。
表:输入数据流
位置
1234567891011
字符
aabbcbbaabc
表:编码过程(min_length
=
2)
步骤位置匹配串输出
11--a
22aa
33--
b
44bb
55--c
66b
b(3,2)
78
a
a
b(7,3)
811cc

3. 哈夫曼树怎么压缩和解压 c++

http://blog.csdn.net/leex_brave/article/details/51598359

4. 哈夫曼编码压缩概念的基本思想如何回答(精简的说)

哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

5. 哈夫曼编码法的压缩和解压缩怎么实现

建立一棵赫夫曼树，设每个父节点的左子节点为1，右子节点为0，然后由根节点到所要编码的字符的叶节点的路径确定字符的编码。比如要编码a，假设a在第三层，则由根节点到a的路径为：根节点——右子节点（0）——左子节点（1）。那么a的编码就为01。就这样把所有字符进行编码，建立一个赫夫曼编码表。利用这个编码表把字符串编码就是压缩了，解压缩就是把参照赫夫曼编码表把编码转为字符串。

6. 在哈夫曼编码压缩程序中应该如何存储哈夫曼编码

我想你理解错了……你所说的128Bit是编码和解码时用的
树怎么保存，方法很多，最简单的办法是为0x00到0xFF按它们出现的频率保存顺序；因为只有256个元素，所以用1字节就能保存到它们的顺序，例如
0x00 0x05
0x01 0x04
0x02 0xF5
……
……
要保存这种表示方式也只是要512字节而已；重建树的时候重再根据这些数据来把树创建出来就是了；

最后建议你把哈夫曼编码原理重新再看一次，是看“原理”

7. 哈夫曼压缩字符文件的分隔符问题

哈夫曼 不需要分隔符 他没有重码

这里可以采用双填充的手段：就是出现eof作为
数据部分的时候用eof eof 的格式读的时候
出现连续的eof eof 时省略eof 保留一个作为数据！

8. 利用哈夫曼编码进行压缩压缩率一般达到多少

哈夫曼编码进行压缩的压缩率是根据平均码长来计算的，压缩率比较低。

例如：用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：

4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

2.61/3=0.87=87%

其平均码长是等长码的87%，所以平均压缩率为13%。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

压缩率，描述压缩文件的效果名，是文件压缩后的大小与压缩前的大小之比，例如：把100m的文件压缩后是90m，压缩率为90/100*100%=90%，压缩率一般是越小越好，但是压得越小，解压时间越长。

(8)哈夫曼压缩扩展阅读

哈夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。