• ベストアンサー

ハフマン符号の圧縮率について

こんにちは。現在、情報処理技術者試験の勉強をして いるのですが、ハフマン符号の圧縮率を問う問題でつ まずいています。 問題は、 同じ文字が、4文字以上続いた場合、(文字)*(文字 数)の3バイトで表す。Aが15文字連続ならA*15の3 バイトです。(厳密には15(2桁)が1バイトで表せな いと思いますが、この問題ではそうなっています。)  その前提で、「同じ文字がn個(1<=n<=15)続く確 率を表1のとおり仮定した場合の圧縮率は何パーセン トか。小数点第一位を四捨五入して答えよ。」(1文字 は1バイトとする) 表1 n   確率 1 0.6   2 0.03 3 0.03 4 0.03 5 0.03 6 0.03 7 0.03 8 0.03 9 0.03 10 0.03 11 0.03 12 0.025 13 0.025 14 0.025 15 0.025 問題は以上です。 私は、1000回事象が起きたと仮定して、 0.6は600回、0.03は30回、0.025は25回 として考えました。 まず、圧縮しない場合、 1*600=600byte(以下b) 2*30=60b 3*30=90b 4*30=120b 5*30=150b 6*30=180b 7*30=210b 8*30=240b 9*30=270b 10*30=300b 11*30=330b 12*25=300b 13*25=325b 14*25=350b 15*25=375b 合計 3800b 次に、圧縮した場合、n=3までは、 1*600=600byte(以下b) 2*30=60b 3*30=90b 合計、750b 4以上は3バイトに圧縮なので、 3b*30=90 これが、4~11まで同じ確率なので、 合計 3b*30*8=720b 12~15は25回なので、 合計 3b*25*4=300b 圧縮した場合の 合計、750+720+300=1770b 圧縮率 1770/3800=47% 解答は、79% でした。字数制限で、詳細を記入できな いのですが、なぜ食い違うのか分かりません。 大変な長文ですみません。よろしくお願いします。

質問者が選んだベストアンサー

  • ベストアンサー
  • fortranxp
  • ベストアンサー率26% (181/684)
回答No.2

あまり深く考えていなかったもので。。。。 しかし全体の文字数が1000文字だったら。。。 その場合の数は やっぱり。。。 圧縮前       圧縮後 01 600文字      600文字 02  30文字      30文字 03  30        30 04  30        30x3/4=22.5 05  30        30X3/5=18.0 06  30        30x3/6=15.0 07  30        30X3/7=12.9 08  30        30X3/8=11.3 09  30        30X3/9=10.0 10  30        30X3/10=9.0 11  30        30X3/11=8.2 12  25        25X3/12=6.3 13  25        25X3/13=5.8 14  25        25X3/14=5.4 15  25        25X3/15=5.0 ---------------------------------------- 合計 1000          790.4 よって790文字/1000文字=79% 問題なのは 、"「同じ文字がn個(1<=n<=15)続く確 率を表1のとおり仮定した場合」"の解釈でしょう。 でも難解で意味わからずなのは同じです。     

taro5088
質問者

お礼

2度にわたりどうもありがとうございます。 どうやら、1000倍して、600,30,25,にしたとき に、それらを文字数ではなく、文字列の出現回数と とらえたのが間違いだったようです。分かりやすい 表で説明してくださり、どうもありがとうございまし た。

その他の回答 (2)

  • ymmasayan
  • ベストアンサー率30% (2593/8599)
回答No.3

1種H12年の問題ですね。 まず、根本的なところから。 1.これはハフマン符号ではありません。   ランレングス法(改良型)といわれるものです。 2.ランレングス法(改良型)では3バイトに圧縮しますが文字数は   1バイトで256-1=最大255文字を表現できます。 本題です。 出現確率の定義がはっきり書いてありませんが文字数と考えるべきのようです。 文字の出現確率(文字数)で考えると問題集の答えになり、 文字列の出現確率で考えるとあなたの答えになります。 答えが違うのは当たり前ですね。 若干、欠陥問題くさい感じもします。

参考URL:
http://www.rs.kagu.sut.ac.jp/~infoserv/j-siken/H12a1/pm02.html
taro5088
質問者

お礼

ご回答ありがとうございます。 参考のURLでも、やはり問題集とおなじこたえのようで す。  おっしゃるとおり、0.025や0.03だとわかりにくいの で、1000倍して25や30にして、これが文字列全体 の出現回数だと思っていました。これは、文字数と とるべきなんですね。違いがよく分かりました。 どうもありがとうございました。

  • fortranxp
  • ベストアンサー率26% (181/684)
回答No.1

