五种大数据压缩算法

1、实用标准文档哈弗曼编码A method for the construction of minimum-re-dundancy codes, 耿国华1数据结构1北京:高等教育出版社,2005:182190 严蔚敏，吴伟民.数据结构（C语言版）M.北京:清华大学出版社,1997. 冯桂，林其伟,陈东华.信息论与编码技术M.北京:清华大学出版社,2007. 刘大有，唐海鹰,孙舒杨，等.数据结构M.北京:高等教育出版社,2001令压缩实现速度要求为了让它（huffman.cpp）快速运行，同时不使用任何动态库，比如STL或者MFC。它压 缩1M数据少于100ms （P3处理器，主频1G）。压缩过程压

2、缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：CHuffmanNode nodes511;for(int nCount = 0; nCount 256; nCount+)nodesfnCount.byAscii = nCount;其次，计算在输入缓冲区数据中，每个ASCII码出现的频率：for(nCount = 0; nCount pLeft = PopNode(pNodes, nBackNode-, false);/ pop second childpNode-pRight = PopNode(pNodes, nBackNode-, true);/ adjust parent

3、of the two poped nodespNode-pLeft-pParent = pNode-pRight-pParent = pNode;/ adjust parent frequencypNodenFrequency=pNodepLeft-nFrequency+pNode-pRight-nFrequency注意事项有一个好的诀窍来避免使用任何队列组件c ASCII码只有256个，但实际分配了 511个 (CHuffmanNode nodes511),前255个记录ASCII码，而用后255个记录哈夫曼树中的 父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *p

4、Nodes256)来指向这 些节点。同样使用两个变量来操作队列索引(int nParentNode=nblodeCount;nBackNode二 nNodeCount-1)a接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：int nDesIndex = 0;/ loop to write codesfor(nCount = 0; nCount nSrcLen; nCount+)(*(DWORD*)(pDesPtr+(nDeslndex3) |=nodespSrcnCount.dwCode (nDeslndex&7);nDesIndex += nodespSrcnCount.nCod

5、eLength;)(nDeslndex3): 3以8位为界限右移后到达右边字节的前面 文案大全实用标准文档(nDeslndex&7): a7 得到最高位.此外，在压缩缓冲区中，必须保存哈夫曼树的节点以及位序列，这样才能在解压缩时重 新构造哈夫曼树(只需保存ASCII值和对应的位序列)。解压缩解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用劝应的ASCII码逐 个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因 此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后 将它的ASCII值添加到输出缓冲区中：int nDesI

6、ndex = 0;DWORD nCode;while(nDeslndex pLeft)(pNode = (nCode&1) ? pNode-pRight: pNode-pLeft;nCode = 1;nSrclndex+;)pDesnDeslndex+ = pNode-byAscii;)令程序实现费诺编码include include include 文案大全实用标准文档include #define M 100typedef struct Fano_Node(char ch;float weight;FanoNodeM;typedef struct node(int start;int en

