CompressionCoding

7. 圧縮符号化

7.1. 概要

データ圧縮はファイルを保存するために必要なスペースの大きさを減らします。もし、ファイルのサイズを半分にできるのであれば、同じコストで2倍のファイルを保存したり、2倍の速さでファイルをダウンロードできるようになるでしょう(そして、ダウンロードに掛かる費用も半額になります)。ディスク容量がどんどん大きくなり、広帯域が一般的になったとしても、小さく圧縮されたファイルを使うことで節約出来るとしたら、それは良いことです。グーグルやフェイスブックによって維持されているような巨大なデータ倉庫にとって、スペースの半減化は、「スペースやコンピューティングが要求する大規模な縮小」「消費と冷却化における結果的な大きな節約」そして「環境に与える影響の大きな縮小」を意味するでしょう。

圧縮の共通フォームは、JPEG(画像用),MP3(オーディオ用),MPEG(DVDを含んだビデオ用),ZIP(多くのデータ用)等で現在使われています。例えば、JPEG法は画像をそのオリジナルサイズの10分の1以下に減らします。このことは、カメラは10倍多くの画像を保存でき、画像のwebでのダウンロード時間を10倍速くすることを意味します。

その裏には何があるでしょう?そう、そこにはデータの質に関する問題があるのです。例えば、高い圧縮率のJPEG画像は圧縮されていない画像と比べると鮮明ではありません。また、圧縮や伸長のための処理時間も掛かります。ほとんどのケースでそのトレードオフには意味があるのですが、いつもという訳ではありません。

この章では、どのように圧縮が行われるのか、それは何に役立つのか、そして、データを圧縮するかどうかを決定する時に考えなければならない、圧縮データの使用に関連したコストを見ていきます。ではランレングス符号化という簡単な例から始めましょう。これは、圧縮にまつわる利益と課題への洞察を与えてくれます。

この活動では、生徒はジャン=ドミニック・ボービーという、瞬き以外の動作が完全にできなかった人によって利用された方法でいくつかの文字を書くことを体験します。簡単な2つの状態(瞬きする/しない)で、彼は1冊の本の著者になることができました。生徒はペアになって活動するとよいでしょう。そして、瞬きだけで単語や簡単な文を正確に送ってみましょう。

7.2. ランレングス符号化

Imagine we have the following simple black and white image.

CC-Diamond.png

コンピュータがこの画像を保存できるとても簡単な方法の1つは、0が白を表し、1が黒を表すような形式を使うことです。上の画像は次の方法によって表現できるでしょう。

011000010000110
100000111000001
000001111100000
000011111110000
000111111111000
001111101111100
011111000111110
111110000011111
011111000111110
001111101111100
000111111111000
000011111110000
000001111100000
100000111000001
011000010000110

この画像を表現しているのは15行15(25?)列の225ビットです。コンピュータが理解できるような方法で、より少ないビットを使って同じ画像を表現出来るでしょうか。誰かにそれを読み聞かせなければいけないことを想像してみましょう。しばらくすれば、「ゼロゼロゼロゼロゼロ」と言う代わりに「5つのゼロ」のように言うでしょう。この技術は、デジタル画像を格納するスペースを切り詰めるために使われ、ランレングス符号化(RLE)として知られています。ランレングス符号化では、それぞれの行を、いくつの連続したピクセルが同じ色であるかを、常に白のピクセルの数をでスタートした場合として、置き換えます。例えば、上のピクセルの最初の1行は、1 白, 2 黒 4 白, 1 黒, 4 白, 2 黒,そして 1 白です。これより次のように表現できます。

1, 2, 4, 1, 4, 2, 1

2行目では、黒の数を言う前に白の数を言わなければいけないので、行のはじめに0があることを、はっきりと言わなければいけません。このことから次のようになります。

0, 1, 5, 3, 5, 1

そして、3行目は、5 白, 5 黒 5 白です。これより次のようになります。

5, 5, 5

ファイルの最初の3行は、RLEを使って次のように表現されると決めました。

