- ベストアンサー
ハフマン符号の圧縮率について
こんにちは。現在、情報処理技術者試験の勉強をして いるのですが、ハフマン符号の圧縮率を問う問題でつ まずいています。 問題は、 同じ文字が、４文字以上続いた場合、(文字)*(文字 数）の３バイトで表す。Aが１５文字連続ならA*15の３ バイトです。(厳密には１５(２桁)が１バイトで表せな いと思いますが、この問題ではそうなっています。） その前提で、「同じ文字がｎ個（１<=n<=15)続く確 率を表１のとおり仮定した場合の圧縮率は何パーセン トか。小数点第一位を四捨五入して答えよ。」(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は６００回、0.03は３０回、0.025は２５回 として考えました。 まず、圧縮しない場合、 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以上は３バイトに圧縮なので、 3b*30=90 これが、４～１１まで同じ確率なので、 合計 3b*30*8=720b 12～15は２５回なので、 合計 3b*25*4=300b 圧縮した場合の 合計、750+720+300=1770b 圧縮率 1770/3800=47% 解答は、79% でした。字数制限で、詳細を記入できな いのですが、なぜ食い違うのか分かりません。 大変な長文ですみません。よろしくお願いします。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
あまり深く考えていなかったもので。。。。 しかし全体の文字数が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<=15)続く確 率を表１のとおり仮定した場合」"の解釈でしょう。 でも難解で意味わからずなのは同じです。
その他の回答 (2)
- ymmasayan
- ベストアンサー率30% (2593/8599)
１種Ｈ１２年の問題ですね。 まず、根本的なところから。 １．これはハフマン符号ではありません。 ランレングス法(改良型)といわれるものです。 ２．ランレングス法(改良型)では３バイトに圧縮しますが文字数は １バイトで２５６－１＝最大２５５文字を表現できます。 本題です。 出現確率の定義がはっきり書いてありませんが文字数と考えるべきのようです。 文字の出現確率(文字数)で考えると問題集の答えになり、 文字列の出現確率で考えるとあなたの答えになります。 答えが違うのは当たり前ですね。 若干、欠陥問題くさい感じもします。
お礼
ご回答ありがとうございます。 参考のURLでも、やはり問題集とおなじこたえのようで す。 おっしゃるとおり、0.025や0.03だとわかりにくいの で、１０００倍して25や30にして、これが文字列全体 の出現回数だと思っていました。これは、文字数と とるべきなんですね。違いがよく分かりました。 どうもありがとうございました。
- fortranxp
- ベストアンサー率26% (181/684)
圧縮率は 文字数 確率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%。 なお ２進数では1バイトで0-15まで表現できます。
お礼
ご回答ありがとうございます。 実は、問題集の解答にもほぼ同じ表がのっていて、 やはり、確率＊圧縮率の総和でした。（書き込もうと したのですが、字数オーバーでできませんでした。す みません。）これが、圧縮率の期待値で、正しい解答 だということは分かるのですが、自分がやった圧縮前 と圧縮後ごとに字数＊確率の総和をもとめて、圧縮前/ 圧縮後にするとなぜ違う数字になるのでしょうか？
お礼
２度にわたりどうもありがとうございます。 どうやら、１０００倍して、600,30,25,にしたとき に、それらを文字数ではなく、文字列の出現回数と とらえたのが間違いだったようです。分かりやすい 表で説明してくださり、どうもありがとうございまし た。