上司と私は、画像処理に関する小さなモノグラフを準備しています。 私は画像圧縮アルゴリズムに関する章をhabrasocietyの裁判所に提出することにしました。 チャプター全体を1つの投稿に収めることは難しいため、3つの投稿に分割することにしました。

1.データ圧縮方法。

2.ロスレス画像圧縮。

3.損失のある画像の圧縮。

以下に、シリーズの最初の投稿があります。



現在、条件付きで2つの大きなグループに分けることができる無損失圧縮アルゴリズムが多数あります。

1.ストリームおよび辞書アルゴリズム。 RLE（ランレングスエンコーディング）、LZ *、および他のファミリのアルゴリズムはこのグループに属します。このグループのすべてのアルゴリズムの機能は、エンコーディング時にメッセージ内の文字の頻度に関する情報ではなく、以前に遭遇したシーケンスに関する情報が使用されることです

2.統計（エントロピー）圧縮のアルゴリズム。 このアルゴリズムのグループは、メッセージにさまざまな文字が出現する頻度の不均一性を使用して情報を圧縮します。 このグループのアルゴリズムには、算術およびプレフィックスコーディングのアルゴリズムが含まれます（シャノンファンノ、ハフマン、割線ツリーを使用）。

情報を変換するアルゴリズムは、個別のグループに区別できます。 このグループのアルゴリズムは情報を直接圧縮しませんが、それらのアプリケーションは、ストリーム、辞書、およびエントロピーアルゴリズムを使用したさらなる圧縮を大幅に簡素化します。

スレッドと辞書のアルゴリズム

シリーズの長さのコーディング

ランレングスエンコーディング（RLE）は、最も単純で最も一般的なデータ圧縮アルゴリズムの1つです。 このアルゴリズムでは、繰り返し文字のシーケンスが文字と反復回数に置き換えられます。

たとえば、ストレージに5バイトを必要とする文字列「AAAAA」（1文字の格納に1バイトが割り当てられている場合）は、2バイトで構成される「5A」に置き換えることができます。 明らかに、このアルゴリズムは一連の繰り返しが長いほど効果的です。



このアルゴリズムの主な欠点は、非繰り返し文字のシーケンスでの効率が極端に低いことです。 たとえば、シーケンス "ABABAB"（6バイト）を考慮すると、RLEアルゴリズムを適用した後、 "1A1B1A1B1A1B"（12バイト）に変わります。 非反復文字の問題を解決するには、さまざまな方法があります。



最も簡単な方法は、次の変更です。反復回数をエンコードするバイトには、反復回数だけでなく、その可用性に関する情報も格納する必要があります。 最初のビットが1の場合、次の7ビットは対応する文字の繰り返し数を示し、最初のビットが0の場合、次の7ビットは繰り返しなしで取得される文字数を示します。 この変更を使用して「ABABAB」をエンコードすると、「-6ABABAB」（7バイト）が得られます。 明らかに、提案された手法は、文字の非反復シーケンスでのRLEアルゴリズムの効率を大幅に向上させることができます。 提案されたアプローチの実装をリスト1に示します。

1. タイプ
2. TRLEEncodedString = バイトの 配列 。
3. 関数 RLEEncode （ InMsg ： ShortString ） ： TRLEEncodedString ;
4. var
5. MatchFl ： ブール値 ;
6. MatchCount ： shortint ;
7. EncodedString ： TRLEEncodedString ;
8. N 、 i ： バイト 。
9. 始める
10. N ： = 0 ;
11. SetLength （ EncodedString 、 2 *長さ（ InMsg ） ） ;
12. 一方、長さ（ InMsg ） > = 1 do
13. 始める
14. MatchFl ： = （長さ（ InMsg ） > 1 ） および （ InMsg [ 1 ] = InMsg [ 2 ] ） ;
15. MatchCount ： = 1 ;
16. while （ MatchCount < = 126 ） and （ MatchCount <length （ InMsg ） ） and （ （ InMsg [ MatchCount ] = InMsg [ MatchCount + 1 ] ） = MatchFl ） do
17. MatchCount ： = MatchCount + 1 ;
18. MatchFlの場合
19. 始める
20. N ： = N + 2 ;
21. EncodedString [ N - 2 ] ： = MatchCount + 128 ;
22. EncodedString [ N - 1 ] ： = ord （ InMsg [ 1 ] ） ;
23. 終わり
24. 他に
25. 始める
26. MatchCount <>長さ（ InMsg ）の 場合
27. MatchCount ： = MatchCount - 1 ;
28. N ： = N + 1 + MatchCount ;
29. EncodedString [ N - 1 - MatchCount ] ： = -MatchCount + 128 ;
30. for i ： = 1 から MatchCount へ
31. EncodedString [ N - 1 - MatchCount + i ] ： = ord （ InMsg [ i ] ） ;
32. 終わり ;
33. 削除（ InMsg 、 1 、 MatchCount ） ;
34. 終わり ;
35. SetLength （ EncodedString 、 N ） ;
36. RLEEncode ： = EncodedString ;
37. 終わり ;

