|
データ圧縮（データあっしゅく）とは、あるデータをそのデータの実質的な性質を保ったまま、データ量を減らした別のデータに変換すること。高効率符号化ともいい、情報理論においては情報源符号化と呼ばれている。アナログ技術を用いた通信技術においては通信路の帯域幅を削減する効果を得るための圧縮ということで帯域圧縮ともいわれた。デジタル技術では、情報を元の表現よりも少ないビット数で符号化することを意味する。 データ圧縮には大きく分けて可逆圧縮と非可逆圧縮がある。可逆圧縮は統計的冗長性を特定・除去することでビット数を削減する。可逆圧縮では情報が失われない。非可逆圧縮は不必要な情報を特定・除去することでビット数を削減する。データファイルのサイズを小さくする処理は一般にデータ圧縮と呼ばれるが、データを記録または転送する前に符号化するという意味では情報源符号化である。 圧縮は、データ転送におけるトラフィックやデータ蓄積に必要な記憶容量の削減といった面で有効である。しかし圧縮されたデータは、利用する前に伸長（解凍）するという追加の処理を必要とする。つまりデータ圧縮は、空間計算量を時間計算量に変換することに他ならない。例えば映像の圧縮においては、それをスムースに再生するために高速に伸長（解凍）する高価なハードウェアが必要となるかもしれないが、圧縮しなければ大容量の記憶装置を必要とするかもしれない。データ圧縮方式の設計には様々な要因のトレードオフがからんでおり、圧縮率をどうするか、（非可逆圧縮の場合）歪みをどの程度許容するか、データの圧縮伸長に必要とされる計算リソースの量などを考慮する。 新たな代替技法として、の原理を使ったリソース効率のよい技法が登場している。圧縮センシング技法は注意深くサンプリングすることでデータ圧縮の必要性を避けることができる。 == 可逆圧縮 == 可逆圧縮（かぎゃくあっしゅく）とは、圧縮データを復元した時に、圧縮前の入力データが完全に復元されるような圧縮方法である。基本的には、入力データの統計的冗長性（出現する符号の偏り、規則性）を利用して、情報を失うことなくより稠密なデータに変換する。例えば、画像には数ピクセル同じ色が並んだ領域がよくみられる。そこでピクセル単位に色情報を並べて表現する代わりに、「n個の赤のピクセル」という形で符号化できる。このような種類の方法は連長圧縮（RLE）と呼ばれる。また、多くの可逆圧縮で使われている方法として、出現頻度（確率）の高いものに短い符号を、出現頻度の低いものに長い符号を割り当てることで、データ全体でみたときの平均符号長を短くする方法がある。これをエントロピー符号化と呼び、具体的な方法としてハフマン符号化や算術符号化などがある。また、データを区間に区切って、それぞれで対応する符号を変えたり、''n'' 個の連続した符号の列に対して符号を割り当てる方法（拡大情報源）など、冗長性を除去することでデータ量を低減させる様々な方法が存在する。これらの方法は、圧縮率や圧縮・展開にかかる計算コスト（時間やメモリ）が異なっており、状況に応じて使い分けたり、互いに組み合わせて使うことができる。 LZ77 (Lempel–Ziv) およびそれを改良したLZSS (Lempel–Ziv-Storer-Szymanski) という圧縮法は、可逆記録方法としては最もよく使われているアルゴリズムである。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 などがある。ブロックソートはデータの統計的モデリング技法であり、圧縮の前処理に使われる。 文法圧縮を使った技法は、繰り返しが非常に多い場合に高い圧縮率を達成でき、同一あるいは関連する種の生物学的データ群、頻繁に改版される文書群、インターネットアーカイブなどの用途がある。文法圧縮では、入力文字列から文脈自由文法を構築する。コードが公開されているアルゴリズムとしては、、Re-Pair、MPMがある。 これらの技法をさらに洗練させるため、統計的予測と算術符号と呼ばれるアルゴリズムを組み合わせる。算術符号は Jorma Rissanen が考案し、Witten、Neal、Cleary がそれを実用的な技法に発展させ、ハフマン符号より優れた圧縮率を達成するようになった。統計的予測が文脈に強く依存する場合のデータ圧縮によく採用されている。二値画像圧縮の標準であるJBIG、文書（スキャン画像）圧縮の標準であるDjVuなどで使われている。テキスト入力システム Dasher は、いわば逆算術符号化器である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「データ圧縮」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Data compression 」があります。 スポンサード リンク
|