Detailed graphic explanation of the LZ77 compression algorithm coding Python implementation principle

Preface

The LZ77 algorithm is a lossless compression algorithm published by Israeli Abraham Lempel in 1977. LZ77 is a typical dictionary-based compression algorithm, and many current compression technologies are based on LZ77. In view of its status in the field of data compression, this article will introduce its principles in detail with pictures and source code.

Principle introduction:

First introduce a few professional terms.

1.lookahead buffer (I don’t know how to express it in Chinese, temporarily called the area to be encoded):

Area waiting for encoding

2. search buffer:

Already encoded area, search buffer

3. Sliding window:

Specified size window, including "search buffer" (left) + "area to be encoded" (right )

Next, the specific encoding process is introduced:

In order to encode the area to be encoded, the encoder searches in the search buffer of the sliding window until it finds a matching string . The distance between the starting string of the matching string and the buffer to be encoded is called the "offset value", and the length of the matching string is called the "matching length". When encoding, the encoder will keep searching in the search area until it finds the maximum matching string and outputs (o, l), where o is the offset value and l is the matching length. Then the window slides l and continues coding. If no matching string is found, (0, 0, c) is output, where c is the next character waiting to be encoded in the area to be encoded, and the window slides "1". The algorithm implementation will be similar to the following:

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;
 }

The main steps are:

1. Set the encoding position to the beginning of the input stream

2. Search in the area to be encoded in the sliding window The maximum matching string in the search area

3. If the string is found, output (offset value, matching length), and the window slides forward "matching length"

4. If not found , output (0, 0, the first character of the area to be encoded), and the window slides forward one unit

5. If the area to be encoded is not empty, return to step 2

Description It's really too complicated, let's explain it with examples

Example:

Now there is the string "AABCBBABC", now encode it.

At the beginning, the window slides into the position shown in the picture

As can be seen from the picture, there are three characters "AAB" in the buffer to be encoded. At this time, the buffer is searched The area is still empty. Therefore, when encoding the first character, since the search area is empty, no matching string can be found, (0,0, A) is output, and the window moves one unit to the right, as shown below

At this time, there is "ABC" in the area to be encoded. Start coding. First encode "A" and find "A" in the search area. Since the area to be encoded has not been exceeded, "AB" starts to be encoded, but no matching string is found in the search area, so it cannot be encoded. Therefore only "A" can be encoded.

Output(1, 1). That is, it is offset by one unit relative to the area to be encoded, and the matching length is 1. Slide the window to the right to match the length, that is, move 1 unit. As shown in the picture below

, if not found, output (0, 0, B), move 1 odd number to the right, as shown in the picture below

Output (0, 0, C), shift 1 unit to the right, as shown below

Output (2, 1), shift 1 unit to the right, As shown below

Output (3, 1), move 1 unit to the right, as shown below

开始编码”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()

只是简单的写了下，没有过多考虑细节，请注意，这不是最终的代码，只是用来阐述原理，仅供参考。输出结果就是上面的输出（格式由于坑爹的博客园固定样式，代码位置有偏移，请注意

The above is the detailed content of Detailed graphic explanation of the LZ77 compression algorithm coding Python implementation principle. For more information, please follow other related articles on the PHP Chinese website!