アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

圧縮アルゴリズムとは

データ圧縮とは、あるデータの情報量を保ったまま、データ量を圧縮することを指します。圧縮アルゴリズムには大きく分けて、圧縮前のデータを完全に再現することができる可逆圧縮と、多少のデータ欠損を認めたうえで効率的な圧縮率を実現する非可逆圧縮の2種類があります。

データ通信の時間や記憶空間を節約を行うために圧縮を行いますが、データはなぜ圧縮することができるのでしょうか。非可逆圧縮についていえば、精度の下がった場合でも耐えうるからです。例えば、JPEG はイメージデータを人間の視覚特性を利用して精度が下がっても劣化を目立たなくします。可逆圧縮においては、データの冗長性や偏りを見つけることができるためです。人間にとって意味のあるデータには何らかの偏りや法則性が見つかります。これを利用して圧縮することができます。

可逆圧縮

可逆圧縮とは圧縮後のデータから、元のデータを完全に再現できる圧縮アルゴリズムです。代表的なものには ランレングス圧縮(連長圧縮) や ハフマン符号 があげられます。

上述の通り、可逆圧縮ではデータの冗長性や偏りを見つけ出し利用することで圧縮を行います。例えば ランレングス圧縮 では、連続するデータ部分に冗長性を見出し、ハフマン符号ではデータの出現頻度に偏りを見出します。(例：英語では "e" の文字が最も出現確率が高くなります。)

• ランレングス圧縮(連長圧縮)
• ハフマン符号

非可逆圧縮

非可逆圧縮とは圧縮後のデータから、元のデータを完全に復元できない圧縮アルゴリズムです。画像や映像、音声など、人間の認知特性上伝わりずらい部分を大幅に減らし、重要となる部分の情報を多く残すようなアルゴリズムになります。逆に一部でも異なれば情報として価値がなくなるもの(テキストデータなど)にはあまり利用されません。

画像では JPEG 形式、音声だと MP3 形式などが代表的なアルゴリズムとしてあげられます。