1, 2, 4, 1, 4, 2, 1
0, 1, 5, 3, 5, 1
5, 5, 5

他の行はどのようになるでしょうか、書き出してみましょう。

どんな表現が保存するためのスペースをより少なくするでしょうか。

これを考えるための1つの簡単な方法は、あなたがこれらの表現をタイピングしていたと想像することです。あなたは、1文字として保存されているオリジナルビットの1つ1つと、各桁やコンマに使用しているRLEコードの1つ1つについて、考えることができました(これは少し粗い表現ですが、出発点です)。

オリジナルの表現では、画像を表現するために225ビットが必要でした。新しい表現でのコンマや桁の数を数えてみましょう(スペースや改行ではありません、これらは無視しましょう)。これが、新しい方法で画像を表現した時に必要とされる文字の数です(あなたが正しいことを保証するために、あなたに与えられた最初の3行は、29文字でしたね)。

新しい画像の表現が正しく得られたと思い、正しく数え上げしたら、あなたは新しい画像は119文字だったとわかるはずです(もしあなたの数が違っていたらダブルチェックしてみましょう!)。このことは、新しい表現(方法)で表現するための文字数は、ほんの53%程度しか必要がないことを意味します(119/225で計算)!これは、画像を保存するために必要なスペースの量の大幅な削減です。新しい表現は、古いものの圧縮された形です。

実際にはこの方法(いくつかの特別な仕掛けを含めて)は、画像をそのオリジナルサイズの約15%にまで圧縮することに使えます。本物のシステムでは、画像はそれぞれのピクセルに黒や白の値を保存するために、1ビットだけを使います。ランレングス数はまた、数を表すためのとても小さなスペースを得るビットパターンをもう一度使うことで、もっと効率よく保存されます。使われるビットパターンは、普通はハフマン符号化と呼ばれる技術に基づいているのですが、その
技術は我々がここで身に付けたいと思う内容を越えています。

黒と白でスキャンされた画像が現在使われている主な部分は、このアプローチを圧縮に使っているファクシミリです。スキャンしたページでそれがうまく働く1つの理由は、連続した白のピクセルの数がとても大きいからです。実際、白だけで走査されたラインが全体にあるでしょう。典型的なファクシミリのページは200以上のピクセルが横切っています。そこで、200ビットを1つの数に置き換えることは大きな節約になります。数そのものを表すには数ビットで十分です。そして、スキャンされたページの他の場所では、ほんの少しの連続的なピクセルが数に置き換えられますが、全体的な節約は重要です。実際、ファクシミリはもしも圧縮を使わなければ、ページの送信に7倍の時間が掛かってしまうでしょう。

7.2.1 Converting Run Length Encoding back to the original representation

我々が圧縮の過程を逆にできることを保証するために、この(圧縮された)画像のオリジナルの表現(0と1)は何でしょうか?

4, 11, 3
4, 9, 2, 1, 2
4, 9, 2, 1, 2
4, 11, 3
4, 9, 5
4, 9, 5
5, 7, 6
0, 17, 1
1, 15, 2

画像は何でしょうか?この画像の圧縮率はどのくらいよかったでしょう?(圧縮の量のための計算を振り返ろう)

Spoiler: Answer for the above image
This image is from the CS Unplugged image representation activity, and the solution is available in the activity (it is a cup and saucer).

あなたはこのテクニックを対話型のこちらを使って体験できます。

★コンテンツは準備中です★

画像の圧縮された表現がオリジナルの表現に逆変換され、そして、オリジナルの表現と圧縮された表現の両方がコンピュータに読まれた時に同じ画像になるときに、この圧縮アルゴリズムは可逆と呼ばれます。つまり、画像の圧縮よって何のデータも失われず、結果として圧縮が全く行われなかった場合です。

すべての圧縮アルゴリズムが可逆ではありません。特に写真、画像、ビデオなどファイルのタイプによっては、もしも、ファイルサイズを大幅に減らせるとしたら、我々はその質を少し犠牲にします(つまり、画像を表現するデータを少し失います)。映画のようなとても大きなファイルをダウンロードするためには、(このことは)ファイルサイズがダウンロードが実行不可能であるほど大きくないと保証するために不可欠です。

