LZ77 圧縮アルゴリズムエンコーディング Python 実装原理図

序文

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

原則の紹介:

まず最初に専門用語をいくつか紹介します。

1. 先読みバッファ（中国語でどう表現したらいいか分からないので、とりあえずエンコード領域と呼ぶ）：

エンコード待ちのエリア

2. 検索バッファ:

すでにエンコードされた領域、検索バッファ

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

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

次に、具体的なエンコードプロセスを紹介します。

エンコードする領域をエンコードするために、エンコーダーは一致する文字列が見つかるまでスライディングウィンドウ内の検索バッファーを検索します。一致する文字列の開始文字列とエンコードするバッファ間の距離を「オフセット値」と呼び、一致する文字列の長さを「一致長」と呼びます。エンコード時に、エンコーダーは最も一致する文字列が見つかるまで検索領域を検索し続け、(o, l) を出力します。ここで、o はオフセット値、l は一致する長さです。その後、ウィンドウがスライドしてエンコードを続行します。一致する文字列が見つからない場合は、(0, 0, c) が出力されます。ここで、c はエンコード領域でエンコードされる次の文字であり、ウィンドウは "1" スライドします。アルゴリズムの実装は次のようになります。

 while ( lookAheadBuffer が空ではない )
 {
 lookAheadBufferのウィンドウ内で最も長い一致へのポインタ( position, match )を取得します。
(位置、長さ、 char ( )) を出力する。
 ウィンドウの長さ+1文字分シフトします。
 }

主な手順は次のとおりです。

1. エンコード位置を入力ストリームの先頭に設定する

2. スライディングウィンドウ内のエンコードする領域の検索領域で、最も一致する文字列を検索する

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 数値右にシフト、以下に示すように

出力(0, 0, C)、右に1単位シフト、以下に示すとおり

出力(2, 1)、右に1単位シフト、以下に示すとおり

出力(3, 1)、右に1単位シフト、以下に示すとおり

「A」のエンコードを開始し、検索バッファ内で一致する文字列を検索します。エンコードするバッファが超過していないため、エンコードは続行されます。「AB」とコーディングを開始すると、これも検索されます。止まらずに、「ABC」のエンコードを続けて、一致する文字列を見つけます。エンコードが継続されるため、ウィンドウを超えてしまうため、「ABC」のみがエンコードされ、出力は (5, 3)、オフセット 5、長さ 3 になります。下図のように右に3単位移動します。

このとき、エンコード対象のバッファが空なので、エンコードは停止します。

最終的な出力は次のようになります

Python コードの実装:

クラスLz77 :
    def __init__ (self, inputStr) :
        self.inputStr = inputStr #入力ストリーム
        self.searchSize = 5 #検索バッファ（エンコード領域）のサイズ
        self.aheadSize = 3 #先読みバッファ（エンコードする領域）のサイズ
        self.windSpiltIndex = 0 #lookHead バッファ開始インデックス
        自己移動 = 0
        self.notFind = -1 #一致する文字列が見つかりません

    #スライディングウィンドウの終了インデックスを取得します
    def getWinEndIndex (self) :
        self.windSpiltIndex + self.aheadSizeを返す

    #スライディングウィンドウの開始インデックスを取得します
    def getWinStartIndex (self) :
        self.windSpiltIndex - self.searchSizeを返す

    #lookHeadバッファが空かどうかを判断します
    def isLookHeadEmpty (self) :
        self.windSpiltIndex + self.move > len(self.inputStr) - 1 の場合はTrueを返し、それ以外の場合はFalse を返します。

    defエンコーディング（自己） :
        ステップ = 0
        print( "ステップ位置一致出力" )
        self.isLookHeadEmpty()ではない場合:
            #1. スライディングウィンドウ
            自己.winMove()
            #2. *** に一致する文字列のオフセット値と長さを取得します
            (オフセット、マッチ長さ) = self.findMaxMatch()
            #3. ウィンドウが次にスライドする距離を設定する
            self.setMoveSteps(マッチ長さ) 
            matchLen == 0の場合:
                #一致は0で、文字列の一致がないことを示し、次にエンコードされる文字が出力されます
                次の文字 = self.inputStr[self.windSpiltIndex]
                結果 = (step, self.windSpiltIndex, '-' , '(0,0)' + nextChar)
            それ以外：
                結果 = (step, self.windSpiltIndex, self.inputStr[self.windSpiltIndex - offset: self.windSpiltIndex - offset + matchLen], '(' + str(offset) + ',' + str(matchLen) + ')' )
            #4. 出力結果
            自己.出力(結果)    
            step = step + 1 #ステップ数を設定するためにのみ使用されます

    #スライディングウィンドウ（移動する分割点）
    def winMove (self) :
        self.windSpiltIndex = self.windSpiltIndex + self.move

    #*** に一致する文字を検索し、ウィンドウの分割点を基準としたオフセット値と一致長さを返します
    def findMaxMatch (self) :
        マッチ長さ = 0
        オフセット = 0
        minEdge = self.minEdge() + 1 #エンコード領域の右端を取得します
        #エンコードする領域を走査し、*** に一致する文字列を検索します
        i が範囲内(self.windSpiltIndex + 1 、minEdge)の場合:
            #print("i: %d" %i)
            オフセット温度 = self.searchBufferOffest(i)
            offsetTemp == self.notFind の場合: 
                （オフセット、マッチ長さ）を返す
            offset = offsetTemp #オフセット値

            matchLen = matchLen + 1 #一致する文字列が見つかるたびに1を加算します

        （オフセット、マッチ長さ）を返す

    #入力文字列が検索バッファ内に存在するかどうかを調べ、存在する場合は一致する文字列の開始インデックスを返します
    def searchBufferOffest (self, i) :
        検索開始 = self.getWinStartIndex()
        searchEnd = self.windSpiltIndex 
        #次のifはプロセス開始時の特別なケースです
        searchEnd < 1 の場合:
            自己を返す。
        searchStart < 0の場合:
            検索開始 = 0
            searchEnd == 0 の場合:
                検索終了 = 1
        searchStr = self.inputStr[searchStart : searchEnd] #検索範囲の文字列
        findIndex = searchStr.find(self.inputStr[self.windSpiltIndex: i]) です。
        findIndex == -1 の場合:
            -1を返す
        len(searchStr)を返す- findIndex

    #次回ウィンドウをスライドさせるステップ数を設定します
    def setMoveSteps (self, matchLen) : 移動ステップの設定
        matchLen == 0の場合:
            自己移動 = 1
        それ以外：
            自己移動 = マッチ長さ

    minEdge (self)を定義します:
        len(self.inputStr)を返します。 len(self.inputStr) - 1 < self.getWinEndIndex()の場合、そうでない場合はself.getWinEndIndex() + 1 です。

    def出力（自己、タプル） ：
        print( "%d %d %s %s" % タプル)

__name__ == "__main__"の場合:
    lz77 = Lz77( "AABCBBABC" )
    lz77.エンコーディング()