内江建网站,WordPress手机插件耗费CPU,建立网站项目计划书模板,网站建设是永久性的吗前言LZ77算法是无损压缩算法#xff0c;由以色列人Abraham Lempel发表于1977年。LZ77是典型的基于字典的压缩算法#xff0c;现在很多压缩技术都是基于LZ77。鉴于其在数据压缩领域的地位#xff0c;本文将结合图片和源码详细介绍其原理。原理介绍#xff1a;首先介绍几个专…前言LZ77算法是无损压缩算法由以色列人Abraham Lempel发表于1977年。LZ77是典型的基于字典的压缩算法现在很多压缩技术都是基于LZ77。鉴于其在数据压缩领域的地位本文将结合图片和源码详细介绍其原理。原理介绍首先介绍几个专业术语。1.lookahead buffer(不知道怎么用中文表述暂时称为待编码区):等待编码的区域2. search buffer已经编码的区域搜索缓冲区3.滑动窗口指定大小的窗包含“搜索缓冲区”(左) “待编码区”(右)接下来介绍具体的编码过程为了编码待编码区 编码器在滑动窗口的搜索缓冲区查找直到找到匹配的字符串。匹配字符串的开始字符串与待编码缓冲区的距离称为“偏移值”匹配字符串的长度称为“匹配长度”。编码器在编码时会一直在搜索区中搜索直到找到最大匹配字符串并输出(o, l )其中o是偏移值 l是匹配长度。然后窗口滑动l继续开始编码。如果没有找到匹配字符串则输出(0, 0, c)c为待编码区下一个等待编码的字符窗口滑动“1”。算法实现将类似下面的while( lookAheadBuffer not empty ){get a pointer (position, match) to the longest matchin the window for the lookAheadBuffer;output a (position, length, char());shift the window length1 characters along;}主要步骤为1.设置编码位置为输入流的开始2.在滑窗的待编码区查找搜索区中的最大匹配字符串3.如果找到字符串输出(偏移值 匹配长度) 窗口向前滑动“匹配长度”4.如果没有找到输出(0, 0, 待编码区的第一个字符)窗口向前滑动一个单位5.如果待编码区不为空回到步骤2描述实在是太复杂还是结合实例来讲解吧实例现在有字符串“AABCBBABC”现在对其进行编码。一开始窗口滑入如图位置由图可见待编码缓冲区有“AAB”三个字符此时搜索缓冲区还是空的。所以编码第一个字符由于搜索区为空故找不到匹配串输出(0,0, A),窗口右移一个单位如下图此时待编码区有“ABC”。开始编码。最先编码A在搜索区找到A。由于没有超过待编码区故开始编码AB但在搜索区没有找到匹配字符串故无法编码。因此只能编码A。输出(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代码实现1 classLz77:2 def __init__(self, inputStr):3 self.inputStr inputStr #输入流4 self.searchSize 5 #搜索缓冲区(已编码区)大小5 self.aheadSize 3 #lookAhead缓冲区(待编码区)大小6 self.windSpiltIndex 0 #lookHead缓冲区开始的索引7 self.move 08 self.notFind -1 #没有找到匹配字符串910 #得到滑动窗口的末端索引11 defgetWinEndIndex(self):12 return self.windSpiltIndex self.aheadSize1314 #得到滑动窗口的始端索引15 defgetWinStartIndex(self):16 return self.windSpiltIndex -self.searchSize1718 #判断lookHead缓冲区是否为空19 defisLookHeadEmpty(self):20 return True if self.windSpiltIndex self.move len(self.inputStr) - 1 elseFalse2122 defencoding(self):23 step 024 print(Step Position Match Output)25 while notself.isLookHeadEmpty():26 #1.滑动窗口27 self.winMove()28 #2. 得到最大匹配串的偏移值和长度29 (offset, matchLen) self.findMaxMatch()30 #3.设置窗口下一步需要滑动的距离31 self.setMoveSteps(matchLen)32 if matchLen 0:33 #匹配为0说明无字符串匹配输出下一个需要编码的字母34 nextChar self.inputStr[self.windSpiltIndex]35 result (step, self.windSpiltIndex, -, (0,0) nextChar)36 else:37 result (step, self.windSpiltIndex, self.inputStr[self.windSpiltIndex - offset: self.windSpiltIndex - offset matchLen], ( str(offset) , str(matchLen) ))38 #4.输出结果39 self.output(result)40 step step 1 #仅用来设置第几步414243 #滑动窗口(移动分界点)44 defwinMove(self):45 self.windSpiltIndex self.windSpiltIndex self.move4647 #寻找最大匹配字符并返回相对于窗口分界点的偏移值和匹配长度48 deffindMaxMatch(self):49 matchLen 050 offset 051 minEdge self.minEdge() 1 #得到编码区域的右边界52 #遍历待编码区寻找最大匹配串53 for i in range(self.windSpiltIndex 1, minEdge):54 #print(i: %d %i)55 offsetTemp self.searchBufferOffest(i)56 if offsetTemp self.notFind:57 return(offset, matchLen)58 offset offsetTemp #偏移值5960 matchLen matchLen 1 #每找到一个匹配串加16162 return(offset, matchLen)6364 #入参字符串是否存在于搜索缓冲区如果存在返回匹配字符串的起始索引65 defsearchBufferOffest(self, i):66 searchStart self.getWinStartIndex()67 searchEnd self.windSpiltIndex68 #下面几个if是处理开始时的特殊情况69 if searchEnd 1:70 returnself.notFind71 if searchStart 0:72 searchStart 073 if searchEnd 0:74 searchEnd 175 searchStr self.inputStr[searchStart : searchEnd] #搜索区字符串76 findIndex searchStr.find(self.inputStr[self.windSpiltIndex : i])77 if findIndex -1:78 return -179 return len(searchStr) -findIndex8081 #设置下一次窗口需要滑动的步数82 defsetMoveSteps(self, matchLen):83 if matchLen 0:84 self.move 185 else:86 self.move matchLen878889 defminEdge(self):90 return len(self.inputStr) if len(self.inputStr) - 1 self.getWinEndIndex() else self.getWinEndIndex() 19192 defoutput(self, touple):93 print(%d %d %s %s %touple)9495969798 if __name__ __main__:99 lz77 Lz77(AABCBBABC)100 lz77.encoding()只是简单的写了下没有过多考虑细节请注意这不是最终的代码只是用来阐述原理仅供参考。输出结果就是上面的输出(格式由于坑爹的博客园固定样式代码位置有偏移请注意)参考文章以上几篇文章都是很好的讲解LZ77原理的大家有兴趣的可以参考下。由于国内介绍该算法的比较少故这些英文文章帮助还是挺大的。