圧縮されたメッセージのデコードは非常に簡単で、圧縮されたメッセージを1回パスするだけです。リスト2を参照してください。

1. タイプ
2. TRLEEncodedString = バイトの 配列 。
3. 関数 RLEDecode （ InMsg ： TRLEEncodedString ） ： ShortString ;
4. var
5. RepeatCount ： shortint ;
6. i 、 j ： 単語 。
7. OutMsg ： ShortString ;
8. 始める
9. OutMsg ： = '' ;
10. i ： = 0 ;
11. 一方、 i <長さ（ InMsg ） は
12. 始める
13. RepeatCount ： = InMsg [ i ] -128 ;
14. i ： = i + 1 ;
15. RepeatCount < 0の 場合
16. 始める
17. RepeatCount ： = abs （ RepeatCount ） ;
18. for j ： = i to i + RepeatCount - 1 do
19. OutMsg ： = OutMsg + chr （ InMsg [ j ] ） ;
20. i ： = i + RepeatCount ;
21. 終わり
22. 他に
23. 始める
24. for j ： = 1 to RepeatCount do
25. OutMsg ： = OutMsg + chr （ InMsg [ i ] ） ;
26. i ： = i + 1 ;
27. 終わり ;
28. 終わり ;
29. RLEDecode ： = OutMsg ;
30. 終わり ;

RLEアルゴリズムの効率を高める2番目の方法は、データを直接圧縮するのではなく、圧縮により便利な形式にする情報変換アルゴリズムの使用です。 そのようなアルゴリズムの例として、Burrows-Wheeler変換の発明者にちなんで命名されたBWT順列を考えます。 この順列は文字自体を変更するのではなく、文字列内の順序を変更するだけです。順列を適用した後のサブストリングの繰り返しは、RLEアルゴリズムを使用して圧縮された密なグループにまとめられます。 直接BWT変換は、次の手順のシーケンスに削減されます。

1.元の行に行末に特殊文字を追加します。これは他のどこにもありません。

2.ソース文字列のすべての巡回置換を取得します。

3.受信した行を辞書式順序でソートします。

4.結果のマトリックスの最後の列を返します。

このアルゴリズムの実装をリスト3に示します。

1. const
2. EOMsg = '|' ;
3. 関数 BWTEncode （ InMsg ： ShortString ） ： ShortString ;
4. var
5. OutMsg ： ShortString ;
6. ShiftTable ： ShortStringの配列 。
7. LastChar ： ANSIChar ;
8. N 、 i ： 単語 。
9. 始める
10. InMsg ： = InMsg + EOMsg ;
11. N ： =長さ（ InMsg ） ;
12. SetLength （ ShiftTable 、 N + 1 ） ;
13. ShiftTable [ 1 ] ： = InMsg ;
14. for i ： = 2 から N
15. 始める
16. LastChar ： = InMsg [ N ] ;
17. InMsg ： = LastChar + copy （ InMsg 、 1 、 N - 1 ） ;
18. ShiftTable [ i ] ： = InMsg ;
19. 終わり ;
20. ソート（ ShiftTable ） ;
21. OutMsg ： = '' ;
22. for i ： = 1 から N
23. OutMsg ： = OutMsg + ShiftTable [ i ] [ N ] ;
24. BWTEncode ： = OutMsg ;
25. 終わり ;

