Hoffman符号 2011/05/23 可逆圧縮と不可逆圧縮 • 可逆圧縮 完全に元に戻る圧縮方法 • 不可逆圧縮 完全に元には戻らない圧縮方法 画像や動画に用いられる場合が多い JPEG MPEGなど ＲＬＥ • 例えば元データが「abcd」の場合、「3abcd」と 符号化される。 • 例えば元データが「aaaa」の場合、「-3a」と符 号化される。 • Packbits BMP ＲＬＥ（２） • 画像データの圧縮向きであり、文書データ等 の圧縮には向かない。 • 圧縮(符号化)／展開(復号化)が高速。 • 圧縮率が悪い。 • 実際の応用例は少ないが、データ圧縮解説 書や情報理論の解説書では簡単な圧縮法の 例として多用されている。 • 圧縮／展開方法が簡単で理解しやすい…… はずだと思う。(^^;) ファイル圧縮 • パソコン通信1980年代 • ＮＴＴ回線、カプラー300bps • モデムの登場 1200bps いかにしてファイルを圧縮し通信費をかせぐか • メールの登場 • バケツリレー式 TrailBlazer 9600bps Ｓｈａｎｏｎ符号化 • Shanon符号化圧縮したいデータに出現する 記号の個数を求め、その個数で記号をソート する ソートしたデータを、なるべく総数が等しくなる ようなところで二分割する。分割した片方の データに0、もう片方のデータに1を割り当てる。 分割して出来た2つのデータをそれぞれ更に 二分割していき、同様に0と1を割り当てていく Shanon 符号化 • AAAAABBBCCCCCCCD • CCCCCCC AAAAABBBD < 0 >|< 1 > • CCCCCCC AAAAA BBBD < 0 >|< 1 > |< 0 >|< 1 > Shanon 符号化 • CCCCCCC AAAAA BBB D < 0 >|< 1 > |< 0 >|< 1 > |<0>|<1> A ... 10 B ... 110 C ... 0 D ... 111 Ｈｕｆｆｍａｎ符号化 • 静的Huffman符号化 • 動的（適応型）Huffman符号化 コンパクト符号 • コンパクト符号 • コンパクト符号とは、一意に復号可能な符号 のうち、同じ符号アルファベットを用いる他の 任意の符号よりも、平均符号長が大きくない 符号のこと。ハフマン符号や算術符号が知ら れている。 LZ77符号化 • Ziv and Lempel 1977 • 元データに含まれる記号の出現率などの事 前情報を必要とせず、しかも元データが長く なればなるほど最良の圧縮効果が期待でき る万能な符号のため、「ユニバーサル符号 (universal coding)」と呼ばれて る ＬＺ７７における圧縮（１） ＬＺ７７における圧縮（２）
© Copyright 2024 ExpyDoc
