LZ77 圧縮アルゴリズムのコーディング Python 実装原理の詳細な図による説明

前書き

LZ77 アルゴリズムは、1977 年にイスラエルの Abraham Lempel によって公開された可逆圧縮アルゴリズムです。 LZ77 は典型的な辞書ベースの圧縮アルゴリズムであり、現在の圧縮テクノロジの多くは LZ77 に基づいています。データ圧縮の分野でのその地位を考慮して、この記事ではその原理を画像とソースコードで詳しく紹介します。

原則の紹介:

まず、いくつかの専門用語を紹介します。

1.先読みバッファ(中国語でどう表現するかわかりませんが、エンコードされる領域を仮に呼んでいます):

エンコード待ちの領域

2. 検索バッファ:

既にエンコードされている領域、検索バッファ

3. スライドウィンドウ:

「検索バッファ」(左) + 「エンコードする領域」(右)を含む指定されたサイズのウィンドウ

次に、具体的なエンコードプロセスを紹介します。エンコードする領域、エンコーダーはスライドします。ウィンドウの検索バッファーは、一致する

string

が見つかるまで検索します。マッチング文字列の先頭文字列とエンコード対象のバッファとの距離を「オフセット値」といい、マッチング文字列の長さを「マッチング長」といいます。エンコード中、エンコーダーは最大の一致する文字列が見つかるまで検索領域内で検索を続け、(o, l) を出力します。ここで、o はオフセット値、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. to- の検索領域で最大一致文字列を見つけます。スライディングウィンドウのエンコードされた領域

3. 文字列が見つかった場合は(オフセット値、一致する長さ)、ウィンドウは前方にスライドして「一致する長さ」を出力します

4. 見つからない場合は、出力(0、 0、エンコードする領域の最初の文字)、ウィンドウが 1 単位スライドします

5. エンコードする領域が空でない場合は、手順 2 に戻ります

説明が複雑すぎるので説明しましょう例を挙げて説明します

例:

「AABCBBABC」という文字列があり、エンコードします。

最初に、ウィンドウは図に示す位置にスライドします

図からわかるように、エンコードされるバッファーには「AAB」という 3 つの文字があり、検索バッファーはまだ残っていますこの時点では空です。したがって、最初の文字をエンコードすると、検索領域が空であるため、一致する文字列が見つからず、(0,0, A) が出力され、以下に示すようにウィンドウが 1 単位右に移動します

このとき、エンコードする領域には「ABC」が存在します。コーディングを開始します。まず「A」をエンコードし、検索領域で「A」を見つけます。エンコード対象領域を超えていないため、「AB」のエンコードが開始されますが、検索範囲内に一致する文字列が見つからず、エンコードできません。したがって、「A」のみをエンコードできます。

出力 (1, 1)。つまり、エンコードされる領域に対して 1 単位だけオフセットされ、一致する長さは 1 になります。ウィンドウを右にスライドさせて長さに合わせます、つまり 1 単位移動します。下の図に示すように、

が見つかりません。(0, 0, B) を出力し、数値を 1 つ右にシフトします。 ) を右に 1 単位ずらし、

は (2, 1) を出力し、

は (3, 1) を右に 1 単位移動します。 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 中国語 Web サイトの他の関連記事を参照してください。