この実験について
すべてのZIPファイル、PNG画像、MP3トラックのサイズが生データより小さいのは、繰り返しを取り除くためです。自分のメッセージで、古典的な可逆圧縮方式を2つ試してみましょう。ランレングス符号化は、同じ記号が続く部分を個数に置き換える方式で、単純な画像には非常に有効ですが、一般的なテキストには役立ちません。ハフマン符号化は、よく使われる記号には短い符号を、まれな記号には長い符号を割り当てます。木を段階的に作りながら符号を生成し、1948年にクロード・シャノンが示した理論上の限界から、記号あたり1ビット以内の効率を実現します。
学習目標
- 可逆圧縮と非可逆圧縮の違いを説明する
- ランレングス符号化でメッセージを符号化・復号し、どのような場合に有効か説明する
- 出現頻度が最も低い2つの記号を繰り返し結合して、ハフマン木を作る
- 木から符号語を読み取り、どの符号も別の符号の先頭にならない理由を説明する
- 圧縮後のサイズをエントロピー限界と比較し、圧縮率を計算する
使い方
- 1Pixel の行を選び、ランレングスを選択します。行を表すのに必要なビット数は、変換前と変換後でそれぞれいくつですか？なぜこれほど効果的なのでしょうか？
- 2ランレングスを選んだまま、Hamlet に切り替えます。メッセージのサイズが大きくなるのはなぜですか？
- 3Mississippi を選び、「木を構築」を押します。各ステップで、どの2つの木が結合されますか？また、それはなぜですか？
- 4木が完成したら、最も出現頻度の高い文字と最も低い文字の符号語を見つけます。ビット数を数えましょう。
- 5ルートから木をたどり、符号化されたメッセージの最初の数ビットを手作業で復号します。
- 61種類の文字だけを使ったメッセージを入力し、次にすべての文字が異なるメッセージを入力します。どちらの場合も、ハフマン符号とエントロピーの限界を比較してください。
モデル
前提条件
- 元のメッセージでは、ASCII と同様に、各文字に8ビットが使われています。
- 各ランレングスのペアは、8ビットの個数と8ビットの文字として格納されるため、255を超える長さのランは分割されます。
- ハフマン符号のサイズに含まれるのは、符号化されたメッセージだけです。実際のファイルでは符号表または各文字の出現回数も格納する必要があり、短いメッセージではそれが重要になります。
- 重みが同じ木が2つある場合、先に作られた木が先に選ばれ、重みの小さい木が0の枝になります。同じ長さの符号でも、同点時の規則が異なれば符号は変わります。
授業で試してみましょう
- Q1ランレングス符号化を使って BBBBBWWWBBBBBBBB を符号化してください。何バイト必要ですか？
- Q2出現回数が A 5、B 2、R 2、C 1、D 1 のハフマン木を作り、ABRACADABRA を符号化するのに必要なビット数の合計を求めてください。
- Q3ハフマン符号が接頭語符号でなければならないのはなぜですか？A を 0、B を 01 とすると、どのような問題が起きますか？
- Q4あるテキストでは、異なる8文字がすべて同じ回数使われています。そのエントロピーはいくつですか？また、ハフマン符号で圧縮できますか？
- Q5JPEGやMP3は、ハフマン符号よりもはるかに高い圧縮率を実現します。そのために何を犠牲にしているのでしょうか？
よくある質問
現在、ハフマン符号はどこで使われていますか？
日常的なさまざまな形式で使われています。ZIPやgzip（DEFLATE方式）、PNG画像、非可逆圧縮後のJPEG画像、MP3音声などです。通常は、別の方式で繰り返しを数値に変換した後に行う最終段階です。
どんなファイルでも圧縮できますか？
いいえ。すべてのファイルを小さくできる可逆圧縮方式があれば、圧縮結果を何度でもさらに圧縮できてしまいます。しかし、短いファイルの数は長いファイルの数より少ないため、それは不可能です。ランダムデータやすでに圧縮されたファイルは、通常それ以上小さくなりません。
ハフマン木は一意ですか？
必ずしもそうではありません。出現回数が同じ場合、異なる選択によって異なる木や符号語ができますが、同じ出現回数から作られたハフマン木なら、どれもビット数の合計は同じになります。