データ圧縮

データ圧縮︵データあっしゅく、英: data compression︶とは、あるデータを、そのデータの実質的な内容︵情報、あるいはその情報量︶を可能な限り保ったまま、データ量を減らした別のデータに変換すること。高効率符号化ともいう。

データ圧縮は、データ転送におけるトラフィックやデータ蓄積に必要な記憶容量の削減といった面で有効である。しかし圧縮されたデータは、利用する前に伸長︵解凍︶するという追加の処理を必要とする。つまりデータ圧縮は、空間計算量を時間計算量に変換することに他ならない。例えば映像の圧縮においては、それをスムーズに再生するために高速に伸長︵解凍︶する高価なハードウェアが必要となるかもしれないが、圧縮しなければ大容量の記憶装置を必要とするかもしれない。データ圧縮方式の設計には様々な要因のトレードオフがからんでおり、圧縮率をどうするか、︵非可逆圧縮の場合︶歪みをどの程度許容するか、データの圧縮伸長に必要とされる計算リソースの量などを考慮する。

データ圧縮には、可逆圧縮と非可逆圧縮の2種類がある。可逆圧縮は、統計的冗長性を特定・除去することでビット数を削減する。可逆圧縮では情報が失われない。可逆圧縮は、数値データや文書、プログラムなど、1ビットの変化で情報の価値が大きく毀損されるようなデータに対して用いられる。一方で、非可逆圧縮は不必要な情報を特定・除去することでビット数を削減する。非可逆圧縮ではいくらかの情報が失われる。非可逆圧縮は、音声や画像、動画など、細部が変化しても情報の意味が変わりにくいデータに対して用いられる。

アナログ技術を用いた通信技術においては通信路の帯域幅を削減する効果を得るための圧縮ということで帯域圧縮ともいわれた。デジタル技術では、情報を元の表現よりも少ないビット数で符号化することを意味する。

新たな代替技法として、圧縮センシングの原理を使ったリソース効率のよい技法が登場している。圧縮センシング技法は注意深くサンプリングすることでデータ圧縮の必要性を避けることができる。

可逆圧縮

可逆圧縮︵かぎゃくあっしゅく︶とは、圧縮データを復元した時に、圧縮前の入力データが完全に復元されるような圧縮方法である。基本的には、入力データの統計的冗長性︵出現する符号の偏り、規則性︶を利用して、情報を失うことなくより稠密なデータに変換する。例えば、画像には数ピクセル同じ色が並んだ領域がよくみられる。そこでピクセル単位に色情報を並べて表現する代わりに、﹁n個の赤のピクセル﹂という形で符号化できる。このような種類の方法は連長圧縮︵RLE︶と呼ばれる。また、多くの可逆圧縮で使われている方法として、出現頻度︵確率︶の高いものに短い符号を、出現頻度の低いものに長い符号を割り当てることで、データ全体でみたときの平均符号長を短くする方法がある。これをエントロピー符号化と呼び、具体的な方法としてハフマン符号化や算術符号化などがある。また、データを区間に区切って、それぞれで対応する符号を変えたり、n 個の連続した符号の列に対して符号を割り当てる方法︵拡大情報源︶など、冗長性を除去することでデータ量を低減させる様々な方法が存在する。これらの方法は、圧縮率や圧縮・展開にかかる計算コスト︵時間やメモリ︶が異なっており、状況に応じて使い分けたり、互いに組み合わせて使うことができる。

LZ77 (Lempel–Ziv) およびそれを改良したLempel–Ziv–Storer–Szymanski (LZSS) という圧縮法は、可逆記録方法としては最もよく使われているアルゴリズムである。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 などがある。ブロックソートはデータの統計的モデリング技法であり、圧縮の前処理に使われる。

文法圧縮を使った技法は、繰り返しが非常に多い場合に高い圧縮率を達成でき、同一あるいは関連する種の生物学的データ群、頻繁に改版される文書群、インターネットアーカイブなどの用途がある。文法圧縮では、入力文字列から文脈自由文法を構築する。コードが公開されているアルゴリズムとしては、Sequitur、Re-Pair、MPMがある。

