前言

LZ77算法是無損壓縮算法，由以色列人Abraham Lempel發(fā)表于1977年。LZ77是典型的基于字典的壓縮算法，現(xiàn)在很多壓縮技術(shù)都是基于LZ77。鑒于其在數(shù)據(jù)壓縮領(lǐng)域的地位，本文將結(jié)合圖片和源碼詳細(xì)介紹其原理。

原理介紹：

首先介紹幾個(gè)專業(yè)術(shù)語。

1.lookahead buffer(不知道怎么用中文表述，暫時(shí)稱為待編碼區(qū)):

等待編碼的區(qū)域

2. search buffer：

已經(jīng)編碼的區(qū)域，搜索緩沖區(qū)

3.滑動窗口：

指定大小的窗，包含“搜索緩沖區(qū)”（左） + “待編碼區(qū)”（右）

接下來，介紹具體的編碼過程：

為了編碼待編碼區(qū)， 編碼器在滑動窗口的搜索緩沖區(qū)查找直到找到匹配的字符串。匹配字符串的開始字符串與待編碼緩沖區(qū)的距離稱為“偏移值”，匹配字符串的長度稱為“匹配長度”。編碼器在編碼時(shí)，會一直在搜索區(qū)中搜索，直到找到***匹配字符串，并輸出(o, l )，其中o是偏移值， l是匹配長度。然后窗口滑動l，繼續(xù)開始編碼。如果沒有找到匹配字符串，則輸出(0, 0, c)，c為待編碼區(qū)下一個(gè)等待編碼的字符，窗口滑動“1”。算法實(shí)現(xiàn)將類似下面的：

while( lookAheadBuffer not empty )
 {
 get a pointer (position, match) to the longest match  in the window for the lookAheadBuffer;
output a (position, length, char());
 shift the window length+1 characters along;
 }

主要步驟為：

1.設(shè)置編碼位置為輸入流的開始

2.在滑窗的待編碼區(qū)查找搜索區(qū)中的***匹配字符串

3.如果找到字符串，輸出(偏移值， 匹配長度)， 窗口向前滑動“匹配長度”

4.如果沒有找到，輸出(0, 0, 待編碼區(qū)的***個(gè)字符)，窗口向前滑動一個(gè)單位

5.如果待編碼區(qū)不為空，回到步驟2

描述實(shí)在是太復(fù)雜，還是結(jié)合實(shí)例來講解吧

實(shí)例：

現(xiàn)在有字符串“AABCBBABC”，現(xiàn)在對其進(jìn)行編碼。

一開始，窗口滑入如圖位置

由圖可見，待編碼緩沖區(qū)有“AAB”三個(gè)字符，此時(shí)搜索緩沖區(qū)還是空的。所以編碼***個(gè)字符，由于搜索區(qū)為空，故找不到匹配串，輸出(0,0, A),窗口右移一個(gè)單位，如下圖

此時(shí)待編碼區(qū)有“ABC”。開始編碼。***編碼”A”，在搜索區(qū)找到”A”。由于沒有超過待編碼區(qū)，故開始編碼”AB”，但在搜索區(qū)沒有找到匹配字符串，故無法編碼。因此只能編碼”A”。

輸出(1, 1)。即為相對于待編碼區(qū)，偏移一個(gè)單位，匹配長度為1。窗口右滑動匹配長度，即移動1個(gè)單位。如下圖

一樣，沒找到，輸出(0, 0, B),右移1個(gè)單號，如下圖

輸出（0， 0， C）,右移1個(gè)單位，如下圖

輸出(2, 1),右移1個(gè)單位，如下圖

輸出(3, 1)， 右移1個(gè)單位，如下圖

開始編碼”A”，在搜索緩沖區(qū)查找到匹配字符串。由于待編碼緩沖區(qū)沒有超過，繼續(xù)編碼。開始編碼”AB”,也搜索到。不要停止，繼續(xù)編碼“ABC”，找到匹配字符串。由于繼續(xù)編碼，則超過了窗口，故只編碼“ABC”，輸出(5, 3),偏移5，長度3。右移3個(gè)單位，如下圖

此時(shí)待編碼緩沖區(qū)為空，停止編碼。

最終輸出結(jié)果如下

python代碼實(shí)現(xiàn)：

class Lz77:
    def __init__(self, inputStr):
        self.inputStr = inputStr #輸入流
        self.searchSize = 5    #搜索緩沖區(qū)(已編碼區(qū))大小
        self.aheadSize = 3     #lookAhead緩沖區(qū)（待編碼區(qū)）大小 
        self.windSpiltIndex = 0 #lookHead緩沖區(qū)開始的索引
        self.move = 0
        self.notFind = -1   #沒有找到匹配字符串

    #得到滑動窗口的末端索引
    def getWinEndIndex(self):
        return self.windSpiltIndex + self.aheadSize

    #得到滑動窗口的始端索引
    def getWinStartIndex(self):
        return self.windSpiltIndex - self.searchSize

    #判斷l(xiāng)ookHead緩沖區(qū)是否為空
    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.設(shè)置窗口下一步需要滑動的距離
            self.setMoveSteps(matchLen) 
            if matchLen == 0:
                #匹配為0，說明無字符串匹配，輸出下一個(gè)需要編碼的字母
                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.輸出結(jié)果
            self.output(result)    
            step = step + 1        #僅用來設(shè)置第幾步

    #滑動窗口(移動分界點(diǎn))
    def winMove(self):
        self.windSpiltIndex = self.windSpiltIndex + self.move

    #尋找***匹配字符并返回相對于窗口分界點(diǎn)的偏移值和匹配長度
    def findMaxMatch(self):
        matchLen = 0
        offset = 0
        minEdge = self.minEdge() + 1  #得到編碼區(qū)域的右邊界
        #遍歷待編碼區(qū)，尋找***匹配串
        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  #每找到一個(gè)匹配串，加1

        return (offset, matchLen)

    #入?yún)⒆址欠翊嬖谟谒阉骶彌_區(qū)，如果存在，返回匹配字符串的起始索引
    def searchBufferOffest(self, i):
        searchStart = self.getWinStartIndex()
        searchEnd = self.windSpiltIndex 
        #下面幾個(gè)if是處理開始時(shí)的特殊情況
        if searchEnd < 1:
            return self.notFind
        if searchStart < 0:
            searchStart = 0
            if searchEnd == 0:
                searchEnd = 1
        searchStr = self.inputStr[searchStart : searchEnd]  #搜索區(qū)字符串
        findIndex = searchStr.find(self.inputStr[self.windSpiltIndex : i])
        if findIndex == -1:
            return -1
        return len(searchStr) - findIndex

    #設(shè)置下一次窗口需要滑動的步數(shù)
    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()

只是簡單的寫了下，沒有過多考慮細(xì)節(jié)，請注意，這不是最終的代碼，只是用來闡述原理，僅供參考。輸出結(jié)果就是上面的輸出（格式由于坑爹的博客園固定樣式，代碼位置有偏移，請注意）