この変換を説明する最も簡単な方法は、特定の例を使用することです。 文字列「パイナップル」を取り、記号「|」が行文字の終わりになることに同意します。 この行のすべての循環順列とその辞書式ソートの結果を表に示します。 1。







つまり 直接変換の結果は、ストリング「| NNAAAS」になります。 この行は元の行よりもはるかに優れていることがわかりやすく、RLEアルゴリズムによって圧縮されています。 繰り返し文字の長いサブシーケンスがあります。

他の変換を使用して他の効果を実現することもできますが、BWT変換の利点は、逆変換が直接変換よりも複雑ですが、可逆的であることです。 元の文字列を復元するには、次の手順を実行する必要があります。

サイズn * nの空の行列を作成します。nは、エンコードされたメッセージの文字数です。

コード化されたメッセージで右端の空の列を埋めます。

表の行を辞書式順序で並べ替えます。

空の列ができるまで手順2〜3を繰り返します。

行末文字で終わる行を返します。



一見すると、逆変換の実装は簡単で、実装オプションの1つをリスト4に示します。

1. const
2. EOMsg = '|' ;
3. 関数 BWTDecode （ InMsg ： ShortString ） ： ShortString ;
4. var
5. OutMsg ： ShortString ;
6. ShiftTable ： ShortStringの配列 。
7. N 、 i 、 j ： 単語 。
8. 始める
9. OutMsg ： = '' ;
10. N ： =長さ（ InMsg ） ;
11. SetLength （ ShiftTable 、 N + 1 ） ;
12. for i ： = 0 から N
13. ShiftTable [ i ] ： = '' ;
14. for i ： = 1 から N
15. 始める
16. jの場合： = 1 から N
17. ShiftTable [ j ] ： = InMsg [ j ] + ShiftTable [ j ] ;
18. ソート（ ShiftTable ） ;
19. 終わり ;
20. for i ： = 1 から N
21. ShiftTable [ i ] [ N ] = EOMsgの場合
22. OutMsg ： = ShiftTable [ i ] ;
23. 削除（ OutMsg 、 N 、 1 ） ;
24. BWTDecode ： = OutMsg ;
25. 終わり ;

しかし、実際には、効率は選択したソートアルゴリズムに依存します。 自明な2次複雑度アルゴリズムは明らかにパフォーマンスに非常に悪影響を及ぼすため、効率的なアルゴリズムを使用することをお勧めします。







7番目の手順で取得したテーブルを並べ替えた後、テーブルからシンボル「|」で終わる行を選択する必要があります。 これが唯一の行であることは簡単にわかります。 T.O. 具体例を使用してBWT変換を調べました。



要約すると、RLEアルゴリズムグループの主な利点はその単純さと速度（デコード速度を含む）であり、主な欠点は非反復文字セットの非効率性であると言えます。 特別な順列を使用すると、アルゴリズムの効率が向上しますが、実行時間も大幅に向上します（特にデコード）。

語彙圧縮（LZアルゴリズム）

辞書アルゴリズムのグループは、RLEグループのアルゴリズムとは異なり、文字の繰り返しの数ではなく、以前に検出された文字のシーケンスをエンコードします。 考慮されたアルゴリズムの操作中に、すでに検出されたシーケンスとそれに対応するコードのリストを含むテーブルが動的に作成されます。 このテーブルはしばしば辞書と呼ばれ、対応するアルゴリズムのグループは辞書と呼ばれます。



辞書アルゴリズムの最も単純なバージョンを以下に説明します。

入力行にあるすべての文字で辞書を初期化します。

辞書で、エンコードされたメッセージの先頭に一致する最長のシーケンス（S）を見つけます。

見つかったシーケンスのコードを指定し、エンコードされたメッセージの先頭から削除します。

メッセージの最後に到達していない場合は、次の文字©を読み、Scを辞書に追加し、手順2に進みます。それ以外の場合は終了します。



たとえば、句「KUKUSKAKUKUSHONKUKILAKAPUSHON」の初期化されたばかりの辞書を表に示します。 3：







