トマトペースト
<<2月のオススメ | トップ | 荒 ら し サ イ ト 荒 ら そ う ぜ>>
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
-->
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
【--/--/-- --:--】 | スポンサー広告 |
<<2月のオススメ | トップ | 荒 ら し サ イ ト 荒 ら そ う ぜ>>
プログラミングできる天才ちょっとこい

1 :VIPがお送りします :2006/03/16(木) 12:18:15.77 ID:bTrZTv+zP
ハフマン符号化ってなに?


6 :VIPがお送りします :2006/03/16(木) 12:21:29.39 ID:bTrZTv+zP
ttp://www.nikonet.or.jp/spring/sanae/inf_box/encode/encode.htm
ここの下のほうにちょっぴし載ってた
わけわかんね。
だがこれを覚えないことには俺は向上できないっ!!


8 :VIPがお送りします :2006/03/16(木) 12:24:05.09 ID:8379LeTO0
よんだ?

9 :VIPがお送りします :2006/03/16(木) 12:30:30.55 ID:bTrZTv+zP
呼んだ
ホフマン符号化について詳しく教えてくれ


11 :VIPがお送りします :2006/03/16(木) 12:51:05.98 ID:atRtATOU0
ハフマン符号化、というが、基本的に圧縮技術だと考えればおk
zipとかpngとかで使われてる。

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


14 :VIPがお送りします :2006/03/16(木) 12:58:56.32 ID:atRtATOU0

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

例として画像データを挙げてみようか。
白黒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


15 :VIPがお送りします :2006/03/16(木) 13:02:26.71 ID:atRtATOU0

これを、ハフマン符号化することによって
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くらいのサイズになるのは理解できるよな?


17 :VIPがお送りします :2006/03/16(木) 13:03:54.27 ID:C3vBbOXz0
うはwww パトラッシュ眠くなってきたおwwww


19 :VIPがお送りします :2006/03/16(木) 13:05:31.17 ID:atRtATOU0
>>17
ちょwwwおまwwww
これはgifとかでも似たような技術が使われている。圧縮の基礎だ。


16 :VIPがお送りします :2006/03/16(木) 13:03:49.16 ID:atRtATOU0
1が聞いてないなら話す意味ねーじゃんwww
一人で踊らされた俺ワロスw


18 :VIPがお送りします :2006/03/16(木) 13:05:22.80 ID:3do4zmF50
>>16
でも続けてwwwwwwわかりやすいよ。
おまいいいヤシwwwwwwwwwwwww

20 :VIPがお送りします :2006/03/16(木) 13:07:58.85 ID:atRtATOU0
>>18
わかったノシ

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


21 :VIPがお送りします :2006/03/16(木) 13:12:36.61 ID:atRtATOU0

さっきの画像で言うと


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割いてやれ。幾分圧縮後のサイズは大きくなるが、
それは情報量という概念からしょうがない問題だ。


27 :VIPがお送りします :2006/03/16(木) 13:17:28.09 ID:atRtATOU0
で、2のために2bit割いてやるわけだが、当然これは圧縮効率が悪い。
この先、64とか192とかデータが出てきたときに、
2bitじゃ足りなくなるのも容易に想像できる。
その場合は3bitでも4bitでも割り振って使え。
どんなに割り振っても、0~255のデータの列を扱ってる限りは8bit以下で足りる。

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


25 :VIPがお送りします :2006/03/16(木) 13:16:48.79 ID:gezxbL4a0
うはwwwwwすげー分かり易いwwwwwwwwwwwww

26 :VIPがお送りします :2006/03/16(木) 13:16:56.29 ID:3do4zmF50
まじで友達になりたいwwwwwwww

22 :VIPがお送りします :2006/03/16(木) 13:14:51.17 ID:fKgSKQt40
ID:atRtATOU0に惚れそうです

23 :VIPがお送りします :2006/03/16(木) 13:16:16.22 ID:I+Q1kzQG0
惚れました

28 :VIPがお送りします :2006/03/16(木) 13:18:26.17 ID:atRtATOU0
>>22-26
ありが?
書いてる甲斐があるよ。


29 :VIPがお送りします :2006/03/16(木) 13:21:31.79 ID:bTrZTv+zP
ごめん説明してくれてた人マジでごめん
今飯食ってた
今から説明読む
ありがとう