今やあなたはランレングス符号化がどのように働くかを知ったのだから、他の誰かがあなたに与えた画像を圧縮する前の状態に戻すように、あなた自身の白と黒の画像を考え、圧縮することができるようになりました。

0と1であなた自身の絵を作ることから始めましょう。(それが長方形であることを確認しましょう。ーすべての行が同じ長さを持っているべきです。)あなたはこれを紙に描いたり、コンピュータ上に用意しましょう。(固定幅のフォントを使わないと、失敗したり、混乱します!)
それを簡単にするために、あなたは描きたい画像をグリッド紙(数学の練習帳のような)に、黒を表すために四角を塗りつぶし、白を表すためにそれを空白のままにして書くことで、始めることができます。一度あなたがそれをやってしまえば、その後、画像を0と1に書き出せるでしょう。

連続長符号化を使ってあなたの画像の圧縮表現を解きましょう。つまり、ここまで説明したコンマ形式で別れた連続長。

では、圧縮された表現のコピー(連続長符号化であってオリジナルの圧縮されていない表現ではない)をクラスメートと交換しましょう。オリジナルの圧縮されていない表現に戻すために、あなたは他の人の画像をそれぞれ圧縮する前の状態に戻すべきです。圧縮されていない表現へと戻す逆変換を確かめるためのチェックは、画像が同じであることを確認することによって正しく行われました。

あなたと友達は共にコンピュータであると想像しながら、このようにすることで、これらの表現のシステムを使った画像が、あるコンピュータ上で圧縮され、別のコンピュータ上で伸長できることを示したのです。圧縮アルゴリズムが役立つためにはこの特性を持つことはとても重要です。もし、友達からコンピュータで圧縮した歌をもらったのに、あなたのコンピュータではその歌に使われた圧縮表現を理解できないとしたら、全く意味がないでしょう。

専門家のためのおまけ

あなたが思いつく最高の圧縮(つまり、オリジナルに対してとても小さなサイズを持った画像)をした画像は何でしょう?圧縮アルゴリズムにとって、このことは最高の出来栄えとなります。

最悪の圧縮についてはどうでしょうか?実際に大きな圧縮表現をした画像を見つけられますか?(我々が使ったバージョンのコンマを忘れないで下さい!)これは、圧縮アルゴリズムに取って最悪の出来栄えなのです。

実際、どんな可逆圧縮アルゴリズムも、非圧縮バージョンよりも圧縮バージョンの方がファイルが大きくなってしまう場合があるのです!コンピュータ科学者達はそのことを証明している、つまり、誰もがすべてのファイルを小さくする可逆圧縮アルゴリズムを考え出すことは不可能なのです。しかし、ほとんどの場合、良い可逆圧縮アルゴリズムは、最高の圧縮をするデータの共通パターンと、極まれにしか発生しない最悪の圧縮をするパターンとを持つ傾向にあるので、このことは問題ではありません。

専門家のためのおまけ

この章の最初で我々が使った、1ピクセルあたり1文字の簡単な表現を用いてる画像形式が実際にあります。この形式はポータブルビットマップ形式(PBM)と呼ばれます。PBMファイルはファイルの拡張子が".pbm"として、画像データを加えた簡単なヘッダーを含んで保存されます。
ファイルの中のデータは、a.txtファイルを開くようにテキストエディタで開くことで見えることと、画像そのものをPBMファイルをサポートするドローや画像閲覧のプログラムで見ることができます(それらはきちんとサポートされてはいませんが、いくつかの画像閲覧や画像編集のプログラムはそれらを見ることができます)。ダイアモンドの画像のPBMファイルは以前次のように使われました。

P1
15 15
011000010000110
100000111000001
000001111100000
000011111110000
000111111111000
001111101111100
011111000111110
111110000011111
011111000111110
001111101111100
000111111111000
000011111110000
000001111100000
100000111000001
011000010000110

