数据压缩算法实现
Ⅰ 压缩文件如何达到高压缩率
压缩文件达到高压缩率的方法有：
1、首先，我们对我们需要进行压缩操作的文件击右键，选择“添加到压缩文件”。
2、由于我们在进行压缩文件的时候，如果我们将文件格式选择为.rar,一般来说这样压缩的文件的压缩比率是较高的。如果我们选择了.zip文件格式，那么一般情况下压缩比率是比较小的，所以我推荐大家还是选择为.rar的文件格式。
3、接下来，我们需要进行的操作就是，将“创建固实压缩文件”和“测试压缩文件”两个选项勾选，这样我们下来压缩的文件就会比较小，大家可以看看自己文件属性里面的压缩比率，如果文件很大的话，会很明显。希望大家勾选“测试压缩文件”，因为我们可能会在压缩文件的过程中遇到某些未知错误。
4、接下来，我们就可以点击“确定”，软件就会自动进行压缩操作，然后看看我们的文件的压缩比率吧。
5、如果我们需要压缩的文件的体积很大，那么为了节约时间，一般情况下也是可以将文件格式选择为.zip，毕竟这样可以节约很多时间的。
(1)数据压缩算法实现扩展阅读：
常用的图像压缩软件有：
①JPEG Optimizer
JPEG Optimizer是一个可以按照指定的压缩比压缩JPEG格式图片的工具软件，它使用Magic Compress技术，能对 JPEG图形文件压缩50%而不损失画质，自定压缩比，能即时显现压缩后的图片，比较差异，效果相当不错。而所有这一切，只需要通过调整杆进行压缩比调整即可。
②The JPEG Wizard
The JPEG Wizard可以在不影响图像质量的情况下对图片进行最大限度的压缩，同时支持对图片的局部压缩、剪切、旋转，调整图片的对比度、亮度和色度。另外，The JPEGWizard还具有较强的批处理功能，避免重复性操作。
③7-Zip
7-Zip是一款号称有着现今最高压缩比的压缩软件，它不仅支持独有的7z文件格式，而且还支持各种其他压缩文件格式，其中包括ZP、RAR、CAB、GZIP、BZP2和TAR。此软件压缩的压缩比要比普通ZIP文件30%~50%。因此，它可以把经 Winzip压缩的文件再压缩2%~10%。
Ⅱ 数据无损压缩技术到底怎么实现的
无损数据压缩（Lossless Compression）是指使用压缩后的数据进行重构（或者叫做还原，解压缩），重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。也就是说数据经过压缩后信息不受损失，还能完全恢复到压缩前的原样。它和有损数据压缩相对。这种压缩通常压缩比小于有损数据压缩的压缩比。
一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2～1/4。一些常用的无损压缩算法有霍夫曼（Huffman）算法和LZW(Lenpel-Ziv & Welch）压缩算法。
Ⅲ 利用huffman树实现文件的压缩与解压
这是本人写的动态哈夫曼压缩算法实现，压缩与解压缩时，
根据文件内容自动生成哈夫曼树，并动态调整节点的权重
和树的形状。900MHZ的PIII赛扬每秒钟可以压缩的好几MB
的数据，只是压缩率不高，文本文件的压缩后容量一般可
以减少25%，比RAR差远了。
源文件共三个，你在VC6.0中新建一个空的命令行项目，
将它们加进去，编译完就可以用了。
===========hfm.cpp===================
#include <stdio.h>
#include <string.h>
#include <io.h>
#include <sys/stat.h>
#include <fcntl.h>
#include "Huffman.h"
int wh;
int rh;
bool Write(unsigned char *s,int len){
_write(wh,s,len);
return true;
}
bool OpenFile(char* source,char* target){
int w_flag=_O_WRONLY | _O_CREAT | _O_EXCL | _O_BINARY;
int r_flag=_O_RDONLY | _O_BINARY;
rh=_open(source,r_flag,_S_IREAD | _S_IWRITE);
wh=_open(target,w_flag,_S_IREAD | _S_IWRITE);
if(rh==-1 || wh==-1){
if(rh!=-1){
_close(rh);
printf("\n打开文件：'%s'失败!",target);
}
if(wh!=-1){
_close(wh);
printf("\n打开文件：'%s'失败!",source);
}
return false;
}else{
return true;
}
}
void PrintUsage(){
printf("\n以动态哈夫曼算法压缩或解压缩文件。\n\n");
printf("\thfm -?\t\t\t\t显示帮助信息\n");
printf("\thfm -e -i source -o target\t压缩文件\n");
printf("\thfm -d -i source -o target\t解压缩文件\n\n");
}
void main(int argc,char *args[]){
int mode,i,j,K=0;
char src[4096];
char target[4096];
unsigned char buffer[BUFFER_SIZE];
Huffman *h;
mode=0;
for(i=1;i<argc;i++){
if(args[i][0]=='-' || args[i][0]=='/'){
switch(args[i][1]){
case '?':
mode=0;//帮助
break;
case 'e':
case 'E':
mode=1;//压缩
break;
case 'd':
case 'D':
mode=2;//解压缩
break;
case 'o':
case 'O':
if(i+1>=argc){
mode=0;
}else{//输出文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
target[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
target[j]='\0';
K |= 1;
}
}
break;
case 'i':
case 'I':
if(i+1>=argc){
mode=0;
}else{//输入文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
src[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
src[j]='\0';
K |=2;
}
}
break;
}
}
}
if(K!=3)mode=0;
switch(mode){
case 0:
PrintUsage();
return;
case 1://压缩
if(!OpenFile(src,target))return;
h=new Huffman(&Write,true);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Encode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("压缩完毕!");
break;
case 2://解压缩
if(!OpenFile(src,target))return;
h=new Huffman(&Write,false);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Decode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("解压缩完毕!");
break;
}
}
=======end of hfm.cpp=======================
=======Huffman.cpp=============================
// Huffman.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////
#include "Huffman.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
Huffman::Huffman(Output *output,bool mode)
{
Hbtree *tmp;
int i;
this->mode=mode;
//设置输出函数，当缓冲区满时，将调用该函数输出
this->output=output;
//初始化列表
for(i=0;i<LIST_LENGTH;i++)this->list[i]=NULL;
//初始化哈夫曼树
this->root=this->NewNode(NOT_CHAR,LEFT,NULL);
this->current=this->root;
tmp=this->NewNode(CODE_ESCAPE,RIGHT,root);
tmp->count=1;
tmp=this->NewNode(CODE_FINISH,LEFT,root);
tmp->count=0;
root->count=root->child[LEFT]->count+root->child[RIGHT]->count;
//设置缓冲区指针
this->char_top=BOTTOM_BIT;
this->bit_top=TOP_BIT;
this->buffer[0]=0;
//重构哈夫曼树的最大计数值
this->max_count=MAX_COUNT;
this->shrink_factor=SHRINK_FACTOR;
this->finished=false;
}
Huffman::~Huffman()
{
if(this->mode==true){//如果是编码
//输出结束码
this->OutputEncode(CODE_FINISH);
this->char_top++;
}
//强制清空缓冲区
this->Flush();
//释放空间
this->ReleaseNode(this->root);
}
Hbtree * Huffman::NewNode(int value, int index, Hbtree *parent)
{
Hbtree *tmp=new Hbtree;
tmp->parent=parent;
tmp->child[0]=NULL;
tmp->child[1]=NULL;
tmp->count=(1 << SHRINK_FACTOR);
tmp->index=(index==0) ? 0 : 1;
tmp->value=value;
if(value!=NOT_CHAR)this->list[tmp->value]=tmp;
if(parent!=NULL)parent->child[tmp->index]=tmp;
return tmp;
}
void Huffman::ReleaseNode(Hbtree *node)
{
if(node!=NULL){
this->ReleaseNode(node->child[LEFT]);
this->ReleaseNode(node->child[RIGHT]);
delete node;
}
}
//输出一位编码
int Huffman::OutputBit(int bit)
{
unsigned char candidates[]={1,2,4,8,16,32,64,128};
if(bit!=0)
this->buffer[this->char_top] |= candidates[this->bit_top];
this->bit_top--;
if(this->bit_top < BOTTOM_BIT){
this->bit_top=TOP_BIT;
this->char_top++;
if(this->char_top >= BUFFER_SIZE){//输出缓冲区
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}
this->buffer[this->char_top]=0;
}
return 0;
}
//输出缓冲区
int Huffman::Flush()
{
this->output(this->buffer,this->char_top);
this->char_top=0;
return 0;
}
int Huffman::Encode(unsigned char c)
{
int value=c,
candidates[]={128,64,32,16,8,4,2,1},
i;
if(this->list[value]==NULL){//字符不存在于哈夫曼树中
//输出转义码
this->OutputEncode(CODE_ESCAPE);
//输出字符
for(i=0;i<8;i++)this->OutputBit(value & candidates[i]);
this->InsertNewNode(value);
}else{
//输出字符编码
this->OutputEncode(value);
//重新调整哈夫曼树
this->BalanceNode(this->list[value]->parent);
}
//重组哈夫曼树
if(this->root->count>=this->max_count)
this->RearrangeTree();
return 0;
}
void Huffman::BalanceNode(Hbtree *node)
{
Hbtree *parent,*child,*brother;
int i,j;
parent=node->parent;
if(parent==NULL)return;//根节点无需调整
if(node->value==NOT_CHAR){//非叶子节点
child=node->child[LEFT]->count > node->child[RIGHT]->count ?
node->child[LEFT] : node->child[RIGHT];
if(child->count > parent->count - node->count){
//失衡
i=!(node->index);
j=child->index;
node->count=parent->count - child->count;
brother=parent->child[i];
node->child[j]=brother;
brother->index=j;
brother->parent=node;
parent->child[i]=child;
child->index=i;
child->parent=parent;
}
}
this->BalanceNode(parent);
}
//输出一个字符的编码
int Huffman::OutputEncode(int value)
{
int stack[CODE_FINISH+2],top=0;
Hbtree *tmp=this->list[value];
//输出编码
if(value<=MAX_VALUE){//字符
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp->count++;
tmp=tmp->parent;
}
}else{//控制码
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp=tmp->parent;
}
}
top--;
while(top>0){
this->OutputBit(stack[--top]);
}
return 0;
}
void Huffman::PrintNode(Hbtree *node,int level)
{
int i;
if(node){
for(i=0;i<level*3;i++)printf(" ");
printf("%p P:%p L:%p R:%p C:%d",node,node->parent,node->child[0],node->child[1],node->count);
if(node->value!=NOT_CHAR)printf(" V:%d",node->value);
printf("\n");
this->PrintNode(node->child[LEFT],level+1);
this->PrintNode(node->child[RIGHT],level+1);
}
}
int Huffman::Encode(unsigned char *s, int len)
{
int i;
for(i=0;i<len;i++)this->Encode(s[i]);
return 0;
}
void Huffman::PrintTree()
{
this->PrintNode(this->root,0);
}
int Huffman::RecountNode(Hbtree *node)
{
if(node->value!=NOT_CHAR)return node->count;
node->count=
this->RecountNode(node->child[LEFT]) +
this->RecountNode(node->child[RIGHT]);
return node->count;
}
void Huffman::RearrangeTree()
{
int i,j,k;
Hbtree *tmp,*tmp2;
//所有非控制码的计数值右移shrink_factor位，并删除计数值为零的节点
for(k=0;k<=MAX_VALUE;k++){
if(this->list[k]!=NULL){
tmp=this->list[k];
tmp->count >>= this->shrink_factor;
if(tmp->count ==0){
this->list[k]=NULL;
tmp2=tmp->parent;
i=tmp2->index;
j=!(tmp->index);
if(tmp2->parent!=NULL){
tmp2->parent->child[i]=tmp2->child[j];
tmp2->child[j]->parent=tmp2->parent;
tmp2->child[j]->index=i;
}else{
this->root=tmp2->child[j];
this->current=this->root;
this->root->parent=NULL;
}
delete tmp;
delete tmp2;
}
}
}
//重新计数
this->RecountNode(this->root);
//重新调整平衡
for(i=0;i<=MAX_VALUE;i++){
if(this->list[i]!=NULL)
this->BalanceNode(this->list[i]->parent);
}
}
void Huffman::InsertNewNode(int value)
{
int i;
Hbtree *tmp,*tmp2;
//将字符加入哈夫曼树
tmp2=this->list[CODE_FINISH];
tmp=this->NewNode(NOT_CHAR, tmp2->index, tmp2->parent);
tmp->child[LEFT]=tmp2;
tmp2->index=LEFT;
tmp2->parent=tmp;
tmp2=this->NewNode(value,RIGHT,tmp);
tmp->count=tmp->child[LEFT]->count+tmp->child[RIGHT]->count;
i=tmp2->count;
while((tmp=tmp->parent)!=NULL)tmp->count+=i;
//从底向上调整哈夫曼树
this->BalanceNode(tmp2->parent);
}
int Huffman::Decode(unsigned char c)
{
this->Decode(c,7);
return 0;
}
int Huffman::Decode(unsigned char *s,int len)
{
int i;
for(i=0;i<len;i++)this->Decode(s[i]);
return 0;
}
int Huffman::Decode(unsigned char c, int start)
{
int value=c,
candidates[]={1,2,4,8,16,32,64,128},
i,j;
Hbtree *tmp;
if(this->finished)return 0;
i=start;
if(this->current==NULL){//转义状态下
while(this->remain >= 0 && i>=0){
if((candidates[i] & value) !=0){
this->literal |= candidates[this->remain];
}
this->remain--;
i--;
}
if(this->remain < 0){//字符输出完毕
//输出字符
this->OutputChar(this->literal);
//将字符插入哈夫曼树
this->InsertNewNode(literal);
//重组哈夫曼树
if(this->root->count>=this->max_count)
this->RearrangeTree();
//设置环境
this->current=this->root;
}
}else{
j=((value & candidates[i])!=0)?1:0;
tmp=this->current->child[j];
i--;
while(tmp->value==NOT_CHAR && i>=0){
j=((value & candidates[i])!=0)?1:0;
tmp=tmp->child[j];
i--;
}
if(tmp->value==NOT_CHAR){//中间节点
this->current=tmp;
}else{
if(tmp->value<=MAX_VALUE){//编码内容
j=tmp->value;
this->OutputChar((unsigned char)j);
//修改计数器
tmp=this->list[j];
while(tmp!=NULL){
tmp->count++;
tmp=tmp->parent;
}
//调整平衡度
this->BalanceNode(this->list[j]->parent);
//重组哈夫曼树
if(this->root->count>=this->max_count)
this->RearrangeTree();
//设置环境
this->current=this->root;
}else{
if(tmp->value==CODE_ESCAPE){//转义码
this->current=NULL;
this->remain=7;
this->literal=0;
}else{//结束码
this->finished=true;
return 0;
}
}
}
}
if(i>=0)this->Decode(c,i);
return 0;
}
int Huffman::OutputChar(unsigned char c)
{
this->buffer[this->char_top++]=c;
if(this->char_top>=BUFFER_SIZE){//输出缓冲区
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}
return 0;
}
========end of Huffman.cpp==================
========Huffman.h============================
// Huffman.h: interface for the Huffman class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(NULL)
#include <stdio.h>
#endif
#if !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)
#define AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#define MAX_COUNT 65536 //最大计数值，大于此值时
#define MAX_VALUE 255 //编码的最大值
#define CODE_ESCAPE MAX_VALUE+1 //转义码
#define CODE_FINISH MAX_VALUE+2 //结束码
#define LIST_LENGTH MAX_VALUE+3 //编码列表长度
#define SHRINK_FACTOR 2 //减小的比例，通过右移位实现
#define LEFT 0 //左孩子索引
#define RIGHT 1 //右孩子索引
#define NOT_CHAR -1 //非字符
#define TOP_BIT 7 //字符最高位
#define BOTTOM_BIT 0 //字符最低位
#define BUFFER_SIZE 81920 //缓冲区大小
//输出函数
typedef bool (Output)(unsigned char *s,int len);
//哈夫曼树的节点定义
typedef struct Hnode{
int count;//计数器
int index;//父节点的孩子索引（0--左孩子，1--右孩子）
Hnode* child[2];
Hnode* parent;
int value;
}Hbtree;
class Huffman
{
private:
//输出一个解码的字符
int OutputChar(unsigned char c);
//从指定位置开始解码
int Decode(unsigned char c,int start);
//插入一个新节点
void InsertNewNode(int value);
//重新调整哈夫曼树构型
void RearrangeTree();
//对各节点重新计数
int RecountNode(Hbtree *node);
//打印哈夫曼树节点
void PrintNode(Hbtree *node,int level);
//输出一个值的编码
int OutputEncode(int value);
//调节哈夫曼树节点使之平衡
void BalanceNode(Hbtree *node);
//输出一位编码
int OutputBit(int bit);
//释放哈夫曼树节点
void ReleaseNode(Hbtree *node);
//新建一个节点
Hbtree *NewNode(int value,int index, Hbtree *parent);
//输出函数地址
Output *output;
//哈夫曼树根地址
Hbtree *root;
//哈夫曼编码单元列表
Hbtree *list[LIST_LENGTH];
//输出缓冲区
unsigned char buffer[BUFFER_SIZE];
//缓冲区顶
int char_top,bit_top;
//收缩哈夫曼树参数
int max_count,shrink_factor;
//工作模式，true--编码，false--解码
bool mode;
//解码的当前节点
Hbtree *current;
int remain;//当前字符剩余的位数
unsigned char literal;//按位输出的字符
bool finished;
public:
//解码指定长度的字符串
int Decode(unsigned char *s,int len);
//解码一个字符
int Decode(unsigned char c);
//打印哈夫曼树
void PrintTree();
//编码指定长度的字符串
int Encode(unsigned char *s,int len);
//编码一个字符
int Encode(unsigned char c);
//清空缓冲区
int Flush();
//output指输出函数，mode指工作模式，true--编码，false--解码
Huffman(Output *output,bool mode);
//析构函数
virtual ~Huffman();
};
#endif // !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)
================end of Huffman.h==================
祝你好运！
Ⅳ 简述一下hdfs的数据压缩算法，工作中用的是哪种算法，为什么
1、在HDFS之上将数据压缩好后，再存储到HDFS
2、在HDFS内部支持数据压缩，这里又可以分为几种方法：
2.1、压缩工作在DataNode上完成，这里又分两种方法：
2.1.1、数据接收完后，再压缩
这个方法对HDFS的改动最小，但效果最低，只需要在block文件close后，调用压缩工具，将block文件压缩一下，然后再打开block文件时解压一下即可，几行代码就可以搞定
2.1.2、边接收数据边压缩，使用第三方提供的压缩库
效率和复杂度折中方法，Hook住系统的write和read操作，在数据写入磁盘之前，先压缩一下，但write和read对外的接口行为不变，比如：原始大小为100KB的数据，压缩后大小为10KB，当写入100KB后，仍对调用者返回100KB，而不是10KB
2.2、压缩工作交给DFSClient做，DataNode只接收和存储
这个方法效果最高，压缩分散地推给了HDFS客户端，但DataNode需要知道什么时候一个block块接收完成了。
推荐最终实现采用2.2这个方法，该方法需要修改的HDFS代码量也不大，但效果最高。
Ⅳ 如何用C语言实现数据压缩
首先选择一个压缩算法
然后按照算法实现压缩代码，调用接口就可以
常见的 可以使用哈夫曼编码压缩，或者使用开源的压缩代码，比如lzo, gzip, lzma等等。
Ⅵ 压缩算法原理
哈夫曼
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。
哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。
2.1 原理
我不打算探究哈夫曼编码的所有实际的细节，但基本的原理是为每个符号找到新的二进制表示，从而通常符号使用很少的位，不常见的符号使用较多的位。
简短的说，这个问题的解决方案是为了查找每个符号的通用程度，我们建立一个未压缩数据的柱状图；通过递归拆分这个柱状图为两部分来创建一个二叉树，每个递归的一半应该和另一半具有同样的权（权是 ∑ N K =1 符号数 k , N 是分之中符号的数量，符号数 k 是符号 k出现的次数 ）
这棵树有两个目的：
1． 编码器使用这棵树来找到每个符号最优的表示方法
2． 解码器使用这棵树唯一的标识在压缩流中每个编码的开始和结束，其通过在读压缩数据位的时候自顶向底的遍历树，选择基于数据流中的每个独立位的分支，一旦一个到达叶子节点，解码器知道一个完整的编码已经读出来了。
压缩后的数据流是 24 位（三个字节），原来是 80 位（ 10 个字节）。当然，我应该存储哈夫曼树，这样解码器就能够解码出对应的压缩流了，这就使得该例子中的真正数据流比输入的流数据量大。这是相对较短的数据上的副作用。对于大数据量来说，上面的哈夫曼树就不占太多比例了。
解码的时候，从上到下遍历树，为压缩的流选择从左 / 右分支，每次碰到一个叶子节点的时候，就可以将对应的字节写到解压输出流中，然后再从根开始遍历。
2.2 实现
哈夫曼编码器可以在基本压缩库中找到，其是非常直接的实现。
这个实现的基本缺陷是：
1． 慢位流实现
2． 相当慢的解码（比编码慢）
3． 最大的树深度是 32 （编码器在任何超过 32 位大小的时候退出）。如果我不是搞错的话，这是不可能的，除非输出的数据大于 2 32字节。
另一方面，这个实现有几个优点：
1． 哈夫曼树以一个紧密的形式每个符号要求 12 位（对于 8 位的符号）的方式存储，这意味着最大的头为 384 。
2． 编码相当容易理解
哈夫曼编码在数据有噪音的情况（不是有规律的，例如 RLE ）下非常好，这中情况下大多数基于字典方式的编码器都有问题。
Ⅶ 多媒体数据压缩的两种基本方法是什么
从信息论的角度看,压缩就是去掉信息中的冗余,即保留不确定的信息,去除确定的信 息.多媒体技术中常用的数据压缩算法分为两大类:无损压缩和有损压缩.冗余压缩法去掉 或减少数据中的冗余,但这些冗余量是可以重新插人到数据中的,因而不会产生失真.其压 缩效率通常较低; 有损压缩则采用一些高效的有限失真数据压缩算法, 大幅度减少多媒体中 的冗余信息,其压缩效率远高于无损压缩.无损压缩.这类方法广泛用于文本数据,程序和 特殊应用场合的图像数据(如指纹图像,医学图像等)的压缩.有损压缩广泛应用于语音,图 像和视频数据的压缩.常见的编码方法可以
Ⅷ 求C++简单文件压缩程序，用基本算法实现
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
void main()
{
ifstream infile("c:\\1.txt");//自己改文件名
ofstream outfile("c:\\2.txt");
char cCurrent,cPre;
int iCount=0;
cPre=-1;
while(infile>>cCurrent)
{
if(cCurrent=='\n') continue;
if(cPre==-1) cPre=cCurrent;
if(cPre==cCurrent)
{
iCount++;
}
else
{
if(cPre>='0'&&cPre<='9')
outfile<<iCount<<'*'<<cPre<<' ';
else
outfile<<iCount<<cPre<<' ';
cPre=cCurrent;
iCount=1;
}
}
if(cPre>='0'&&cPre<='9')
outfile<<iCount<<'*'<<cPre<<' ';
else
outfile<<iCount<<cPre<<' ';
infile.close();
outfile.close();
}
Ⅸ 数据压缩
数据压缩技术主要研究数据的表示、传输和转换方法，目的是减少数据所占据的存储空间和缩短数据传输时所需要的时间。
衡量数据压缩的3个主要指标：一是压缩前后所需的信息存储量之比要大；二是实现压缩的算法要简单，压缩、解压缩速度快，要尽可能做到实时压缩和解压缩；三是恢复效果要好，要尽可能完全恢复原始数据。
数据压缩主要应用于两个方面。一是传输：通过压缩发送端的原始数据，并在接收端进行解压恢复，可以有效地减少传输时间和增加信道带宽。二是存储：在存储时压缩原始数据，在使用时进行解压，可大大提高存储介质的存储量。
数据压缩按照压缩的失真度分成两种类型：一种叫作无损压缩，另一种叫作有损压缩。
无损压缩是指使用压缩后的数据进行重构（或者叫作还原、解压缩），重构后的数据与原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/4～1/2。一些常用的无损压缩算法有霍夫曼（Huffman）算法、算术算法、游程算法和LZW（Lenpel-Ziv ＆ Welch）压缩算法。
1）霍夫曼算法属于统计式压缩方法，其原理是根据原始数据符号发生的概率进行编码。在原始数据中出现概率越高的符合，相应的码长越短，出现概率越少的符合，其码长越长。从而达到用尽可能少的符号来表示原始数据，实现对数据的压缩。
2）算术算法是基于统计原理，无损压缩效率最高的算法。即将整段要压缩的数据映射到一段实数半封闭的范围［0，1）内的某一区段。该区段的范围或宽度等于该段信息概率。即是所有使用在该信息内的符号出现概率全部相乘后的概率值。当要被编码的信息越来越长时，用来代表该信息的区段就会越来越窄，用来表示这个区段的位就会增加。
3）游程算法是针对一些文本数据特点所设计的压缩方法。主要是去除文本中的冗余字符或字节中的冗余位，从而达到减少数据文件所占的存储空间。压缩处理流程类似于空白压缩，区别是在压缩指示字符之后加上一个字符，用于表明压缩对象，随后是该字符的重复次数。本算法具有局限性，很少单独使用，多与其他算法配合使用。
4）LZW算法的原理是用字典词条的编码代替在压缩数据中的字符串。因此字典中的词条越多，压缩率越高，加大字典的容量可以提高压缩率。字典的容量受计算机的内存限制。
有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。
Ⅹ 如何写压缩软件，运用哈夫曼算法实现
到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式。然而，还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构，以前还不知道他又什么用，其实他最大的用途就是用来做压缩，也是一些rar,zip压缩的祖先，称为哈弗曼压缩（什么你不知道谁是哈弗曼，也不知道哈弗曼压缩，不急等下介绍）。
随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。
特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。
一、什么是哈弗曼压缩
Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。
二、怎么实现哈弗曼压缩
哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
故我们得了解几个概念：
1、二叉树：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。2、哈夫曼编码(Huffman Coding)：是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。三、哈夫曼编码生成步骤：
①扫描要压缩的文件，对字符出现的频率进行计算。
②把字符按出现的频率进行排序，组成一个队列。
③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。
④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。
⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。
⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。
既如 (a)、(b)、(c)、(d)几个图，就可以将离散型的数据转化为树型的了。
如果假设树的左边用0表示右边用1表示，则每一个数可以用一个01串表示出来。
则可以得到对应的编码如下：
1-->110
2-->111
3-->10
4-->0
每一个01串，既为每一个数字的哈弗曼编码。
为什么能压缩：
压缩的时候当我们遇到了文本中的1、2、3、4几个字符的时候，我们不用原来的存储，而是转化为用它们的01串来存储不久是能减小了空间占用了吗。（什么01串不是比原来的字符还多了吗？怎么减少？）大家应该知道的，计算机中我们存储一个int型数据的时候一般式占用了2^32-1个01位，因为计算机中所有的数据都是最后转化为二进制位去存储的。所以，想想我们的编码不就是只含有0和1嘛，因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。
比如：
1这个数字，用整数写进计算机硬盘去存储，占用了2^32-1个二进制位
而如果用它的哈弗曼编码去存储，只有110三个二进制位。
效果显而易见。