LZ77 压缩算法编码原理详解(结合图片和简单代码)
fan0fan1
8年前
<h2><strong>前言</strong></h2> <p>LZ77算法是无损压缩算法，由以色列人Abraham Lempel发表于1977年。LZ77是典型的基于字典的压缩算法，现在很多压缩技术都是基于LZ77。鉴于其在数据压缩领域的地位，本文将结合图片和源码详细介绍其原理。</p> <p><strong>原理介绍：</strong></p> <p>首先介绍几个专业术语。</p> <p>1.lookahead buffer(不知道怎么用中文表述，暂时称为待编码区):</p> <p>等待编码的区域</p> <p>2. search buffer：</p> <p>已经编码的区域，搜索缓冲区</p> <p>3.滑动窗口：</p> <p>指定大小的窗，包含“搜索缓冲区”（左） + “待编码区”（右）</p> <p>接下来，介绍具体的编码过程：</p> <p>为了编码待编码区， 编码器在滑动窗口的搜索缓冲区查找直到找到匹配的字符串。匹配字符串的开始字符串与待编码缓冲区的距离称为“偏移值”，匹配字符串的长度称为“匹配长度”。编码器在编码时，会一直在搜索区中搜索，直到找到最大匹配字符串，并输出(o, l )，其中o是偏移值， l是匹配长度。然后窗口滑动l，继续开始编码。如果没有找到匹配字符串，则输出(0, 0, c)，c为待编码区下一个等待编码的字符，窗口滑动“1”。算法实现将类似下面的：</p> <pre> while( lookAheadBuffernot empty ) { get a pointer (position, match) tothelongestmatch in thewindowfor thelookAheadBuffer; output a (position, length, char()); shiftthewindowlength+1 charactersalong; } </pre> <p>主要步骤为：</p> <p>1.设置编码位置为输入流的开始</p> <p>2.在滑窗的待编码区查找搜索区中的最大匹配字符串</p> <p>3.如果找到字符串，输出(偏移值， 匹配长度)， 窗口向前滑动“匹配长度”</p> <p>4.如果没有找到，输出(0, 0, 待编码区的第一个字符)，窗口向前滑动一个单位</p> <p>5.如果待编码区不为空，回到步骤2</p> <p>描述实在是太复杂，还是结合实例来讲解吧</p> <p><strong>实例：</strong></p> <p>现在有字符串“AABCBBABC”，现在对其进行编码。</p> <p>一开始，窗口滑入如图位置</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/59660d28a2921a7fe8233203ce0fca4e.png"></p> <p>由图可见，待编码缓冲区有“AAB”三个字符，此时搜索缓冲区还是空的。所以编码第一个字符，由于搜索区为空，故找不到匹配串，输出(0,0, A),窗口右移一个单位，如下图</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/0c384133da1c6d80b34774a299b43184.png"></p> <p>此时待编码区有“ABC”。开始编码。最先编码”A”，在搜索区找到”A”。由于没有超过待编码区，故开始编码”AB”，但在搜索区没有找到匹配字符串，故无法编码。因此只能编码”A”。</p> <p>输出(1, 1)。即为相对于待编码区，偏移一个单位，匹配长度为1。窗口右滑动匹配长度，即移动1个单位。如下图</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/ed5a71e91e6bf1248954ef1187afb173.png"></p> <p>一样，没找到，输出(0, 0, B),右移1个单号，如下图</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/906ee8a44d2b9a221b6e843709888a03.png"></p> <p>输出（0， 0， C）,右移1个单位，如下图</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/7ca54ca41dd1d8298529a09cda02045a.png"></p> <p>输出(2, 1),右移1个单位，如下图</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/e4f3fd5735d284d511247f629918099f.png"></p> <p>输出(3, 1)， 右移1个单位，如下图</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/9169b076193489277921521984eafbea.png"></p> <p>开始编码”A”，在搜索缓冲区查找到匹配字符串。由于待编码缓冲区没有超过，继续编码。开始编码”AB”,也搜索到。不要停止，继续编码“ABC”，找到匹配字符串。由于继续编码，则超过了窗口，故只编码“ABC”，输出(5, 3),偏移5，长度3。右移3个单位，如下图</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/f725d7fa93b02825f718df5c170e61fa.png"></p> <p>此时待编码缓冲区为空，停止编码。</p> <p>最终输出结果如下</p> <p style="text-align: center;"><img src="https://simg.open-open.com/show/9eb5abeb01e75ffbf67845a87b5ba2cf.png"></p> <p>python代码实现：</p> <pre> class Lz77: def __init__(self, inputStr): self.inputStr = inputStr #输入流 self.searchSize = 5 #搜索缓冲区(已编码区)大小 self.aheadSize = 3 #lookAhead缓冲区（待编码区）大小 self.windSpiltIndex = 0 #lookHead缓冲区开始的索引 self.move = 0 self.notFind = -1 #没有找到匹配字符串 #得到滑动窗口的末端索引 def getWinEndIndex(self): return self.windSpiltIndex + self.aheadSize #得到滑动窗口的始端索引 def getWinStartIndex(self): return self.windSpiltIndex - self.searchSize #判断lookHead缓冲区是否为空 def isLookHeadEmpty(self): return True if self.windSpiltIndex + self.move> len(self.inputStr) - 1 else False def encoding(self): step = 0 print("Step Position Match Output") while not self.isLookHeadEmpty(): #1.滑动窗口 self.winMove() #2. 得到最大匹配串的偏移值和长度 (offset, matchLen) = self.findMaxMatch() #3.设置窗口下一步需要滑动的距离 self.setMoveSteps(matchLen) if matchLen == 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(offset) + ',' + str(matchLen) + ')') #4.输出结果 self.output(result) step = step + 1 #仅用来设置第几步 #滑动窗口(移动分界点) def winMove(self): self.windSpiltIndex = self.windSpiltIndex + self.move #寻找最大匹配字符并返回相对于窗口分界点的偏移值和匹配长度 def findMaxMatch(self): matchLen = 0 offset = 0 minEdge = self.minEdge() + 1 #得到编码区域的右边界 #遍历待编码区，寻找最大匹配串 for i in range(self.windSpiltIndex + 1, minEdge): #print("i: %d" %i) offsetTemp = self.searchBufferOffest(i) if offsetTemp == self.notFind: return (offset, matchLen) offset = offsetTemp #偏移值 matchLen = matchLen + 1 #每找到一个匹配串，加1 return (offset, matchLen) #入参字符串是否存在于搜索缓冲区，如果存在，返回匹配字符串的起始索引 def searchBufferOffest(self, i): searchStart = self.getWinStartIndex() searchEnd = self.windSpiltIndex #下面几个if是处理开始时的特殊情况 if searchEnd < 1: return self.notFind if searchStart < 0: searchStart = 0 if searchEnd == 0: searchEnd = 1 searchStr = self.inputStr[searchStart : searchEnd] #搜索区字符串 findIndex = searchStr.find(self.inputStr[self.windSpiltIndex : i]) if findIndex == -1: return -1 return len(searchStr) - findIndex #设置下一次窗口需要滑动的步数 def setMoveSteps(self, matchLen): if matchLen == 0: self.move = 1 else: self.move = matchLen def minEdge(self): return len(self.inputStr) if len(self.inputStr) - 1 < self.getWinEndIndex() else self.getWinEndIndex() + 1 def output(self, touple): print("%d %d %s %s" % touple) if __name__ == "__main__": lz77 = Lz77("AABCBBABC") lz77.encoding() </pre> <p>只是简单的写了下，没有过多考虑细节，请注意，这不是最终的代码，只是用来阐述原理，仅供参考。输出结果就是上面的输出（格式由于坑爹的博客园固定样式，代码位置有偏移，请注意）</p> <p> </p> <p>来自：http://blog.jobbole.com/106146/</p> <p> </p>