最初の2行はヘッダーです。1行目はファイルのフォーマットを指定しています(P1はファイルがアスキーの0と1を含んでいることを意味します。2行目は画像の幅と高さをピクセルで指定しています。)。このことは、例えファイルの行を分けている改行コードが失われたとしても、コンピュータが画像のサイズや大きさを知ることを可能にします。データの残りが上に示した画像です。もしあなたがしたいと思うなら、この表現(ヘッダーを含んで)をテキストファイルへとコピー&ペーストし、拡張子.pbmとしたファイルで保存できるでしょう。もしあなたがあなたのコンピュータにPBMファイルを開くことのできるプログラムを持っているのなら、あなたはそれで画像を見ることができるでしょう。あなたはこれらのファイルを出力するプログラムを書けるのなら、画像として表示することもできるでしょう。

文字の代わりにピクセルをビットへと詰め込むこのフォーマットのバリエーションや、グレイスケールやカラー画像のためのバリエーションがあります。この形式についてのより詳しい情報はWikipediaにあります。

Challenge: Best and worse cases of run length encoding
What is the image with the best compression (i.e. an image that has a size that is a very small percentage of the original) that you can come up with? This is the best case performance for this compression algorithm.
What about the worst compression? Can you find an image that actually has a larger compressed representation? (Don’t forget the commas in the version we used!) This is the worst case performance for this compression algorithm.

Spoiler: Answer for above challenge
The best case above is when the image is entirely white (only one number is used per line). The worst case is when every pixel is alternating white and black, so there's one number for every pixel. In fact, in this case the size of the compressed file is likely to be a little larger than the original one because the numbers are likely to take more than one bit to store. Real systems don't represent the data exactly as we've discussed here, but the issues are the same.

Curiosity: Compression methods can expand files

   In the worst case (with alternating black and white pixels) the run length encoding method will result in a file that's larger than the original! As noted above, every lossless compression method that makes at least one file smaller must also have some files that it makes larger --- it's not mathematically possible to have a method that always makes files smaller unless the method is lossy. As a trivial example, suppose someone claims to have a compression method that will convert any 3-bit file into a 2-bit file. How many different 3-bit files are there? (There are 8.) How many different 2-bit files are there? (There are 4.) Can you see the problem? We've got 8 possible files that we might want to compress, but only 4 ways to represent them. So some of them will have identical representations, and can't be decoded exactly.

Over the years there have been several frauds based on claims of a lossless compression method that will compress every file that it is given. This can only be true if the method is lossy (loses information); all lossless methods must expand some files. It would be nice if all files could be compressed without loss; you could compress a huge file, then apply compression to the compressed file, and make it smaller again, repeating this until it was only one byte --- or one bit! Unfortunately, this isn't possible.

7.3. 画像圧縮:JPEG

画像は多くのスペースを消費します。そして、画像がコンピュータに保存される際の時間の大部分は、画像はより多くのスペースを消費することを避けるために圧縮されます。多くの画像(特に写真)で、画像をオリジナルで正確に保存する必要はありません。なぜなら、それは、人間(?)が見て取れる以上の詳細(の情報?)を含んでいるからです。このことは、特に、紛失する詳細が人々が知覚困難な種類であれば、スペースにかなりの節約をもたらす可能性もあります。この圧縮の種類が、不可逆圧縮です。医学的なスキャンや高品質な画像処理のように、画像をオリジナルとして正確に保存する必要がある他の場面があります。これらの場合は可逆圧縮の方法が使われたり、画像を全く圧縮しません(つまり、カメラのそのままの形式を使います)。

データ表現の章で、我々は、各ピクセルのカラー表現により少ないビットを使うことで、画像ファイルのサイズを減らす方法を見ました。しかしながら、JPEGのような画像圧縮法は、それを表すために必要とされるスペースを減らすために、不必要な画像への影響を与えることなく、画像の中にあるパターンの利点を活かします。

