前言LZ77算法是一种无损压缩算法，由以色列人AbrahamLempel于1977年发表。LZ77是典型的基于字典的压缩算法，很多压缩技术都是基于LZ77。鉴于其在数据压缩领域的地位，本文将结合图片和源码详细介绍其原理。原理介绍：首先介绍几个技术术语。1.lookaheadbuffer（中文不知道怎么表达，暂称areatobeencoded）：等待编码的区域2.searchbuffer：已经编码的区域，searchbuffer3.滑动窗口：一个指定大小的窗口，包括“searchBuffer”（左）+“待编码区域”（右）接下来介绍具体的编码过程：为了对待编码区域进行编码，编码器在搜索滑动窗口的缓冲区，直到找到匹配的字符串。匹配串的起始串与待编码缓冲区的距离称为“偏移值”，匹配串的长度称为“匹配长度”。编码时，编码器会在搜索区域中不断搜索，直到找到最佳匹配字符串，并输出(o,l)，其中o为偏移值，l为匹配长度。然后窗口滑动l，继续开始编码。如果没有找到匹配的字符串，则输出(0,0,c)，c为待编码区域下一个等待编码的字符，窗口滑动“1”。算法实现将如下所示：输出一个（位置，长度，字符（））；移动窗口长度+1个字符；}主要步骤为：1.将编码位置设置为输入流的开始2.在滑动窗口中待编码区域的搜索区域中寻找最匹配的字符串3.如果找到该字符串，则输出(偏移值，匹配长度），窗口向前滑动“匹配长度”4.如果没有找到，则输出（0,0,待编码区域的第一个字符），窗口向前滑动一个单位5.如果该区域tobeencodedisnot如果为空，则返回步骤2。描述的太复杂了，我们举个例子来解释一下。示例：现在有一个字符串“AABCBBABC”，现在对其进行编码。开始时，窗口滑入如图所示的位置。从图中可以看出待编码的缓冲区中有“AAB”三个字符，此时搜索缓冲区还是空的。于是对第一个字符进行编码，因为搜索区为空，所以找不到匹配的字符串，输出(0,0,A)，窗口向右移动一个单位，如下图，有此时待编码区域中的“ABC”。开始编码。***编码“A”，在搜索区域中找到“A”。由于没有超出需要编码的区域，所以开始编码“AB”，但是在搜索区域没有找到匹配的字符串，所以无法编码。因此只能对“A”进行编码。输出(1,1)。即相对于待编码区域，偏移量为1个单位，匹配长度为1，窗口向右滑动匹配长度，即移动1个单位。如下图，如果没有找到，输出(0,0,B)，右移1个奇数，输出(0,0,C)如下图，右移1个单位，输出(2,1)下图中，向右移动1个单元，输出(3,1)如下图，向右移动1个单元，开始编码“A”如下图，找到搜索缓冲区中的匹配字符串。由于尚未超出待编码缓冲区，继续编码。开始编码“AB”，也进行了搜索。不要停下来，继续编码“ABC”，找到匹配的字符串。由于继续编码，超出了窗口，所以只编码了“ABC”，输出了(5,3)，偏移量5，长度3。向右移动3个单元，如下图，此时待编码的缓冲区为空，停止编码。最终输出结果通过python代码实现如下：classLz77:def__init__(self,inputStr):self.inputStr=inputStr#inputstreamself.searchSize=5#searchbuffer(encodedarea)sizeself.aheadSize=3#lookAheadbufferArea（待编码区域）大小self.windSpiltIndex=0#lookHead缓冲区起始索引self.move=0self.notFind=-1#Nomatchingstringfound#GettheendindexoftheslidingwindowdefgetWinEndIndex(self):returnself.windSpiltIndex+self.aheadSize#获取滑动窗口的起始索引defgetWinStartIndex(self):returnself.windSpiltIndex-self.searchSize#判断lookHead缓冲区是否为空defisLookHeadEmpty(self):如果self.windSpiltIndex+self.move>len(self.inputStr)-1则返回Truedefencoding(self):step=0print("StepPositionMatchOutput")whilenotself.isLookHeadEmpty():#1.滑动窗口self.winMove()#2.获取***匹配串的偏移值和长度(offset,matchLen)=self.findMaxMatch()#3.在下一步self中设置窗口需要滑动的距离。setMoveSteps(matchLen)ifmatchLen==0:#匹配为0，表示没有字符串匹配，输出下一个需要编码的字母nextChar=self.inputStr[self.windSpiltIndex]result=(step,self.windSpiltIndex,'-','(0,0)'+nextChar)else:result=(step,self.windSpiltIndex,self.inputStr[self.windSpiltIndex-offset:self.windSpiltIndex-offset+matchLen],'('+str(偏移量)+','+str(matchLen)+')')#4。输出结果self.output(result)step=step+1#只用来设置前几步#滑动窗口（移动分割点）defwinMove(self):self.windSpiltIndex=self.windSpiltIndex+self.move#Find***匹配字符并返回相对于窗口分界点的偏移值和匹配长度deffindMaxMatch(self):matchLen=0offset=0minEdge=self.minEdge()+1#获取编码区右边界#遍历要编码的区域，在range(self.windSpiltIndex+1,minEdge)中为i寻找***匹配字符串：#print("i:%d"%i)offsetTemp=self.searchBufferOffest（我）ifoffsetTemp==self.notFind:return(offset,matchLen)offset=offsetTemp#偏移值matchLen=matchLen+1#每找到一个匹配的字符串加1return(offset,matchLen)#输入的字符串是否存在于搜索缓冲区,如果存在则返回匹配字符串的起始索引defsearchBufferOffest(self,i):searchStart=self.getWinStartIndex()searchEnd=self.windSpiltIndex#下面的ifs是开始处理的特例ifsearchEnd<1:returnself.notFindifsearchStart<0:searchStart=0ifsearchEnd==0:searchEnd=1searchStr=self.inputStr[searchStart:searchEnd]#搜索区域字符串findIndex=searchStr.find(self.inputStr[self.windSpiltIndex:i])iffindIndex==-1:return-1returnlen(searchStr)-findIndex#设置下一个窗口需要滑动的步数defsetMoveSteps(self,matchLen):ifmatchLen==0:self.move=1其他：自己。move=matchLendefminEdge(self):返回len(self.inputStr)iflen(self.inputStr)-1
