すべてのカテゴリ » 知識・教養・学問 » 知識・学問 » 数学・サイエンス

質問

終了

ハフマン符号について質問です。
符号化する際のアルゴリズムは理解できたのですが、それによりデータ容量が圧縮される理由が分かりません。
皆さんには分かりますか?

  • 質問者:初心者
  • 質問日時:2009-07-16 23:05:27
  • 0

ハフマン符号は出現頻度の高い文字のビット数を小さくします。
よく出現する文字のビット数が小さくなるので、データが圧縮されます。

具体例として、3ビットのテキストデータを符号化する場合で考えてみます。
(8ビットでやりたいところですが、大変なので勘弁してください。)

テキストデータの文字数はN個で、その出現頻度は以下の様になっていたとします。
 a:30%
 b:20%
 c:15%
 d:12%
 e:10%
 f:7%
 g:4%
 h:2%

これをハフマン符号で符号化するとこうなります。
(アルゴリズムはご存知だという事なので割愛します。)
 a:00
 b:11
 c:010
 d:100
 e:101
 f:0110
 g:01110
 h:01111

ここで文字aに着目します。
文字aの出現頻度は30%ですから、文字aの個数は0.3N個です。
文字aを1文字表すのに2ビット必要なので、全部で0.6Nビット必要になります。
これを全文字に対して行うと以下の様になります。
 a:0.6Nビット
 b:0.4Nビット
 c:0.45Nビット
 d:0.36Nビット
 e:0.30Nビット
 f:0.28Nビット
 g:0.2Nビット
 h:0.1Nビット
これらを合計すると2.69Nビットになります。

符号化前のテキストデータのサイズは3Nビットです。
(どの文字も3ビットなので、3ビット×文字数がファイルサイズ。)

3Nビットから2.69Nビットに減っているので、データが圧縮された事が分かります。

  • 回答者:arta (質問から20時間後)
  • 1
この回答の満足度
  
とても参考になり、非常に満足しました。回答ありがとうございました。
お礼コメント

大変良く分かりました。
ありがとうございました。

並び替え:

ファイルの中のデータ(8ビットと考えても良い)の出現頻度のもっとも大きい物を、1ビット(1)で、次に多い物を 2ビット(01)、3番目は4ビット(0011)、4番目も4ビット(0010)、5番目も4ビット(0001)と言う感じで、出現頻度の大きい物が元のデータよりも少ないビットで表せる様になっています。 なので、例えば全て、「A」の文字だけで、80バイトのファイルが有ったとすれば、1/8の10バイトに圧縮されると言う訳です。(実際は、データと符号の対応テーブルが要るので、テーブル分はファイル容量が増すが。) もちろん、ファイルの中のデータの出現頻度が、どのデータも同程度の場合、返って圧縮ファイルのサイズの方が増えてしまいます。

===補足===
>これは単なる一例として挙げられただけでしょうか?

単なる例です。

>以下の8文字を符号化してみてください。(横にある数字は出現頻度です。)
> a:20%、b:18%、c:16%、d:14%、e:12%、f:10%、g:6%、h:4%

a: 00
b: 111
c: 110
d: 101
e: 100
f: 011
g: 0101
h: 0100

と言う所だろうか。

この回答の満足度
  
お礼コメント

回答ありがとうございます。
ですが、
「出現頻度の高い順に1ビット、2ビット、4ビット、4ビットと割り当てる」
という回答が引っかかりました。

ハフマン符号のアルゴリズムだと、最も出現頻度の高いものが1ビットになる保証はありませんし、その後も2ビット、4ビット、4ビットとなることも保証されなかったと思います。
これは単なる一例として挙げられただけでしょうか?

とりあえずシティーさんがハフマン符号をご理解されている事を確認するため、以下の8文字を符号化してみてください。(横にある数字は出現頻度です。)
 a:20%、b:18%、c:16%、d:14%、e:12%、f:10%、g:6%、h:4%
失礼かと思いますが、よろしくお願いします。


補足ありがとうございました。
しかし何度計算しても、この様なビット列にはならないんですよねぇ・・・

関連する質問・相談

Sooda!からのお知らせ

一覧を見る