次の3つの画像は、ビットの深さと具体的な画像圧縮システム利用の違いを示しています。左手の画像はオリジナルで、ピクセル当り24ビットです。中央の画像はJPEGを使ってオリジナルサイズの3分の1に圧縮してあります。オリジナルの"不可逆圧縮"のバージョンですが、その違いに気付くことはないでしょう。右手の画像は256色に減らしたもので、ピクセル当り24ビットではなく8ビットが使われています。これもまた、オリジナルサイズの3分の1で保存したことを意味します。例えそれが同数のビットを失ったとしても、情報の欠落は、それがどのように見えるかに、多くの影響を与えています。これがJPEGの強みです。情報は取り除かれているけれども、知覚的な質にあまり影響を与えていません。

CC-CompressionComparison.png

例えば、次の画像は、上の(高画質)画像から目の回りの詳細の部分のピクセルの見え方の拡大を示しています。

CC-Zoomed2.png

多くの細かい部分を持つこの画像のこの部分でも、隣接したピクセルの色がとてもよく似ていることに気付いて下さい。それらのピクセルは、例えば、ちょうどとても濃い色からとても明るい色へと徐々に変化するところの赤い枠の中に示されています。

CC-Zoomed2Box.png

連続長符号化はこの状態ではあなたはピクセルの色を明示するバリエーションを使えました。そして、いくつのピクセルが同じ色であるかを言えます。しかし、隣接したピクセルがほとんど同じであったとしても、それらを同一視する機会はほとんどなく、同一の色の連続はほとんどみられないでしょう。

しかし、徐々に変化する色を利用する方法はあります。上記の赤枠の中のピクセルのために、あなたは、最初の1つと最後の1つを特別視して、おおよそのこれらの色のバージョンを生成できるでしょう。そして、コンピュータに間が滑らかになるようにビットを挿入させるのです。5つのピクセルの値を保存する代わりに、2つだけが必要で、おそらくそれを見ている誰かは、何らかの違いに気付かないでしょう。正確にオリジナルを再生産することはできないので、不可逆となります。しかし、それで多くの目的のためには十分ですし、多くのスペースを節約します。

Jargon Buster: Interpolation

   The process of guessing the colours of pixels between two that are known is an example of interpolation. A linear interpolation assumes that the values increase at a constant rate between the two given values; for example, for the five pixels above, suppose the first pixel has a blue colour value of 124, and the last one has a blue value of 136, then a linear interpolation would guess that the blue values for the ones in between are 127, 130 and 133, and this would save storing them. In practice, a more complex approach is used to guess what the pixels are, but linear interpolation gives the idea of what's going on.

写真に広く使われているJPEGシステムは、このアイデアのもっと洗練されたバージョンを使います。我々が上記で行った、5×1のピクセルの連続を使う代わりに、8×8のピクセルのブロックで作業します。そして、線形関数で値を見積もる代わりに、コサイン波の組合せを使います。

Curiosity: What are cosine waves

コサイン波の公式は、三角形の辺を計算するためにしばしば使われる三角関数からきています。あなたが0度から180度までのコサインの値を点で打てば、1から-1までの滑らかな曲線を描くことができます。この描画のバリエーションは、1色から数色までで構成される画素の値に近付けるために使われます。もし、高周波のコサイン波を含めたら、面白い形を作ることができます。理論によれば、画素のあらゆるパターンは、異なる複数のコサイン波を加え合わせることによって創り出すことができるのです!

CC-CosineGraph.png

Couriosity:
高い圧縮率のJPEG画像を拡大すれば、8×8のブロックを見ることができます。例えば、次の画像はJPEGを用いて非常に高い圧縮率で作られています(オリジナルサイズのちょうど1.5%です)。

CC-LowQualityJPEG.png

目の周辺を拡大したら、8 x 8 のピクセルのブロックが見えるでしょう。

CC-ZoomedJPEG.png