圧縮中に、辞書はメッセージ内で見つかったシーケンスによって補足されます。 辞書を更新するプロセスを表に示します。 4。







アルゴリズムを説明する際、辞書が完全に満たされた状況の説明は意図的に省略されました。 アルゴリズムのバリアントに応じて、異なる動作が可能です。辞書の完全または部分的なクリア、辞書の終了、またはコードのビット深度の対応する増加を伴う辞書の拡張。 これらのアプローチにはそれぞれ一定の欠点があります。 たとえば、辞書の補充が終了すると、圧縮可能な行の先頭で発生するシーケンスが辞書に保存されますが、後で発生することはありません。 同時に、辞書をクリアすると、頻繁なシーケンスが削除される可能性があります。 使用される実装のほとんどは、ディクショナリに記入するときに圧縮の度合いを追跡し始め、圧縮が特定のレベルを下回ると、ディクショナリが再構築されます。 次に、辞書がいっぱいになると辞書の更新を停止する最も単純な実装を検討します。



まず、辞書を、検出された部分文字列だけでなく、辞書に保存されている部分文字列の数も格納するレコードとして定義します。

1. タイプ
2. TDictionary = レコード
3. WordCount ： バイト ;
4. 単語： 文字列の 配列 ;
5. 終わり ;

先に出会ったサブシーケンスはWords配列に保存され、そのコードはこの配列内のサブシーケンスの数です。

また、辞書内の検索関数と辞書への追加も定義します。

1. const
2. MAX_DICT_LENGTH = 256 ;
4. 関数 FindInDict （ D ： TDictionary ; str ： ShortString ） ： 整数 ;
5. var
6. r ： 整数 ;
7. i ： 整数 ;
8. fl ： ブール値 ;
9. 始める
10. r ： = - 1 ;
11. Dの場合 WordCount > 0 then
12. 始める
13. i ： = D WordCount
14. fl ： = false ;
15. while （ not fl ） and （ i> = 0 ） do
16. 始める
17. i ： = i - 1 ;
18. fl ： = D 単語 [ i ] = str ;
19. 終わり ;
20. 終わり ;
21. フロリダなら
22. r ： = i ;
23. FindInDict ： = r ;
24. 終わり ;
26. プロシージャ AddToDict （ var D ： TDictionary ; str ： ShortString ） ;
27. 始める
28. Dの場合 WordCount <MAX_DICT_LENGTH その後
29. 始める
30. D. WordCount ： = D WordCount + 1 ;
31. SetLength （ D. ワード 、 D。 ワードカウント） ;
32. D. 言葉 [ D. WordCount - 1 ] ： = str ;
33. 終わり ;
34. 終わり ;

これらの関数を使用して、説明したアルゴリズムによるエンコードプロセスを次のように実装できます。

1. 関数 LZWEncode （ InMsg ： ShortString ） ： TEncodedString ;
2. var
3. OutMsg ： TEncodedString ;
4. tmpstr ： ShortString ;
5. D ： TDictionary ;
6. i 、 N ： バイト 。
7. 始める
8. SetLength （ OutMsg 、長さ（ InMsg ） ） ;
9. N ： = 0 ;
10. InitDict （ D ） ;
11. 一方、長さ（ InMsg ） > 0 do
12. 始める
13. tmpstr ： = InMsg [ 1 ] ;
14. while （ FindInDict （ D 、 tmpstr ） > = 0 ） および （ length （ InMsg ） > length （ tmpstr ） ） do
15. tmpstr ： = tmpstr + InMsg [長さ（ tmpstr ） + 1 ] ;
16. FindInDict （ D 、 tmpstr ） < 0の 場合
17. 削除（ tmpstr 、長さ（ tmpstr ） 、 1 ） ;
18. OutMsg [ N ] ： = FindInDict （ D 、 tmpstr ） ;
19. N ： = N + 1 ;
20. 削除（ InMsg 、 1 、長さ（ tmpstr ） ） ;
21. 長さ（ InMsg ） > 0の 場合
22. AddToDict （ D 、 tmpstr + InMsg [ 1 ] ） ;
23. 終わり ;
24. SetLength （ OutMsg 、 N ） ;
25. LZWEncode ： = OutMsg ;
26. 終わり ;