これらの技法をさらに洗練させるため、統計的予測と算術符号と呼ばれるアルゴリズムを組み合わせる。算術符号は Jorma Rissanen が考案し、Witten、Neal、Cleary がそれを実用的な技法に発展させ、ハフマン符号より優れた圧縮率を達成するようになった。統計的予測が文脈に強く依存する場合のデータ圧縮によく採用されている。二値画像圧縮の標準であるJBIG、文書︵スキャン画像︶圧縮の標準であるDjVuなどで使われている。テキスト入力システム Dasher は、いわば逆算術符号化器である。

非可逆圧縮

非可逆圧縮︵ひかぎゃくあっしゅく︶は可逆圧縮とは逆で、データを復元したときに完全には元にもどらない圧縮方法をいう。多くの非可逆圧縮では人間があまり強く認識しない成分を削除することでデータを圧縮する方法がとられている。たとえば人間は大きな音と小さな音を同時に聞いた場合、小さな音をあまり認識できないし︵マスキング効果︶、画像に対しても小さな色の変化は輝度の変化ほど認識されない。このためデータをフーリエ変換︵あるいはその一種である離散コサイン変換など︶し、高周波成分や低振幅成分を削除してしまっても、受け手に与える印象の変化に大きな差は現れない。当然削除する範囲が多ければ、元データとの差異は大きくなり、違いに気づく人間も増える。画像のサイズを小さくする、動画のフレームレートを下げるなども一種の非可逆圧縮と言える。画像圧縮技法であるJPEGは、データの本質的でない部分を丸めることで圧縮を達成している部分もある。情報の喪失と圧縮率はトレードオフの関係にある。このような人間の知覚の特性を利用した非可逆圧縮は、音声、画像、映像などのデータによく使われている。

デジタルカメラでは、画質の低下を抑えつつ撮影枚数を増やすのに非可逆圧縮を使うことがある。また、DVDで使用しているMPEG-2も映像︵動画︶の非可逆圧縮法の一つである。

音響データの非可逆圧縮では音響心理学が応用されており、音響信号のうちヒトの耳に聞こえない︵聞こえにくい︶成分を捨てている。ヒトの声のデータ圧縮にはさらに専用の技法が使われることが多く、音声符号化は音響圧縮とは別の領域とされることがある。音声圧縮はVoIP、音響圧縮はCDのリッピングなどで使われている。

理論

圧縮の理論的背景としては、可逆圧縮については情報理論︵とそれに密接に関連するアルゴリズム情報理論︶、非可逆圧縮についてはレート歪み理論がある。これらの分野の基盤を作り上げたのはクロード・シャノンで、1940年代後半から1950年代前半にかけて基盤となる論文をいくつか発表している。符号理論も関係している。データ圧縮の考え方は推計統計学とも密接に関連している。

機械学習

「機械学習」も参照

機械学習と圧縮の間には密接な関係がある。ある系列の完全な履歴を入力として事後確率を予測するシステムは︵出力分布に対して算術符号を使用することで︶最適なデータ圧縮に利用でき、一方最適な圧縮器は︵履歴から最もうまく圧縮するシンボルを見つけることで︶予測に利用できる。この等価性を利用して、データ圧縮は﹁一般知能﹂(general intelligence) を評価するベンチマークとして使われてきた。

データの差分抽出

データ圧縮はデータの差分抽出 (data differencing) の特殊ケースとみることもできる。データの差分抽出は﹁ソース﹂と﹁ターゲット﹂の﹁差分﹂を抽出し、﹁ソース﹂と﹁差分﹂から﹁ターゲット﹂を再現できるようにするものだが、データ圧縮は﹁ターゲット﹂から圧縮したデータを作り、﹁ターゲット﹂をその圧縮したデータのみから再現する。したがって、データ圧縮は﹁ソース﹂が空の場合の差分抽出とみなすことができ、圧縮データは﹁無からの差分﹂に対応する。これは、情報量︵データ圧縮に相当︶がカルバック・ライブラー情報量︵差分抽出に相当︶の初期データがない特殊ケースと対応しているのと同じである。

このような関係を強調したい場合、データの差分抽出を﹁差分圧縮﹂(differential compression) と呼ぶことがある。

「差分符号化」も参照

アナログ帯域圧縮

