Detaillierte grafische Erläuterung des Python-Implementierungsprinzips für die Codierung des LZ77-Komprimierungsalgorithmus

Vorwort

Der LZ77-Algorithmus ist ein verlustfreier Komprimierungsalgorithmus, der 1977 vom Israeli Abraham Lempel veröffentlicht wurde. LZ77 ist ein typischer wörterbuchbasierter Komprimierungsalgorithmus, und viele aktuelle Komprimierungstechnologien basieren auf LZ77. Angesichts seines Status im Bereich der Datenkomprimierung werden in diesem Artikel seine Prinzipien anhand von Bildern und Quellcode ausführlich vorgestellt.

Prinzipielle Einführung:

Führen Sie zunächst einige Fachbegriffe ein.

1. Lookahead-Puffer (ich weiß nicht, wie ich es auf Chinesisch ausdrücken soll, wird vorübergehend als zu kodierender Bereich bezeichnet):

Bereich, der auf die Kodierung wartet

2. Suchpuffer:

Bereits codierter Bereich, Suchpuffer

3. Schiebefenster:

Ein Fenster mit angegebener Größe, einschließlich „Suchpuffer“ (links) + „Bereich zu kodiert werden“ (rechts )

Als nächstes wird der spezifische Kodierungsprozess vorgestellt:

Um den zu kodierenden Bereich zu kodieren, sucht der Encoder im Suchpuffer des Schiebefensters, bis er findet die passende Zeichenfolge . Der Abstand zwischen der Startzeichenfolge der übereinstimmenden Zeichenfolge und dem zu codierenden Puffer wird als „Offsetwert“ bezeichnet, und die Länge der übereinstimmenden Zeichenfolge wird als „Übereinstimmungslänge“ bezeichnet. Beim Codieren sucht der Encoder so lange im Suchbereich, bis er die maximal passende Zeichenfolge findet und (o, l) ausgibt, wobei o der Offsetwert und l die passende Länge ist. Dann verschiebt sich das Fenster l und die Codierung wird fortgesetzt. Wenn keine passende Zeichenfolge gefunden wird, wird (0, 0, c) ausgegeben, c ist das nächste Zeichen, das im zu codierenden Bereich auf die Codierung wartet, und das Fenster gleitet auf „1“. Die Implementierung des Algorithmus ähnelt der folgenden:

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

Die Hauptschritte sind:

1 Setzen Sie die Codierungsposition auf den Anfang des Eingabestreams

2 . Suchen Sie im Schiebefenster nach der maximal passenden Zeichenfolge im Suchbereich

3. Wenn die Zeichenfolge gefunden wird (Versatzwert, passende Länge), schieben Sie das Fenster nach vorne „passende Länge“.

4. Wenn nicht gefunden, wird (0, 0, das erste Zeichen des zu kodierenden Bereichs) ausgegeben und das Fenster wird um eine Einheit nach vorne verschoben.

5 encoded ist nicht leer, kehren Sie zu Schritt 2 zurück

Die Beschreibung ist zu kompliziert, erklären wir es mit Beispielen

Beispiel:

Jetzt gibt es jetzt die Zeichenfolge „AABCBBABC“. kodieren Sie es.

Zu Beginn gleitet das Fenster in die im Bild gezeigte Position

Wie auf dem Bild zu sehen ist, gibt es drei Zeichen „AAB“ im zu kodierenden Puffer. Zu diesem Zeitpunkt wird der Puffer durchsucht. Der Bereich ist noch leer. Daher kann beim Codieren des ersten Zeichens keine passende Zeichenfolge gefunden werden, da der Suchbereich leer ist. (0,0, A) wird ausgegeben und das Fenster bewegt sich um eine Einheit nach rechts, wie unten gezeigt

Zu diesem Zeitpunkt befindet sich in dem zu kodierenden Bereich „ABC“. Beginnen Sie mit dem Codieren. Codieren Sie zunächst „A“ und suchen Sie „A“ im Suchbereich. Da der zu kodierende Bereich nicht überschritten wurde, beginnt die Kodierung von „AB“, es wird jedoch keine passende Zeichenfolge im Suchbereich gefunden, sodass die Kodierung nicht durchgeführt werden kann. Daher kann nur „A“ kodiert werden.

Ausgabe (1, 1). Das heißt, es ist um eine Einheit relativ zum zu kodierenden Bereich versetzt und die passende Länge beträgt 1. Schieben Sie das Fenster nach rechts, um es an die Länge anzupassen, d. h. um 1 Einheit zu verschieben. Wie im Bild unten gezeigt

wird der Ausgang (0, 0, B) nicht gefunden und um 1 ungerade Zahl nach rechts verschoben, wie im Bild unten gezeigt

Ausgabe (0, 0, C), um 1 Einheit nach rechts verschieben, wie unten gezeigt

Ausgabe ( 2, 1), um 1 Einheit nach rechts verschieben, wie in der Abbildung unten gezeigt,

gibt (3, 1) aus und verschiebt sich um 1 Einheit nach rechts, wie in gezeigt die Abbildung unten

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

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

Das obige ist der detaillierte Inhalt vonDetaillierte grafische Erläuterung des Python-Implementierungsprinzips für die Codierung des LZ77-Komprimierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!