データ圧縮

出典: フリー百科事典『ウィキペディア（Wikipedia）』
2014年4月19日 (土) 01:56時点におけるDARAS (トーク)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内、 検索

テンプレート:Redirect データ圧縮（データあっしゅく）とは、あるデータをそのデータの実質的な性質を保ったまま、データ量を減らした別のデータに変換すること。高効率符号化ともいい、情報理論においては情報源符号化と呼ばれている[1]。アナログ技術を用いた通信技術においては通信路の帯域幅を削減する効果を得るための圧縮ということで帯域圧縮ともいわれた。デジタル技術では、情報を元の表現よりも少ないビット数で符号化することを意味する[2]。

データ圧縮には大きく分けて可逆圧縮と非可逆圧縮がある。可逆圧縮は統計的冗長性を特定・除去することでビット数を削減する。可逆圧縮では情報が失われない。非可逆圧縮は不必要な情報を特定・除去することでビット数を削減する[3]。データファイルのサイズを小さくする処理は一般にデータ圧縮と呼ばれるが、データを記録または転送する前に符号化するという意味では情報源符号化である[4]。

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

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

可逆圧縮

可逆圧縮（かぎゃくあっしゅく）アルゴリズムは通常、統計的冗長性を利用して情報を失うことなくより稠密にデータを表現する。データを復元したときに、完全に元にもどる圧縮方法である。実世界のデータの多くは統計的冗長性（出現する符号の偏り、規則性）があるため、可逆圧縮が可能となる。例えば、画像には数ピクセル同じ色が並んだ領域がよくみられる。そこでピクセル単位に色情報を並べて表現する代わりに、「n個の赤のピクセル」という形で符号化できる。これは連長圧縮の初歩的な例である。このように冗長性を除去することでファイルサイズを低減させる様々な技法が存在する。多くの可逆圧縮では出現頻度の高いものに短い符号を、出現頻度の低いものに長い符号を与えることで、平均符号長を短くする方法がとられている。また区間的に分けてそれぞれ符号を変える、より長い符号に対して前述の処理を行う（拡大情報源）などの方法で、可逆圧縮間でも圧縮率や展開速度に差が出る。

LZ77 (Lempel–Ziv) およびそれを改良したLZSS (Lempel–Ziv-Storer-Szymanski) という圧縮法は、可逆記録方法としては最もよく使われているアルゴリズムである[6]。DeflateはLZSSを伸長速度と圧縮率の面で最適化した派生技法だが、圧縮は時間がかかることがある。Deflateは、テンプレート:仮リンク、gzip、PNGで採用されている。LZW (Lempel–Ziv–Welch) はGIFで採用されている。また、LZR (Lempel-Ziv–Renau) アルゴリズムはZIPの基盤として採用されている。LZでは、データに繰り返し出現する記号列をテーブルを使って置換する方式を採用している。多くのLZ系の技法では、このテーブルを動的に生成しつつ入力を先頭から順次処理していく。テーブル自体はハフマン符号で符号化されることが多い（例えば、SHRI、LZX）。LZ系で最も効率がよいのはLZXで、マイクロソフトのCAB形式などで使われている。

圧縮効率が最も高い可逆圧縮法は乱択アルゴリズムを導入したもので Prediction by Partial Matching などがある。ブロックソートはデータの統計的モデリング技法であり、圧縮の前処理に使われる[7]。

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

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

非可逆圧縮

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

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

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

理論

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

機械学習

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

データの差分抽出

データ圧縮はデータの差分抽出テンプレート:Enlinkの特殊ケースとみることもできる[13][14]。データの差分抽出は「ソース」と「ターゲット」の「差分」を抽出し、「ソース」と「差分」から「ターゲット」を再現できるようにするものだが、データ圧縮は「ターゲット」から圧縮したデータを作り、「ターゲット」をその圧縮したデータのみから再現する。したがって、データ圧縮は「ソース」が空の場合の差分抽出とみなすことができ、圧縮データは「無からの差分」に対応する。これは、情報量（データ圧縮に相当）がカルバック・ライブラー情報量（差分抽出に相当）の初期データがない特殊ケースと対応しているのと同じである。

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

テンプレート:See also

展望と今後の可能性

全世界のストレージに記録されているデータの総量は、既存の圧縮アルゴリズムを使っても平均で 4.5:1 に圧縮できるとされている。2007年時点で、全世界のストレージに格納されているデータは1,300エクサバイトと見積もられているが、内容別に最適な圧縮を施せば、その情報量は295エクサバイトだという[15]。

