人工智能实验报告、LZ77压缩算法实验报告

“人工智能”实验报告老师：黄芳班级：计科1001学号：0909090430姓名：赵鼎平目录一、神经网络实验群 4二、生产式系统实验群 5三、搜索策略实验群 6四、自动规划实验群 8五、实验心得和体会 11神经网络实验群姓名赵鼎平指导老师:黄芳日期:2013年11月7日实验目的理解反向传播网络的结构和原理，掌握反向传播算法对神经元的训练过程，了解反向传播公式。通过构建BP网络实例，熟悉前馈网络的原理及结构。网络拓朴图训练数据集（输入节点0，输入节点1，输入节点2，输入节点5）（0,0,0,0）（0,0,1,0）（0,1,1,1）（1,0,0,0）（1,0,1,1）（1,1,0,1）（1,1,1,1）（输入节点0，输入节点1，输入节点4）（0,0,0）（0,1,0）（1,0,1）（Known，New，Short，Home,Reads）（1,1,0，1,0）（0,1,1，0,1）（0,0,0,0,0）（1,0,0,1,0）（1,1,1,1,1）（1,0,0,0,0）（0,0,1,0,0）（0,1,1,0,1）（1,0,0,1,0）（1,1,0,0,0）（0,0,1,1,0）（1,1,0,0,0）（1,0,1,1,1）（1,1,1,0,1）（1,1,1,1,1）（1,0,1,0,1）（1,1,1,1,1）（0,1,1,0,1）训练误差第1代误差1.68第51代误差0.52第101代误差0.11第151代误差0.05第201代误差0.03第1代误差0.018第51代误差0.010第101代误差0.010第151代误差0.010第201代误差0.010第1代误差4.67第51代误差0.66第101代误差0.12第151代误差0.06第201代误差0.03模拟的问题或函数多数赞成表决器异或问题MailReading（邮件信息识别）观测结果经过200代的进化，误差以明显的阶梯型降低由于初始误差比较低，故经过50代的进化，误差已经极大地降低，几乎不再变化经过200代的进化，误差极大地降低学生结论神经计算能够实现“多数赞成表决器”功能单层的神经网络无法实现异或问题，但是含有中间层的BP网络却可以很好的解决异或问题经过训练的BP网络可以进行邮件识别，解决信息识别的难题，可以极大地提高生产力生产式系统实验群姓名赵鼎平指导老师黄芳日期2013.11.7实验目的熟悉和掌握产生式系统的运行机制，掌握基于规则推理的基本方法。推理方法逆向推理建立规则库建立事实库该动物是哺乳动物<-该动物有毛发.该动物是哺乳动物<-该动物有奶.该动物是鸟<-该动物有羽毛.该动物是鸟<-该动物会飞&会下蛋.该动物是食肉动物<-该动物吃肉.该动物是食肉动物<-该动物有犬齿&有爪&眼盯前方.该动物是有蹄类动物<-该动物是哺乳动物&有蹄.该动物是有蹄类动物<-该动物是哺乳动物&是嚼反刍动物.该动物是金钱豹<-该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.该动物是虎<-该动物是哺乳动物&该动物是食肉动物&是黄褐色&身上有黑色条纹.该动物是长颈鹿<-该动物是有蹄类动物&有长脖子&有长腿&身上有暗斑点.该动物是斑马<-该动物是有蹄类动物&身上有黑色条纹.该动物是鸵鸟<-该动物是鸟&有长脖子&有长腿&不会飞&有黑白二色.该动物是企鹅<-该动物是鸟&会游泳&不会飞&有黑白二色.该动物是信天翁<-该动物是鸟&善飞.%------动物识别系统事实集：%会游泳.%--该动物是企鹅%不会飞.%有黑白二色.%该动物是鸟.%--------%--该动物是鸟%该动物会飞.%会下蛋.%----该动物是金钱豹<-该动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.%该动物有毛发.%是食肉动物.%是黄褐色.%身上有暗斑点.%----该动物是虎<-该动物是哺乳动物&该动物是食肉动物&是黄褐色&身上有黑色条纹.%该动物是哺乳动物.%是食肉动物.%是黄褐色.%身上有暗斑点.%----该动物是长颈鹿<-该动物是有蹄类动物&有长脖子&有长腿&身上有暗斑点.%该动物是有蹄类动物.%有长脖子.%有长腿.%身上有暗斑点.预测结果假设目标为该动物是金钱豹，则结果为true.实验过程及结果(注意观测规则的匹配过程和方法)（1）假设这个动物是金钱豹。为了检验这个假设，根据规则，要求这个动物是哺乳动物&是食肉动物&是黄褐色&身上有暗斑点.（2）必须检验这个动物是否为哺乳动物。先由规则库中的：该动物是哺乳动物<-该动物有毛发.该动物是哺乳动物<-该动物有奶.可知，均不和事实相匹匹配，这条链是失败的，但事实库中有：该动物是哺乳动物.这个事实，故存在成功的链路。（3）同理对于其他三者，事实库中均存在给点的事实即：是食肉动物.是黄褐色.身上有黑色条纹.所以存在一条成功的链路，使所有的规则与事实匹配。故结果为True.根据逆向推理可以逐步确定学生结论在产生式系统的推理过程中，我们需要恰当的设置好规则与事实，同时应注意两者之间的匹配。在逆向推理中，必须寻找所存在的规则，最终找到存在事实库，若所需条件存在则为true，否则为false指导老师意见搜索策略实验群姓名赵鼎平年级计科1001班指导老师黄芳日期2013年11月7日实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。搜索图使用的是实验环境中已经建立好的“多重路径修建”搜索图算法比较深度优先BestFirst（贪婪算法）A*算法Open表{0}{1.3.4}{3.4.2}{4.2.6}{.8}{}{5.7.8}{7.8}{8}{空}{0}{1.3.4}{3.4.2}{4.2.6}{.8}{}{5.7.8}{7.8}{8}{空}{0}{1.3.4}{3.4.2}{4.2.6}{.8}{}{5.7.8}{7.8}{8}{空}Close表{空}{0}{0.1}{0.1.3}{}{.2}{.2.6}{.2.6.5}{.}{..8}{空}{0}{0.1}{0.1.3}{}{.2}{.2.6}{.2.6.5}{.}{..8}{空}{0}{0.1}{0.1.3}{}{.2}{.2.6}{.2.6.5}{.}{..8}估价函数f(x)=g(x)f(x)=h(x)f(x)*=g(x)*+h(x)*搜索节点次序记录节点0->节点1->节点3->节点4->节点2->节点4->节点6->节点4->节点7->节点5->节点6->节点8节点0->节点1->节点3->节点4->节点2->节点4->节点6->节点4->节点7->节点5->节点6->节点8节点0->节点1->节点3->节点4->节点2->节点4->节点6->节点5->节点7->节点6->节点8观测结果最终路径是节点0->节点4->节点8最终路径是节点0->节点4->节点8最终路径是节点0->节点4->节点8学生结论广度优先搜索算法是一种搜索策略，与之相对应的还有深度优先搜索算法。广度优先是指从图G中的某点为始点出发，标记出所有与之相邻的点，并再以所有与之相邻的点为始点，搜索所有与这些点相邻的点，从而逐层向下扩展，实现对图的遍历。同理，深度优先搜索是指从某点出发，逐层向下扩展，直到无路可扩展时向上回溯，它是优先考虑图的深度（指从某点的扩展深度），而广度优先则优先考虑图的广度（指从某点的可扩展量）。贪婪算法是一种不追求最优解，只希望得到较为满意解的方法。贪婪算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪算法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。A*算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如Dijkstra算法）。它通过一个估价函数（HeuristicFunction）f(h)来估计图中的当前点p到终点的距离(带权值)，并由此决定它的搜索方向，当这条路径失败时，它会尝试其它路径。我们说如果在一般的图搜索算法中应用了上面的估价函数对OPEN表进行排序的，就称A算法。在A算法之上，如果加上一个条件，对于所有的结点x，都有h(x)<=h*(x)，那就称为A*算法。如果取h(n)=0同样是A*算法，这样它就退化成了有序算法。A*算法是否成功，也就是说是否在效率上胜过蛮力搜索算法，就在于h(n)的选取，它不能大于实际的h*(n)，要保守一点，但越接近h*(n)给我们的启发性就越大，是一个难把握的东西。自动规划实验群姓名赵鼎平班级计科1001指导老师黄芳日期2013.11.7实验目的熟悉和掌握自动规划的基本原理,方法和主要技术。实验原理规划是一种问子题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。简而言之，规划是一个行动过程的描述。一个总规划可以含有若干个子规划。实验环境转载相关源文件实验环境转载相关源文件实现过程单步观察实验算法算法结果分析观测结果通过规定规则，确定initialstate和goalstate，使得移动臂按照规则进行移动。分别进行clearholdingpickupputdownputdowntable等实现对木块的移动。实现过程先进行逆向推理选择，找出途径后再进行移动。学生结论对于不同的规则将会出现不同的移动过程。通过规定不同的动作可实现不通过的移动。实验心得和体会 当初觉得好奇报了人工智能这一个学科，接触了一学期后发现人工智能挺有趣的。其中涉及到了很多与我们的生活息息相关的知识以及它所代表的也是我们科学进步发展最前沿的体现。 除了计算机科学以外,人工智能还涉及信息论、控制论、自动、仿生学、生物学、心理学、数理逻、语言、医学和哲学等多门学科。人工智能学科研究的主要内容包括：知识表示、自动推理和搜索方法、机器学习和知识获取、知识处理系统、自然语言理、计算机视觉、智能机器人、自动程序设计等方面。 同时通过这几次的实验，我对人工智能的一些思想以及应用有了更进一步的了解。 在实验期间，也遇到了很多困难，我通过在书本上查找答案以及询问周边的同学，希望能得到合理的答案，在大家的帮助下，解决了不少实验中的问题以及很多难以理解的理论和思想，不过还有很多地方自己和同学们都不是很了解，希望在今后的学习中能慢慢解决问题。 在其中，我更学到了并巩固了书本上的知识。再生产式系统中，主要用到了系统自带的动物识别系统，动物识别系统的实质是将人的思维过程转化为计算机语言的逻辑过程，其关键在于知识和信息的表示，智能推理或求解的基础—知识库的创建和管理，以及基于某种知识和信息表示的智能推理或求解过程。在搜索策略实验群中，我渐渐了解启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。同时还有神经网络群以及自动规划群，规划是一种问子题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。简而言之，规划是一个行动过程的描述。一个总规划可以含有若干个子规划。通过这一段的实验，增长了知识，更锻炼了自我的能力，希望今后能在人工智能这块领域内取得获得更多的知识。LZ77压缩算法实验报告一、实验内容：使用C++编程实现LZ77压缩算法的实现。二、实验目的：用LZ77实现文件的压缩。三、实验环境：1、软件环境：VisualC++6.02、编程语言：C++四、实验原理：LZ77算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。五、LZ77算法的基本流程：1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤2，否则进行步骤3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。代码如下：#include<windows.h>#include<stdio.h>#include<memory.h>#include"lz77.h"////////////////////////////////////////////////////////////////////outfileformat://0;flag2;buffer;0;flag2;buffer;...flag1;flag2;bufferlast//flag1-2bytes,sourcebufferblocklength//ifblocksizeis65536,bezero//flag2-2bytes,compressedbufferlength//ifcannotcompress,besamewithflag1//////////////////////////////////////////////////////////////////voidmain(intargc,char*argv[]){/*if(argc!=4){puts("Usage:");printf("Compress:%scsourcefiledestfile\n",argv[0]);printf("Decompress:%sdsourcefiledestfile\n",argv[0]);return;}*/ BYTEsoubuf[65536];BYTEdestbuf[65536+16]; FILE*in;FILE*out; /*in=fopen("input.txt","rb");if(in==NULL){ puts("Can'topensourcefile"); return;}out=fopen("compress.txt","wb");if(out==NULL){ puts("Can'topendestfile"); fclose(in); return;} fseek(in,0,SEEK_END); longsoulen=ftell(in); fseek(in,0,SEEK_SET); CCompressLZ77cc;WORDflag1,flag2;*/ inttemp;printf("compress(0)ordecompress(1)?:"); scanf("%d",&temp);if(temp==0)//compress{ in=fopen("input.txt","rb"); if(in==NULL) { puts("Can'topensourcefile"); return; } out=fopen("compress.txt","wb"); if(out==NULL) { puts("Can'topendestfile"); fclose(in); return; } fseek(in,0,SEEK_END); longsoulen=ftell(in); fseek(in,0,SEEK_SET); CCompressLZ77cc; WORDflag1,flag2;intlast=soulen,act;while(last>0){act=min(65536,last);fread(soubuf,act,1,in);last-=act;if(act==65536)//out65536bytesflag1=0;else//outlastblocksflag1=act;fwrite(&flag1,sizeof(WORD),1,out); intdestlen=cc.Compress((BYTE*)soubuf,act,(BYTE*)destbuf);if(destlen==0)//can'tcompresstheblock{flag2=flag1;fwrite(&flag2,sizeof(WORD),1,out);fwrite(soubuf,act,1,out);}else{flag2=(WORD)destlen;fwrite(&flag2,sizeof(WORD),1,out);fwrite(destbuf,destlen,1,out);}}}elseif(temp==1)//decompress{ in=fopen("compress.txt","rb"); if(in==NULL) { puts("Can'topensourcefile"); return; } out=fopen("decompress.txt","wb"); if(out==NULL) { puts("Can'topendestfile"); fclose(in); return; } fseek(in,0,SEEK_END); longsoulen=ftell(in); fseek(in,0,SEEK_SET); CCompressLZ77cc; WORDflag1,flag2;intlast=soulen,act;while(last>0){fread(&flag1,sizeof(WORD),1,in);fread(&flag2,sizeof(WORD),1,in);last-=2*sizeof(WORD);if(flag1==0)act=65536;elseact=flag1;last-=flag2?(flag2):act; if(flag2==flag1){fread(soubuf,act,1,in);}else{fread(destbuf,flag2,1,in);if(!cc.Decompress((BYTE*)soubuf,act,(BYTE*)destbuf)){puts("Decompresserror");fclose(in);fclose(out);return;}}fwrite((BYTE*)soubuf,act,1,out);}}else{puts("Usage:");printf("Compress:%scsourcefiledestfile\n",argv[0]);printf("Decompress:%sdsourcefiledestfile\n",argv[0]);} fclose(in);fclose(out);}////////////////////////////////LZ77.h////////////////////////////////使用在自己的堆中分配索引节点，不滑动窗口//每次最多压缩65536字节数据//的优化版本#ifndef_WIX_LZ77_COMPRESS_HEADER_001_#define_WIX_LZ77_COMPRESS_HEADER_001_//滑动窗口的字节大小#define_MAX_WINDOW_SIZE 65536classCCompress{public: CCompress(){}; virtual~CCompress(){};public: virtualintCompress(BYTE*src,intsrclen,BYTE*dest)=0; virtualBOOLDecompress(BYTE*src,intsrclen,BYTE*dest)=0;protected: //tools ///////////////////////////////////////////////////////// //CopyBitsInAByte:在一个字节范围内复制位流 //参数含义同CopyBits的参数 //说明： // 此函数由CopyBits调用，不做错误检查，即 // 假定要复制的位都在一个字节范围内 voidCopyBitsInAByte(BYTE*memDest,intnDestPos, BYTE*memSrc,intnSrcPos,intnBits); //////////////////////////////////////////////////////// //CopyBits:复制内存中的位流 // memDest-目标数据区 // nDestPos-目标数据区第一个字节中的起始位 // memSrc-源数据区 // nSrcPos-源数据区第一个字节的中起始位 // nBits-要复制的位数 // 说明： // 起始位的表示约定为从字节的高位至低位（由左至右） // 依次为0，，...,7 // 要复制的两块数据区不能有重合 voidCopyBits(BYTE*memDest,intnDestPos, BYTE*memSrc,intnSrcPos,intnBits); ////////////////////////////////////////////////////////////// //将DWORD值从高位字节到低位字节排列 voidInvertDWord(DWORD*pDW); ///////////////////////////////////////////////////////////// //设置byte的第iBit位为aBit // iBit顺序为高位起从记数（左起） voidSetBit(BYTE*byte,intiBit,BYTEaBit); //////////////////////////////////////////////////////////// //得到字节byte第pos位的值 // pos顺序为高位起从记数（左起） BYTEGetBit(BYTEbyte,intpos); //////////////////////////////////////////////////////////// //将位指针*piByte(字节偏移),*piBit(字节内位偏移)后移num位 voidMovePos(int*piByte,int*piBit,intnum); ///////////////////////////////////////////////////////// //取log2(n)的upper_bound intUpperLog2(intn); ///////////////////////////////////////////////////////// //取log2(n)的lower_bound intLowerLog2(intn);};classCCompressLZ77:publicCCompress{public: CCompressLZ77(); virtual~CCompressLZ77();public: ///////////////////////////////////////////// //压缩一段字节流 //src-源数据区 //srclen-源数据区字节长度,srclen<=65536 //dest-压缩数据区，调用前分配srclen字节内存 //返回值>0压缩数据长度 //返回值=0数据无法压缩 //返回值<0压缩中异常错误 intCompress(BYTE*src,intsrclen,BYTE*dest); ///////////////////////////////////////////// //解压缩一段字节流 //src-接收原始数据的内存区,srclen<=65536 //srclen-源数据区字节长度 //dest-压缩数据区 //返回值-成功与否 BOOLDecompress(BYTE*src,intsrclen,BYTE*dest);protected: BYTE*pWnd; //窗口大小最大为64k，并且不做滑动 //每次最多只压缩64k数据，这样可以方便从文件中间开始解压 //当前窗口的长度 intnWndSize; //对滑动窗口中每一个字节串排序 //排序是为了进行快速术语匹配 //排序的方法是用一个k大小的指针数组 //数组下标依次对应每一个字节串：(0000)(0001)...(0100)(0101)... //每一个指针指向一个链表，链表中的节点为该字节串的每一个出现位置 structSTIDXNODE { WORDoff; //在src中的偏移 WORDoff2; //用于对应的字节串为重复字节的节点 //指从off到off2都对应了该字节串 WORDnext; //在SortHeap中的指针 }; WORDSortTable[65536];//256*256指向SortHeap中下标的指针 //因为窗口不滑动，没有删除节点的操作，所以 //节点可以在SortHeap中连续分配 structSTIDXNODE*SortHeap; intHeapPos; //当前分配位置 //当前输出位置(字节偏移及位偏移) intCurByte,CurBit;protected: //////////////////////////////////////// //输出压缩码 //code-要输出的数 //bits-要输出的位数(对isGamma=TRUE时无效) //isGamma-是否输出为γ编码 void_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma); /////////////////////////////////////////////////////////// //在滑动窗口中查找术语 //nSeekStart-从何处开始匹配 //offset,len-用于接收结果，表示在滑动窗口内的偏移和长度 //返回值-是否查到长度为或以上的匹配字节串 BOOL_SeekPhase(BYTE*src,intsrclen,intnSeekStart,int*offset,int*len); /////////////////////////////////////////////////////////// //得到已经匹配了个字节的窗口位置offset //共能匹配多少个字节 inlineint_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset); ////////////////////////////////////////// //将窗口向右滑动n个字节 inlinevoid_ScrollWindow(intn); //向索引中添加一个字节串 inlinevoid_InsertIndexItem(intoff); //初始化索引表，释放上次压缩用的空间 void_InitSortTable();};#endif//_WIX_LZW_COMPRESS_HEADER_001_////////////////////////////////LZ77.CPP//////////////////////////////#include<windows.h>#include<stdio.h>#include<memory.h>#include<crtdbg.h>#include"lz77.h"///////////////////////////////////////////////////////////取log2(n)的upper_boundintCCompress::UpperLog2(intn){inti=0;if(n>0){intm=1;while(1){if(m>=n)returni;m<<=1;i++;}}elsereturn-1;}//UpperLog2////////////////////////////////////////////////////////////////////////////////////////////////////////////////////取log2(n)的lower_boundintCCompress::LowerLog2(intn){inti=0;if(n>0){intm=1;while(1){if(m==n)returni;if(m>n)returni-1;m<<=1;i++;}}elsereturn-1;}//LowerLog2///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////将位指针*piByte(字节偏移),*piBit(字节内位偏移)后移num位voidCCompress::MovePos(int*piByte,int*piBit,intnum){num+=(*piBit);(*piByte)+=num/8;(*piBit)=num%8;}//MovePos//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////得到字节byte第pos位的值//pos顺序为高位起从记数（左起）BYTECCompress::GetBit(BYTEbyte,intpos){intj=1;j<<=7-pos;if(byte&j)return1;elsereturn0;}//GetBit////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////设置byte的第iBit位为aBit//iBit顺序为高位起从记数（左起）voidCCompress::SetBit(BYTE*byte,intiBit,BYTEaBit){if(aBit)(*byte)|=(1<<(7-iBit));else(*byte)&=~(1<<(7-iBit));}//SetBit//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////将DWORD值从高位字节到低位字节排列voidCCompress::InvertDWord(DWORD*pDW){unionUDWORD{DWORDdw;BYTEb[4];};UDWORD*pUDW=(UDWORD*)pDW;BYTEb;b=pUDW->b[0];pUDW->b[0]=pUDW->b[3];pUDW->b[3]=b;b=pUDW->b[1];pUDW->b[1]=pUDW->b[2];pUDW->b[2]=b;}//InvertDWord////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////CopyBits:复制内存中的位流//memDest-目标数据区//nDestPos-目标数据区第一个字节中的起始位//memSrc-源数据区//nSrcPos-源数据区第一个字节的中起始位//nBits-要复制的位数//说明：//起始位的表示约定为从字节的高位至低位（由左至右）//依次为0，，...,7//要复制的两块数据区不能有重合voidCCompress::CopyBits(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits){intiByteDest=0,iBitDest;intiByteSrc=0,iBitSrc=nSrcPos;intnBitsToFill,nBitsCanFill;while(nBits>0){//计算要在目标区当前字节填充的位数nBitsToFill=min(nBits,iByteDest?8:8-nDestPos);//目标区当前字节要填充的起始位iBitDest=iByteDest?0:nDestPos;//计算可以一次从源数据区中复制的位数nBitsCanFill=min(nBitsToFill,8-iBitSrc);//字节内复制CopyBitsInAByte(memDest+iByteDest,iBitDest,memSrc+iByteSrc,iBitSrc,nBitsCanFill);//如果还没有复制完nBitsToFill个if(nBitsToFill>nBitsCanFill){iByteSrc++;iBitSrc=0;iBitDest+=nBitsCanFill;CopyBitsInAByte(memDest+iByteDest,iBitDest,memSrc+iByteSrc,iBitSrc,nBitsToFill-nBitsCanFill);iBitSrc+=nBitsToFill-nBitsCanFill;}else{iBitSrc+=nBitsCanFill;if(iBitSrc>=8){iByteSrc++;iBitSrc=0;}}nBits-=nBitsToFill;//已经填充了nBitsToFill位iByteDest++;}}//CopyBits////////////////////////////////////////////////////////////////////////////////////////////////////////////////////CopyBitsInAByte:在一个字节范围内复制位流//参数含义同CopyBits的参数//说明：//此函数由CopyBits调用，不做错误检查，即//假定要复制的位都在一个字节范围内voidCCompress::CopyBitsInAByte(BYTE*memDest,intnDestPos,BYTE*memSrc,intnSrcPos,intnBits){BYTEb1,b2;b1=*memSrc;b1<<=nSrcPos;b1>>=8-nBits;//将不用复制的位清b1<<=8-nBits-nDestPos;//将源和目的字节对齐*memDest|=b1;//复制值为的位b2=0xff;b2<<=8-nDestPos;//将不用复制的位置b1|=b2;b2=0xff;b2>>=nDestPos+nBits;b1|=b2;*memDest&=b1;//复制值为的位}//CopyBitsInAByte///////////////////////////////////////////////////////////------------------------------------------------------------------CCompressLZ77::CCompressLZ77(){SortHeap=newstructSTIDXNODE[_MAX_WINDOW_SIZE];}CCompressLZ77::~CCompressLZ77(){delete[]SortHeap;}//初始化索引表，释放上次压缩用的空间voidCCompressLZ77::_InitSortTable(){memset(SortTable,0,sizeof(WORD)*65536);nWndSize=0;HeapPos=1;}//向索引中添加一个字节串voidCCompressLZ77::_InsertIndexItem(intoff){WORDq;BYTEch1,ch2;ch1=pWnd[off];ch2=pWnd[off+1];if(ch1!=ch2){//新建节点q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}else{//对重复字节串//因为没有虚拟偏移也没有删除操作，只要比较第一个节点//是否和off相连接即可q=SortTable[ch1*256+ch2];if(q!=0&&off==SortHeap[q].off2+1){//节点合并SortHeap[q].off2=off;}else{//新建节点q=HeapPos;HeapPos++;SortHeap[q].off=off;SortHeap[q].off2=off;SortHeap[q].next=SortTable[ch1*256+ch2];SortTable[ch1*256+ch2]=q;}}}////////////////////////////////////////////将窗口向右滑动n个字节voidCCompressLZ77::_ScrollWindow(intn){for(inti=0;i<n;i++){nWndSize++;if(nWndSize>1)_InsertIndexItem(nWndSize-2);}}/////////////////////////////////////////////////////////////得到已经匹配了个字节的窗口位置offset//共能匹配多少个字节intCCompressLZ77::_GetSameLen(BYTE*src,intsrclen,intnSeekStart,intoffset){inti=2;//已经匹配了个字节intmaxsame=min(srclen-nSeekStart,nWndSize-offset);while(i<maxsame&&src[nSeekStart+i]==pWnd[offset+i])i++;_ASSERT(nSeekStart+i<=srclen&&offset+i<=nWndSize);returni;}/////////////////////////////////////////////////////////////在滑动窗口中查找术语//nSeekStart-从何处开始匹配//offset,len-用于接收结果，表示在滑动窗口内的偏移和长度//返回值-是否查到长度为或以上的匹配字节串BOOLCCompressLZ77::_SeekPhase(BYTE*src,intsrclen,intnSeekStart,int*offset,int*len){intj,m,n;if(nSeekStart<srclen-1){BYTEch1,ch2;ch1=src[nSeekStart];ch2=src[nSeekStart+1];WORDp;p=SortTable[ch1*256+ch2];if(p!=0){m=2;n=SortHeap[p].off;while(p!=0){j=_GetSameLen(src,srclen,nSeekStart,SortHeap[p].off);if(j>m){m=j;n=SortHeap[p].off;}p=SortHeap[p].next;}(*offset)=n;(*len)=m;returnTRUE;}}returnFALSE;}//////////////////////////////////////////输出压缩码//code-要输出的数//bits-要输出的位数(对isGamma=TRUE时无效)//isGamma-是否输出为γ编码voidCCompressLZ77::_OutCode(BYTE*dest,DWORDcode,intbits,BOOLisGamma){if(isGamma){BYTE*pb;DWORDout;//计算输出位数intGammaCode=(int)code-1;intq=LowerLog2(GammaCode);if(q>0){out=0xffff;pb=(BYTE*)&out;//输出q个CopyBits(dest+CurByte,CurBit,pb,0,q);MovePos(&CurByte,&CurBit,q);}//输出一个out=0;pb=(BYTE*)&out;CopyBits(dest+CurByte,CurBit,pb+3,7,1);MovePos(&CurByte,&CurBit,1);if(q>0){//输出余数,q位intsh=1;sh<<=q;out=GammaCode-sh;pb=(BYTE*)&out;InvertDWord(&out);CopyBits(dest+CurByte,CurBit,pb+(32-q)/8,(32-q)%8,q);MovePos(&CurByte,&CurBit,q);}}else{DWORDdw=(DWORD)code;BYTE*pb=(BYTE*)&dw;InvertDWord(&dw);CopyBits(dest+CurByte,CurBit,pb+(32-bits)/8,(32-bits)%8,bits);MovePos(&CurByte,&CurBit,bits);}}///////////////////////////////////////////////压缩一段字节流//src-源数据区//srclen-源数据区字节长度//dest-压缩数据区，调用前分配srclen+5字节内存//返回值>0压缩数据长度//返回值=0数据无法压缩//返回值<0压缩中异常错误intCCompressLZ77::Compress(BYTE*src,intsrclen,BYTE*dest){inti;CurByte=0;CurBit=0;intoff,len;if(srclen>65536)return-1;pWnd=src;_InitSortTable();for(i=0;i<srclen;i++){if(CurByte>=srclen)return0;if(_SeekPhase(src,srclen,i,&off,&len)){//输出匹配术语flag(1bit)+len(γ编码)+offset(最大bit)_OutCode(dest,1,1,FALSE);_OutCode(dest,len,0,TRUE);//在窗口不满k大小时，不需要位存储偏移_OutCode(dest,off,UpperLog2(nWndSize),FALSE);_ScrollWindow(len);i+=len-1;}else