代表的なものとして、TV放送に用いられるNTSC、PALなどのコンポジット映像信号がある。コンポジット映像信号では、映像信号を輝度成分と色成分に分離した後、輝度成分に対しては十分な帯域幅を与えているのに対し、色成分についてはそれと比べ帯域幅を狭くしている。結果として元の画質と比較すると、色彩の細かい変化が失われた、例を上げるなら黒白写真に着色したものに近いような画質になっているはずだが、人間の視覚の特性上、通常のいわゆる﹁自然画﹂や、いわゆるアニメ絵でも縁の黒い線の輝度成分に助けられ、あまり気にならない︵また画質が気になるような、静止している映像に対しては三次元Y/C分離によって高画質な再生が可能である︶。しかしゲーム画面やCGのような、隣接する場所の色彩が極端に変化する動画ではいわゆる﹁色滲み﹂が避けられない。

中波～短波のAMラジオ放送では、占有帯域をあまり広くしないように、4kHz程度から上を切っている。電話においても効率よく多重化するため、電話は300 Hz- 3600 Hz程度が伝われば良いので、その範囲以外を切っている。

他に、以前は電話の交換機と交換機の間をPAM︵パルス振幅変調︶方式を使い0.125μsに分割することで、信号を多重化して送っていた。後にPAM方式からPCM︵パルス符号変調︶方式へ変わり、事実上デジタル方式に変わっている。

デジタル圧縮

デジタル圧縮の歴史

デジタル符号化されたデータの圧縮の歴史は意外と古く、1830年代に発明されたモールス信号に用いられるモールス符号も圧縮符号の一種である。これは、文字通信の中で比較的出現頻度の高いアルファベットに短い符号を割り当て、出現頻度の低いものには長い符号を割り当てることで、通信に要する手間を省いている。︵しかし日本語のモールス符号はそうなっていない。モールス信号の項目を参照︶

1967年、音響心理学的マスキング効果が発表されている。

その後、コンピュータの発達とともに、デジタル通信やファイルの保存でデータ圧縮の重要性が高まったことで研究が進み、1970年代後半頃からはデータ圧縮の要素技術に関する重要な特許も出願されるようになった。特許については、近年でも、オーディオ圧縮で用いられるMP3のライセンスの問題や、ウェブサイトの画像で広く用いられている GIF画像のライセンス問題など多くの紛争を発生させており、それだけデジタル時代の重要な基幹技術であることを示している。

1980年代に入ると音声通信分野のデジタル化の動きが始まり、音声圧縮の分野ではADPCMなど初期の比較的単純な圧縮方式が実用化された。また、パーソナルコンピュータやパソコン通信︵ただし、日本では通信自由化以降︶が普及するようになり、オンラインソフトウェアの分野からもZIPやLHAといった現在も幅広く使用されているファイル圧縮方式も誕生した。1988年、ブエノスアイレス大学の Oscar Bonello が IBM PC を使ったラジオ放送局用自動音声圧縮システムを開発した。

1990年代前半に入ると、音声圧縮や画像圧縮の分野で2005年現在でも広く知られている多くのデータ圧縮方式が発表された。音声︵オーディオ︶の分野では、1992年に登場したミニディスク (MD) に搭載されているATRACなどがある。また、画像の分野ではJPEG圧縮方式が国際標準規格として勧告され、広く普及した。これらの背景には、集積回路 (IC) の生産技術や設計技術の発達で大規模で高度な処理が行えるICが比較的安価な製品でも搭載可能になった点や、パーソナルコンピュータの急速な性能向上でソフトウェア的な画像処理が容易に行えるようになった点も大きい。

また、動画圧縮の分野でも、この頃、TV会議システム用の動画圧縮方式 (H.261) やビデオCDの圧縮方式 (MPEG-1) も標準化されている。また、パーソナルコンピュータ向けに企業独自の圧縮方式を採用したコーデックも登場するようになった。しかし、動画圧縮の分野では音声圧縮や画像圧縮に比べてさらに高度な技術が要求されるため、まだしばらくの間、業務用や限定的な用途に限られていた。これとは別に、デジタル時代の重要な基幹技術である動画圧縮技術には特許の権益に絡む思惑もあり、この方面でも標準化までに長い時間を要した。

1990年代後半になると、動画圧縮の分野でも国際的な標準規格であるMPEG-2が標準化され、業務用分野から幅広く利用されるようになり、1996年に登場したDVDプレーヤーや、2000年に開始されたBSデジタル放送など、家電製品にも採用されるようになった。