7、d;struct node *next;JLinkQueueNode;typedef struct(LinkQueueNode *front;LinkQueueNode *rear;JLinkQueue;建立队列void EnterQueue(LinkQueue *qjnt sjnt e)(LinkQueueNode *NewNode;生成新节点NewNode=(LinkQueueNode*)malloc(sizeof( LinkQueueNode);if(NewNode!=NULL)(NewNode-start=s;文案大全实用标准文档NewNode-end=e;NewNode-next=N

8、ULL;q-rear-next=NewNode;q-rear=NewNode;)else(printf(Error!);exit(-1);)按权分组void Divide(FanoNode f,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 ij,n,maxfm,hM;int sta

9、,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(HPlease input the number of node:1);输入信息scanf(%d,&n);超过定义M,退出if(n=M)(pri

10、ntf(=%d,M);exit(-1);)i=1;从第二个元素开始录入while(i=n)文案大全实用标准文档printf(,f%d weight and node:“)；scanf(%f %c,&FNi.weight,&FNi.ch);forO=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.weigh

11、t)(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=Qfront-next; 出队Q-front-next=p-next;if(p=Q-rear)Q-rear=Q-front;sta=p-start;end=p-end;free(p);DMde(FN,sta,&m,end); /*按权分组*/for(i=sta;i=m;i+)(fcihi=*O;+hi;)if(sta!=m)EnterQ

12、ueue(Q,sta,m);elsefcstahsta=O;for(i=m+1;i=end;i+)(fcihi=1;文案大全实用标准文档+hi;)if(m=sta&(m+1 )=end)如果分组后首元素的下标与中间元素的相等，并且和最后元素的下标相差为1,则编码码字字符串结束(fcmhm=O;fcendhend=O;)elseEnterQueue(Q,m+1 ,end);)for(i=1;iv=n;i+)/* 打印编码信息*/(printf(%c:,FNi.ch);printf(%sn,fci);)systemCpause1);编码解码include include include #defi

13、ne N 100#define M 2*N-1typedef char * HuffmanCode2*M;/haffman 编码文案大全实用标准文档typedef struct(int weight;/权值int parent;父节节点int LChild;左子节点int RChild;右子节点HTNode,HuffmanM+1;/huffman 树typedef struct Node(int weight; /叶子结点的权值char c; 叶子结点int num; /叶子结点的二进制码的长度WNode,WeightNodeN;/*产生叶子结点的字符和权值*”/void CreateWeig

14、ht(char ch,int *s,WeightNode CW,int *p)(intint tag;*p=0;叶子节点个数统计字符出现个数，放入CWfor(i=0;chi!=0;i+)(tag=1;forg=0;ji;j+)if(chj=chi)(tag=O;文案大全实用标准文档break;)if(tag)(CW+*p.c=chi;CW*p.weight=1;for(k=i+1;chk!=0;k+)if(chi=chk)CWp.weight+;/权值累加)*s=i; 字符串长度)/*创建 HuffmanTree*/void CreateHuffmanTree(Huffman ht.Weigh

15、tNode w,int n)(int i,j;ints1,s2;初始化哈夫曼树for(i=1;i=n;i+)(hti.weight =wi.weight;hti.parent=O;hti.LChild=O;hti.RChild=O;)for(i=n+1;i=2*n-1;i+)文案大全实用标准文档hti.weight=O;hti.parent=O;hti.LChild=O;hti.RChild=O;)for(i=n+1;i=2*n-1;i+)(forQ=1;j=i-1;j+)if(!htj. parent)break;s1=j; /找到第一个双亲为零的结点for(;jhtj.weight?j:s

16、1;hts1.parent=i;hti.LChild=s1;forQ=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; 权值累加文案大全实用标准文档*叶子结点的编码*叶子结点的编码7void CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weightjnt mjnt n)(int i,c,p,s

17、tart;char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1尸(y；/末尾置0for(i=1;i=n;i+)(start=n-1; /cd串每次从末尾开始c=i；p=hti.parent;/p 在 n+1 至 2n-1while(p) 沿父亲方向遍历,直到为0(start-; 依次向前置值if(htp.LChild=二c)与左子相同，置 0cdstart=O;else 否则置1cdstart=r；c=p;p=htp.parent;)weighti.num=n-start; 二进制码的长度(包含末尾0) hi=(char *)malloc(n-star

18、t)*sizeof(char);文案大全实用标准文档strcpy(hi,&cdstart);将二进制字符串拷贝到指针数组h中free(cd);/释放 cd 内存system(Hpausen);void CrtHuffmanCode(char chOHuffmanCode h,HuffmanCode hc.WeightNode weightjnt njnt m)int i,k;for(i=0;im;i+)for(k=1;k=n;k+)m weightk.c 中查找与 chi相等的下标 K*/if(chi=weightk.c)break;hci=(char *)malloc(weightk.num

19、)*sizeof(char);strcpy(hcifhk); 拷贝二进制编码void TrsHuffmanTree(Huffman ht.WeightNode w,HuffmanCode hcjnt njnt m)int i=O,j,p;printfStringinformation n)p=2*n-1;从父亲节点向下遍历直到叶子节点文案大全实用标准文档for0=O;hci0!=O;j+)(if(hci0=O)p=htp.LChild;elsep=htp.RChild;)printf(%c,wp.c); /*打印原信息*/i+；)/*释放 huffman 编码内存*/void FreeHuff

20、manCode(HuffmanCode h.HuffmanCode hcjnt n,int m)(int i;for(i=1;i=n;i+)释放叶子结点的编码free(hi);for(i=0;ivm;i+) 释放所有结点的编码free(hci);)void main()(int i,n=0; /*n为叶子结点的个数*/int m=0; /*m为字符串ch的长度char chN; /*chN存放输入的字符串*/Huffman ht; /*Huffman 二叉数*/HuffmanCode h,he;/*h存放叶子结点的编码，he存放所有结点的编码*/文案大全实用标准文档WeightNode wei

21、ght; /*存放叶子结点的信息*/printf(t*HuffmanCoding*n);printf(please input informationgets(ch); /*输入字符串*/CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch的氏度*/printf(*Weightlnformation*n Node);for(i=1;i=n;i+)/*输出叶子结点的字符与权值*/printf(%c ,weighti.c);printf(nWeight);for(i=1;i=n;i+)printf(%d ,weighti.weight);CreateH

22、uffmanTree(ht,weight,n); C产生 Huffman 树*7printf(n*HuffamnTreelnformation*n);printf(MtitweighttparenttLChildtRChildnM);for(i=1;iv=2*r1;i+) /*打印 Huffman 树的信息*7printf(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”)

23、; /*打印叶子结点的编码*/for(i=1;i=n;i+)(printf(t%c:,weighti.c);printf(%sn,hi);)CrtHuffmanCode(ch,h,he,weight,n,m); /* 所有字符的编码*/printf(*StringCode*n); /* 打印字符串的编码*/for(i=0;im;i+)printf(%s,hci);文案大全实用标准文档system(HpauseH);TrsHuffmanTree(ht,weight,hc,n,m); /* 解码 */FreeHuffmanCode(h,hc,n,m);system(HpauseH);5Matlab

24、实现Matlab中简易实现Huffman编译码：n=input(,Please input the total number:);hf=zeros(2*n-1,5);hq=D；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 miniif hq(:,k)=mhq1hq=hq(:,1:(k-1) hq(:,(k+1):m)

25、;m=m-1;break文案大全实用标准文档elsek=k+1;endendk=1;while hf(k,2)-=mhq1 |hf(k,5)=1 %find mini locationk=k+1;endhf(k,5)=1;k1=k;mhq2=min(hq);k=1;while k=ndisplayCError! You did not input this number.*);breakendendif k=nbreakendr=Q;while hf(k,5)=1kc=n+1;while hf(kc,3)=k&hf(kc,4)二kkc=kc+1;文案大全实用标准文档endif hf(kc,3)

26、=kr=0 r;elser=1 r;endk=kc;end r elsea=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.1); break end end文案大全实用标准文档if k=0breakendr=hf(k.2)

27、;endchoose=input(,Choose what you want:n1: Encodingn2: Decodingn3:.Exitn);cic;endif choose-=1 &choose-=2cic;end LZ变换令LZ77压缩算法1977年，Jacob Ziv和Abraham Lempel描述了一种基于滑动窗I I缓存的技术，该缓 存用于保存最近刚刚处理的文本(J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression, IEEE Transaction on Informatio

28、n Theory, May 1977) o这个算法一般称为IZ77。LZ77和它的变体发现，在正文流中词汇和短语(GIF中的图像模式)很可能会出现重 So当出现一个重复时，重发的序列可以用一个短的编码来代替。压缩程序扫描这样的重 更，同时生成编码来代替重复序列。随着时间的过去，编码可以重用来捕获新的序列。算 法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。在研究LZ77的细节之前，先看一个简单的例子(J. Weiss and D. Schremp, uPutting Data on a Diet” , IEEE Spectrum, August 1993)。考虑这样一句话：文案大

29、全实用标准文档the brown fox jumped over the brown foxy jumping frog这个短语的长度总共是53个八位组二424 bito算法从左向右处理这个文本。初始 时，每个字符被映射成9 bit的编码，二进制的1跟着该字符的8 bit ASCII码。在处理 进行时，算法查找重史的序列。当碰到一个重复时，算法继续扫描直到该重复序列终止。 换句话说，每次出现一个重灾时，算法包括尽可能多的字符。碰到的第一个这样的序列是 the brown fox。这个序列被替换成指向前一个序列的指针和序列的长度。在这种情况下， 前一个序列的the brown fox出现在26个

30、字符之前，序列的长度是13个字符。对于这个 例子，假定存在两种编码选项：8 bit的指针和4 bit的长度，或者12 bit的指针和6 bit的长度。使用2 bit的首部来指示选择了哪种选项，00表示第一种选项，01表示第二 种选项。因此,the brown fox的第二次出现被编码为,或者00 00011010 1101c压缩报文的剩余部分是字母y；序列替换了由一个空格跟着jump组成 的序列，以及字符序列ing frogo图03-05-3演示了压缩映射的过程。压缩过的报文由35个9 bit字符和两个编码组 成，总长度为35 x 9 + 2 x 14 = 343比特。和原来未压缩的长度为42

31、4比特的报文相 比，压缩比为1.24。The brown fox jumped over the brown foxy jumping frog1 27 The brown jumped overy。端7/ ing frog图03-05-3 LZ77模式例（-）压缩算法说明LZ77 （及其变体）的压缩算法使用了两个缓存。滑动历史缓存包含了前面处理过的N 个源字符，前向缓存包含了将要处理的下面L个字符（图03-05-4 （a）。算法尝试将前向缓 存开始的两个或多个字符与滑动历史缓存中的字符串相匹配。如果没有发现匹配，前向缓 存的第一个字符作为9 bit的字符输出并且移入滑动窗口，滑动窗I I中最

32、久的字符被移 出。如果找到匹配，算法继续扫描以找出最长的匹配。然后匹配字符串作为三元组输出文案大全实用标准文档(指示标记、指针和长度)。对于K个字符的字符串，滑动窗I I中最久的K个字符被移 出，并且被编码的K个字符被移入窗I I。图03-05-4 (b)显示了这种模式对于我们的例子的运行情况。这里假定了 39个字符的滑动窗I I和13个字符的前向缓存。在这个例子的上半部分，已经处理了前面的40个字符，滑动窗II中是未压缩的最近的39个字符。剩下的源字符串在前向窗I I中。压缩算法确定了下一个匹配，从前向窗口将5个字符移入到滑动窗口中，并且输出了这个匹配字符串 的编码。经过这些操作的缓存的状态

33、显示在这个例子的卜.半部分。移入源正文源正文输出压缩的正文jumping froging frog(a)通用结构jumping froging froglie brown fox jumped over the brown foxyown fcx jumped over the 历cwn foxy jump(b)例子图 03-05-4 LZ77 模式尽管LZ77是有效的，对于当前的输入情况也是合适的，但是存在一些不足。算法使 用了有限的窗口在以前的文本中查找匹配，对于相对于窗口大小来说非常长的文本块，很 多可能的匹配就会被去掉。窗II大小可以增加，但这会带来两个损失：(1)算法的处理时间 会增

34、加，因为它必须为滑动窗11的每个位置进行一次与前向缓存的字符串匹配的工作： (2)指针字段必须更长，以允许更长的跳转。(-)压缩算法描述为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：T1 输入数据流(input stream)：待压缩处理的字符序列。EI 字符(character)：输入数据流中的基本单元。文案大全实用标准文档口 编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲器中的开始字符。口 前向缓冲器(lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。B 窗口 (Window)：指包含W个字符的

35、窗口，字符是从编码位置开始向后数也就是最后处理的字符数。H 指针(Pointer)：指向窗口中的匹配串且含长度的指针。LZ77编码算法的核心是查找从前向缓冲器开始的最长的匹配串。算法的具体执行步骤 如下：。把编码位置设置到输入数据流的开始位置。查找窗口中最长的匹配串。 输出(Pointer, Length) Characters,其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度， Characters是前向缓冲器中的第1个不匹配的字符。如果前向缓冲器不是空的，则把编码位置和窗II向前移Length+1个字符，然后返回到步骤2。例：待编码的数据流如表03-05-1所示，

36、编码过程如表03-05-2所示。现作如下说 明：“步骤”栏表示编码步骤。“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置lo“匹配”栏表示窗口中找到的最长的匹配串。O“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。输出栏以(Back_chars, Chars_length) Explicit_character 格式输出。其中(Back_chars, Chars_length)是指 指向匹配串的指针，告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”， Explicit_character是真实字符。例如，表3-13中的输出“

37、(5, 2) C”告诉译码器回退5个字符，然后拷贝2个字符 “AB”表03-05-1待编码的数据流文案大全实用标准文档步mi位置匹配串字符输出11A(0, 0) A22AB(1, 1) B34C(0, 0) C45BB(2, 1) B07A BC(5, 2) C（三）解压算法对于LZ77压缩文本的解压很简单。解压算法必须保存解压输出的最后N个字符。当碰 到编码字符串时，解压算法使用指针），和长度，字段将编码替换成实际的正文字符串。实现#include #include #include #include #define OFFSET_CODING_LENGTH#define MAX_WND_S

38、IZE#define OFFSET_CODING_LENGTH#define MAX_WND_SIZE/#define MAX_WND_SIZE#define OFFSET_MASK_CODE(10)1024(1OFFSET-CODING_LENGTH)(MAX_WND_SIZE-1)文案大全实用标准文档const ULONG m=3;UCHAR _bufferl_0 x200000;UCHAR _buffer2_0 x200000;/voidWrite lToBitStream(PUCHAR pBuffer,ULONG ulBitOffsetULONG ulByteBoundary;ULON

39、G ulOffsetlnByte;ulByteBoundary = ulBitOffset3;u I Offset In Byte = ulBitOffset&7;*(pBuffer+ulByteBoundary) |= (lulOffsetlnByte); )voidWriteOToBitStream(PUCHAR pBuffer,ULONG ulBitOffsetULONG ulByteBoundary;ULONG ulOffsetlnByte;ulByteBoundary = ulBitOffset3;u I Offset In Byte = ulBitOffset&7;*(pBuffe

40、r+ulByteBoundary) &= ( 1 u I Offset I n Byt e); )ULONGReadBitFromBitStream(PUCHAR pBuffer,ULONG ulBitOffset文案大全实用标准文档ULONG ulByteBoundary;ULONG ulOffsetlnByte;ulByteBoundary = ulBitOffset3;u I Offset In Byte = ulBitOffset&7;return (*(PULONG)(pBuffer+ulByteBoundary)ulOffsetlnByte)&l; )ULONG WINAPI Wr

41、iteGolombCode(ULONG x, PUCHAR pBuffer, ULONG ulBitOffsetULONGq, r;inti;q = (x-l)m;r = x-(qm)-l;for(i=0; (ULONG)iq; i+, ulBitOffset+)(WritelToBitStream(pBuffer, ulBitOffset);)WriteOToBitStream(pBufferz ulBitOffset); ulBitOffset+;for(i=0; im; i+, ulBitOffset+)(if( (ri)&l)WritelToBitStream(pBuffer, ulB

42、itOffset);elseWriteOToBitStream(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(pBufferz ulBitOffset); ulBitOffset+;if( !bit) break; )for(i=0, r=

43、0; (ULONG)im; i+, ulBitOffset+) (bit = (ULONG)ReadBitFromBitStream(pBufferz ulBitOffset); bit = i;r |= bit;)*pulCodingLength = m + q + 1;return r+(qm)+l; )ULONGCompareStrings(PUCHAR stringsPUCHAR string4 ULONG length文案大全实用标准文档ULONGi;PUCHARpl, p2;pl = stringl;p2 = string2;for(i=0; i0) (length = Compa

44、reStrings(pSrc, pString, ulMaxLength);if( length*pulSubstringLength ) *pulSubstringLength = length;*pulSubstringOffset = offset;pSrc+;offset+; ulMaxLength-;) )/* void FindLongestSubstring(PUCHAR pSourceString,PUCHAR pString,ULONG ulSourceStringLength,PULONG pulSubstringOffset, PULONG pulSubstringLen

45、gth )(PUCHAR pCurrentOffset;PUCHAR pl, p2;ULONG offset, length;pCurrentOffset = pSourceString;*pulSubstringOffset = offset = 0;*pulSubstringLength = length = 0;文案大全实用标准文档while( pCurrentOffsetpSourceString+ulSourceStringLength ) (pl = pCurrentOffset;p2 = pString;if( *pl=*p2 ) while( pl*pulSubstringLe

46、ngth ) *pulSubstringLength = length;*pulSubstringOffset = (ULONG)pCurrentOffset - (ULONG)pSourceString; pCurrentOffset+;) ) */voidWriteBits(PUCHAR pDataBuffer,ULONG ulOffsetToWrite,ULONG ulBits, ULONG ulBitLength ) (ULONG ulDwordsOffset;ULONG ulBitsOffset, ulBitsRemained;文案大全实用标准文档ulDwordsOffset = u

47、lOffsetToWrite5;ulBitsOffset = ulOffsetToWrite&31;ulBitsRemained = 32 - ulBitsOffset;if( 0=ulBitsOffset) (*(PULONG)pDataBuffer+ulDwordsOffset) = ulBits;)else if( ulBitsRemained=ulBitLength) (*(PULONG)pDataBuffer+ulDwordsOffset) |= (ulBitsulBitsOffset);) else (*(PULONG)pDataBuffer+ulDwordsOffset) |=

48、(ulBitsulBitsOffset);*(PULONG)pDataBuffer+ulDwordsOffset+l) = ulBitsulBitsRemained; ) ) void ReadBits(PUCHAR pDataBuffecULONG ulOffsetToRead, PULONG pulBits ) (ULONG ulDwordsOffset;ULONG ulBitsOffset, ulBitsLength;ulDwordsOffset = ulOffsetToRead5;ulBitsOffset = ulOffsetToRead&31;ulBitsLength = 32 -

49、ulBitsOffset;*pulBits = *(PULONG)pDataBuffer+ulDwordsOffset);if( 0!=ulBitsOffset)(*pulBits) = ulBitsOffset;(*pulBits) |= (*(PULONG)pDataBuffer+ulDwordsOffset+l)ulBitsLength;)voidIz77compress(文案大全实用标准文档PUCHAR pDataBuffecULONG ulDataLength, PUCHAR pOutputBuffer, PULONG pulNumberOfBits )LONG iSlideWind