圧縮率は 文字数 確率X圧縮率(圧縮後/圧縮前の文字数) 1     0.6X1  =0.6 2    0.03X1  =0.03 3    0.03X1  =0.03 4    0.03X3/4 =0.023 5    0.03X3/5 =0.018 6    0.03X3/6 =0.015 7    0.03X3/7 =0.013 8    0.03X3/8 =0.011 9    0.03X3/9 =0.01 10    0.03X3/10=0.01 11    0.03X3/11=0.009 12   0.025X3/12= 0.006 13   0.025X3/13= 0.006 14   0.025X3/14= 0.005 15   0.025X3/15= 0.005 ---------------------------      合計   0.79 よってn=1からn=15までの全事象の確率は79%。 なお 2進数では1バイトで0-15まで表現できます。

taro5088
質問者

お礼

ご回答ありがとうございます。 実は、問題集の解答にもほぼ同じ表がのっていて、 やはり、確率*圧縮率の総和でした。(書き込もうと したのですが、字数オーバーでできませんでした。す みません。)これが、圧縮率の期待値で、正しい解答 だということは分かるのですが、自分がやった圧縮前 と圧縮後ごとに字数*確率の総和をもとめて、圧縮前/ 圧縮後にするとなぜ違う数字になるのでしょうか?

