「圧縮ファイル」はこの項目へ転送されています。複数のファイルを一つのファイルにまとめることについては「アーカイブ (コンピュータ)」をご覧ください。
データ圧縮(データあっしゅく、英: data compression)とは、あるデータを、そのデータの実質的な内容(情報、あるいはその情報量)を可能な限り保ったまま、データ量を減らした別のデータに変換すること。高効率符号化ともいう。
データ圧縮は、データ転送におけるトラフィックやデータ蓄積に必要な記憶容量の削減といった面で有効である。しかし圧縮されたデータは、利用する前に伸長(解凍)するという追加の処理を必要とする。つまりデータ圧縮は、空間計算量を時間計算量に変換することに他ならない。例えば映像の圧縮においては、それをスムーズに再生するために高速に伸長(解凍)する高価なハードウェアが必要となるかもしれないが、圧縮しなければ大容量の記憶装置を必要とするかもしれない。データ圧縮方式の設計には様々な要因のトレードオフがからんでおり、圧縮率をどうするか、(非可逆圧縮の場合)歪みをどの程度許容するか、データの圧縮伸長に必要とされる計算リソースの量などを考慮する[1]。
データ圧縮には、可逆圧縮と非可逆圧縮の2種類がある。可逆圧縮は、統計的冗長性を特定・除去することでビット数を削減する。可逆圧縮では情報が失われない。可逆圧縮は、数値データや文書、プログラムなど、1ビットの変化で情報の価値が大きく毀損されるようなデータに対して用いられる。一方で、非可逆圧縮は不必要な情報を特定・除去することでビット数を削減する[2]。非可逆圧縮ではいくらかの情報が失われる。非可逆圧縮は、音声や画像、動画など、細部が変化しても情報の意味が変わりにくいデータに対して用いられる。
アナログ技術を用いた通信技術においては通信路の帯域幅を削減する効果を得るための圧縮ということで帯域圧縮ともいわれた。デジタル技術では、情報を元の表現よりも少ないビット数で符号化することを意味する[3]。
新たな代替技法として、圧縮センシングの原理を使ったリソース効率のよい技法が登場している。圧縮センシング技法は注意深くサンプリングすることでデータ圧縮の必要性を避けることができる。 可逆圧縮(かぎゃくあっしゅく)とは、圧縮データを復元した時に、圧縮前の入力データが完全に復元されるような圧縮方法である。基本的には、入力データの統計的冗長性(出現する符号の偏り、規則性)を利用して、情報を失うことなくより稠密なデータに変換する。例えば、画像には数ピクセル同じ色が並んだ領域がよくみられる。そこでピクセル単位に色情報を並べて表現する代わりに、「n個の赤のピクセル」という形で符号化できる。このような種類の方法は連長圧縮(RLE)と呼ばれる。また、多くの可逆圧縮で使われている方法として、出現頻度(確率)の高いものに短い符号を、出現頻度の低いものに長い符号を割り当てることで、データ全体でみたときの平均符号長を短くする方法がある。これをエントロピー符号化と呼び、具体的な方法としてハフマン符号化や算術符号化などがある。また、データを区間に区切って、それぞれで対応する符号を変えたり、n 個の連続した符号の列に対して符号を割り当てる方法(拡大情報源
可逆圧縮
LZ77 (Lempel?Ziv) およびそれを改良したLempel?Ziv?Storer?Szymanski (LZSS) という圧縮法は、可逆記録方法としては最もよく使われているアルゴリズムである[4]。DeflateはLZSSを伸長速度と圧縮率の面で最適化した派生技法だが、圧縮は時間がかかることがある。Deflateは、PKZIP
(英語版)、gzip、PNGで採用されている。Lempel?Ziv?Welch (LZW) はGIFで採用されている。また、LZR (Lempel-Ziv?Renau) アルゴリズムはZIPの基盤として採用されている。LZでは、データに繰り返し出現する記号列をテーブルを使って置換する方式を採用している。多くのLZ系の技法では、このテーブルを動的に生成しつつ入力を先頭から順次処理していく。テーブル自体はハフマン符号で符号化されることが多い(例えば、SHRI、LZX)。LZXはDeflateよりも効率が良く、マイクロソフトのCAB形式などで使われている。また、ハフマン符号に代わりRange Coderを採用したLZMAやLZMA2はさらに圧縮率が良い。圧縮効率が最も高い可逆圧縮法は乱択アルゴリズムを導入したもので Prediction by Partial Matching などがある。ブロックソートはデータの統計的モデリング技法であり、圧縮の前処理に使われる[5]。
文法圧縮を使った技法は、繰り返しが非常に多い場合に高い圧縮率を達成でき、同一あるいは関連する種の生物学的データ群、頻繁に改版される文書群、インターネットアーカイブなどの用途がある。文法圧縮では、入力文字列から文脈自由文法を構築する。コードが公開されているアルゴリズムとしては、Sequitur(英語版)、Re-Pair、MPMがある。
これらの技法をさらに洗練させるため、統計的予測と算術符号と呼ばれるアルゴリズムを組み合わせる。算術符号は Jorma Rissanen が考案し、Witten、Neal、Cleary がそれを実用的な技法に発展させ、ハフマン符号より優れた圧縮率を達成するようになった。統計的予測が文脈に強く依存する場合のデータ圧縮によく採用されている。二値画像圧縮の標準であるJBIG、文書(スキャン画像)圧縮の標準であるDjVuなどで使われている。テキスト入力システム Dasher は、いわば逆算術符号化器である[6]。 非可逆圧縮(ひかぎゃくあっしゅく)は可逆圧縮とは逆で、データを復元したときに完全には元にもどらない圧縮方法をいう。多くの非可逆圧縮では人間があまり強く認識しない成分を削除することでデータを圧縮する方法がとられている。たとえば人間は大きな音と小さな音を同時に聞いた場合、小さな音をあまり認識できないし(マスキング効果)、画像に対しても小さな色の変化は輝度の変化ほど認識されない。このためデータをフーリエ変換(あるいはその一種である離散コサイン変換など)し、高周波成分や低振幅成分を削除してしまっても、受け手に与える印象の変化に大きな差は現れない。当然削除する範囲が多ければ、元データとの差異は大きくなり、違いに気づく人間も増える。画像のサイズを小さくする、動画のフレームレートを下げるなども一種の非可逆圧縮と言える。画像圧縮技法であるJPEGは、データの本質的でない部分を丸めることで圧縮を達成している部分もある[7]。情報の喪失と圧縮率はトレードオフの関係にある。このような人間の知覚の特性を利用した非可逆圧縮は、音声、画像、映像などのデータによく使われている。 デジタルカメラでは、画質の低下を抑えつつ撮影枚数を増やすのに非可逆圧縮を使うことがある。また、DVDで使用しているMPEG-2も映像(動画)の非可逆圧縮法の一つである。 音響データの非可逆圧縮では音響心理学が応用されており、音響信号のうちヒトの耳に聞こえない(聞こえにくい)成分を捨てている。ヒトの声のデータ圧縮にはさらに専用の技法が使われることが多く、音声符号化は音響圧縮とは別の領域とされることがある。音声圧縮はVoIP、音響圧縮はCDのリッピングなどで使われている[8]。 圧縮の理論的背景としては、可逆圧縮については情報理論(とそれに密接に関連するアルゴリズム情報理論)、非可逆圧縮についてはレート歪み理論
非可逆圧縮
理論
機械学習「機械学習」も参照
機械学習と圧縮の間には密接な関係がある。ある系列の完全な履歴を入力として事後確率を予測するシステムは(出力分布に対して算術符号を使用することで)最適なデータ圧縮に利用でき、一方最適な圧縮器は(履歴から最もうまく圧縮するシンボルを見つけることで)予測に利用できる。この等価性を利用して、データ圧縮は「一般知能」(general intelligence) を評価するベンチマークとして使われてきた[10]。 データ圧縮はデータの差分抽出 (data differencing
データの差分抽出