LZ77 압축 알고리즘 코딩 Python 구현 원리에 대한 자세한 그래픽 설명

서문

LZ77 알고리즘은 이스라엘의 아브라함 렘펠(Abraham Lempel)이 1977년 발표한 무손실 압축 알고리즘이다. LZ77은 대표적인 사전 기반 압축 알고리즘으로 현재 많은 압축 기술이 LZ77을 기반으로 하고 있습니다. 데이터 압축 분야에서의 현황을 고려하여 이 글에서는 그 원리를 그림과 소스코드와 함께 자세히 소개하겠습니다.

원리 소개:

먼저 몇 가지 전문 용어를 소개합니다.

1. Lookahead 버퍼(한자로 어떻게 표현해야 할지 몰라 임시로 인코딩할 영역이라고 함) :

인코딩을 기다리는 영역

2. 검색 버퍼:

이미 인코딩된 영역, 검색 버퍼

3. 슬라이딩 윈도우:

"검색 버퍼"(왼쪽) + "검색할 영역"을 포함한 지정된 크기의 창 be encoded" (right )

다음으로 구체적인 인코딩 과정을 소개합니다.

인코딩할 영역을 인코딩하기 위해 인코더는 슬라이딩 윈도우의 검색 버퍼에서 해당 영역이 나올 때까지 검색합니다. 일치하는 문자열 을 찾습니다. 일치하는 문자열의 시작 문자열과 인코딩할 버퍼 사이의 거리를 "오프셋 값"이라 하고, 일치하는 문자열의 길이를 "일치 길이"라고 합니다. 인코딩할 때 인코더는 일치하는 최대 문자열을 찾을 때까지 검색 영역에서 계속 검색하고 (o, l)을 출력합니다. 여기서 o는 오프셋 값이고 l은 일치하는 길이입니다. 그런 다음 창이 슬라이드 l되고 코딩이 계속됩니다. 일치하는 문자열이 없으면 (0, 0, c)가 출력되고, c는 인코딩할 영역에서 인코딩을 기다리는 다음 문자이고 창은 "1"로 슬라이드됩니다. 알고리즘 구현은 다음과 유사합니다.

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. 인코딩 위치를 입력 스트림의 시작 부분으로 설정합니다.

2. 슬라이딩 윈도우에서 인코딩할 영역에 검색 영역에서 최대 일치 문자열

3. 문자열이 발견되면 출력(오프셋 값, 일치 길이), 창을 앞으로 밀어 "일치 길이"

4. 찾을 수 없으면 출력(0, 0, 인코딩할 영역의 첫 번째 문자)하고 창을 한 단위 앞으로 밉니다.

5. 비어 있음, 2단계로 돌아가기

설명 너무 복잡합니다. 예를 들어 설명하겠습니다.

예:

이제 "AABCBBABC" 문자열이 있으니 인코딩해 보겠습니다.

처음에는 창이 그림과 같은 위치로 미끄러져 들어갑니다

그림을 보면 알 수 있듯이 "AAB"라는 글자가 3개 있습니다. 인코딩할 버퍼에서 버퍼를 검색합니다. 해당 영역은 여전히 ​​비어 있습니다. 따라서 첫 번째 문자를 인코딩하면 검색 영역이 비어 있으므로 일치하는 문자열을 찾을 수 없으며 (0,0, A)가 출력되고 아래와 같이 창이 오른쪽으로 한 단위 이동합니다

이때, 인코딩할 부분에 "ABC"가 있습니다. 코딩을 시작하세요. 먼저 "A"를 인코딩하고 검색 영역에서 "A"를 찾으세요. 인코딩할 영역을 초과하지 않았기 때문에 "AB"의 인코딩이 시작되지만, 검색 영역에 일치하는 문자열이 없어 인코딩을 수행할 수 없습니다. 따라서 "A"만 인코딩할 수 있습니다.

출력(1, 1). 즉, 인코딩할 영역을 기준으로 1 단위만큼 오프셋되어 일치하는 길이가 1이 된다. 창을 오른쪽으로 밀어서 길이에 맞게, 즉 1단위 이동합니다. 아래 그림

과 같이 발견되지 않고(0,0,B) 아래 그림과 같이 홀수 1개를 오른쪽으로 이동합니다.

출력(0, 0, C), 아래와 같이 1단위 오른쪽으로 이동

출력( 2, 1), 오른쪽으로 1단위 이동, 아래 그림과 같이

는 (3, 1)을 출력하고, 오른쪽으로 1단위 이동합니다. 아래 그림에서

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

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

위 내용은 LZ77 압축 알고리즘 코딩 Python 구현 원리에 대한 자세한 그래픽 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!