• 締切済み

情報理論でのハフマン符号・・・?

 学校で情報理論を習っていて、 ハフマン符号化のやり方は、習いました。  2元情報源を非等長でハフマン符号化は、 たとえば、0,1を確率0.8,0.2で発生する 記憶のない情報源sでは、確率の大きい0の ランレングスを利用すれば、2元情報源を ランレングスハフマン符号化すればできる らしいのですが、 4元情報源を非等長でハフマン符号化をす るのには、どうすれば分かりません。 2元と同じようにランレングスでできる らしいのですが・・・。  どなたかアドバイスお願いします。

みんなの回答

  • Esna
  • ベストアンサー率36% (4/11)
回答No.3

こんにちは.Esnaです. 4元情報源でランレングス符号化してからハフマン符号化ということですか…. ランレングス符号化を行うと,t_amanoさんが言われたとおり,例えば, aaaaabbccccdddaaa 5a2b4c3d3a となります.組み合わせとしては, 自然数,記号,自然数,記号,… となっています. 記号の部分には,確率によるハフマン符号を割り当てればいいと思いますが,自然数の部分をどのように表現するかが問題となります. 2パスで圧縮を行えば,出現した自然数の確率が求められますが,1パスの場合には,最大値が既知でないとハフマン符号は使えません. 2パスにしても,自然数の出現確率を使って,それをハフマン符号で表現する方法もありますし,自然数の部分をMH(Modified Huffman)のように64進法で表現して,ハフマン符号に変換する方法もあります. 1パスの場合には,Elias符号などを使う方法もあります. 回答になっているかわかりませんが,ごめんなさい.

  • t_amano
  • ベストアンサー率42% (16/38)
回答No.2

前の方もハフマンについて説明してますがもう少し単純にランレングスとハフマンの説明をします。 ランレングスは同じ記号が続く場合にその記号と個数の組み合わせで表現します。たとえばaaaaを4aとすると半分の容量で済みます。ただし同じ記号がほとんど続かないパターンだとかえって容量が増す場合もあるので圧縮にならないですね。 ハフマンは頻繁に出てくる記号を短いビット数の記号に割り当ててめったに出てこない記号を長いビット数に割り当てることで圧縮を可能にしてます。たとえばaという記号が頻繁に出てくる場合はaは通常1010の4ビットですがこれを0とすると1/4で済みます。 この二つは組み合わせて使用することも可能です。 この点を抑えて問題に取り組めばおのずと答えはでてくるのではないですか。がんばってください。

googly
質問者

補足

ものすごく大切のことを書き忘れました。4元情報源をランレングスハフマン符号化をして*2元*の符号語にしなければならないということです。本当にごめんなさい。

  • Esna
  • ベストアンサー率36% (4/11)
回答No.1

こんにちは.Esnaです. ハフマン符号化とランレングス符号化は,別物です. ただ,ハフマン符号化は,記号に対して,それぞれ少なくとも1ビット以上の符号を割り当てるので,2元情報源の場合には,記号(1ビット)に1ビット以上の割り当てが行われるので,圧縮できないためランレングスを用いたのだと思います. (ただし,数記号のブロック化を行えば別ですが…) 4元情報源の場合には,アルファベットが4種類あっておそらく出現確率が与えられていると思います. ハフマン符号化の方法を習ったのであれば,ハフマン木の構成方法を習ったの思うのですが,それを適用すれば,ランレングスを用いなくても,構成できます. 例を示すと,記号a,b,c,dの出現確率がそれぞれ0.5,0.25,0.125,0.125とすると, ハフマン木を構成し,木のパスに0,1を割り当てると, (記号:ハフマン符号) (a : 0) (b : 10) (c : 110) (d : 111) ができます.

googly
質問者

補足

ランレングス符号化をおこなってからハフマン符号化をしてより効率的な符号をつくれという出題だったのです。説明不足みたいでごめんなさい。2元情報源(0,1)で長さ4までの符号化でなら1,01,001,0001としてそれぞれの確率を求めて、それをハフマン符号すればいいということは、わかるのですが、4元情報源(A,B,D,C)なら??? という状態でした。

