五种数据压缩算法.doc

n 哈弗曼编码Amethodfortheconstructionofminimum-re-dundancycodes,耿国华1数据结构1北京:高等教育出版社,2005:182190严蔚敏,吴伟民.数据结构(C语言版)M.北京:清华大学出版社,1997.冯桂,林其伟,陈东华.信息论与编码技术M.北京:清华大学出版社,2007.刘大有,唐海鹰,孙舒杨,等.数据结构M.北京:高等教育出版社,2001 压缩实现速度要求为了让它(huffman.cpp)快速运行，同时不使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。压缩过程压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：CHuffmanNode nodes511;for(int nCount = 0; nCount 256; nCount+)nodesnCount.byAscii = nCount;其次，计算在输入缓冲区数据中，每个ASCII码出现的频率：for(nCount = 0; nCount pLeft = PopNode(pNodes, nBackNode-, false);/ pop second childpNode-pRight = PopNode(pNodes, nBackNode-, true);/ adjust parent of the two poped nodespNode-pLeft-pParent = pNode-pRight-pParent = pNode;/ adjust parent frequencypNode-nFrequency=pNode-pLeft-nFrequency + pNode-pRight-nFrequency注意事项有一个好的诀窍来避免使用任何队列组件。ASCII码只有256个，但实际分配了511个(CHuffmanNode nodes511)，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes256)来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount 1)。接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：int nDesIndex = 0;/ loop to write codesfor(nCount = 0; nCount 3) |=nodespSrcnCount.dwCode 3): 3 以8位为界限右移后到达右边字节的前面(nDesIndex&7): &7 得到最高位.此外，在压缩缓冲区中，必须保存哈夫曼树的节点以及位序列，这样才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。解压缩解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中：int nDesIndex = 0;DWORD nCode;while(nDesIndex 3)(nSrcIndex&7);pNode = pRoot;while(pNode-pLeft)pNode = (nCode&1) ? pNode-pRight : pNode-pLeft;nCode = 1;nSrcIndex+;pDesnDesIndex+ = pNode-byAscii; 程序实现费诺编码#include #include #include #include #define M 100typedef struct Fano_Nodechar ch;float weight;FanoNodeM;typedef struct nodeint start;int end;struct node *next;LinkQueueNode;typedef structLinkQueueNode *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;elseprintf(Error!);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+=fi.weight;/*m=s;sum1=0;for(i=s;ifabs(sum-2*sum1-2*fi+1.weight)?(i+1):*m;if(*m=i) break;void main()int i,j,n,max,m,hM;int sta,end;float w;char c,fcMM;FanoNode FN;LinkQueueNode *p;LinkQueue *Q;/初始化队QQ=(LinkQueue *)malloc(sizeof(LinkQueue);Q-front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);Q-rear=Q-front;Q-front-next=NULL;printf(t*FanoCoding*n);printf(Please input the number of node:);/输入信息scanf(%d,&n);/超过定义M,退出if(n=M)printf(=%d,M);exit(-1);i=1; /从第二个元素开始录入while(i=n)printf(%d weight and node:,i);scanf(%f %c,&FNi.weight,&FNi.ch);for(j=1;ji;j+)if(FNi.ch=FNj.ch)/查找重复printf(Same node!n); break;if(i=j)i+;/排序(降序)for(i=1;i=n;i+)max=i+1;for(j=max;j=n;j+)max=FNmax.weightFNj.weight?j:max;if(FNi.weightFNmax.weight)w=FNi.weight;FNi.weight=FNmax.weight;FNmax.weight=w;c=FNi.ch;FNi.ch=FNmax.ch;FNmax.ch=c;for(i=1;ifront-next!=NULL)p=Q-front-next; /出队Q-front-next=p-next;if(p=Q-rear)Q-rear=Q-front;sta=p-start;end=p-end;free(p);Divide(FN,sta,&m,end); /*按权分组*/for(i=sta;i=m;i+)fcihi=0;+hi;if(sta!=m)EnterQueue(Q,sta,m);elsefcstahsta=0;for(i=m+1;i=end;i+)fcihi=1;+hi;if(m=sta&(m+1)=end)/如果分组后首元素的下标与中间元素的相等，/并且和最后元素的下标相差为1，则编码码字字符串结束fcmhm=0;fcendhend=0;elseEnterQueue(Q,m+1,end);for(i=1;i=n;i+) /*打印编码信息*/printf(%c:,FNi.ch);printf(%sn,fci);system(pause);4编码解码#include #include #include #define N 100#define M 2*N-1typedef char * HuffmanCode2*M;/haffman编码typedef structint weight;/权值int parent;/父节节点int LChild;/左子节点int RChild;/右子节点HTNode,HuffmanM+1;/huffman树typedef struct Nodeint weight; /叶子结点的权值char c; /叶子结点int num; /叶子结点的二进制码的长度WNode,WeightNodeN;/*产生叶子结点的字符和权值*/void CreateWeight(char ch,int *s,WeightNode CW,int *p)int i,j,k;int tag;*p=0;/叶子节点个数/统计字符出现个数,放入CWfor(i=0;chi!=0;i+)tag=1;for(j=0;ji;j+)if(chj=chi)tag=0;break;if(tag)CW+*p.c=chi;CW*p.weight=1;for(k=i+1;chk!=0;k+)if(chi=chk)CW*p.weight+;/权值累加*s=i;/字符串长度/*创建HuffmanTree*/void CreateHuffmanTree(Huffman ht,WeightNode w,int n)int i,j;int s1,s2;/初始化哈夫曼树for(i=1;i=n;i+)hti.weight =wi.weight;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)hti.weight=0;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)for(j=1;j=i-1;j+)if(!htj.parent)break;s1=j; /找到第一个双亲为零的结点for(;jhtj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;j=i-1;j+)if(!htj.parent)break;s2=j; /找到第二个双亲为零的结点for(;jhtj.weight?j:s2;hts2.parent=i;hti.RChild=s2;hti.weight=hts1.weight+hts2.weight;/权值累加/*叶子结点的编码*/void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int m,int n)int i,c,p,start;char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1=0;/末尾置0for(i=1;i=n;i+)start=n-1; /cd串每次从末尾开始c=i;p=hti.parent;/p在n+1至2n-1while(p) /沿父亲方向遍历,直到为0start-;/依次向前置值if(htp.LChild=c)/与左子相同,置0cdstart=0;else /否则置1cdstart=1;c=p;p=htp.parent;weighti.num=n-start; /二进制码的长度(包含末尾0)hi=(char *)malloc(n-start)*sizeof(char);strcpy(hi,&cdstart);/将二进制字符串拷贝到指针数组h中free(cd);/释放cd内存system(pause);/*所有字符的编码*/void CrtHuffmanCode(char ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)int i,k;for(i=0;im;i+)for(k=1;k=n;k+) /*从weightk.c中查找与chi相等的下标K*/if(chi=weightk.c)break;hci=(char *)malloc(weightk.num)*sizeof(char);strcpy(hci,hk); /拷贝二进制编码/*解码*/void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)int i=0,j,p;printf(*StringInformation*n);while(im)p=2*n-1;/从父亲节点向下遍历直到叶子节点for(j=0;hcij!=0;j+)if(hcij=0)p=htp.LChild;elsep=htp.RChild;printf(%c,wp.c); /*打印原信息*/i+;/*释放huffman编码内存*/void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)int i;for(i=1;i=n;i+)/释放叶子结点的编码free(hi);for(i=0;im;i+) /释放所有结点的编码free(hci);void main()int i,n=0; /*n为叶子结点的个数*/int m=0; /*m为字符串ch的长度*/char chN; /*chN存放输入的字符串*/Huffman ht; /*Huffman二叉数*/HuffmanCode h,hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/WeightNode weight; /*存放叶子结点的信息*/printf(t*HuffmanCoding*n);printf(please input information :);gets(ch); /*输入字符串*/CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch的长度*/printf(*WeightInformation*n Node );for(i=1;i=n;i+) /*输出叶子结点的字符与权值*/printf(%c ,weighti.c);printf(nWeight );for(i=1;i=n;i+)printf(%d ,weighti.weight);CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/printf(n*HuffamnTreeInformation*n);printf(titweighttparenttLChildtRChildn);for(i=1;i=2*n-1;i+) /*打印Huffman树的信息*/printf(t%dt%dt%dt%dt%dn,i,hti.weight,hti.parent,hti.LChild,hti.RChild);CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/printf( *NodeCode*n); /*打印叶子结点的编码*/for(i=1;i=n;i+)printf(t%c:,weighti.c);printf(%sn,hi);CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/printf(*StringCode*n); /*打印字符串的编码*/for(i=0;im;i+)printf(%s,hci);system(pause);TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/FreeHuffmanCode(h,hc,n,m);system(pause);5Matlab实现Matlab 中简易实现Huffman编译码：n=input(Please input the total number: );hf=zeros(2*n-1,5);hq=;for ki=1:nhf(ki,1)=ki;hf(ki,2)=input(Please input the frequency: );hq=hq,hf(ki,2);endfor ki=n+1:2*n-1hf(ki,1)=ki;mhq1=min(hq);m=size(hq);m=m(:,2);k=1;while k=m%del min1if hq(:,k)=mhq1hq=hq(:,1:(k-1) hq(:,(k+1):m);m=m-1;breakelsek=k+1;endendk=1;while hf(k,2)=mhq1|hf(k,5)=1%find min1 locationk=k+1;endhf(k,5)=1;k1=k;mhq2=min(hq);k=1;while k=ndisplay(Error! You did not input this number.);breakendendif k=nbreakendr=;while hf(k,5)=1kc=n+1;while hf(kc,3)=k&hf(kc,4)=kkc=kc+1;endif hf(kc,3)=kr=0 r;elser=1 r;endk=kc;endrelsea=input(Please input the metrix you want to Decoding: );sa=size(a);sa=sa(:,2);k=2*n-1;while sa=0if a(:,1)=0k=hf(k,3);elsek=hf(k,4);enda=a(:,2:sa);sa=sa-1;if k=0display(Error! The metrix you entered is a wrong one.);breakendendif k=0breakendr=hf(k,2);endchoose=input(Choose what you want:n1: Encodingn2: Decodingn3:.Exitn);clc;endif choose=1&choose=2clc;endn 变换 LZ77压缩算法原理1977年，Jacob Ziv和Abraham Lempel描述了一种基于滑动窗口缓存的技术，该缓存用于保存最近刚刚处理的文本（J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression”, IEEE Transaction on Information Theory, May 1977）。这个算法一般称为IZ77。 LZ77和它的变体发现，在正文流中词汇和短语(GIF中的图像模式)很可能会出现重复。当出现一个重复时，重复的序列可以用一个短的编码来代替。压缩程序扫描这样的重复，同时生成编码来代替重复序列。随着时间的过去，编码可以重用来捕获新的序列。算法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。 在研究LZ77的细节之前，先看一个简单的例子（J. Weiss and D. Schremp, “Putting Data on a Diet”, IEEE Spectrum, August 1993）。考虑这样一句话： the brown fox jumped over the brown foxy jumping frog 这个短语的长度总共是53个八位组 = 424 bit。算法从左向右处理这个文本。初始时，每个字符被映射成9 bit的编码，二进制的1跟着该字符的8 bit ASCII码。在处理进行时，算法查找重复的序列。当碰到一个重复时，算法继续扫描直到该重复序列终止。换句话说，每次出现一个重复时，算法包括尽可能多的字符。碰到的第一个这样的序列是the brown fox。这个序列被替换成指向前一个序列的指针和序列的长度。在这种情况下，前一个序列的the brown fox出现在26个字符之前，序列的长度是13个字符。对于这个例子，假定存在两种编码选项：8 bit的指针和4 bit的长度，或者12 bit的指针和6 bit的长度。使用2 bit的首部来指示选择了哪种选项，00表示第一种选项，01表示第二种选项。因此，the brown fox的第二次出现被编码为 ，或者00 00011010 1101。 压缩报文的剩余部分是字母y；序列替换了由一个空格跟着jump组成的序列，以及字符序列ing frog。 图03-05-3演示了压缩映射的过程。压缩过的报文由35个9 bit字符和两个编码组成，总长度为35 x 9 + 2 x 14 = 343比特。和原来未压缩的长度为424比特的报文相比，压缩比为1.24。 图03-05-3 LZ77模式例 （一）压缩算法说明 LZ77（及其变体）的压缩算法使用了两个缓存。滑动历史缓存包含了前面处理过的N个源字符，前向缓存包含了将要处理的下面L个字符(图03-05-4(a)。算法尝试将前向缓存开始的两个或多个字符与滑动历史缓存中的字符串相匹配。如果没有发现匹配，前向缓存的第一个字符作为9 bit的字符输出并且移入滑动窗口，滑动窗口中最久的字符被移出。如果找到匹配，算法继续扫描以找出最长的匹配。然后匹配字符串作为三元组输出（指示标记、指针和长度）。对于K个字符的字符串，滑动窗口中最久的K个字符被移出，并且被编码的K个字符被移入窗口。 图03-05-4(b)显示了这种模式对于我们的例子的运行情况。这里假定了39个字符的滑动窗口和13个字符的前向缓存。在这个例子的上半部分，已经处理了前面的40个字符，滑动窗口中是未压缩的最近的39个字符。剩下的源字符串在前向窗口中。压缩算法确定了下一个匹配，从前向窗口将5个字符移入到滑动窗口中，并且输出了这个匹配字符串的编码。经过这些操作的缓存的状态显示在这个例子的下半部分。 (a)通用结构(b)例子 图03-05-4 LZ77模式 尽管LZ77是有效的，对于当前的输入情况也是合适的，但是存在一些不足。算法使用了有限的窗口在以前的文本中查找匹配，对于相对于窗口大小来说非常长的文本块，很多可能的匹配就会被丢掉。窗口大小可以增加，但这会带来两个损失：(1)算法的处理时间会增加，因为它必须为滑动窗口的每个位置进行一次与前向缓存的字符串匹配的工作；(2)字段必须更长，以允许更长的跳转。 （二）压缩算法描述 为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语： 输入数据流(input stream)：待压缩处理的字符序列。字符(character)：输入数据流中的基本单元。 编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲器中的开始字符。 前向缓冲器(lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 窗口(Window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。 指针(Pointer)：指向窗口中的匹配串且含长度的指针。 LZ77编码算法的核心是查找从前向缓冲器开始的最长的匹配串。算法的具体执行步骤如下： 把编码位置设置到输入数据流的开始位置。 查找窗口中最长的匹配串。 输出(Pointer， Length) Characters，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲器中的第1个不匹配的字符。 如果前向缓冲器不是空的，则把编码位置和窗口向前移Length+1个字符，然后返回到步骤2。 例：待编码的数据流如表03-05-1所示，编码过程如表03-05-2所示。现作如下说明： “步骤”栏表示编码步骤。 “位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。 “匹配”栏表示窗口中找到的最长的匹配串。 “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。 “输出”栏以(Back_chars， Chars_length) Explicit_character格式输出。其中(Back_chars， Chars_length)是指指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。例如，表3-13中的输出“(5，2) C”告诉译码器回退5个字符，然后拷贝2个字符“AB” 表03-05-1 待编码的数据流 位置1 2 3 4 5 6 7 8 9 字符 A A B C BBABC表03-05-2 编码过程 步骤位置 匹配串字符输出1 1 - A (0，0) A 2 2 A B (1，1) B 34 - C (0，0) C 45 B B (2，1) B 57 A B C (5，2) C （三）解压算法 对于LZ77压缩文本的解压很简单。解压算法必须保存解压输出的最后N个字符。当碰到编码字符串时，解压算法使用，和，字段将编码替换成实际的正文字符串。实现#include #include #include #include #define OFFSET_CODING_LENGTH (10)#define MAX_WND_SIZE 1024/#define MAX_WND_SIZE (13 ; ulOffsetInByte = ulBitOffset&7; *(pBuffer+ulByteBoundary) |= (13 ; ulOffsetInByte = ulBitOffset&7; *(pBuffer+ulByteBoundary) &= (13 ; ulOffsetInByte = ulBitOffset&7; return (*(PULONG)(pBuffer+ulByteBoundary)ulOffsetInByte)&1 ;ULONG WINAPIWriteGolombCode( ULONG x, PUCHAR pBuffer, ULONG ulBitOffset ) ULONG q, r; int i; q = (x-1)m; r = x-(qm)-1; for(i=0; (ULONG)iq; i+, ulBitOffset+) Write1ToBitStream(pBuffer, ulBitOffset); Write0ToBitStream(pBuffer, ulBitOffset); ulBitOffset+; for(i=0; ii)&1 ) Write1ToBitStream(pBuffer, ulBitOffset); else Write0ToBitStream(pBuffer, ulBitOffset); return m+q+1;ULONGReadGolombCode( PULONG pulCodingLength, PUCHAR pBuffer, ULONG ulBitOffset ) ULONG q, r; ULONG bit; int i; for(q=0; ;q+) bit = (ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset); ulBitOffset+; if( !bit ) break; for(i=0, r=0; (ULONG)im; i+, ulBitOffset+) bit = (ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset); bit = i; r |= bit; *pulCodingLength = m + q + 1; return r+(qm)+1;ULONGCompareStrings( PUCHAR string1, PUCHAR string2, ULONG length ) ULONG i; PUCHAR p1, p2; p1 = string1; p2 = string2; for(i=0; i0 ) length = CompareStrings(pSrc, pString, ulMaxLength); if( length*pulSubstringLength ) *pulSubstringLength = length; *pulSubstringOffset = offset; pSrc+; offset+; ulMaxLength-; /*voidFindLongestSubstring( PUCHAR pSourceString, PUCHAR pString, ULONG ulSourceStringLength, PULONG pulSubstringOffset, PULONG pulSubstringLength ) PUCHAR pCurrentOffset; PUCHAR p1, p2; ULONG offset, length; pCurrentOffset = pSourceString; *pulSubstringOffset = offset = 0; *