30 :VIPがお送りします :2006/03/16(木) 13:22:38.31 ID:atRtATOU0
>>29
ノシ

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

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

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


32 :VIPがお送りします :2006/03/16(木) 13:24:53.28 ID:atRtATOU0
んで、ちょっと頭が良い香具師なら、>>27について
「ん?2って2進数で表すと10だよなぁ…、これは元に戻すときに
 0 255という2つのデータになっちゃって128が消えちゃうんじゃ?」と考えたはずだ。

これについて説明する。


33 :VIPがお送りします :2006/03/16(木) 13:25:32.33 ID:3do4zmF50
『ハフマン符号の定義部分』てのは
>>21で言うと 0=255 ;1=0 ;2=128
の事だよな?

34 :VIPがお送りします :2006/03/16(木) 13:27:57.00 ID:atRtATOU0
>>33正解。おまいは賢いな。

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

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

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


37 :VIPがお送りします :2006/03/16(木) 13:30:40.78 ID:bTrZTv+zP
「ななめ」でたぶん打てるお!


41 :VIPがお送りします :2006/03/16(木) 13:39:45.37 ID:atRtATOU0

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


     0/     \1

   0/     \1(255) 0/ \1(0)

 0/\1(128)      0/\1(64)


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

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


42 :VIPがお送りします :2006/03/16(木) 13:40:36.90 ID:atRtATOU0


     0/         \1

   0/ \1(255)    0/ \1(0)

 0/\1(128)    0/\1(64)


ツリーのAAずれた…AAは苦手だ…orz


46 :VIPがお送りします :2006/03/16(木) 13:48:08.72 ID:atRtATOU0

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

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

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


     0/      \1(白)

   0/ \1

 0/\1(赤) 0/\1(青)


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

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


47 :VIPがお送りします :2006/03/16(木) 13:49:32.03 ID:atRtATOU0


     0/      \1(白)

   0/     \1

 0/\1(赤) 0/\1(青)


またずれた…orz

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


48 :VIPがお送りします :2006/03/16(木) 13:50:42.99 ID:atRtATOU0
質問は受け付ける!


49 :VIPがお送りします :2006/03/16(木) 13:55:03.34 ID:3do4zmF50
>>48
乙!!?クス!!!
ちと、>>21でシミュレートしてみる

50 :VIPがお送りします :2006/03/16(木) 13:58:10.88 ID:bTrZTv+zP
うほっ!わかりやすい説明してくれてありがとう!
つまり一番よく使われているものから順に樹形図作って
一番多く使われているのに小さい数値を割り当てるってこと?
やっぱ難しいな


51 :VIPがお送りします :2006/03/16(木) 13:59:05.66 ID:atRtATOU0
>>50
そうそう、分かりやすい要約?クス。
俺は樹形図の作り方で挫折した…orz


52 :VIPがお送りします :2006/03/16(木) 14:00:47.37 ID:1ZdF9LuX0
あー、それでPNGは減色するとサイズがむちゃくちゃ減るのか!!
なぞが解けた!!
atRtATOU0は教師ですか??

53 :VIPがお送りします :2006/03/16(木) 14:05:08.08 ID:3do4zmF50
>>21で、仮にハフマンツリーを


     0/      \1(白)

   0/     \1

 0/\1(灰) 0/\1(黒)


とすると
0 0 0 2 1 2 0 0 0
( 0=白 ;1=黒 ;2=灰)

111001011001111
のビット配列になるでおk?

54 :VIPがお送りします :2006/03/16(木) 14:12:36.74 ID:atRtATOU0
>>53
大正解。それは2バイトで保存できるから、
元データが9バイトあることを考えれば2/9くらいに圧縮できた事になるな。
>>52
ドット打ちするときにも、
データの数字は出来るだけ少ないパターンにしておくと圧縮率いいお!
俺がドット打ちするときは32の倍数の数字しか使ってない。

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


55 :VIPがお送りします :2006/03/16(木) 14:17:16.87 ID:3do4zmF50
>>54
うはwww少し理解した気がする。
ただ、効率のいいハフマンツリーをどう作るかが問題だ。

スゲー高校生だな!!
ぐぐって出てきたサイトより、はるかに判り易いよ。
テラ?クス!!!!!!

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