ファイル圧縮

詳細は「アーカイブ (コンピュータ)#ファイル圧縮」を参照

静止画像圧縮

画像圧縮の各方式については画像圧縮のコーデックを参照

代表的なものとしては、インターネットのウェブサイトで広く用いられるJPEG、GIFがある。非可逆圧縮による高能率圧縮を行うものと、劣化を生じさせない可逆圧縮を用いるものがある。

例えば、非可逆圧縮形式のJPEGの場合、一定の画素数のブロックに分割したデータを離散コサイン変換 (Discrete Cosine Transform, DCT) と呼ばれる演算で処理して符号化を行う。

画像圧縮アルゴリズムの評価には、レナなどの画像サンプルが広く使われている。

音声圧縮

詳細は「音声圧縮」を参照

音声圧縮の各方式については音声圧縮のコーデックを参照

音声圧縮では、人の聴覚の特性を利用して高能率の非可逆圧縮を行うものが広く用いられている。非可逆圧縮の代表的な方式としてMP3がある。CDの音声データ (1411.2kbps: 44.1kHz, 16bit, 2ch) を128kbpsのMP3形式に圧縮した場合、圧縮率は約1/11となる。最近では高音質の320kbpsの圧縮率が一般的になりつつある。

一方で、まったく劣化を生じさせない可逆圧縮方式を用いたものも増えてきている。 ALAC、FLAC、Monkey's Audio(APE)などがその代表である。

動画圧縮

動画圧縮の各方式については、動画圧縮のコーデックを参照

動画圧縮では、各フレームの静止画の圧縮と時系列の圧縮技法︵動きベクトル、フレーム間予測、動き補償など︶を組み合わせて行う。通常動画データには同期した音声も付属しているため、動画圧縮のコーデックは音声圧縮用コーデックを統合してパッケージ化されていることが多い。

動画圧縮アルゴリズムのほとんどが非可逆圧縮である。圧縮前の動画はあまりにも多大なデータとなり、ストリーミングに際しても巨大な帯域幅を必要とする。可逆な動画用コーデックの圧縮性能は平均で3倍程度だが、非可逆なMPEG-4の圧縮性能は20倍から200倍である。非可逆圧縮では、画質、圧縮・伸長のコスト、要求されるシステム性能といったトレードオフが考慮される。圧縮率が高すぎるとブロックノイズなどの圧縮アーティファクトが生じることがある。

動画圧縮では一般に四角い範囲の隣接するピクセル群をグループとして扱い、これをマクロブロックと呼ぶ。このブロックを次のフレームの同じ位置のブロックと比較し、差分のみをデータとして送る。そのため、動きが激しい動画では差分が大きくなり、より多くのデータを符号化しなければならなくなる。したがって固定ビットレートでは、爆発シーン、炎のシーン、動物の群れ、視点︵カメラ︶の平行移動などで画質が低下することがあり、可変ビットレートではデータ転送量が増加する。

符号化理論

動画データは、一連の静止画フレームからなっている。このフレーム列には空間的にも時間的にも冗長性があり、動画圧縮アルゴリズムはそれを除去することで全体のサイズを小さくしようとする。隣接するフレームは相互によく似ていることが多く、フレーム間の差分だけを格納することでこれを利用する。また、ヒトの目は色の変化には鈍感で輝度の変化には敏感である。そこで、静止画圧縮のJPEGのようにフレーム内の似たような色が並んでいる領域を平均化するような圧縮を行う。これらの技法には本質的に非可逆なものと原本の情報を保持する可逆なものがある。

フレーム間圧縮では、フレーム列を前後で比較したとき、全く変化しない領域があれば、前のフレームの同じ領域をそのままコピーせよというコマンドを生成する。領域が単純に変化している場合、シフト、回転、明るくする、暗くするなどのコマンドを生成する。このようにコマンド列を生成した方が各フレームを静止画として圧縮するよりサイズが小さくなる。このようなフレームをまたいだ圧縮は単純に再生する用途では問題ないが、圧縮された動画を編集したい場合には問題となることがある。

