ロスレス情報圧縮。 パート2

最初の部分。



2番目の部分では、算術コーディングとバロウズウィーラー変換を検討します（後者は多くの記事でしばしば忘れられがちです）。 HabréにはすでにLZアルゴリズムに関する良い記事があったので、LZアルゴリズムのファミリーは検討しません。



それでは、算術コーディングから始めましょう-私の意見では、最もエレガントな（アイデアの観点から）圧縮方法の1つです。

はじめに

最初の部分では、ハフマンコーディングについて説明しました。 これは時間をかけて検証された素晴らしいアルゴリズムであるという事実にもかかわらず、（他のすべてのアルゴリズムと同様に）欠点がないわけではありません。 ハフマンアルゴリズムの弱点を例を挙げて説明します。 ハフマン法を使用してエンコードする場合、ストリーム内の文字の出現頻度は、2のべき乗の倍数に近づきます。 シャノンの定理により、周波数fの各文字が-log ₂ fビットを使用してエンコードされている場合、最適な圧縮が達成されることを思い出させてください。 小さなスケジュールを作成します（美しいスケジュールを作成するのが苦手なので、事前に謝罪します）。





ご覧のとおり、相対周波数が2のべき乗ではない場合、アルゴリズムの効率は明らかに低下します。 これは、それぞれ周波数253/256および3/256の2つのシンボルaおよびbのストリームの簡単な例で簡単に検証できます。 この場合、理想的には、 、つまり24ビット。 同時に、Huffmanメソッドはこれらの文字をそれぞれコード0および1でエンコードし、メッセージは256ビットを使用しますが、もちろん元のメッセージの256バイト未満です（各文字のサイズは最初にバイト単位であると仮定します）が、最適値の10分の1。



それでは、算術コーディングの検討に移りましょう。これにより、最良の結果を得ることができます。

算術コーディング

ハフマン法と同様に、算術符号化はエントロピー圧縮法です。 エンコードされたデータは、テキストを最もコンパクトな方法で表示できるように選択される分数の形式で表示されます。 これはどういう意味ですか？