コーディング結果は、辞書内の単語の数になります。

復号化プロセスはコードの直接復号化に削減されますが、作成された辞書を転送する必要はありませんが、辞書の復号化は符号化時と同じ方法で初期化されれば十分です。 次に、前のサブシーケンスと現在の文字を連結することにより、デコード中に辞書が直接完全に復元されます。



唯一の問題は、次の状況で発生する可能性があります。辞書にまだないサブシーケンスをデコードする必要がある場合。 現在のステップで追加されるサブストリングを抽出する必要がある場合にのみ、これが可能であることを確認するのは簡単です。 そして、これは、部分文字列がcScパターン、つまり 同じ記号で始まり、終わります。 同時に、cSは前の手順で追加されたサブストリングです。 考慮されている状況は、まだ追加されていない文字列をデコードする必要がある場合のみです。 上記を考慮すると、圧縮された文字列をデコードするための次のオプションを提供できます。

1. 関数 LZWDecode （ InMsg ： TEncodedString ） ： ShortString ;
2. var
3. D ： TDictionary ;
4. OutMsg 、 tmpstr ： ShortString ;
5. i ： バイト ;
6. 始める
7. OutMsg ： = '' ;
8. tmpstr ： = '' ;
9. InitDict （ D ） ;
10. for i ： = 0 から length （ InMsg ） -1 do
11. 始める
12. InMsg [ i ] > = Dの場合 ワードカウント
13. tmpstr ： = D。 単語 [ InMsg [ i - 1 ] ] + D 言葉 [ InMsg [ i - 1 ] ] [ 1 ]
14. 他に
15. tmpstr ： = D。 言葉 [ InMsg [ i ] ] ;
16. OutMsg ： = OutMsg + tmpstr ;
17. i> 0の 場合
18. AddToDict （ D 、 D. ワード [ InMsg [ i - 1 ] ] + tmpstr [ 1 ] ） ;
19. 終わり ;
20. LZWDecode ： = OutMsg ;
21. 終わり ;

辞書アルゴリズムの利点には、RLEと比較して高い圧縮効率が含まれます。 それでも、これらのアルゴリズムの実際の使用には、いくつかの実装上の困難が伴うことを理解する必要があります。

エントロピーコーディング

シャノンファーノツリーコーディング

Shannon-Fanoアルゴリズムは、開発された最初の圧縮アルゴリズムの1つです。 このアルゴリズムは、より短いコードを使用してより頻繁な文字を表すという考えに基づいています。 さらに、Shannon-Fanoアルゴリズムを使用して取得したコードには、プレフィックスのプロパティがあります。 他のコードの先頭にコードはありません。 prefixプロパティにより、コーディングが1対1になります。 Shannon-Fanoコードを構築するアルゴリズムを以下に示します。

1.アルファベットを2つの部分に分割します。これらの部分の文字の合計確率は、互いにできるだけ近いものにします。

2.文字の最初の部分のプレフィックスコードに0を追加し、文字の2番目の部分のプレフィックスコードに1を追加します。

3.各パート（少なくとも2つの文字がある）に対して、手順1〜3を再帰的に実行します。

比較的単純であるにもかかわらず、Shannon-Fanoアルゴリズムには欠点がないわけではありません。その中で最も重要なのは、最適でないコーディングです。 各ステップでの分割は最適ですが、アルゴリズムは全体として最適な結果を保証しません。 たとえば、「AAAABVGDEZH」という行を考えてください。 対応するシャノン・ファノの木とそれに基づいて得られたコードを図に示します。 1：







エンコードしない場合、メッセージは40ビットを占有し（各文字が4ビットでエンコードされている場合）、Shannon-Fanoアルゴリズム4 * 2 + 2 + 4 + 4 + 3 + 3 + 3 = 27ビットを使用します。 メッセージの量は32.5％減少しましたが、この結果を大幅に改善できることを以下に示します。

ハフマンツリーコーディング

Shannon-Fanoアルゴリズムの数年後に開発されたHuffmanコーディングアルゴリズムも接頭辞の特性を持ち、さらに、実証された最小の冗長性があります。これは、その非常に広い分布によるものです。 ハフマンコードを取得するには、次のアルゴリズムを使用します。

