- ベストアンサー
ハフマン符号化による圧縮
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
ひどく原始的な方法を紹介します。実用価値は皆無です。 １）まず出現パターンとその頻度を表にまとめる。 java.util.TreeMapでも使って表現してください。 ２）出現頻度に従い符号化して符号化前と符号化後の対応表を保持。 java.util.HashMapでも使ってみてください。 ３）先の表に従い対象を符号化。 これで終了です。複合化のときに出現頻度表または対応表が必要になるのでどちらかを保持してください。
関連するQ&A
- ハフマン符号化による圧縮
１と０でできたN×Nの行列 例えば ０ １ １ １ １ ０ ０ １ １ ０ ０ ０ １ １ ０ ０ １ １ １ ０ ０ １ １ ０ １ １ ０ ０ １ ０ ０ ０ １ １ ０ ０ というような行列を ＿＿＿ ｜０１｜１ １ １ ０ ｜０１｜１ ０ ０ ０ ￣￣￣ １ １ ０ ０ １ １ １ ０ ０ １ １ ０ １ １ ０ ０ １ ０ ０ ０ １ １ ０ ０ このように４ビットごとに分けてハフマン符号化による圧縮を行うプログラムを作りたいと考えていますが、よくわかりません。どなたか教えてください。 また四角で囲んだところは０１０１と考えていいそうです。
- 締切済み
- Java
- ハフマン符号化について
ハフマン符号化についてですが、圧縮のためであるので、 ハフマン符号化を行いなさいといわれた場合において、 木構造の１と０の取り方はどんなものでも良いのでしょうか？ 生起確率が Ａ：０．１２ Ｂ：０．１２ Ｃ：０．２８ Ｄ：０．４８ であった場合、 添付画像の青い文字のように符号化を行い、 Ａ：０００ Ｂ：００１ Ｃ：０１ Ｄ：１ としても、赤い文字のように符号化を行い、 Ａ：１１１ Ｂ：１１０ Ｃ：１０ Ｄ：０ としても、どちらでもハフマン符号化としては正解なのでしょうか？ また、０と１を階層ごとにランダムにとっても問題ないのでしょうか？
- 締切済み
- その他（ITシステム運用・管理）
- ハフマン符号のプログラム
以下の問題に回答できる方，いらっしゃいましたらソースファイルと実行結果を送ってください。 ファァイル（記号列）を読み込んで，ハフマン符号によりファイルを圧縮するプログラム（C言語）を作成する（プログラムは，圧縮を行うものと，解凍を行うものの2つ作る）。また，いくつか適当なファイルに対して，圧縮を行い圧縮率を測定する。 （1）圧縮プログラムについて 圧縮のステップ （ａ）入力ファイルを読み込み各記号の出現頻度をカウントする。 （ｂ）得られた出現頻度を使って各符号のハフマン符号を生成する。 （ｃ）各符号の出現頻度を出力ファイルに書き出す。 （ｄ）もう一度入力ファイルを読み込みながら各符号をハフマン符号で置き換え て出力ファイルに出力する。圧縮ファイルの形式は次のようになる。 0x00の 0x01の … 0xffの 先頭文字の 2文字目の … 終端文字の 出現頻度 出現頻度 出現頻度 符号語 符号語 符号語 （ｃ）で書きこむ部分 （ｄ）で書きこむ部分 （2）解凍プログラムについて 解凍のステップ （ａ）各符号の出現頻度を圧縮ファイルから読み込む。 （ｂ）得られた出現頻度を使って各符号のハフマン符号を生成する。 （ｃ）圧縮ファイルの符号語を読み込みながら各符号のハフマン符号と比較しも し一致したらその記号を解凍ファイルに出力する。 （ｄ）(c)をファイルの終わりもしくは出現頻度をすべて足し合わせた記号数分処 理するまで繰り返す。 関数について 関数get_bit ファイルから1bit読み込んで戻り値として返す。 （ファイルポインタはグローバル変数で用意する） 関数put_bit 引数として0，または1を渡すと1bitずつファイルに書き込む。 （ファイルポインタはグローバル変数で用意する）
- ベストアンサー
- C・C++・C#
- JPEG画像にさらにハフマン符号化をかけると・・・？
現在卒業研究の一環で「なぜJPEG画像にハフマン符号化をかけてもほとんど圧縮できないのか？」というテーマについて考えています。 研究の過程でハフマン符号化プログラムを組み、様々な種類のJPEG画像を圧縮し、圧縮率を検証しました。その結果、フルカラー画像もグレースケール画像もほとんど圧縮できませんでしたが、単純な線画（白地に黒い線を数本引いただけのもの）の画像のみ元の２割程度まで圧縮できました。 最初はやはりJPEG画像には元からハフマン符号化がかかっているから圧縮率が悪いのかな、とも思ったのですが、『単純な線画の画像のみ元の２割程度まで圧縮できている』ので、単に「元からハフマン符号化がかかっているから」では説明がつかないように思えます。 おおまかで構いませんので、これの原因について皆様のご意見をお聞かせください。よろしくお願いします。
- ベストアンサー
- その他([技術者向] コンピューター)
- ハフマン符号によるエントロピー符号化？
現在、JPEG画像圧縮について調べていまして、 １ 非可逆圧縮では、まず離散コサイン変換をして、画像の空間領域を周波数領域に変換 ２ 次に１によって変換した周波数領域をアナログデータと見たて、デジタル化する量子化を行い情報量を削る。 ３ 最後にハフマン符号によるエントロピー符号化で圧縮 とwikipediaで調べて2までは理解できたのですが、３のハフマン符号によるエントロピー符号化というのがよくわかりません。 どなたか詳しい方、わかりやすく教えていただけないでしょうか？ 回答よろしくおねがいいたします。
- ベストアンサー
- その他([技術者向] コンピューター)
- ハフマン符号化の解き方
学校で「晴れ、曇り、雨の発生確率が0.125、0.75、 0.125のとき、ハフマン符号化したらどうなるか 答えよ。また、そのときの平均符号長とエントロ ピーについて述べよ。」という問題が出て解き方がわからないので教えてください。
- 締切済み
- その他([技術者向] コンピューター)
- 静的ハフマンと動的ハフマンの違い
現在、データ圧縮に少し手を出して興味が出たのですが、 符号化アルゴリズムについて理解ができていません。 そこで、 静的ハフマン符号化と動的ハフマン符号化の違いについて 知りたいと思い投稿させていただきました。 もしよろしければ、 処理的な違いやLHAなどにどちらが用いられているのか、 また、その理由についてご存知の方がいらっしゃったらご教授ください 本当に、 知識はところどころしかかじっていないので、 大まかな違いや、深いところもよろしければお願いします。
- 締切済み
- その他([技術者向] コンピューター)
- ハフマン符号の圧縮率について
こんにちは。現在、情報処理技術者試験の勉強をして いるのですが、ハフマン符号の圧縮率を問う問題でつ まずいています。 問題は、 同じ文字が、４文字以上続いた場合、(文字)*(文字 数）の３バイトで表す。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% でした。字数制限で、詳細を記入できな いのですが、なぜ食い違うのか分かりません。 大変な長文ですみません。よろしくお願いします。
- ベストアンサー
- 情報処理技術者
- 情報理論でのハフマン符号・・・？
学校で情報理論を習っていて、 ハフマン符号化のやり方は、習いました。 ２元情報源を非等長でハフマン符号化は、 たとえば、0,1を確率0.8,0.2で発生する 記憶のない情報源ｓでは、確率の大きい0の ランレングスを利用すれば、２元情報源を ランレングスハフマン符号化すればできる らしいのですが、 ４元情報源を非等長でハフマン符号化をす るのには、どうすれば分かりません。 ２元と同じようにランレングスでできる らしいのですが・・・。 どなたかアドバイスお願いします。
- 締切済み
- その他（学問・教育）
お礼
ありがとうございました。参考になりました。