フレーム間圧縮を行うと、フレームからフレームにデータをコピーしていくことになるため、大本となるフレームが消されると︵転送に失敗すると︶その後のフレーム列を正しく再生できなくなる。DVのようなデジタルビデオ規格では、フレーム毎の圧縮しか行わない。その場合は編集で一部をカットするのが容易である。フレーム毎の圧縮しか行わない場合、各フレームのデータ量はほぼ同じになる。フレーム間圧縮システムでは、あるフレーム︵MPEG-2では﹁Iフレーム﹂と呼ぶ︶は他のフレームからデータをコピーせずに再現できるフレームでフレーム間圧縮の起点となっているため、前後の他のフレームより多くのデータを含んでいる。

フレーム間圧縮を施した動画データの編集はフレーム毎の圧縮のみの場合よりはるかにコンピュータの性能を要求するが、例えばHDVなどの規格ではMPEG-2データのノンリニア編集が可能である。

2013年現在、主に使われている動画圧縮技法︵例えば、ITU-TまたはISOが規格として承認したもの︶は、空間的冗長性の削減に離散コサイン変換 (DCT) を採用しているものが多い。この技法は1974年、N. Ahmed、T. Natarajan、K. R. Rao が導入した。他の技法としてはフラクタル圧縮や matching pursuit がある。研究段階では離散ウェーブレット変換 (DWT) も使われているが、製品としては実用化されていない︵静止画圧縮では使用している例がある︶。フラクタル圧縮は最近の研究の進展で比較的有効性が低いとされ、人気が衰えている。

動画圧縮規格の年表

動画（映像）圧縮規格の年表

年	規格	策定者	主な実装・用途
1984	H.120	ITU-T
1990	H.261	ITU-T	テレビ会議、テレビ電話
1993	MPEG-1 Part 2	ISO、IEC	ビデオCD
1995	MPEG-2 Part 2	ISO、IEC、ITU-T	DVD-Video、Blu-ray、DVB、SVCD
1996	H.263	ITU-T	テレビ会議、テレビ電話、携帯電話での動画再生 (3GP)
1999	MPEG-4 Part 2	ISO、IEC	第3世代携帯電話、インターネット上の動画 (DivX, Xvid ...)
2003	H.264/MPEG-4 AVC	ソニー、パナソニック、サムスン、ISO、IEC、ITU-T	Blu-ray、HD DVD DVB、iPod Video、Apple TV、ワンセグ
2008	VC-2 (Dirac)	ISO	インターネット上の動画、HDTV放送、UHDTV
2013	H.265/HEVC	ISO、IEC、ITU-T	UHD（スーパーハイビジョン）

遺伝学

塩基配列データの圧縮は可逆圧縮の新たな用途であり、データの特性に適応させた一般的な圧縮アルゴリズムと遺伝学的なアルゴリズムが使われている。2012年、ジョンズ・ホプキンス大学のチームは特定の外部の配列データベースに依存しない世界初の遺伝子圧縮アルゴリズムを発表した。HAPZIPPERは HapMap 向けに作られており、20分の1に圧縮（ファイルサイズを95%削減）できる。これは、一般的圧縮ユーティリティの2倍から4倍の圧縮率であり、しかも高速である。彼らはSNP（一塩基多型）をマイナー対立遺伝子でソートすることでデータセットを均質化するMAF（マイナー対立遺伝子頻度）ベースの符号化 (MAFE) を導入した。

関連項目

• アルゴリズム情報理論
• 暗号
• ウェーブレット変換
• エントロピー符号
• 音響信号処理
• 可逆圧縮
• ガンマ符号
• コルモゴロフ複雑性
• ゴロム符号
• 最小記述長
• 実行ファイル圧縮
• 情報量
• データ
• トランスコード
• ハフマン符号
• ファイルフォーマット
• 符号化方式
• ベクトル量子化
• Range Coder

外部リンク

• Data Compression Basics (Video)
• Wiley - Introduction to Compression Theory
• EBU subjective listening tests on low-bitrate audio codecs
• Audio Archiving Guide: Music Formats - 正しいコーデックの選び方
• MPEG 1&2 video compression intro (pdf format)
• hydrogenaudio.org wiki comparison
• Introduction to Data Compression by Guy E Blelloch from CMU
• Digital Audio - 多くのコーデックで使われている可逆圧縮技法の解説
• SoundExpert - 各種音声コーデックの評価サイト
• TestVid - 圧縮の評価・研究用に圧縮されていない動画データが公開されている。
• Videsignline - Intro to Video Compression