どのブロックにも、とても小さな変化があることに気付いて下さい。次の画像のブロックのいくつかを見てみましょう(?)。赤のブロックには上から下への変化しかありません。おそらくは2つの値を与えるだけで作れてしまうでしょう。緑の四角は左から右へ変化しているだけです。そして、こちらも64ではなく保存された2値だけが必要です。青のブロックはその中に1色しかありません!黄色のブロックは、画像のその部分の中に、他の処理が施されている(?)ため、より複雑です。そこには、複数のコサイン波が入り込んでいるのです。"波"の値は上下に変化します。暗明暗と変わる左から右への変化と主に暗明と変わる上端から下端への変化によって、表現されています。このように、ほんの数個の値が最大64の代わりに保存されることが必要です。

CC-ZoomedJPEGHighlighted.png

質はとても低いですが、スペースは大きく節約します。それは、60分の1以下になります(例えば、それは60倍速くダウンロードできるでしょう)。高品質のJPEG画像は、それぞれの8×8ブロックをより詳細に保存します。それは、オリジナルの画像に近くなりますが、詳細が保存されているためにより大きなファイルになります。

Jargon Buster

"JPEG"という名前は、"Joint Photographic Experts Group"を短くしたもので、1980年代に標準化を作るために組織されました。これによって、撮影されたディジタル写真が装置のブランドが異なっていても表示されるようになりました。ファイルの拡張子は3文字と制限されているので、それはしばしは".jpg"拡張子として見ることがあります。

Extra for Experts

"JPEG"という名前は、"Joint Photographic Experts Group"を短くしたもので、1980年代に標準化を作るために組織されました。これによって、撮影されたディジタル写真が装置のブランドが異なっていても表示されるようになりました。ファイルの拡張子は3文字と制限されているので、それはしばしは".jpg"拡張子として見ることがあります。

JPEGは滑らかに変化する色として画像を表現するので、ある重要な問題が発生します。もしも、色が突然変わったら何が起きるでしょうか?このような場合には、色の突然の変化を作るために多くのコサイン波が加えられて、多くの値を保存しなくてはいけなくなるのです。突然の変化ではコサイン波が過剰に発生することが想像できるでしょう。それは、エッジが乱れた次の画像にあるように、画像の乱れを生じさせます。

CC-CleanJPEGLowQ.jpg

オリジナルは鋭いエッジを持っていましたが、そのJPEGバージョンの拡大は、エッジが段になっているだけでなく、暗いピクセルが白いスペースの先へと生じていて、影や繰り返しのように見えています。

CC-CleanJPEGLowQZoom.jpg

この理由から、JPEGは写真や自然画像に使われますが、このような人工的な画像には他の技術(他の章で見るGIFやPNGのような)の方が上手く働きます。

7.4. 汎用的な圧縮

汎用的な圧縮法は、ユーザがデータの変化に気付かないだろうとは、仮定できないので、可逆であることが必要です。最も広く使われている汎用的な圧縮アルゴリズム(ZIPやgzipやrarのような)は、1970年代にヤコブ・ジブとアブラハム・ランペルによって発明された"Ziv-Lempel(ジブ・ランペル)符号化"と呼ばれる方法に基づいています。

テキストファイルを扱うこの例を見てみましょう。ジブ・ランペル符号の主なアイデアは、ファイルの中で何度も繰り返される文字列は(例えば文字列"image"がこの章では何度も出てきます)、繰り返しの発生の替わりに、それが最後に発生した場所への参照で置き換えるというものです。置き換えられるフレーズよりも参照が小さい程、多くのスペースを節約できるでしょう。概ねこのアプローチに基づいたシステムは、テキストファイルをそのオリジナルサイズの4分の1程度に減らすことができ、文字を圧縮するために知られている任意の方法と同じくらい良い方法です。

次の対話型(コンテンツ)はこのアイデアを探求させてくれます。空の箱は、それ以前に発生したテキストへの参照で置き換えられています。あなたは、箱をクリックすることで、その参照がどこにあるかわかり、参照した文字列をテキストに復号できるようになります(?)。もし、参照が他の参照を指していたら何が起きるでしょう?最初から最後まであなたがそれを復号すれば、(あなたがそれを必要とする前に?)情報が使えるようになるでしょう。