62 :VIPがお送りします :2006/03/16(木) 14:34:18.65 ID:bTrZTv+zP
ええええええ!!!!!!!!
ID:atRtATOU0先生って高校生だったのですか!!!!!!
26歳くらいのプログラマーかなにかしてらっしゃるお方かと思っていましたよ・・・
お若いのにすごい・・・


65 :VIPがお送りします :2006/03/16(木) 14:38:52.83 ID:atRtATOU0

あと、>>21のデータが本当にアレだけなら


     0/      \1(白)
   0/(灰)\1 (黒)


とツリーを作れば

0 0 0 2 1 2 0 0 0
( 0=白 ;1=黒 ;2=灰)

111000100111
の、12ビットで表現できる。効率の良いツリーって難しいなorz
あと、>>1は理解できた?おまいさんが理解するまでつきあうお(`・ω・´)


72 :VIPがお送りします :2006/03/16(木) 15:33:33.00 ID:W/2lUz1u0
ツリーの意味がわからん

73 :VIPがお送りします :2006/03/16(木) 15:37:12.60 ID:atRtATOU0
>>72
意味って、ツリーの存在意義?定義?分岐処理?


74 :VIPがお送りします :2006/03/16(木) 15:42:38.32 ID:W/2lUz1u0
全て

75 :VIPがお送りします :2006/03/16(木) 15:59:34.63 ID:atRtATOU0
>>74
漠然とした質問だから答えにくいが…。

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

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

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

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


77 :VIPがお送りします :2006/03/16(木) 16:50:26.99 ID:0YJGRb4r0
いまさらだが、
>>30の
>全部のデータの出現率が高いせい
これが惜しいな。
全部のデータが全体的に均等なせいだ。

78 :VIPがお送りします :2006/03/16(木) 17:05:45.23 ID:0YJGRb4r0
一応補足
例えば2x2の絵を仮定した場合。
2色
255 0
0 255
の場合は、0:50% 255:50%
3色
255 128
0 255
の場合は、0:25% 128:25% 255:50%
4色
255 128
0 64
の場合は、0:25% 64:25% 128:25% 255:25%
この出現率が均等になると、bit長の短いものも長いものも同じ位でてきてしまう。
データの量が増えた場合、bit長は元のbit長より長くなるものもある。
結果、元のファイルより大きくなるということが起きる。

80 :VIPがお送りします :2006/03/16(木) 17:15:46.34 ID:gezxbL4a0
本当に分かり易いな
ちょっと為になったぜ

81 :VIPがお送りします :2006/03/16(木) 18:26:09.12 ID:WX4tXpLZ0
暗号化とか圧縮のアルゴリズム思いついた人って本当頭良すぎ
こればかりは知識云々なんかじゃなくて「発想力」なんだろうな…
裾具

83 :VIPがお送りします :2006/03/16(木) 19:30:03.50 ID:atRtATOU0
>>78
正直スマンかった
>>81
エントロピーだとか情報量だとかいう学問を深めていくと
最終的にたどり着く答えがこういうのしかなくなっちゃうのだ(´・ω・`)
符号化みたいなのに頼らずに圧縮アルゴリズムを作れたら
それこそ神レベルの「発想力」だと思われ。

スポンサーサイト
【2006/03/16 20:06】 | (´・∀・`) ヘー | トラックバック(0) | コメント(3) |
<<2月のオススメ | トップ | 荒 ら し サ イ ト 荒 ら そ う ぜ>>
コメント
ハフッ、ハフハフ ハムッ!
【2006/03/16 21:25】 URL | 名乗るのマンドクセ #79D/WHSg[ 編集]
atRtATOU0は頭いいな
【2006/03/16 22:47】 URL | 名乗るのマンドクセ #79D/WHSg[ 編集]
ハムッ ハフハフ ホフッ!
【2006/03/16 22:48】 URL | 名乗るのマンドクセ #79D/WHSg[ 編集]
トラックバック
トラックバックURL
http://nantara.blog73.fc2.com/tb.php/461-0adcb220
この記事にトラックバックする(FC2ブログユーザー)
オススメ

月別アーカイブ

カテゴリー

ブログ内検索

個人的に大好き


リンク

最近のコメント

最近のトラックバック

その他

2ちゃんねる関連リンク・2ちゃんねらオンリ検索エンジン

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。