1.アルファベットのすべての文字はフリーノードとして表されますが、ノードの重みはメッセージ内のシンボルの頻度に比例します。

2.空きノードのセットから、最小の重みを持つ2つのノードが選択され、選択したノードの重みの合計に等しい重みを持つ新しい（親）ノードが作成されます。

3.選択したノードが空きリストから削除され、それらに基づいて作成された親ノードがこのリストに追加されます。

4.空きリストに複数のノードが存在するまで、手順2〜3が繰り返されます。

5.構築されたツリーに基づいて、アルファベットの各シンボルにプレフィックスコードが割り当てられます。

6.メッセージは受信したコードでエンコードされます。



Shannon-Fanoアルゴリズムの場合と同じ例を考えてみましょう。 ハフマンツリーとメッセージ「AAAABVGDEZH」に対して受信したコードを図5に示します。 2：







エンコードされたメッセージのボリュームが26ビットであると計算するのは簡単です。これは、シャノンファノアルゴリズムの場合よりも少なくなります。 それとは別に、ハフマンアルゴリズムの人気により、現時点では、シンボル周波数の送信を必要としない適応コーディングを含む、ハフマンコーディングの多くのオプションがあります。

ハフマンアルゴリズムの欠点のうち、重要な部分は、実装の複雑さに関連する問題です。 周波数の周波数を格納するために実変数のシンボルを使用すると、精度が低下するため、実際には整数変数がよく使用されますが、 親ノードの重みは絶えず大きくなり、遅かれ早かれオーバーフローが発生します。 したがって、アルゴリズムが単純であるにもかかわらず、その正しい実装は、特に大きなアルファベットの場合、依然としていくつかの困難を引き起こす可能性があります。

Secant関数ツリーを使用したエンコード

割線関数によるコーディング-著者が開発したアルゴリズムで、プレフィックスコードを取得できます。 このアルゴリズムは、各ノードに割線関数が含まれるツリーを構築するという考えに基づいています。 アルゴリズムをより詳細に説明するには、いくつかの定義を導入する必要があります。

ワードは、mビットの順序付けられたシーケンスです（mはワード長と呼ばれます）。

割線リテラルは、タイプが排出のタイプの排出値です。 たとえば、リテラル（4,1）は、ワードの4ビットが1に等しくなければならないことを意味します。リテラルの条件が満たされる場合、リテラルはtrueと見なされ、そうでない場合はfalseと見なされます。

kビット割線は、kリテラルのセットです。 すべてのリテラルが真である場合、割線関数自体は真であり、そうでない場合は偽です。



ツリーは、各ノードがアルファベットをできるだけ近い部分に分割するように構築されます。 図図3は、セカントツリーの例を示しています。







一般に、セカント関数のツリーは最適なコーディングを保証するものではありませんが、ノードでの操作が簡単なため、非常に高速です。

算術コーディング

算術コーディングは、情報を圧縮する最も効果的な方法の1つです。ハフマンアルゴリズムとは異なり、算術コーディングでは、文字あたり1ビット未満のエントロピーでメッセージをエンコードできます。なぜならほとんどの算術符号化アルゴリズムは特許によって保護されています。基本的な考え方のみを以下に説明します。

使用されるアルファベットに、それぞれ頻度p_1、...、p_NのN個の文字a_1、...、a_Nがあると仮定します。次に、算術符号化アルゴリズムは次のようになります。

動作する半間隔として、[0; 1）;

作業半区間をN個の互いに素な半区間に分割します。さらに、i番目の半区間の長さはp_iに比例します。

メッセージの最後に到達していない場合は、i番目の半間隔を新しい作業間隔として選択し、手順2に進みます。それ以外の場合は、作業半間隔から任意の数値を返します。バイナリコードのこの番号のレコードは、エンコードされたメッセージになります。

図図4は、「ABAAV」メッセージをエンコードするプロセスを示しています







。



算術コーディングの明らかな利点はその効率性であり、主な（特許の制限を除く）マイナスは、エンコードおよびデコードプロセスの非常に高い複雑さです。