Explication graphique détaillée de l'algorithme de compression LZ77 codant le principe de mise en œuvre de Python

Avant-propos

L'algorithme LZ77 est un algorithme de compression sans perte publié par l'Israélien Abraham Lempel en 1977. LZ77 est un algorithme de compression typique basé sur un dictionnaire, et de nombreuses technologies de compression actuelles sont basées sur LZ77. Compte tenu de son statut dans le domaine de la compression de données, cet article présentera ses principes en détail avec des images et le code source.

Introduction du principe :

Introduisez d'abord quelques termes professionnels.

1.lookahead buffer (je ne sais pas comment l'exprimer en chinois, appelé temporairement la zone à encoder) :

Zone en attente d'encodage

2. tampon de recherche :

Zone déjà codée, tampon de recherche

3. Fenêtre coulissante :

Une fenêtre de taille spécifiée, comprenant "tampon de recherche" (à gauche) + "zone à laquelle être encodé" (à droite)

Ensuite, le processus d'encodage spécifique est introduit :

Afin d'encoder la zone à encoder, l'encodeur recherche dans le tampon de recherche de la fenêtre coulissante jusqu'à ce qu'elle trouve la chaîne correspondante. La distance entre la chaîne de départ de la chaîne correspondante et le tampon à coder est appelée « valeur de décalage », et la longueur de la chaîne correspondante est appelée « longueur correspondante ». Lors de l'encodage, l'encodeur continuera à chercher dans la zone de recherche jusqu'à ce qu'il trouve la chaîne correspondante maximale et génère (o, l), où o est la valeur de décalage et l est la longueur correspondante. Ensuite, la fenêtre glisse l et continue le codage. Si aucune chaîne correspondante n'est trouvée, (0, 0, c) est affiché, c est le prochain caractère en attente d'être encodé dans la zone à encoder et la fenêtre fait glisser "1". La mise en œuvre de l'algorithme sera similaire à la suivante :

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

Les principales étapes sont :

1 Définissez la position d'encodage au début du flux d'entrée

2. . Dans la fenêtre coulissante à encoder Recherche de zone Recherchez la chaîne correspondante maximale dans la zone de recherche

3. Si la chaîne est trouvée, affichez (valeur de décalage, longueur correspondante), faites glisser la fenêtre vers l'avant "longueur correspondante".

4. Si s'il n'est pas trouvé, affichez (0, 0, le premier caractère de la zone à encoder), et la fenêtre avance d'une unité

5. encoded n'est pas vide, revenez à l'étape 2

La description est trop compliquée, expliquons-la avec des exemples

Exemple :

Maintenant il y a la chaîne "AABCBBABC", maintenant encodez-le.

Au début, la fenêtre glisse dans la position indiquée sur l'image

Comme on peut le voir sur l'image, il y a trois caractères "AAB" dans le tampon à encoder A ce moment, le tampon est recherché La zone est toujours vide. Par conséquent, lors de l'encodage du premier caractère, puisque la zone de recherche est vide, aucune chaîne correspondante ne peut être trouvée, (0,0, A) est affiché et la fenêtre se déplace d'une unité vers la droite, comme indiqué ci-dessous

À ce moment, il y a "ABC" dans la zone à encoder. Commencez à coder. Encodez d’abord « A » et recherchez « A » dans la zone de recherche. Puisque la zone à coder n'a pas été dépassée, le codage de "AB" commence, mais aucune chaîne correspondante n'est trouvée dans la zone de recherche, le codage ne peut donc pas être effectué. Par conséquent, seul « A » peut être codé.

Sortie (1, 1). Autrement dit, il est décalé d'une unité par rapport à la zone à coder et la longueur correspondante est de 1. Faites glisser la fenêtre vers la droite pour correspondre à la longueur, c'est-à-dire déplacez-la d'1 unité. Comme le montre l'image ci-dessous

, il n'est pas trouvé Sortie (0, 0, B) et déplacez 1 nombre impair vers la droite, comme le montre l'image ci-dessous.

Sortie (0, 0, C), décaler vers la droite de 1 unité, comme indiqué ci-dessous

Sortie ( 2, 1), décale vers la droite de 1 unité, comme indiqué dans la figure ci-dessous,

sorties (3, 1), et décale vers la droite de 1 unité, comme indiqué dans la figure ci-dessous

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

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!