プログラミングできる天才ちょっとこい

ハフマン符号化ってなに？

第四章で仲間になるアイツ？

　　　　　　　　　　　　　　 ,,r''"~:................~`ヽ､
　　　　　　　　　　　　　　,r'"::::::::::::::::::::::::::::::............ﾞヽ、
　　　　　　　　　　　 　 r'::::::::::::::::::::::::::::::::::::::::::::.........:::.ヽ.
　　　　　　　　　　　　,:'::::::::::::::::::::::::::::::::::::::::::::::::::::::...::::::..ﾞ:,　　　　　
　　　　　　　　　　　 l':::::r:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::.ﾞ:,　　　
　　　　　　　　　　 ,:':::::::|::::::::i::::::::::::::,:::::::::::::::::::::::::::i:::::::::::::...ﾞ:,　　
　　　　　　　　　 ,r':::::::::::ヽ、l,::;::i,::::::l:::::::::::::i:::::::ﾉ::::ﾉ::::::::::::::...ﾞ:、　　
　　　　　　　　,,,r'::::::::::::::::::|~-ﾆ.._-､;;!､;;:::ノ-‐''-'',!::::::::::::::::::::::..ﾞ:,　　　
　　　　　　　,:':::::::::::::::::::::::::ﾞiヾ.ヾ::ｼﾌ 　ヾゞ::ｼﾆ' .!:ヽ::::::::::::::::::::::::ﾞ:､
　　　　　,r''"::::::::::::::::::::::::::::::ﾞi,　　 　 ,; ,　　　　　!:.,':::::::::::::::::::::::::::､::ﾞ::､
　　　 ,r"r"::::::::::::::::::::::::::::::::::::ﾞ:、　　 ﾞ'"　　　　 !,j::::::::::::::::::::::::::::::::）､::::ヽ 　　呼んだか？
　　　　`'ｰ:､_:::::::::::::::::::/:::::::::::::::ヽ, 　~￣ 　 ,,ri':::::::::::::::::::::::::i:::::::,,r'' ﾞ''''"
　　　　　　　ﾞ'-､:::::::::/;:::::::::::::::::::::l ヽ、_,,,..r'',　!::::::::,:::::::::::::::,,jr'"
　　　　　　　　　 ﾞ ｰ''-､_::::::::::;;;;;;;;i　　''''''''/::::|;;;;;;;;;i;;;;;;;;;r'''"
　　　　　　　　　　　 ＿　,,r'";;;;:r-l　　　 i'::::::::`ｰ､;;;:;;;;;;`ｰ-､_
　　　　　　　　　　/";;;;;;";;;;;;;;;;l　　　　　 l__,,,r'''"~;;;;;;;;;;;;;;;;;;;;;;;;ﾞ'ヽ
　　　　　　　　 ,-';;;;;;;;;;;;;;;;;;;;;;;;;ﾞｰ-;;;;;''"~~;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ﾞi,
　　　　　　　 r';;;;;;;;;;;;,,r'';;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ﾞヽ,
　　　　　　　,!;;;;;;;;;,;;;r';;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,r'";;;;;;r';;;;;;;;;;;;;;;;;;;;;;;;;;;ヽ
　　　　　 ,r'";;;;;;;r';;;;ﾞt;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;,r'';;;;;;;;;,r'";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ﾞi,
　　　　　ｌ;;;;;;;;;;;;i';;;;;;;;;;;ヽ､;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;..-'";;;;;;;;;;,r'';;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ﾞi
　　　　　ﾞt,;;;;;;;;l;;t_;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ヽ.,;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ﾞi
　　　　 　 /;;;;;;;l;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ヽ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;ﾞi

>>2
それホフマンｗｗｗｗｗｗｗ
しかもそれ第五章

>>3
それハマーン

ttp://www.nikonet.or.jp/spring/sanae/inf_box/encode/encode.htm
ここの下のほうにちょっぴし載ってた
わけわかんね。
だがこれを覚えないことには俺は向上できないっ！！

http://72.14.203.104/search?q=cache:hJ3aMRxn2FcJ:www.geocities.jp/m_hiroi/zsaru/zfix20.html+%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7%E5%8C%96+decode&hl=ja&gl=jp&ct=clnk&cd=3
なんかよさげなところのグーグルキャッシュ

よんだ？

呼んだ
ホフマン符号化について詳しく教えてくれ

>>9
今から説明する
まっとれ

ハフマン符号化、というが、基本的に圧縮技術だと考えればおｋ
zipとかpngとかで使われてる。

まず、画像だろうとエロ動画だろうと基本的に数字の羅列で出来てるのは知ってるよな？

>>9
ホ　ほんとのところは
フ　普通の女の子でいたい
マ　ママは私に頑張ってというけれど
ン　ン〜、マンダム

って、1聞いてるか？

まず、ハフマン符号化をするにあたって、その数字の羅列の特徴について調べる。

例として画像データを挙げてみようか。白黒bmpで日の丸を書いてあるものを想像してくれ。
↓みたいな感じにデータとしては保存してあるわけだ。

255 255 255 255 255 255 255 255 255
255 255 255 255 　 0 255 255 255 255
255 255 255 　 0 　 0 　 0 255 255 255
255 255 　0 　 0 　 0 　 0 　 0 255 255
255 255 　0 　 0 　 0 　 0 　 0 255 255
255 255 255 　 0 　 0 　 0 255 255 255
255 255 255 255 　 0 255 255 255 255
255 255 255 255 255 255 255 255 255

これを、ハフマン符号化することによって
0=255
1=0
を符号として定義することによってこの画像は
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0
と置換できる。0,1だけで成り立ってるんだからbitとして上手く保存すれば1/8くらいのサイズになるのは理解できるよな？

1が聞いてないなら話す意味ねーじゃんｗｗｗ
一人で踊らされた俺ﾜﾛｽｗ

うはｗｗｗ　パトラッシュ眠くなってきたおｗｗｗｗ

>>16
でも続けてｗｗｗｗｗｗわかりやすいよ。
おまいいいヤシｗｗｗｗｗｗｗｗｗｗｗｗｗ

>>17
ちょｗｗｗおまｗｗｗｗ
これはgifとかでも似たような技術が使われている。圧縮の基礎だ。

>>18
わかったﾉｼ

ハフマン符号化ってののすごいところは、出現率が高いデータほど小さいbitに収める。って所だ。
さっきの日の丸は2色データだったが、3色だったらどうするのか。
そうなったら、3色目についても符号を割り当ててやればいい。

さっきの画像で言うと
255 255 255 255 255 255 255 255 255
255 255 255 128 　 0 128 255 255 255
255 255 128 　 0 　 0 　 0 128 255 255
255 255 　0 　 0 　 0 　 0 　 0 255 255
255 255 　0 　 0 　 0 　 0 　 0 255 255
255 255 128 　 0 　 0 　 0 128 255 255
255 255 255 128 　 0 128 255 255 255
255 255 255 255 255 255 255 255 255
灰色の128ってのを加えたぞ。符号化するには
0=255 ;1=0 ;2=128
として
0 0 0 0 0 0 0 0 0
0 0 0 2 1 2 0 0 0
0 0 2 1 1 1 2 0 0
0 0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0 0
0 0 2 1 1 1 2 0 0
0 0 0 2 1 2 0 0 0
0 0 0 0 0 0 0 0 0
となり、2が加わる。　ひぇー、こうなったらbitじゃ保存できねー！と挫折するなかれ。
2のために、2bit割いてやれ。幾分圧縮後のサイズは大きくなるが、それは情報量という概念からしょうがない問題だ。

ID:atRtATOU0に惚れそうです

惚れました

うはｗｗｗｗｗｗｗｗｗおｋｗｗｗｗｗｗｗｗｗｗｗ

うはｗｗｗｗｗすげー分かり易いｗｗｗｗｗｗｗｗｗｗｗｗｗ

まじで友達になりたいｗｗｗｗｗｗｗｗ

で、2のために2bit割いてやるわけだが、当然これは圧縮効率が悪い。
この先、64とか192とかデータが出てきたときに、2bitじゃ足りなくなるのも容易に想像できる。その場合は3bitでも4bitでも割り振って使え。
どんなに割り振っても、0〜255のデータの列を扱ってる限りは8bit以下で足りる。

だが、圧縮効率を高めるためには1つでも少ないビットで終わらせなきゃならん。
そのために、全データを概して見て、一番出現率の高いデータに少ないbit、出現率の低いデータに多いbitを割いてやることが一番のポイント。

>>22-26
ありが�d
書いてる甲斐があるよ。

ごめん説明してくれてた人マジでごめん
今飯食ってた
今から説明読む
ありがとう

>>29
ﾉｼ

例としては、適当なグラフィックソフトでpng保存をしたときに、色数を増やすとどんどんデータが大きくなっていく。

以前photoshopで、砂嵐に半透明の砂嵐を重ね雲模様を重ね…。と、非常に情報量の多い砂嵐をpng保存してみたら
bmpよりもサイズが大きくなったｗｗｗｗｗｗ
それは、0〜255全部のデータの出現率が高いせいで、最初の『ハフマン符号の定義部分』だけデータ量が増えたんだろうな。

気が向いたら試してみれ。同じピクセルサイズの画像でも、色数が多いか少ないかでzipによる圧縮率は大きく違う。

thx!

さープログラミングしたくなってきたから仕事しよ

んで、ちょっと頭が良い香具師なら、>>27について
「ん？2って2進数で表すと10だよなぁ…、これは元に戻すときに0 255という2つのデータになっちゃって128が消えちゃうんじゃ？」と考えたはずだ。

これについて説明する。

『ハフマン符号の定義部分』てのは
>>21で言うと　0=255 ;1=0 ;2=128
の事だよな？

>>33正解。おまいは賢いな。

実は、この>>32の部分がハフマン符号化をハフマン符号化たらしめる一番の特徴で

0=255 ; 1=0 ; 2=128　と定義する代わりにもっと効率よく
「ハフマンツリー」ってのを構築するのだ。

ちょｗｗその前に誰か「バックスラッシュ」ってどうやって打つのか教えてくれｗｗｗｗｗ／←の左右逆の奴ｗｗｗｗ

>>33
だろうな
本職ＰＧなのにハフマン符号化を始めて知った俺ガイル
携わらない部分って結構あるもんだなーと思った
>>ID:atRtATOU0 ｶﾞﾝｶﾞﾚ。仕事の合間に勉強させてもらう

「きごう」で変換するんだｽﾈｰｸ

「ななめ」でたぶん打てるお！

>>36 >>37
�dクス！んじゃ続行する！

おまえさんは説明してくれてるんだから�dクス言うのはこっちの立場ですよ
�dクス

忍たまみたいなボケと突っ込みでﾜﾛﾀ

ハフマンツリーってのは、簡単に言ってこういう風になってる

　　　　　0／ 　　　 ＼1

　　 0／ 　　　 ＼1(255) 0／ ＼1(0)

　0／＼1(128)　　　　　　0／＼1(64)
こうして、次のビットが0か1かで上から樹形図を枝分かれしながら下りてくる。
データのbitに忠実に下りてきて、( )が付いてる地点に到達したら復号完了。次のデータに移るわけだ。

このツリーで行けば 01=255　;　11=0 ; 101=64　って定義される。
重要なのは、出現率の高いデータほどツリーの上のほう=少ないビット数で復号できる地点に置くって事だ

　　　　　0／ 　　　　　　　 ＼1

　　 0／ ＼1(255)　　　 0／ ＼1(0)

　0／＼1(128)　　　　0／＼1(64)
ツリーのAAずれた…AAは苦手だ…orz

ttp://bluestar9999.hp.infoseek.co.jp/a_report_dq4_0022.jpg
後衛にいるのがホフマン

ttp://bluestar9999.hp.infoseek.co.jp/a_report_dq4_0011.jpg

これらを符号化するのか・・・やっかいだな

>>42
判り易いよ。気にせずに続けてくれ！

http://live22x.2ch.net/test/read.cgi/news/1142482168/

16 ：番組の途中ですが名無しです ：2006/03/16(木) 13:13:21.24 ID:ODhob2Xf0
VIPって何？池沼板なの？

17 ：番組の途中ですが名無しです ：2006/03/16(木) 13:13:37.14 ID:eIJfTN8L0
>>16
そうだよ

29 ：番組の途中ですが名無しです ：2006/03/16(木) 13:15:33.03 ID:8sQnckoJO
>>16
小学生板だよ

36 ：番組の途中ですが名無しです ：2006/03/16(木) 13:17:25.70 ID:mdrQPzzj0 ?
VIPではクオリティ＝キチガイ度が高いスレじゃないと住民にかまってもらえないからな

41 ：番組の途中ですが名無しです ：2006/03/16(木) 13:18:53.38 ID:rOVwOV1N0
( 　ﾟ,_ゝﾟ)ﾊﾞｶｼﾞｬﾈｰﾉ
売ればいいのに

47 ：番組の途中ですが名無しです ：2006/03/16(木) 13:21:18.04 ID:YU5FNyYo0
これがVIPクオリティとか言い出すんだろ？
何だこいつら

59 ：番組の途中ですが名無しです ：2006/03/16(木) 13:31:07.62 ID:brciF2y00
びっぱー＋ゲーム脳
最悪だな

67 ：エスティ [sage] ：2006/03/16(木) 13:39:28.12 ID:WgA5o1aS0 ?
基地外ははたで見てるのが一番面白い

ついでに、>>42によれば001=128になるな。

ハフマンツリーの形はデータの出現率の割合によって変わる

具体的に白塗りの紙に、赤やら青やらが点在しているだけだったらツリーの形は
　　　　　0／ 　　　　 ＼1(白)

　　 0／ ＼1

　0／＼1(赤) 0／＼1(青)
ってなるかも知れない。 こうすれば、一番出現率の高い白のピクセルが1bitで表現できるから高い圧縮率が期待できる。
その分（赤）=001　(青)=011ってなって、多めにbitを消費しちゃうが
赤・青の存在数が少ないなら白のピクセルで削った分で十分おつりが来る。

こういう折り合いを上手くつけるのが難しい。

　　　　　0／ 　　　　 ＼1(白)

　　 0／ 　　　　＼1

　0／＼1(赤) 0／＼1(青)
またずれた…orz


これで一通りハフマンの概念についての説明はおしまい。
おまいらガンガレ！

質問は受け付ける！

>>48
乙！！�dクス！！！
ちと、>>21でシミュレートしてみる

うほっ！わかりやすい説明してくれてありがとう！
つまり一番よく使われているものから順に樹形図作って
一番多く使われているのに小さい数値を割り当てるってこと？
やっぱ難しいな

>>50
そうそう、分かりやすい要約�dクス。
俺は樹形図の作り方で挫折した…orz

あー、それでPNGは減色するとサイズがむちゃくちゃ減るのか！！
なぞが解けた！！
atRtATOU0は教師ですか？？

>>21で、仮にハフマンツリーを
　　　　　0／ 　　　　 ＼1(白)

　　 0／ 　　　　＼1

　0／＼1(灰) 0／＼1(黒)

とすると
0 0 0 2 1 2 0 0 0
（ 0=白 ;1=黒 ;2=灰）
は
１１１００１０１１００１１１１
のビット配列になるでおｋ？

>>53
大正解。それは2バイトで保存できるから、元データが9バイトあることを考えれば2/9くらいに圧縮できた事になるな。
>>52
ドット打ちするときにも、データの数字は出来るだけ少ないパターンにしておくと圧縮率いいお！
俺がドット打ちするときは32の倍数の数字しか使ってない。

白黒青赤黄緑紫水色は全部0と255だけで表現できるから、8色でドット打ちすると圧縮率は鬼。
あと漏れはただの卒業式終わって暇な高校生orz

>>54
うはｗｗｗ少し理解した気がする。
ただ、効率のいいハフマンツリーをどう作るかが問題だ。

スゲー高校生だな！！
ぐぐって出てきたサイトより、はるかに判り易いよ。
ﾃﾗ�dｸｽ！！！！！！

このスレたてた>>1にも感謝！

便乗で悪いんだけどさ
ttp://www.vipper.org/vip215231.c
これのハフマン符号化ってのがどうなってるのかわからないんだけど
たぶんcのプログラムかなんかで書かれてるんだけど何がなされてるの？
というかゲーム改造 文字コードの領域に入っちゃうから
ゲーム改造好きのプログラマーじゃないとわけわかんないかもしれんが

これが読めるとドラクエ5の改造が色々と出来て面白いことになるのだが
はい、ゲーム厨ですみません

>>56
本職の俺が解読してやろうか？
今日は暇だからいくらでも時間避ける

×やろうか？
○やってみようか？

>>58-59
ママママママジですか！！！
ゲームの内容だからただハフマン符号がわかるだけじゃわけわかめになっちゃうと思って
ム板も駄目だし頼りにするところがなかったんですよ。

両刀使いですか？

ハフマン符号はID:atRtATOU0のおかげで理解した。
もしもちゃんとしたｿｰｽｺｰﾄﾞならｺﾒﾝﾄも期待できるし、
仕様ﾚﾍﾞﾙくらいなら解読出来ると思う。

今最中

ええええええ！！！！！！！！
ID:atRtATOU0先生って高校生だったのですか！！！！！！
26歳くらいのプログラマーかなにかしてらっしゃるお方かと思っていましたよ・・・
お若いのにすごい・・・

解読。

まずこのｿｰｽはＣ言語。
やってることはﾊﾌﾏﾝ符号化が云々よりも、ﾊﾌﾏﾝ符号化されたﾃﾞｰﾀﾌｧｲﾙを参照して
ﾌｫﾝﾄﾃﾞｰﾀをﾌｧｲﾙ出力してるだけ。
多分この関数呼んだ後、「出力したﾌｫﾝﾄﾃﾞｰﾀを参照→画面に表示」ってやってると思う

違ったら誰かﾌｫﾛｰ頼む

うおー、ありがとうー！
ちなみに根城はココ
http://game9.2ch.net/test/read.cgi/gameurawaza/1139887784/

ttp://image.i-bbs.sijex.net/bbs/azma111/1142423166316o.png
サンテョの一番始めのメッセージを変更をしようと思ったが
ハフマン圧縮されているため文字がグチャグチャになってエラーになったの図

あと、>>21のデータが本当にアレだけなら
　　　　　0／ 　　　　 ＼1(白)
　　 0／(灰)＼1 (黒)
とツリーを作れば

0 0 0 2 1 2 0 0 0
（ 0=白 ;1=黒 ;2=灰）
は
111000100111
の、12ビットで表現できる。効率の良いツリーって難しいなorz
あと、>>1は理解できた？おまいさんが理解するまでつきあうお(｀･ω･´)

>>26
ちょｗｗｗｗ26歳とかどこから出てきたｗｗｗｗｗｗｗｗ漏れはただのしがないVIPPERだｗｗｗｗｗｗｗ

>>64
おｋｗｗｗ把握したｗｗｗｗｗｗ
ｶﾞﾝｶﾞﾚとしか言えん罠ｗっうぇｗっうぇｗｗｗ

>>64
ハフマンの符号は可変長だから、bit単位で操作してやらないと大変なことになるな

ttp://www.vipper.org/vip215259.png
ロマサガのメッセージ改変なんかはクソ簡単だったんだ。
一文字は1バイトのデータでできてたから・・・

ドラクエはハフマンやら可変長やらでわけわかめ

ほしゅ

>>69
1文字を構成するビット数が不定なんだから、そのままじゃ絶対無理。
一回符号を全部復号してから改変しなきゃダメ。んで再圧縮して還元するしかない。

それはそうと>>1さんﾏﾀﾞｰ？分からないところとか。
話を一通り理解できたのなら、上の方で張られてるハフマン符号のを読んでみるといいさ。

ツリーの意味がわからん

>>72
意味って、ツリーの存在意義？定義？分岐処理？

全て

>>74
漠然とした質問だから答えにくいが…。

まず、ツリーってのはただの樹形図の事な。ちなみに枝の先に付いてる要素のことを「葉」って呼んだりする。

存在意義は、圧縮させるときに、効率よく一塊のデータと1つの符号を対応させる為にある点だ。

枝分かれは必ず二又であり。三つ又にはならない。それは1bitが0か1しか表現できないからだ。
樹形図を一番上から辿っていくにあたり、それぞれの分岐点で0か1かを参照していく。0なら左、1なら右。
そして、どこかで葉にたどり着けば、そこまでの道順⇔目的地が1対1で対応しあうわけだ。
0と1のみで作られる道順と、0〜255までの値を示すデータが対応しあうわけだな。

あとはその道順だけを書き並べていけば、元のデータの羅列をもっと少ないデータ量で表現できますよ。ということだ。

ここまでのこと、おｋ？ダメなら具体的にどこからダメだったのか教えてくれ…。

いまさらだが、
＞全部のデータの出現率が高いせい
これが惜しいな。
全部のデータが全体的に均等なせいだ。

一応補足
例えば2x2の絵を仮定した場合。
２色
255 0
0 255
の場合は、0:50% 255:50%
３色
255 128
0 255
の場合は、0:25% 128:25% 255:50%
４色
255 128
0 64
の場合は、0:25% 64:25% 128:25% 255:25%
この出現率が均等になると、bit長の短いものも長いものも同じ位でてきてしまう。
データの量が増えた場合、bit長は元のbit長より長くなるものもある。
結果、元のファイルより大きくなるということが起きる。

>>78
確かに圧縮作業の過程でファイルサイズがでっかくなｒったことが何度かあった

本当に分かり易いな
ちょっと為になったぜ

暗号化とか圧縮のアルゴリズム思いついた人って本当頭良すぎ
こればかりは知識云々なんかじゃなくて「発想力」なんだろうな…
裾具

保守しといたほうがいいかもわからんね

>>78
正直スマンかった
>>81
エントロピーだとか情報量だとかいう学問を深めていくと
最終的にたどり着く答えがこういうのしかなくなっちゃうのだ(´･ω･｀)
符号化みたいなのに頼らずに圧縮アルゴリズムを作れたらそれこそ神レベルの「発想力」だと思われ。
>>82
ぇ