发布时间 : 星期六 文章调研数据压缩原理与相关的算法实现更新完毕开始阅读
调研数据压缩原理及算法实现
压缩，是为了减少存储空间而把数据转换成比原始格式更紧凑形式的过程。以下我们将介绍几种压缩算法。
1哈夫曼编码
数据结构（C语言版）严蔚敏 吴伟民著；
数据结构（用面向对象方法与C++描述） 殷人昆 等；
原理：哈夫曼编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率.
算法：向量HT的前N个分量表示叶子节点，最后一个分量表示根节点。各字符的编码长度不等，所以按实际长度动态分配空间。下面的算法求每个字符的哈夫曼编码是从叶子到根的逆向处理的。//无栈非递归遍历哈夫曼树，求哈夫曼编码// HC=（HuffmancCode）malloc（（n+1）*sizeof（char *））； P=m；cdlen=0；
For(i=1;i<=m;++i) HT[i],weight=0;//遍历哈夫曼树时用作节点的字符的编码 While(p){
if(HT[p].weight==0){ //向左 HT[p].weight=1; If(HT[p].lchild!=0)
{p=HT[p].lchild};cd[cdlen++]=”0”;}
Else if(HT[p].rchild==0){ //登记叶子节点的字符的编码 HC[p]=(char*)malloc((cdlen+1)*sizeof(char)); Cd[cdlen]=”\\0”;strcpy(HC[p],cd); //复制编码 }}
else if(HT[p].weight==1){ //向右 HT[p].weight=2;
If(HT[p].weight!=0){p=HT[p].rchild;cd[cdlen++]=”1”;} }else { //HT[p].weight==2，退回
HT[p].weight=0;p=HT[p].parent;--clden;//退到父结点，编码长度减一 }//else }//while
压缩过程
压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount;
其次，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes);
构造哈夫曼树
将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩下一个节点（树根）。 // parent node
pNode = &nodes[nParentNode++]; // pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false); // pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true); // adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode; // adjust parent frequency pNode->nFrequency=pNode->pLeft->nFrequency + pNode->pRight->nFrequency
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中: int nDesIndex = 0; // loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++) {
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7); nDesIndex += nodes[pSrc[nCount]].nCodeLength; }
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面(nDesIndex&7): &7 得到最高位.
解压缩：将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区
是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中： int nDesIndex = 0; DWORD nCode; while(nDesIndex < nDesLen) {
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7); pNode = pRoot; while(pNode->pLeft) { pNode = (nCode&1) ? pNode->pRight : pNode->pLeft; nCode >>= 1; nSrcIndex++; } pDes[nDesIndex++] = pNode->byAscii; }
结构：费诺编码 #include
typedef struct Fano_Node {
char ch; float weight;} FanoNode[M]; typedef struct node {int start; int end;
struct node *next;} LinkQueueNode; typedef struct{ LinkQueueNode *front; LinkQueueNode *rear; } LinkQueue;//建立队列
void EnterQueue(LinkQueue *q,int s,int e) {
LinkQueueNode *NewNode;//生成新节点
NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) {
NewNode->start=s; NewNode->end=e; NewNode->next=NULL; q->rear->next=NewNode;
}
q->rear=NewNode;
else { }
printf(\exit(-1);
}//按权分组
void Divide(FanoNode f,int s,int *m,int e) { int i;
float sum,sum1; sum=0; for(i=s;i<=e;i++)
sum+=f[i],weight;//
*m=s; sum1=0; for(i=s;i sum1+=f[i],weight;