データ圧縮

出典: Wikipedio

データ圧縮（データあっしゅく）とは、あるデータをそのデータの実質的な性質を保ったまま、データ量を減らした別のデータに変換すること。高効率符号化ともいい、情報理論においては情報源符号化と呼ばれている。

主な目的は、データ転送におけるトラフィックやデータ蓄積に必要な記憶容量の削減といった、資源の節約である。なお、アナログ技術を用いた通信技術においては通信路の帯域幅を削減する効果を得るための圧縮ということで帯域圧縮ともいわれた。

データ圧縮には大きく分けて可逆圧縮と非可逆圧縮がある。また、バイナリデータを対象としたデータ圧縮方式の中には、複数のファイルを1つにまとめて扱えるようにするアーカイブ機能を兼ね備えるものもある。

基本原理

可逆圧縮

可逆圧縮（かぎゃくあっしゅく）とは、データを復元したときに、完全に元にもどる圧縮方法をいう。通常、意味のあるデータには、現れる符号に偏りすなわち規則性、冗長性が存在する。そのため多くの可逆圧縮では出現頻度の高いものに短い符号を、出現頻度の低いものに長い符号を与えることで、平均符号長を短くする方法がとられている。また区間的に分けてそれぞれ符号を変える、より長い符号に対して前述の処理を行う（拡大情報源）などの方法で、可逆圧縮間でも圧縮率や展開速度に差が出る。 Template:Main

非可逆圧縮

非可逆圧縮（ひかぎゃくあっしゅく）とは、データを復元したときに、完全には元にもどらない圧縮方法をいう。多くの非可逆圧縮では人間があまり強く認識しない成分を削除することでデータを圧縮する方法がとられている。たとえば人間は大きな音と小さな音を聞いた場合、小さな音をあまり認識できないし、画像に対しても小さな色の変化は認識されない。このためデータをフーリエ変換（あるいは離散コサイン変換などフーリエ変換の一種）し、高周波成分や低振幅成分を削除してしまっても、受け手に与える印象の変化に大きな差は現れない。当然削除する範囲が多ければ、元データとの差異は大きくなり、違いに気づく人間も増える。画像のサイズを小さくする、動画のフレームレートを下げるなども一種の非可逆圧縮と言える。 Template:Main

主な圧縮アルゴリズム

非ユニバーサル符号
- 連長圧縮（ランレングス圧縮、RLE）
整数の符号化
- アルファ符号 (unary code)
- Elias符号（ガンマ符号、デルタ符号、オメガ符号）
- ゴロム符号 (Golomb)
最小冗長符号あるいはエントロピー符号
ユニバーサル符号
- 再帰時間符号化法
  - インターバル符号
  - Move To Front (MTF) あるいは再帰順位 (recency rank) 法
- 辞書式
  - LZ77
    - LZMA
    - LZSS
      - LZB
    - LZX
    - LZO
  - LZ78
    - LZS
    - LZW
  - LZT
  - LZC
  - BPE
- ソートに基づく手法
  - ブロックソート(BWT)
- 統計型
- 文法型
  - SERQUITUR
  - MPM(by Kieffer et al.)
量子化
- スカラー量子化
- ベクトル量子化
サブサンプリング
- インターレース
- サンプリングファクタ
自己相関性を利用した圧縮

アナログ帯域圧縮

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

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

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

デジタル圧縮

デジタル圧縮の歴史

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

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

1980年代に入ると音声通信分野のデジタル化の動きが始まり、音声圧縮の分野ではADPCMなど初期の比較的単純な圧縮方式が実用化された。また、パーソナルコンピュータやパソコン通信（ただし、日本では通信自由化以降）が普及するようになり、オンラインソフトウェアの分野からもZIPやLHAといった現在も幅広く使用されているファイル圧縮方式も誕生した。

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

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

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

ファイル圧縮

ファイル圧縮では圧縮前の状態に完全に復元可能な可逆圧縮が用いられる。

ファイル圧縮は、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で使われるオープンソースの高圧縮形式

静止画像圧縮

Template:Main2

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

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

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

音声圧縮

Template:Main Template:Main2

音声圧縮では、人の聴覚の特性を利用して高能率の非可逆圧縮を行うものが広く用いられている。非可逆圧縮の代表的な方式としてMP3がある。CDの音声データ (1411.2kbps: 44.1kHz, 16bit, 2ch) を128kbpsのMP3形式に圧縮した場合、圧縮率は約1/11となる。MP3では1/3-1/4ぐらいの圧縮率で原音との差がほぼ識別できない程度の品質を維持することが出来ると言われている。

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

動画圧縮