這篇文章給大家介紹Python中實(shí)現(xiàn)一個(gè)LZ77壓縮算法，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

成都創(chuàng)新互聯(lián)公司是專(zhuān)業(yè)的鶴慶網(wǎng)站建設(shè)公司，鶴慶接單;提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專(zhuān)業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行鶴慶網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專(zhuān)業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專(zhuān)業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

原理介紹：

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

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

等待編碼的區(qū)域

2. search buffer：

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

3.滑動(dòng)窗口：

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

接下來(lái)，介紹具體的編碼過(guò)程：

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

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è)置編碼位置為輸入流的開(kāi)始

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

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

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

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

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

實(shí)例：

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

一開(kāi)始，窗口滑入如圖位置

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

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

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

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

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

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

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

開(kāi)始編碼”A”，在搜索緩沖區(qū)查找到匹配字符串。由于待編碼緩沖區(qū)沒(méi)有超過(guò)，繼續(xù)編碼。開(kāi)始編碼”AB”,也搜索到。不要停止，繼續(xù)編碼“ABC”，找到匹配字符串。由于繼續(xù)編碼，則超過(guò)了窗口，故只編碼“ABC”，輸出(5,  3),偏移5，長(zhǎng)度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ū)開(kāi)始的索引self.move = 0self.notFind = -1   #沒(méi)有找到匹配字符串#得到滑動(dòng)窗口的末端索引def getWinEndIndex(self):return self.windSpiltIndex + self.aheadSize#得到滑動(dòng)窗口的始端索引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 Falsedef encoding(self):step = 0print("Step   Position   Match   Output")while not self.isLookHeadEmpty():#1.滑動(dòng)窗口self.winMove()#2. 得到***匹配串的偏移值和長(zhǎng)度(offset, matchLen) = self.findMaxMatch()#3.設(shè)置窗口下一步需要滑動(dòng)的距離self.setMoveSteps(matchLen) if matchLen == 0:#匹配為0，說(shuō)明無(wú)字符串匹配，輸出下一個(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        #僅用來(lái)設(shè)置第幾步#滑動(dòng)窗口(移動(dòng)分界點(diǎn))def winMove(self):self.windSpiltIndex = self.windSpiltIndex + self.move#尋找***匹配字符并返回相對(duì)于窗口分界點(diǎn)的偏移值和匹配長(zhǎng)度def findMaxMatch(self):matchLen = 0offset = 0minEdge = 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è)匹配串，加1return (offset, matchLen)#入?yún)⒆址欠翊嬖谟谒阉骶彌_區(qū)，如果存在，返回匹配字符串的起始索引def searchBufferOffest(self, i):searchStart = self.getWinStartIndex()
        searchEnd = self.windSpiltIndex #下面幾個(gè)if是處理開(kāi)始時(shí)的特殊情況if searchEnd < 1:return self.notFindif searchStart < 0:
            searchStart = 0if searchEnd == 0:
                searchEnd = 1searchStr = self.inputStr[searchStart : searchEnd]  #搜索區(qū)字符串findIndex = searchStr.find(self.inputStr[self.windSpiltIndex : i])if findIndex == -1:return -1return len(searchStr) - findIndex#設(shè)置下一次窗口需要滑動(dòng)的步數(shù)def setMoveSteps(self, matchLen):if matchLen == 0:
            self.move = 1else:
            self.move = matchLendef minEdge(self):return len(self.inputStr)  if len(self.inputStr) - 1 < self.getWinEndIndex() else self.getWinEndIndex() + 1def output(self, touple):print("%d      %d           %s     %s" % touple)if __name__ == "__main__":
    lz77 = Lz77("AABCBBABC")
    lz77.encoding()

關(guān)于Python中實(shí)現(xiàn)一個(gè)LZ77壓縮算法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

新聞名稱(chēng)：Python中實(shí)現(xiàn)一個(gè)LZ77壓縮算法
分享地址：http://jinyejixie.com/article26/ppiocg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、用戶(hù)體驗(yàn)、電子商務(wù)、虛擬主機(jī)、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)