コードの実例.
可逆圧縮
コンピュータ上でよく扱われるLZH、ZIP、CABや、画像圧縮形式のPNG、GIFなどが可逆圧縮である。
アルゴリズム.
すべてのデータを効果的に圧縮できる可逆圧縮アルゴリズムは存在しない（可逆圧縮の限界の節を参照）。そのため、データの種類によって多くのアルゴリズムが存在する。下記に主要な可逆圧縮方式を列挙する。
可逆圧縮の限界.
可逆圧縮アルゴリズムはすべての入力データに対して圧縮後のデータサイズが圧縮前より小さいことを保証できない。すなわち、どのような可逆圧縮アルゴリズムでも圧縮処理後にデータサイズが小さくならない入力データが存在し、また圧縮処理後にデータサイズが小さくなる入力データが存在する場合、圧縮処理後にデータサイズが大きくなる入力データも必ず存在する。前者の証明は下記の通り。
後者の証明は鳩の巣原理を用いたものであり、下記の通りとなっている。
可逆圧縮アルゴリズムのベンチマークにはが広く使われている。サイズ、速度、メモリ使用量がトレードオフの関係にあり、たとえばデータ圧縮比が高いアルゴリズムはメモリ使用量が多い場合が多い。
非可逆圧縮
一般的に「データ圧縮」というときには、広い意味で非可逆圧縮も含めることが多いが、狭義のデータ圧縮では非可逆圧縮は入らない。「データ圧縮」の正確な定義は、「情報量を保ったまま」データ量を減らした別のデータに変換することすなわち可逆圧縮をいうからであり、非可逆圧縮の場合は「情報量を保ったまま」という定義から外れる。
非可逆圧縮では、圧縮により一部のデータは欠落するが、人間の感覚に伝わりにくい部分は情報を大幅に減らし、伝わりやすい部分の情報を多く残すことで、劣化を目立たなくする。この結果、すべてのデータを均一に扱う可逆圧縮と比較して圧倒的な圧縮率が得られる。また、圧縮率と品質を両天秤にかけることができ、目的や環境に応じて適切なバランスを選ぶことができる。例えば、低速なナローバンドを使う場合や、データが高い品質を必要としない場合は、圧縮率を高めてデータ量を小さくする。逆に、高速なブロードバンドインターネット接続を使う場合や、より鮮明なコンテンツを表示する場合などは、圧縮率を低くして品質を高くする。
名称の由来.
歴史.
概要.
UNIXとの違い.