関連するQ&A

  • ハフマン符号化の解き方

    学校で「晴れ、曇り、雨の発生確率が0.125、0.75、 0.125のとき、ハフマン符号化したらどうなるか 答えよ。また、そのときの平均符号長とエントロ ピーについて述べよ。」という問題が出て解き方がわからないので教えてください。

  • 情報理論、ハフマン符号について

    こんにちは、 今年、技術士1次試験(電気電子部門)を受験する予定です。試験問題(専門科目)をざっと見たのですが、だいたい勉強すれば解けそうなものが多いのですが、中に「情報理論」「符号理論」「ハフマン符号」「符合の木」と呼ばれる全く馴染みのない問題が出題されていました。 全く知らないので初歩を勉強したいのですが、これらを初歩の初歩から解説した本等を教えてください。アマゾンで調べましたが、概要がすぐに解かる様な本はなかったです。 下記解説も、いきなり「エントロピー」が出てきて難解そうです。一応エントロピー(エネルギーの質が時間経過により悪化するもの)はボルツマンの熱力学第二法則として理解しておるつもりですが、なぜそのエントロピーが、情報や符号と関わりあうのか?何となく理解できそうで、理解できません。この理論は本気で取り組むと底が深そうなので、エントロピー無しの本が有難いです。ちなみに試験は10月です。 http://www.yobology.info/text/Huffman_code/Huffman_code.htm

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

    ハフマン符号化についてですが、圧縮のためであるので、 ハフマン符号化を行いなさいといわれた場合において、 木構造の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を階層ごとにランダムにとっても問題ないのでしょうか?

  • 2元ハフマン符号化プログラムが作れなくて困っています。

    以下のC言語のプログラムを作成出来る方、いらっしゃいましたらソースファイルを載せて下さい。 2元ハフマン符号化プログラム:具体的な無記憶情報源が入力されたときに、そのハフマン記号を出力される ご教授よろしくおねがいします

  • ハフマン符号 情報源記号と符号語の対応表

    S=(a1 0.15 , a2 0.3 , a3 0.05 , a4 0.2 a5 0.25 , a6 0.05) この情報源Sに対するハフマン符号をハフマン符号の木を構成することにより、情報源記号と符号語の対応表を示せ。 という問題があるのですが、これについて質問です。 符号の木は、これらのa1~a6が二進数でどうなるのかがわからないと書けないと思うのですが、この問題にはその二進数の割り当てがしてありません。 これは最初からa1ならば0やa2ならば01という風に決まっていたり、また、勝手に割り当ててもいいのでしょうか? どなたかご教授お願いします。

  • JPEG画像にさらにハフマン符号化をかけると・・・?

    現在卒業研究の一環で「なぜJPEG画像にハフマン符号化をかけてもほとんど圧縮できないのか?」というテーマについて考えています。 研究の過程でハフマン符号化プログラムを組み、様々な種類のJPEG画像を圧縮し、圧縮率を検証しました。その結果、フルカラー画像もグレースケール画像もほとんど圧縮できませんでしたが、単純な線画(白地に黒い線を数本引いただけのもの)の画像のみ元の2割程度まで圧縮できました。 最初はやはりJPEG画像には元からハフマン符号化がかかっているから圧縮率が悪いのかな、とも思ったのですが、『単純な線画の画像のみ元の2割程度まで圧縮できている』ので、単に「元からハフマン符号化がかかっているから」では説明がつかないように思えます。 おおまかで構いませんので、これの原因について皆様のご意見をお聞かせください。よろしくお願いします。

  • 情報理論

    今、情報理論について学んでいます。 学ぶ内容は、自己情報量、エントロピー、Shannon-Fano符号、Huffman符号、Lempel-Ziv符号です。 これらを独学で学べる参考書はあるでしょうか? もし、知っている方、教えて下さい(>_<)

  • ハフマン符号化の問題を解くプログラム

    ハフマンの符号化の問題を解くプログラムをC言語(コンソールアプリケーション)で作りたいのですが ファイルの圧縮とかをするプログラムはいろいろなサイトにあったのですが、 簡単な情報源を与えられたものを符号化するプログラムで参考にできるようなサイトは見つかりませんでした。 誰かプログラムの例を教えていただけないでしょうか? 入力する例はつぎのようなものです S=(a1, a2, a3, a4, a5, a6/0.35, 0.15, 0.15, 0.20, 0.10, 0.05)

  • ハフマン符号化プログラミング

     学校の課題でVisualStudioで実現できるハフマン符号化プログラム(3次拡大)を作成せよ。という課題が出題されました。  しかし私は今まで入門程度のプログラミングしかやったことがなく、。指定されたファイルの文字数を調べる程度の事しかできない程度のプログラミングの知識なのでさっぱりです。  指定されたtxtファイルを読み込んで、文字数を数えて、文字の種類を調べて、各文字の発生確率を調べて、各文字を3次拡大行列にし、ツリー構造のアルゴリズムを作成し、各値を2進数に変換して、2進数に変換したものをtxtファイルにして保存するということは何となくわかるのですが、それを実現する知識がありません。  プログラミングの知識をお持ちの方のご協力をお願いいたします。

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

    現在学校の研究で「ブロック(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(圧縮対象データのファイルサイズ)です。 やはり、バッファリングに使う配列をもう少しサイズの大きい型で宣言するとこから始めるべきでしょうか? ご教授お願いします。