圧縮アルゴリズム - 通信用語の基礎知識

情報の大きさを縮めるための方法のこと。

概要

可逆・非可逆
特許問題
理論

特徴

主な圧縮アルゴリズム
主なエントロピー符号
主なユニバーサル符号

概要

可逆・非可逆

縮めて戻したときに完全に元通りになるものを「可逆」、縮めたときに劣化してしまい完全に戻らないものを「非可逆」という。非可逆は、元持っていた情報の一部を捨てることで、より小さく縮めることを実現したものである。

プログラム等のデータを圧縮するときには前者の可逆が使われ、画像や映像など多少劣化しても問題の少ないものは後者の「非可逆」が使われる。

特許問題

情報圧縮は様々な局面で欠くことのできない重要な要素である。通信速度は年々速くなっているのに、なぜ圧縮するのか。それは、いつでも通信速度よりCPUのほうが速いからである。

このため、ここで使われるアルゴリズムは多くの場合、企業の特許となっており、自由な利用ができない。

現在世界を支えているオープンソースのフリーソフトウェアではこのような特許技術を使うことは出来ないが、元々特許が無い理論を、あとから第三者の企業が特許にしてしまうという事態もまれに発生し、大問題となることもある。

理論

現在も、より効果的な圧縮を求め、研究が進められている。しかし現状では、全てベル研究所のClaude Elwood Shannonが発表した「情報エントロピー」という基礎理論の、エントロピー自体が最小になるようにデータを分析、分析結果を最大効率で表現可能なアルゴリズムの作成と言う具体的な方法にすぎない。

更なる圧縮率の追求のためには、情報エントロピーを超える発想が求められている。

特徴

主な圧縮アルゴリズム

圧縮アルゴリズムは大きく「エントロピー符号」と「ユニバーサル符号」という二種類に分けることができる。

これらを利用した、代表的な圧縮手法に、次のようなものが存在する(順不同)。

エントロピー符号
- 離散コサイン変換(DCT)
- 算術圧縮
- シャノン・ファノ法
- ハフマン符号
ユニバーサル符号
- 辞書法
  - スライド辞書法
  - 動的辞書法
- 統計法
- ランレングス圧縮

これらを組み合わせて、実際のアルゴリズムを作る。

中には特許となっているものもあり、それらは自由な利用ができず、人の目に触れることも少なく慎ましい余生を送っている。

主なエントロピー符号

算術圧縮
- Jones符号
- RangeCoder
ハフマン符号
- 静的ハフマン符号
- 動的ハフマン符号
  - FGK符号
- MH符号 (ハフマン+ランレングス圧縮)

主なユニバーサル符号

LZ
- LZ77(スライド辞書法)
  - LZARI
  - LZH
  - LZO
  - LZMA
  - LZR
  - LZSS
    - LZHUF
    - Deflate
- LZ78(動的辞書法)
  - LZB
  - LZBW
  - LZC
  - LZFG
  - LZJ
  - LZM
  - LZT
  - LZW

リンク