区間[0,1）（計算の便宜上、このような区間が選択されます）、および単語「ボックス」の形式の入力データの例での分数の構成を検討してください。 私たちのタスクは、最初の間隔を、キャラクターの出現確率に等しい長さのサブ間隔に分割することです。



入力テキストの確率表を作成しましょう。

記号	頻度	確率	範囲
ああ	2	0.4	[0.0、0.4）
に	1	0.2	[0.4、0.6）
P	1	0.2	[0.6、0.8）
B	1	0.2	[0.8、1.0）

ここで、「頻度」とは、入力ストリーム内の文字の出現回数を意味します。



これらの量は、エンコードとデコードの両方で既知であると想定しています。 シーケンスの最初の文字（この場合、「 To 」） をエンコードする場合、0から1の範囲全体が使用されます。この範囲は、表に従ってセグメントに分割する必要があります。

作業間隔として、現在のエンコードされた文字に対応する間隔が取られます。 この間隔の長さは、ストリーム内のシンボルの出現頻度に比例します。

現在のシンボルの間隔を見つけた後、この間隔は拡大し、前の間隔と同様に周波数に従って分割されます（つまり、例2の場合、同じ方法で0.4から0.6の間隔をサブ間隔に分割する必要があります最初のステップで行ったように）。 このプロセスは、ストリームの最後の文字がエンコードされるまで続きます。

つまり、i番目の文字には間隔が割り当てられます



ここで、Nはアルファベットの文字数、p _iはi番目の文字の確率です。



私たちの場合、このように見えます







そのため、最後の文字の間隔が0.45312から0.4544になるまで、入力ストリームの各文字の間隔を順次狭くしました。 それがコーディング時に使用するものです。



ここで、この間隔にある任意の数を取る必要があります。 0.454としましょう。 驚いたことに（しかし、私がこの方法を研究していたとき、それは非常に驚くべきことでした）、この数とシンボル周波数の値は、元のメッセージを完全に復元するのに十分です。



ただし、実装を成功させるには、分数をバイナリ形式で表す必要があります。 分数をバイナリ形式で表現することの特性により（10進法で有限数の桁を持つ一部の分数はバイナリで無限の桁数を持っていることを思い出します）、エンコードは通常、ターゲット範囲の上限と下限に基づいています。



デコードはどのように機能しますか？ デコードは同様の方法で行われます（逆の順序ではなく、同様の方法で）。



シンボルの頻度に応じて、0から1までの間隔から始めます。 数値が下がる間隔（0.454）をチェックします。 この間隔に対応する文字は、シーケンスの最初の文字になります。 次に、この間隔をスケール全体に拡張し、手順を繰り返します。



私たちの場合、プロセスは次のようになります。





もちろん、間隔を短くして精度を上げ、「シンボル」をどんどん増やすことを妨げるものは何もありません。 したがって、この方法でエンコードする場合は、元のメッセージの文字数を事前に知るか、メッセージの終わりを正確に判断できるようにメッセージを一意の文字に制限する必要があります。



アルゴリズムを実装するとき、いくつかの要因を考慮する価値があります。 まず、上記の形式のアルゴリズムでは、ビット深度の制限により短い文字列のみをエンコードできます。 この制限を回避するために、実際のアルゴリズムは整数で動作し、分子と分母が整数である分数で動作します。



算術符号化の圧縮率を評価するには、最小数Nを見つける必要があります。これにより、作業間隔内で、最後の文字を圧縮するときに、符号がゼロのみであるバイナリ表現の数を明らかに見つけることができます。 このため、間隔の長さは1/2 ^N以上でなければなりません^。 また、間隔の長さがすべてのシンボルの確率の積に等しいことも知られています。



記事の冒頭で提案された確率253/256および3/256のシンボルaおよびbのシーケンスを考えます。 256文字の文字列の最後の作業間隔の長さは次と等しくなります。





この場合、目的のNは24に等しくなります（23は間隔が大きすぎるため、25は最小ではありません）。つまり、ハフマン法の256ビットに対して24ビットのみのコーディングに費やします。

バローズ-ウィーラー変換

そのため、圧縮方法が異なるデータセットで異なる効率を示すことがわかりました。 これから進むと、かなり論理的な疑問が生じます。特定のデータに対して圧縮アルゴリズムがうまく機能する場合、圧縮前にデータに対して何らかの操作を実行して「品質」を向上させることは可能でしょうか。



はい、可能です。 説明するために、複雑な依存関係を持つデータブロックを、構造がより簡単にモデル化されるブロックに変換する、バロウズウィーラー変換を検討してください。 当然、この変換も完全に可逆的です。 このメソッドの作成者は、David WheelerとMike Burrowsです（Wikiによれば、Michael Burrows、彼は現在Googleで働いています）。



そのため、Burrows-Wheelerアルゴリズム（以降、簡潔にするためにBTW-Burrows-Wheeler Transformと呼びます）は、入力ブロックをより便利な圧縮形式に変換します。 しかし、実践が示すように、ブロックの変換の結果として得られる従来の方法は、このために特別に開発された方法ほどうまく圧縮されないため、実際の使用では、対応するデータエンコーディング方法とは別にBWTアルゴリズムを考慮することはできませんが、その動作の原理を研究することですそれには何の問題もありません。



1994年に公開された元の記事では、著者は3つのアルゴリズムのコーディングの実装を提案しました。

• 実際、BWT
• ロシア文学では書籍のスタックを移動することで知られる、Move-to-Front変換
• データの最初の2段階で取得された統計圧縮エンコーダー。

確かに、2番目のステップは別の同様のアルゴリズムに置き換えることも、エンコードフェーズの複雑さのために完全に除外することもできます。 BWT はデータのサイズに影響を与えず 、ブロックの配置を変更するだけであることを理解することが重要です。

変換アルゴリズム

BWTはブロックアルゴリズムです。つまり、データブロックで動作し、特定のサイズのブロックの要素の構成について事前に知っています。 これにより、文字単位の圧縮またはオンザフライ圧縮が必要な場合にBWTを使用することが難しくなります。 原則として、このような実装は可能ですが、アルゴリズムは非常に高速ではありません。



変換原理は非常に簡単です。 古典的な「本」の例-「アブラカダブラ」という言葉で考えてみましょう。これは、いくつかの基準に完全に適合しています。繰り返し文字が多く、これらの文字は単語全体に均等に分布しています。



変換の最初のステップは、ソースデータの循環順列のリストをコンパイルすることです。 つまり、初期データを取得し、最後の文字を最初の場所に移動します（またはその逆）。 元の文字列を再度取得するまで、この操作を実行します。 このようにして得られたすべての行は、すべて巡回置換になります。 この場合、次のようになります。

これは文字のマトリックスと見なします。各セルはそれぞれ1文字で、行は単語全体に対応します。 元の行をマークし、マトリックスをソートします。

ソートは最初に最初の文字で実行され、次に最初の文字が一致する行（2番目の行など）に対して行われます。 このようなソートの後、マトリックスは次の形式を取ります。

    –          
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般に、これで変換はほぼ終了します。残りの作業は、元の行の番号を忘れずに最後の列を書き留めることだけです。 これを行うと、以下が得られます。

 «>><<»
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

または、別の方法で、

 «»,2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のように、文字の分布が大幅に改善されました。5文字のうち4文字「a」が隣り合っており、両方の文字「b」が並んでいます。

可逆性

前述したように、変換は完全に可逆です。 そうでないと意味をなさないため、これは理解できます。 では、メッセージの元の外観を復元する方法は？



まず、キャラクターを順番に並べる必要があります。 これにより、文字列「aaaaabbdkrr」が得られます。 循環順列のマトリックスは順番に並べ替えられているため、この文字列は循環順列のマトリックスの最初の列にすぎません。 さらに、最後の列（実際には、変換自体の結果）も知っています。 そのため、この段階で、マトリックスを次のように復元できます。

でも	...	p
でも	...	d
でも	...	でも
でも	...	に
でも	...	p
b	...	でも
b	...	でも
d	...	でも
に	...	でも
p	...	b
p	...	b

マトリックスは循環シフトによって取得されたため、最後の列と最初の列の文字はペアを形成します。 これらのペアを昇順で並べ替えると、最初の2列が取得されます。 次に、これらの2つの列と最後のフォームはすでに文字のトリプルを形成します。

最後に、マトリックスを完全に復元します。ソースデータを含む行の番号がわかっているため、元の形式を簡単に取得できます。



つまり、復元は次のように実行されます。

1. 左の最後の列の文字を最初の列の文字に添付します
2. 最後を除くすべての列を並べ替える

マトリックスが完全に満たされるまで、これらの2つのステップを繰り返す必要があります。



この例では、最初の4つの回復手順は次のようになります。

  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...  ->  ->  ->  ->...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

職場でのリソースコスト

データの可逆性を証明した後、アルゴリズムの実装には行列全体をメモリに保存する必要がないことを証明します。 実際、たとえば1メガバイトのブロックに対応するマトリックスを完全に保存した場合、マトリックスは正方形であるため、膨大な量のメモリが必要になります。 当然、このオプションは受け入れられません。



逆変換の場合、実際のデータに加えて、逆変換のベクトル（ブロック内の文字数に等しいサイズの数値の配列）が必要です。 したがって、線形変換中のメモリオーバーヘッドは、ブロックサイズに比例して増加します。



逆変換中に、マトリックスの次の列を取得するために同じアクションが実行されました。 つまり、新しい行は、古い行の最後の列の文字と同じ行の既知の文字を組み合わせることによって取得されました。 もちろん、ソート後、新しい行はマトリックス内の別の位置に移動しました。 列を追加するとき、新しい位置への行の移動が同じであることが重要です。 逆変換ベクトルを取得するには、最後の文字から最初の列の文字を取得する順序を決定する必要があります。つまり、新しい行番号で行列を並べ替えます







変換ベクトルは、行番号の値から形成されます：{2,5,6,7,8,9,10,1,3,3,4}。



これで、簡単に元の文字列を取得できます。 行列の元の行の番号に対応する逆変換ベクトルの要素を取得します。T[2] = 6。 つまり、元の文字列の最初の文字として、文字列「rdakraaaabb」の6番目の文字、つまり文字「a」を取得する必要があります。

その後、見つかったシンボル「a」が同じシンボルの中で2番目の位置に移動したシンボルを調べます。 これを行うには、文字「a」が取得された文字列の変換ベクトルから数値を取得します。これは数値6です。

次に、行番号6を見て、そこから最後の文字を選択します-これが文字「b」です。 残りの文字についてこの手順を続けると、元の文字列を簡単に復元できます。

書籍の移動スタック

書籍のスタックの移動は、BWTの後、直接コーディングの前に使用することを著者が推奨する中間アルゴリズムです。 アルゴリズムは次のように機能します。



前のパートでBWTで取得した「rdakraaaabb」という行を考えてみましょう。 この場合、アルファベットは5文字で構成されています。 それらを注文すると、

M = {a、b、d、k、p}。



そのため、ライン上で書籍のスタックを移動するアルゴリズムを使用します。 文字列の最初の文字（ "p"）は、4番目のアルファベットにあります。 この番号（4）を出力ブロックに書き込みます。 次に、最初に使用したシンボルを最初に配置し、2番目のシンボルでプロセスを繰り返し、3番目のシンボルでプロセスを繰り返します。 処理は次のようになります（「番号」の下では、出力ストリームに送られる番号を想定しています）。

記号	アルファベット	数
p	abdkr	4
d	rabdk	3
でも	単調	2
に	adrbk	4
p	クラブ	3
でも	rkadb	2
でも	arkdb	0
でも	arkdb	0
でも	arkdb	0
b	arkdb	4
b	樹皮	0

結果はシーケンスになります

 43243200040
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この段階では、このアルゴリズムがどの程度優れているかは完全には明らかではありません。 実際、良い使用法があります。 より抽象的なシーケンスを考えてみましょう：

開始するには、Huffmanメソッドを使用してエンコードします。 明確にするために、書籍のスタックの移動を使用する場合と、それを使用しない場合のツリーの保存コストは同じであると想定しています。

この場合、4文字すべてが出現する確率は¼に等しく、つまり、各文字のエンコードには2ビットが必要です。 エンコードされた文字列は40ビットかかると計算するのは簡単です。

ここで、書籍のスタックを移動するアルゴリズムを使用して行を変更しましょう。 最初は、アルファベットの形式は

 M={,,,}.
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アルゴリズムを使用した後、文字列は次のようになります

 10002000030000300003
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合、文字の出現頻度は大きく異なります。

記号	頻度	確率	ハフマンコード
0	15	3/4	0
3	3	3/20	10
2	1	1/20	110
1	1	1/20	111

この場合、コーディング後、15 + 6 + 3 + 3 = 27ビットのシーケンスを取得します。これは、書籍のスタックを移動せずに取得される40ビットよりもはるかに少ないです。

おわりに

そのため、この記事では、算術コーディングと、より便利な圧縮ストリームを取得できる変換アルゴリズムについて検討しました。 BWTなどのアルゴリズムの使用は、入力ストリームに大きく依存していることに注意してください。 効率は、文字の辞書式シーケンス、エンコーダーのバイパスの方向（左から右または右から左への圧縮）、ブロックサイズなどの要因の影響を受けます。 記事の次の部分では、実際のエンコーダーで使用されているより複雑なアルゴリズムを検討します（これはまだ決めていません）。

文学

• Vatolin D.、Ratushnyak A.、Smirnov M. Yukin V.データ圧縮方法。 デバイスアーカイバ、画像およびビデオ圧縮。 ISBN 5-86404-170-X; 2003年
• リドフスキーV.V.情報理論：教科書。 -M。：Sputnik + Company、2004年。
• Semenyuk V.V.個別情報の経済的なコーディング。 -SPb。：SPbGITMO（TU）、2001
• ウィッテンIH、ニールRM、データ圧縮のためのCleary JG算術コーディング、CACM、1987年。