アルゴリズム、データ圧縮とは

（『Newton2021年11月号』から抜粋）

「データ圧縮」とは、そのデータの内容を失わないようにしつつ、データのサイズを小さくするアルゴリズムである。

私たちは日常的に、テレビ放送やインターネットなどで、圧縮されたデジタル・データを視聴している。

データの圧縮は２種に分かれ、元の状態に戻せる「可逆圧縮」と、元に戻せない「不可逆圧縮」がある。

可逆圧縮で簡単なものは、「ランレングス圧縮」である。

これは同じ文字が並んでいる所を、数字に置き換えて短くする。

例えば「aaaabbbcccc」だったら、「4a3b4c」にすることで短くする。
これならば簡単に元のデータに戻せる。

だが、かつてのパソコンは８色しか画像に使えなかったが、今では１６００万以上の色を識別する。

このようにデータが複雑化したので、同じ文字や色が続くことが少なくなり、ランレングス圧縮だけではデータ圧縮が難しくなった。

そこで、もう１つの可逆圧縮である「ハフマン符号化」が増えた。

コンピュータは全てのデータを０と１を使った「二進法」で表記するが、英語の文字は８ビット（二進法で８桁）で表記される。

８ビットで２５６通りを表記できるので、十分に英語を表記できる。

「ハフマン符号化」では、文字を８ビットで表記するのをやめて、代わりに多く登場する文字に短いビットを割り当てて、登場の少ない文字に長いビットを割り当てる。

この変換でデータを圧縮し、どのように変換したかのデータを添えることでいつでも元に戻せるようにする。

ハフマン符号化は、圧縮率が高くて、特許が無くて誰でも自由に使えるため、Zip形式の圧縮などに使われている。

次に不可逆圧縮を述べる。

実は画像や音声のデータには、人が感知できないデータも含まれている。

その部分を削除してデータを圧縮するのである。

ただし、削ったデータは元に戻せない。
（※補足すると、圧縮率を高めて削りを多くすると、人が分かる位に画像や音が劣化する）

不可逆圧縮は、データの質を保ったまま圧縮するのが重要である。

画像の場合、人間の目は明るさの変化には敏感だが、色の変化にはあまり敏感ではない。
そこで色の成分（データ）を削るのだが、その際に用いるのが「フーリエ変換」である。

フーリエ変換では、色のデータを単純な縞模様に分解して、縞の幅ごとに分ける。

そして人間が感知できない、幅の狭い縞模様を削除する。

JPEGのデータにする圧縮では、フーリエ変換だけではなく、可逆圧縮のランレングス圧縮やハフマン符号化も組み合わされている。

MP３やMP４も、フーリエ変換とハフマン符号化などを組み合わせて圧縮している。

（2022年8月5日に作成）