50、owPtr;ULONGulBytesCoded;ULONGulMaxlength;PUCHARpSIideWindowPtr;PUCHARpUnprocessedDataPtr;ULONG offset;ULONG length;ULONG ulCodingLength;ULONG ulBitOffset;UCHAR cc;int i;iSlideWindowPtr = -MAX_WND_SIZE; pSIideWindowPtr = NULL;ulBitOffset = 0;ulBytesCoded = 0;while( ulBytesCoded=0)pSIideWindowPtr = pD

51、ataBuffer+iSlideWindowPtr; ulMaxlength = MAX_WND_SIZE;else if( iSlideWindowPtr=-MAX_WND_SIZE )pSIideWindowPtr = pDataBuffer;ulMaxlength = MAX_WND_SIZE + iSlideWindowPtr; elsepSIideWindowPtr = NULL;ulMaxlength = 0;文案大全实用标准文档pUnprocessedDataPtr = pDataBuffer + ulBytesCoded;if( ulMaxlengthulDataLength-

52、ulBytesCoded ) ulMaxlength = ulDataLength-ulBytesCoded;FindLongestSubstring( pSIideWindowPtr, pUnprocessedDataPtr, ulMaxlength, &offset, &length );assert( length=MAX_WND_SIZE ); assert( offsetl) WritelToBitStream(pOutputBuffer, ulBitOffset); ulBitOffset+;for(i=0; iOFFSET_CODING_LENGTH; i+, ulBitOffs

53、et+) (if (offseti)&l) WritelToBitStream(pOutputBuffer, ulBitOffset); else WriteOToBitStream(pOutputBuffer, ulBitOffset); )ulCodingLength = WriteGolombCode(length, pOutputBuffer, ulBitOffset);ulBitOffset += ulCodingLength; iSlideWindowPtr += length; ulBytesCoded += length; else文案大全实用标准文档WriteOToBitSt

