LZ77 壓縮算法編碼原理詳解(結合圖片和簡單代碼)
前言
LZ77算法是無損壓縮算法，由以色列人Abraham Lempel發表于1977年。LZ77是典型的基于字典的壓縮算法，現在很多壓縮技術都是基于LZ77。鑒于其在數據壓縮領域的地位，本文將結合圖片和源碼詳細介紹其原理。
原理介紹：
首先介紹幾個專業術語。
1.lookahead buffer(不知道怎么用中文表述，暫時稱為待編碼區):
等待編碼的區域
2. search buffer：
已經編碼的區域，搜索緩沖區
3.滑動窗口：
指定大小的窗，包含“搜索緩沖區”（左） + “待編碼區”（右）
接下來，介紹具體的編碼過程：
為了編碼待編碼區， 編碼器在滑動窗口的搜索緩沖區查找直到找到匹配的字符串。匹配字符串的開始字符串與待編碼緩沖區的距離稱為“偏移值”，匹配字符串的長度稱為“匹配長度”。編碼器在編碼時，會一直在搜索區中搜索，直到找到最大匹配字符串，并輸出(o, l )，其中o是偏移值， l是匹配長度。然后窗口滑動l，繼續開始編碼。如果沒有找到匹配字符串，則輸出(0, 0, c)，c為待編碼區下一個等待編碼的字符，窗口滑動“1”。算法實現將類似下面的：
while( lookAheadBuffernot empty )
{
get a pointer (position, match) tothelongestmatch
in thewindowfor thelookAheadBuffer;
output a (position, length, char());
shiftthewindowlength+1 charactersalong;
}
主要步驟為：
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代碼實現：
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()
只是簡單的寫了下，沒有過多考慮細節，請注意，這不是最終的代碼，只是用來闡述原理，僅供參考。輸出結果就是上面的輸出（格式由于坑爹的博客園固定樣式，代碼位置有偏移，請注意）
來自：http://blog.jobbole.com/106146/