アナログ帯域圧縮

代表的なものとして、TV放送に用いられるNTSC、PALなどのコンポジット映像信号がある。これは、映像信号を輝度成分と色成分に分離し、さらにインターレースと呼ばれる方式を用いて放送信号の伝送に必要な帯域が少なくなるように工夫されている。

また、電話においても多重化するために帯域圧縮を行っている。電話は300 Hz - 3600 Hz程度が伝われば良いので、その範囲以外をカットする手法が使われている。

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

デジタル圧縮

デジタル圧縮の歴史

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

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

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

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

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

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

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

ファイル圧縮

ファイル圧縮では圧縮前の状態に完全に復元可能な可逆圧縮が用いられる。また、バイナリデータを対象としたデータ圧縮方式の中には、複数のファイルを1つにまとめて扱えるようにするアーカイブ機能を兼ね備えるものもある。

ファイル圧縮は、PC分野では1980年代後半頃からパソコン通信の発達とともにLHAやZIPなどの圧縮方式が誕生した。2000年代ではZIPがオペレーティングシステムの垣根を越えて幅広く使われている。

  • ZIP - 事実上、世界標準の圧縮形式。
  • 7z - 7-Zipで扱うことの出来る多機能な超高圧縮形式。オープンソース
  • RAR - マルチメディア系の圧縮が得意な高圧縮形式
  • AFA - マルチメディア系の圧縮が得意な高圧縮形式. ZIPやRARの何倍も早い。
  • CAB (Cabinet archive) - Windowsが標準で利用できる圧縮形式
  • GCA, DGCA (G Compression Archive) - テキストデータに強い日本産圧縮形式
  • LHA (Lempel-Ziv & Huffman Archive か？) - 純日本産の圧縮形式。LZHとも
  • StuffIt - Macintosh系列で利用される圧縮形式
  • Compact Pro - Macintosh系列で利用された圧縮形式。開発は終了している。
  • pack - UNIXの初期からある形式。今ではほとんど使われず、compressに取って代わられている。
  • compress - packの置き換えとして商用UNIXで標準で使われている形式。
  • gzip (GNU Zip) - 商用UNIXに標準のcompressには特許の問題があり、フリーのUNIX用にcompressの代用品として開発された。
  • bzip (bunzip) - 特許侵害のために配布が中止された高圧縮形式。算術符号使用
  • bzip2 (bunzip ver.2) - 主にUNIXで使われるオープンソースの高圧縮形式

静止画像圧縮

テンプレート:Main2

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

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

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

音声圧縮

テンプレート:Main テンプレート:Main2

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

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

動画圧縮

テンプレート:Main2

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

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

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

符号化理論

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

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

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

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

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

動画圧縮規格の年表

動画（映像）圧縮規格の年表
年 規格 策定者 主な実装・用途
1984 テンプレート:仮リンク 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) を導入した[27]。

脚注

テンプレート:Reflist

関連項目

テンプレート:Div col

テンプレート:Div col end

外部リンク

テンプレート:データ圧縮 テンプレート:圧縮フォーマット

テンプレート:データ圧縮ソフトウェア
  1. ↑ テンプレート:Cite book
  2. ↑ テンプレート:Cite journal
  3. ↑ テンプレート:Cite journal
  4. ↑ テンプレート:Cite book
  5. ↑ テンプレート:Cite book
  6. ↑ テンプレート:Cite journal
  7. ↑ テンプレート:Cite journal
  8. ↑ テンプレート:Cite journal
  9. ↑ テンプレート:Cite web
  10. ↑ テンプレート:Cite journal
  11. ↑ テンプレート:Cite web
  12. ↑ テンプレート:Cite web
  13. ↑ テンプレート:Cite web
  14. ↑ テンプレート:Citation
  15. ↑ テンプレート:Cite journal
  16. ↑ テンプレート:Cite book
  17. ↑ テンプレート:Cite journal
  18. ↑ テンプレート:Cite web
  19. ↑ テンプレート:Cite book
  20. ↑ テンプレート:Cite web
  21. ↑ テンプレート:Cite book
  22. ↑ テンプレート:Cite web
  23. ↑ テンプレート:Cite web
  24. ↑ テンプレート:Cite book
  25. ↑ テンプレート:Cite journal
  26. ↑ テンプレート:Cite book
  27. ↑ テンプレート:Cite journal
「http://wikippe.e-do-match.com/index.php?title=データ圧縮&oldid=2138」から取得