54、ream(pOutputBuffer, ulBitOffset); ulBitOffset+;cc = (*pUnprocessedDataPtr); for(i=0; i8; i+, ulBitOffset+) (if( (cci)&l) WritelToBitStream(pOutputBuffer, ulBitOffset); else WriteOToBitStream(pOutputBuffer, ulBitOffset); )iSlideWindowPtr+; ulBytesCoded+; )if( ulBytesCoded!=ulDataLength )( assert(ulBy

55、tesCoded=ulDataLength);)*pulNumberOfBits = u I BitOffset;)void Iz77decompress( PUCHAR pDataBuffec ULONG ulNumberOfBits, PUCHAR pOutputBuffer, PULONG pulNumberOfBytes )(LONG iSlideWindowPtr;PUCHAR pSIideWindowPtr;ULONG length, offset;文案大全实用标准文档ULONG bit;UCHAR cc;int i;ULONG ulBytesDecoded;ULONG ulBit

56、Offset;ULONG ulCodingLength;PUCHAR pWrite;iSlideWindowPtr = -MAX_WND_SIZE;pWrite = (PUCHAR)pOutputBuffer;ul BitOffset = 0;ulBytesDecoded = 0;while( uIBitOffset=0)(pSIideWindowPtr = pOutputBuffer + iSlideWindowPtr;)else if( iSlideWindowPtr=-MAX_WND_SIZE)(pSIideWindowPtr = pOutputBuffer;)else(pSIideWi

57、ndowPtr = NULL;) for(i=0, offset=0; KOFFSET-CODING-LENGTH; i+, ulBitOffset+) (bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset);offset |= (biti);)文案大全实用标准文档length= ReadGolombCode(&ulCodingLength, pDataBuffer, ulBitOffset);assert(offsetMAX_WND_SIZE)(assert(length=MAX_WND_SIZE);)ulBitOffset += ulCo