関連するQ&A

  • ハフマン符号化について

    ハフマン符号化についてですが、圧縮のためであるので、 ハフマン符号化を行いなさいといわれた場合において、 木構造の1と0の取り方はどんなものでも良いのでしょうか? 生起確率が A:0.12 B:0.12 C:0.28 D:0.48 であった場合、 添付画像の青い文字のように符号化を行い、 A:000 B:001 C:01 D:1 としても、赤い文字のように符号化を行い、 A:111 B:110 C:10 D:0 としても、どちらでもハフマン符号化としては正解なのでしょうか? また、0と1を階層ごとにランダムにとっても問題ないのでしょうか?

  • ハフマン符号化による圧縮

    1と0でできたN×Nの行列 例えば 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 というような行列を ___ |01|1 1 1 0 |01|1 0 0 0  ̄ ̄ ̄  1 1  0 0 1 1  1 0  0 1 1 0  1 1  0 0 1 0  0 0  1 1 0 0 このように4ビットごとに分けてハフマン符号化による圧縮を行うプログラムを作りたいと考えていますが、よくわかりません。どなたか教えてください。 また四角で囲んだところは0101と考えていいそうです。

  • ハフマン符号のプログラム

     以下の問題に回答できる方,いらっしゃいましたらソースファイルと実行結果を送ってください。  ファァイル(記号列)を読み込んで,ハフマン符号によりファイルを圧縮するプログラム(C言語)を作成する(プログラムは,圧縮を行うものと,解凍を行うものの2つ作る)。また,いくつか適当なファイルに対して,圧縮を行い圧縮率を測定する。 (1)圧縮プログラムについて  圧縮のステップ  (a)入力ファイルを読み込み各記号の出現頻度をカウントする。  (b)得られた出現頻度を使って各符号のハフマン符号を生成する。  (c)各符号の出現頻度を出力ファイルに書き出す。  (d)もう一度入力ファイルを読み込みながら各符号をハフマン符号で置き換え    て出力ファイルに出力する。圧縮ファイルの形式は次のようになる。   0x00の  0x01の … 0xffの 先頭文字の 2文字目の … 終端文字の   出現頻度 出現頻度 出現頻度 符号語   符号語    符号語    (c)で書きこむ部分      (d)で書きこむ部分 (2)解凍プログラムについて  解凍のステップ  (a)各符号の出現頻度を圧縮ファイルから読み込む。  (b)得られた出現頻度を使って各符号のハフマン符号を生成する。  (c)圧縮ファイルの符号語を読み込みながら各符号のハフマン符号と比較しも    し一致したらその記号を解凍ファイルに出力する。  (d)(c)をファイルの終わりもしくは出現頻度をすべて足し合わせた記号数分処   理するまで繰り返す。  関数について  関数get_bit  ファイルから1bit読み込んで戻り値として返す。  (ファイルポインタはグローバル変数で用意する)  関数put_bit  引数として0,または1を渡すと1bitずつファイルに書き込む。  (ファイルポインタはグローバル変数で用意する)

  • ブロックハフマン符号化プログラムの作成

    現在学校の研究で「ブロック(n次拡大情報源)ハフマン符号化」プログラムをC言語で作成しています。 これは、通常のハフマン符号化でデータ1個ごとに出現頻度を調べてそれぞれにハフマン符号を割り当てるところを、ファイル中で隣り合うデータ2個(あるいは3個、4個、・・・n個)を一かたまりと見なし、それぞれの出現頻度を調べてハフマン符号を割り当てる、というものです。 通常のハフマン符号化は以前作成したことがあるのですが、これをどのようにして上記のようなプログラムに改変すればいいのかわかりません。 ちなみに、データのバッファリングは以下のようにし、 #define BUFFER_SIZE 102400 unsigned char buffer[BUFFER_SIZE]; (中略) int i,c; i = 0; while(i < BUFFER_SIZE && (c = fgetc(fp_i)) != EOF) { buffer[i] = c; i++; } 各データの出現頻度は以下のようにして調べています。 #define N 256 (中略) int hist[N * 2]; for(i = 0;i < (N * 2);i++) hist[i] = 0; for(i = 0;i < size;i++) hist[data[i]]++; ※data[i]は前述のbuffer[i]、sizeは前述のi(圧縮対象データのファイルサイズ)です。 やはり、バッファリングに使う配列をもう少しサイズの大きい型で宣言するとこから始めるべきでしょうか? ご教授お願いします。

  • 屈折率について

    屈折率nと誘電率εの間にε=n^2が成り立つときには、透磁率μ=1を仮定していますが、この条件はどのような場合になぜ適応できるのでしょうか。

  • CPU利用率の求め方。

    CPU利用率の求め方。 (1)ある計算機において、n個のプロセスがメモリ中で実行されているとする。 プロセスが実行されている時間中に確率p(0<=p<=1)でI/O待ち等の理由で待ちとなる場合、CPU利用率R(0<=R<=1)をpとnで表せ。 (2)プロセスにおけるI/O待ちとなる確率pが0.8、かつ実行に必要なメモリ容量が40MBであり、搭載もメモリで可能な限りプロセスの多重度を上げると仮定した場合、CPU利用率Rが0.7(70%)以上になるために必要なメモリ容量を求め理由と共に述べよ。ただし、メモリは64MB単位で搭載可能であり、仮想記憶は用いていないものとする。 という問題なのですが、(1)からして分かりません。 nに関係なくR=(1-p)な気がするのですが、違いますよね。 すみませんが考え方教えてください。

  • 確率の問題

    表が出る確率がpであるコインをn回投げる試行を考える(n>=2).次の問に答えよ (1)nがkの倍数であると仮定する。jk+1回目から(j+1)k回目までの間に一回以上裏が出るという事項をAjで表す(j=1,2,....n/k) についてAjの起こる確率P(Aj)を求めよ。 (2)nがkの倍数であると仮定する。少なくとも1つのj=1,.....,n/kについてAjが起こる事項をBで表す。Bの起こる確率P(B)を求めよ。 (3)nがkの倍数であると仮定する。n回の試行の中に、k回連続して表が出る箇所がどこにも存在しないという事項をAで表す。Aが起こる確率P(A)とP(B)はどちらが大きいか? (4)nを無限大にする時、n回の試行の中に、k回連続して表が出る箇所が存在する確率が1に収束することを示せ。

  • 転送時間と圧縮率について

    情報の課題で問題が出たのですが、いまいち理解出来ずに困っています。 (1)8Mbpsの通信回線において、10MBのデータをダウンロードした場合、転送時間は何秒になりますか。ただし、1B=8bです。 (2)1.2MBのデータを圧縮し、480KBとなったとき、圧縮率は何%ですか。 わかる方がいましたら、回答お願いします。

  • 情報圧縮の問題

    情報科学の問題なのですが、分からないのでどなたかお助けください。 各日の天気は,それまでの天気と無関係に晴れが 80%, 雨が 20% の確率で起きるものと仮定する。 晴れを1,雨を0 とした時の1年間の天気を示した365ビットの列を, 3日分づつを塊にすることにより,より短い文字列に表現する方法を考えよ。 またその方法での,圧縮率を求めよ。 111、110、101、100…と3日分ずつだと8種類の文字列のどれかになりますよね。 それを例えば111=1というふうに表現する事に決めたりすればいいのでしょうか? いまいちよく分からないのでお助けください。

  • 硬貨の表がr回以上出る確率・・・

    表と裏の出る確率がそれぞれ1/2である硬貨を2n回投げるとき、表がr回以上出る確率をa_r、表がs回以下出る確率をb_rとする。 (1)n=1のときa_1、b_1を求めよ (2)a_n=b_nを示せ (3)a_n+1=1/2[1-{(2n)!/ (2^n*n!)^2}]を示せ この問題を解いています (1)は3/4となりました (2)は帰納法みたいにして示してはダメでしょうか? (3)はいったいどこからこんな複雑な式を導くのか見当もつきませんでした。 回答いただければ幸いです。 ぜひよろしくお願いします

専門家に質問してみよう