締切済み ハフマン符号 2006/07/17 23:51 akckyykp をハフマン符号化するとどうなりますか? みんなの回答 (2) 専門家の回答 みんなの回答 natu2000 ベストアンサー率69% (83/119) 2006/07/18 00:09 回答No.2 何か宿題か、課題のような雰囲気が・・・・・謎 しかしここは教えてサイトですから質問はいいとして それに手助けになりそうな事を回答したいと思います。 勉強は、勉強サイトか自力で行ってください。 http://www.chichibu.ne.jp/~kawahira/library/comp03.htm 木の作り方あたりが参考になると思います。 質問者 お礼 2006/07/18 01:12 わかるやすくて参考になりました!ありがとうございました!! 広告を見て全文表示する ログインすると、全ての回答が全文表示されます。 通報する ありがとう 0 sittaka-kun ベストアンサー率22% (153/686) 2006/07/17 23:57 回答No.1 木によります 広告を見て全文表示する ログインすると、全ての回答が全文表示されます。 通報する ありがとう 0 カテゴリ [技術者向] コンピューターその他([技術者向] コンピューター) 関連する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を階層ごとにランダムにとっても問題ないのでしょうか? ハフマン符号化の解き方 学校で「晴れ、曇り、雨の発生確率が0.125、0.75、 0.125のとき、ハフマン符号化したらどうなるか 答えよ。また、そのときの平均符号長とエントロ ピーについて述べよ。」という問題が出て解き方がわからないので教えてください。 ハフマン符号によるエントロピー符号化? 現在、JPEG画像圧縮について調べていまして、 1 非可逆圧縮では、まず離散コサイン変換をして、画像の空間領域を周波数領域に変換 2 次に1によって変換した周波数領域をアナログデータと見たて、デジタル化する量子化を行い情報量を削る。 3 最後にハフマン符号によるエントロピー符号化で圧縮 とwikipediaで調べて2までは理解できたのですが、3のハフマン符号によるエントロピー符号化というのがよくわかりません。 どなたか詳しい方、わかりやすく教えていただけないでしょうか? 回答よろしくおねがいいたします。 ネットワークエンジニアとは?技術職の未来を考える OKWAVE コラム ハフマン符号のプログラム 以下の問題に回答できる方,いらっしゃいましたらソースファイルと実行結果を送ってください。 ファァイル(記号列)を読み込んで,ハフマン符号によりファイルを圧縮するプログラム(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ずつファイルに書き込む。 (ファイルポインタはグローバル変数で用意する) ハフマン符号化による圧縮 1と0からだけでできた100文字の列を4ビットごとに区切ってハフマン符号化による圧縮したいのですが、いまいちわかりません。どなたか教えてください。 情報理論でのハフマン符号・・・? 学校で情報理論を習っていて、 ハフマン符号化のやり方は、習いました。 2元情報源を非等長でハフマン符号化は、 たとえば、0,1を確率0.8,0.2で発生する 記憶のない情報源sでは、確率の大きい0の ランレングスを利用すれば、2元情報源を ランレングスハフマン符号化すればできる らしいのですが、 4元情報源を非等長でハフマン符号化をす るのには、どうすれば分かりません。 2元と同じようにランレングスでできる らしいのですが・・・。 どなたかアドバイスお願いします。 ハフマン符号化による圧縮 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と考えていいそうです。 JPEG画像にさらにハフマン符号化をかけると・・・? 現在卒業研究の一環で「なぜJPEG画像にハフマン符号化をかけてもほとんど圧縮できないのか?」というテーマについて考えています。 研究の過程でハフマン符号化プログラムを組み、様々な種類のJPEG画像を圧縮し、圧縮率を検証しました。その結果、フルカラー画像もグレースケール画像もほとんど圧縮できませんでしたが、単純な線画(白地に黒い線を数本引いただけのもの)の画像のみ元の2割程度まで圧縮できました。 最初はやはりJPEG画像には元からハフマン符号化がかかっているから圧縮率が悪いのかな、とも思ったのですが、『単純な線画の画像のみ元の2割程度まで圧縮できている』ので、単に「元からハフマン符号化がかかっているから」では説明がつかないように思えます。 おおまかで構いませんので、これの原因について皆様のご意見をお聞かせください。よろしくお願いします。 VB2008 ハフマン符号のプログラム ハフマン符号のプログラムソースを探しています! http://www.ccad.sist.chukyo-u.ac.jp/~mito/syllabi/daisu/huffman/index.htm#TOP に、Visual C++で作成されたプログラムがあります。 これを、VB2008に書きかえることのできる方いらっしゃいませんか? 符号化と複合化を別に(コントロールのボタンを用いて「符号化」、「複合化」とできるなど)していただければありがたいです。 ぜひ、よろしくお願いします!! 2元ハフマン符号化プログラムが作れなくて困っています。 以下のC言語のプログラムを作成出来る方、いらっしゃいましたらソースファイルを載せて下さい。 2元ハフマン符号化プログラム:具体的な無記憶情報源が入力されたときに、そのハフマン記号を出力される ご教授よろしくおねがいします 静的ハフマンと動的ハフマンの違い 現在、データ圧縮に少し手を出して興味が出たのですが、 符号化アルゴリズムについて理解ができていません。 そこで、 静的ハフマン符号化と動的ハフマン符号化の違いについて 知りたいと思い投稿させていただきました。 もしよろしければ、 処理的な違いやLHAなどにどちらが用いられているのか、 また、その理由についてご存知の方がいらっしゃったらご教授ください 本当に、 知識はところどころしかかじっていないので、 大まかな違いや、深いところもよろしければお願いします。 ハフマン符号と平均語長の問題 事象x1からx5までをハフマン符号で表し、平均語長をとると、 0.2×2+0.21×2+0.09×3+0.18×3+0.32×2=2.27なんですが、それぞれの項のかける数 2と3って何の数値ですか? AIは使う人の年齢や市場にも影響する?人工知能の可能性 OKWAVE コラム ブロックハフマン符号化プログラムの作成 現在学校の研究で「ブロック(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(圧縮対象データのファイルサイズ)です。 やはり、バッファリングに使う配列をもう少しサイズの大きい型で宣言するとこから始めるべきでしょうか? ご教授お願いします。 ハフマン符号 情報源記号と符号語の対応表 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という風に決まっていたり、また、勝手に割り当ててもいいのでしょうか? どなたかご教授お願いします。 情報理論、ハフマン符号について こんにちは、 今年、技術士1次試験(電気電子部門)を受験する予定です。試験問題(専門科目)をざっと見たのですが、だいたい勉強すれば解けそうなものが多いのですが、中に「情報理論」「符号理論」「ハフマン符号」「符合の木」と呼ばれる全く馴染みのない問題が出題されていました。 全く知らないので初歩を勉強したいのですが、これらを初歩の初歩から解説した本等を教えてください。アマゾンで調べましたが、概要がすぐに解かる様な本はなかったです。 下記解説も、いきなり「エントロピー」が出てきて難解そうです。一応エントロピー(エネルギーの質が時間経過により悪化するもの)はボルツマンの熱力学第二法則として理解しておるつもりですが、なぜそのエントロピーが、情報や符号と関わりあうのか?何となく理解できそうで、理解できません。この理論は本気で取り組むと底が深そうなので、エントロピー無しの本が有難いです。ちなみに試験は10月です。 http://www.yobology.info/text/Huffman_code/Huffman_code.htm ハフマン符号化の問題を解くプログラム ハフマンの符号化の問題を解くプログラムを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ファイルにして保存するということは何となくわかるのですが、それを実現する知識がありません。 プログラミングの知識をお持ちの方のご協力をお願いいたします。 Huffman木の作成の問題 Huffman法のプログラムを作成する上で、Huffman木の作成と符号化のところがなかなか出来なくて困っています。 英文を読み込んで、各文字の出現回数を数えて、というところまではいけるのですが… 教えていただけませんか? ハフマン符号の圧縮率について こんにちは。現在、情報処理技術者試験の勉強をして いるのですが、ハフマン符号の圧縮率を問う問題でつ まずいています。 問題は、 同じ文字が、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% でした。字数制限で、詳細を記入できな いのですが、なぜ食い違うのか分かりません。 大変な長文ですみません。よろしくお願いします。 0の符号って? 馬鹿な質問ですいませんが、 例えば「2」とか「5」の符号はプラス(正)で、「-4」とか「-7」の符号はマイナス(負)ですよね。 そうすると「0」の符号ってどう定義されているのでしょうか? 例えば「3→-4」とか「-2→5」って符号が変わったって言えると思うんですが、「3→0」とか「-2→0」は符号が変わったと言えるんでしょうか? 注目のQ&A 「You」や「I」が入った曲といえば? Part2 結婚について考えていない大学生の彼氏について 関東の方に聞きたいです 大阪万博について 駅の清涼飲料水自販機 不倫の慰謝料の請求について 新型コロナウイルスがもたらした功績について教えて 旧姓を使う理由。 回復メディアの保存方法 好きな人を諦める方法 小諸市(長野県)在住でスキーやスノボをする方の用具 カテゴリ [技術者向] コンピューター OS(技術者向け) データベース プログラミング・開発 業務ソフトウェア ITシステム運用・管理 その他([技術者向] コンピューター) カテゴリ一覧を見る OKWAVE コラム 突然のトラブル?プリンター・メール・LINE編 携帯料金を賢く見直す!格安SIMと端末選びのポイントは? 友達って必要?友情って何だろう 大震災時の現実とは?私たちができる備え 「結婚相談所は恥ずかしい」は時代遅れ!負け組の誤解と出会いの掴み方 あなたにピッタリな商品が見つかる! OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど インターネット回線 プロバイダ、光回線など
お礼
わかるやすくて参考になりました!ありがとうございました!!