あなたはまた"テキスト"タブをクリックすることで、あなた自身の文字を入力することができます。そして、いくつの文字が参照で置き換えられていたのかを知るために、あなたが書いた文字を繋ぎ合わせられるでしょう。

参照は、実際2つの数です。第1の数は、前のフレーズがスタートする場所までいくつの文字を戻るのかを示します。そして、第2の数は、参照のフレーズがどれだけ長いかを示します。どの参照でも概ね、1〜2文字のスペースを取ります。従って、システムは2文字が置き換わる長さで節約をします。上の対話型コンテンツのオプションは、1つの参照が1つの文字で置き換わることを避けるために、置き換わる長さが少なくとも2文字を必要とするようになっています。もちろん、アルファベットだけではなく、すべての記号を数えるので、システムはまた、単語間の空白に戻って参照ができる。実際、ほとんど共通する文字列のいくつかは、後ろにスペースがつく終止符のようなものである。

このアプローチはまた白と黒の画像に対しても上手く働く。"10の白いピクセル"のような列は、以前発生していたもののようにありえることであるから。ここに、この章で前に出た例のビット列がある。あなたは、これらを上の対話型コンテンツに貼付けて、これを表すためにいくつのポインターが必要となるかを調べられる。

011000010000110
100000111000001
000001111100000
000011111110000
000111111111000
001111101111100
011111000111110
111110000011111

実際、このことはGIFやPNG画像で起きていることとして、不可欠である。ピクセルの値は、同じ色が連続するピクセルが多い場合に上手く働くジブ・レンペルアルゴリズムが使われることで圧縮される。
しかし、ピクセルパターンが繰り返されることがほとんどないような写真では上手く働かない。

好奇心

我々がここで述べてきた方法は、1970年代にそれを発明したヤコブ・ジブとアブラハム・レンペルという2人のコンピュータ科学者の名をとって、"ジブ-レンペル"圧縮と名付けられました。彼らがそれについての記事を書いたとき、不幸にも誰かが彼らの名前をごちゃ混ぜにしてしまい、"ZL"圧縮の代わりに"LZ"符号と呼びました。そして、ジブとレンペルの方法は今では"LZ"圧縮と呼ぶ間違いを、多くの人がコピーしました!

7.5. オーディオ圧縮編集

音楽を圧縮ためのもっとも広く使われている方法の1つがMP3であって、実は、ビデオ圧縮規格から来ています。人々が機器の異なるブランド(特にDVD)でも同じビデオを簡単に再生できるように、標準化に同意した会社や研究者が集まった組織でした。彼らの規格の最初のバージョン(MPEG1と呼ばれる)は、音楽のトラック(レイヤー1,2,3)を保存する3つの方法を持っていました。これらの方法の1つ(MPEG1のレイヤー3)は、音楽を圧縮するためにとても広まり、MP3と省略されました。

いくつかの方法は、同じ量を蓄えるためのより良い品質を提供しますが、他のほとんどのオーディオ圧縮方法はMP3の方法と類似したアプローチを使います。MP3がどのように働くのかを知ることは不可欠ではないですが、一般的な考え方は、音を異なる周波数の帯域へと分解することです。そして、簡単な数式の値(コサイン波の合計, 正確に)を加え合わせることで、それぞれの帯域を表現します。

cs4fnのサイトやI Programmerサイトの記事には、どのようにMP3符号が働くかについての詳細があります。

あなたが目にするであろう他のオーディオ圧縮システムはAACやALAC、Ogg、WMAを含みます。これらの方法はそれぞれにいろいろな利点があります。そして、いくつかの方法は、互換性があったり、他よりもオープンであったりします。

圧縮されたオーディオに伴う主な疑問は、どのようにファイルを小さくできるのかということと、その音質が人の耳にとってどうなのか、ということです。(ファイルを符号化するためにどの位の時間が掛かるかという質問もあります。それは、システムがどれ程便利かということに影響するかも知れません)音質とオーディオファイルの大きさとの間にあるトレードオフは、あなたがどのような状態にあるかに依存します。あなたがもしもジョギングをしながら音楽を聴いているなら、音質はそれほど重要ではないでしょう。でも、それを格納するために使用可能なスペースを減らすことは良いことです。一方、良い音響システムを使い、自宅で録音を聞いている人にとっては、音質が良くさえあれば、音楽を保存するために大きな機器を持つことについて、気にしないかも知れません。

