Hoffman符号 2011/05/23.

Presentation on theme: "Hoffman符号 2011/05/23."— Presentation transcript:

1 Hoffman符号 2011/05/23

2 可逆圧縮と不可逆圧縮 可逆圧縮 完全に元に戻る圧縮方法 不可逆圧縮 完全に元には戻らない圧縮方法 画像や動画に用いられる場合が多い
　完全に元に戻る圧縮方法 不可逆圧縮 　完全に元には戻らない圧縮方法 　画像や動画に用いられる場合が多い 　JPEG MPEGなど

3 ＲＬＥ 例えば元データが「abcd」の場合、「3abcd」と符号化される。 例えば元データが「aaaa」の場合、「-3a」と符号化される。
Packbits BMP

4 ＲＬＥ（２） 画像データの圧縮向きであり、文書データ等の圧縮には向かない。 圧縮(符号化)／展開(復号化)が高速。 圧縮率が悪い。
実際の応用例は少ないが、データ圧縮解説書や情報理論の解説書では簡単な圧縮法の例として多用されている。 圧縮／展開方法が簡単で理解しやすい……はずだと思う。(^^;)

5 ファイル圧縮 パソコン通信1980年代 ＮＴＴ回線、カプラー300bps モデムの登場 1200bps
いかにしてファイルを圧縮し通信費をかせぐか メールの登場 　バケツリレー式　TrailBlazer 9600bps

6 Ｓｈａｎｏｎ符号化 Shanon符号化圧縮したいデータに出現する記号の個数を求め、その個数で記号をソートする ソートしたデータを、なるべく総数が等しくなるようなところで二分割する。分割した片方のデータに0、もう片方のデータに1を割り当てる。 分割して出来た2つのデータをそれぞれ更に二分割していき、同様に0と1を割り当てていく

7 Shanon 符号化 AAAAABBBCCCCCCCD CCCCCCC AAAAABBBD < 0 >|< 1 >
< >|< > CCCCCCC AAAAA BBBD 　< >|< 　　 > 　 |< 0 >|< 1 >

8 Shanon 符号化 CCCCCCC AAAAA BBB D < 0 >|< 1 >
< >|< > |< >|< > |<0>|<1> A B C ... 0 D

9 Ｈｕｆｆｍａｎ符号化 静的Huffman符号化 動的（適応型）Huffman符号化

10 コンパクト符号 コンパクト符号 コンパクト符号とは、一意に復号可能な符号のうち、同じ符号アルファベットを用いる他の任意の符号よりも、平均符号長が大きくない符号のこと。ハフマン符号や算術符号が知られている。

11 LZ77符号化 Ziv and Lempel 1977 元データに含まれる記号の出現率などの事前情報を必要とせず、しかも元データが長くなればなるほど最良の圧縮効果が期待できる万能な符号のため、「ユニバーサル符号(universal coding)」と呼ばれて る

12 ＬＺ７７における圧縮（１）

13 ＬＺ７７における圧縮（２）