可逆圧縮アルゴリズム
可逆圧縮アルゴリズムとは、圧縮したファイルなどを圧縮する前に戻せるアルゴリズムのことを言います。
たとえばメールで圧縮したエクセルファイルとかを送ったことありませんか?
zipファイルとかです。これは可逆圧縮アルゴリズムが使われています。なぜなら、圧縮したファイルを圧縮する前に戻せますからね。
ランレングス符号化(RLE)
ランレングス符号化は、単純なアルゴリズムで今も広く使われています。
ランレングス符号化は、[ある値]×[その値が連続して繰り返されている回数]で表示するアルゴリズムです。
例えば、ccsaassss55ssaaaaaaa
という値をランレングス符号化を使って圧縮してみましょう。
すると、c2s1a2s452s2a7
になります。もとは、20文字だったものが、14文字に圧縮できました。
しかし、このアルゴリズムは時として、圧縮前の文字数より圧縮後の文字数が増えてしまうことがあります。
それがデメリットです。
ハフマン符号化
このアルゴリズムを知るには、まず符号化を知らねばなりません。
符号化とは、データを「0」と「1」の2進数に置き換えることです。
コンピュータが扱う最小単位のことをビット(bit)といい、1ビットで表現できるのは0と1だけです。2ビット、3ビット…と増えていくと倍々に表現できる数も増えてきます。
話しは戻ってハフマン符号化とは、データが現れる出現頻度に注目した圧縮方法です。
例えば、DACDBCDBCD
という数字を圧縮しようと考えます。
まず、出現頻度を表にして考えてみましょう。
A | B | C | D |
---|---|---|---|
1 | 2 | 3 | 4 |
このような表現ができるかとおもいます。出現回数が多い順にビット列0、ビット列1、ビット列10、ビット列11を与えていくんです。
すると、0111010101010
というふうに表現できます。13ビットで表現できます。
もし、出現回数を考えずにAから順に0, 1, 10, 11とビット列を与えていくと、11110111101111011
18ビットで表現しないといけなくなります。
このようにビット数を減らして圧縮する方法がハフマン符号化というアルゴリズムです。
非可逆圧縮アルゴリズム
非可逆圧縮アルゴリズムは、可逆圧縮アルゴリズムの逆で圧縮してしまったら、圧縮前に戻せないアルゴリズムのことです。
その例を何個か見ていきましょう。
画像圧縮
画像圧縮はどのように行われいるかというと、めちゃくちゃ簡単にいうと、人間の目では違いが分からない色を消すことによって、圧縮しているんです。コンピュータは約1677万色の色を表現できます。それに対して人間が理解できる色は、700~800万色なので、半分くらいの色は消しても画像を見ることに問題はないんですね。
音声圧縮
音声圧縮も画像圧縮と考え方は変わりません。人間には聞き取れない音波的なものがあるみたいです。それを消すことによって音声圧縮をしているみたいです。
動画圧縮
動画というのは文字通り、画像が動いているものになります。つまり、何万枚の画像が高速で動くことによって動画をなしているんですね。
そこでどう圧縮するのかというと、1枚1枚の画像の中で変化する部分と変化しない部分の差分をとり、それを記憶しておくことで圧縮が可能になります。
どの圧縮方法も専門的な話は個人的に難しかったので分かる方がいらっしゃいましたら、ご教示いただけると幸いです。
【参考記事】