58、dingLength;RtlMoveMemory(pWrite, pSIideWindowPtr+offset, length);pWrite+=length;iSlideWindowPtr+=length;ulBytesDecoded+=length;elsefor(i=0, cc=0; i8 ; i+, ulBitOffset+)(bit = ReadBitFromBitStream(pDataBufferz ulBitOffset);cc |=(UCHAR)biti);)*pWrite+ = cc;iSlideWindowPtr+;ulBytesDecoded+;)*pulNumberO

59、f Bytes = ulBytesDecoded;)externvoid WINAPILZ77Compress(PUCHAR _pDataBufferzULONG _ulDataLength,PUCHAR _pOutputBufferzPULONG _pulNumberOfBits externvoid WINAPI文案大全实用标准文档LZ77Decompress(PUCHAR _pDataBuffecULONG _ulNumberOfBits, PUCHAR _pOutputBufferz PULONG _pulNumberOfBytes );intmain(int argc, char *

60、argv)(FILE *fp=NULL;FILE *fpl;ULONG fsize;ULONG ulNumberOfBits;ULONG ulFileCompressedSize;ULONG ulFileDecompressedSize;SYSTEMTIME tl, t2;if( 3!=argc)( printf(HUsage: Iz77 /c | /d filenamenH); return -1;)/ char sl=,abcdabcdefgabcdefaffasdaN;/ ULONG a, b;/ FindLongestSubstring(PUCHAR)slz (PUCHAR)sl+ll