オーディオ圧縮を評価するためには、あなたはあなたの持っている高音質のオリジナル、典型としてはCD(または圧縮をしていないWAVAやIFFファイル)の様々な録音を選ぶべきでしょう。異なるスタイルの音楽や演説のような他のオーディオの種類、そして、おそらくは全体的には静かな録音を創作でさえも選びましょう。そして、これらの録音を異なるオーディオ形式に変換しましょう。このことをする1つのシステムにフリーでダウンロードするアップルのiTunesです。これはCDを色々なフォーマットへと変換(?)し、質やサイズの設定の選択を与えます。たくさんの他のオーディオシステムがファイルの変換ができたり、改造のできるプラグインを持っています。

どの圧縮ファイルが高音質のオリジナルから作られたかを確かめながら、様々な方法を使ってあなたの録音を圧縮してみましょう。それぞれの録音の過程に掛かった時間や、圧縮ファイルのサイズ、オリジナルと比べた音質の評価を示す表を作りましょう。トレードオフに関係した議論をしましょう。ー良い質の音を保存するために、あなたはもっと大きなファイルが必要ですか?どの位の小さなファイルを作れるかという制限はありますか。そしてそれは音としてokですか?他のものよりもスピーチのためにより良い方法はありますか?2分間の沈黙の録音は1分間の沈黙の録音よりも多くのスペースを使いますか?1分間の音楽の録音は、1分間の沈黙よりも多くのスペースを使いますか?

7.6. まとめ

この章では圧縮システムがどのように働くかの詳細を、それらがどのように働くかよりもファイルサイズや方法のスピードについて考えながら説明(?)してきました。大部分の圧縮システムはここでカバーしてきたアイデアの変形ですが、我々が言及して来なかった1つの基本的な方法にハフマン符号化があります。これは、これまでの方法すべての最終ステージとして役立つものへと進展させます。そして、しばしば教科書の圧縮の議論の中で最初に言及されるトピックの1つです。(ここにはその簡易な探求があります。近く関連システムが算術符号化です。)ビデオの圧縮は、他のほとんどの圧縮よりも多くのスペースを節約するにも関わらず、動画もまた省略されてきました(?)。ほとんどのビデオ圧縮は、"MPEG"規格(動画専門家集団)に基づいています。"Movie Magic"のCS4FNの記事にはどのようにこれが働くかについての情報があります。

示したジブ・ランペル法は、"LZ77"法と呼ばれるものの変型です。もっとポピュラーな圧縮法の多くがこれに基づいています。多くの変型があるのですが、"LZW"と呼ばれるその1つもまた、多く使われてきました。他の高圧縮汎用圧縮法がbzipで、Burrows-Wheeler変換と呼ばれるとても賢い方法に基づいています。

"達成できる最大の圧縮は何か"のような質問は、情報理論の分野によって扱われています。CSアンプラグドには情報理論の活動があり、情報理論を説明する楽しい活動があります。この理論に基づけば、英語のテキストは最善でオリジナルサイズの12%以下には圧縮できないと思われています。画像、音声、ビデオについては、非可逆圧縮が使え、オリジナルのデータに正確に再現する必要がないことから、もっと効率よく圧縮することができます。

7.7. 参考文献

  • "データ圧縮"(マーク・ネルソン, ジーン・ループ)は、この話題の良い概要になっています。
  • この分野の本のリスト(圧縮に関する他の多くの情報を含め)は、データ圧縮のサイトから利用可能です。
  • グレイクの著書"情報"には、圧縮へのバックグラウンドと一般的なコーディングがあります。

7.7.1. 関連サイト

powered by Quick Homepage Maker 5.1
based on PukiWiki 1.4.7 License is GPL. QHM

最新の更新 RSS  Valid XHTML 1.0 Transitional