2023年4月16日日曜日

データ圧縮のパイオニア?

 データ圧縮のパイオニアであるジェイコブ・ジヴ氏の功績とその半生とは?

2年前の記事に何を今更という感じですが、偶然たどり着きました。昔(高校生くらいの頃かな?)データ圧縮について色々調べたことがあり、記事の内容についてちょっと気になったので今更ですがいくつかコメントします。

どっかで似たようなことを書いてる人もいそうですが。

Ziv博士って何者?

記事にある通り、データ圧縮で有名な研究者です。Lempel博士とともにLZ77とLZ78という圧縮アルゴリズムを開発しました。

LempelさんとZivさんが1977年に開発したものがLZ77、翌年に開発したものがLZ78という安直なわかりやすいネーミングです。

LZ77が改良されてZIPやPNGなどが生み出され、LZ78が改良されてGIFが生み出されたと聞けば、いかに重要な発明かわかるでしょう。

ちなみにLempel博士は今年の2月に、Ziv博士は3月に亡くなっています。この記事書いてて初めて知った。

気になったところ

可逆圧縮の生みの親?

まずは、タイトルから始まって全編通してZiv博士が可逆圧縮を初めて開発したかのように書いてあること。

「このような可逆圧縮技術は何が画期的で、どのように生み出されたのか、その生みの親であるジェイコブ・ジヴ氏の半生と功績について...」「このような可逆圧縮を可能にするアルゴリズムの生みの親が、ジェイコブ・ジヴ氏です。」のように。

LZ77以前から可逆圧縮アルゴリズムは存在していました。コンピューターサイエンスを学んだ人なら聞いたことがあるかと思いますが、ハフマン符号化がそれです。さらに言うならその前にシャノン符号化もありますし、そもそも「同じ記号が連続して出現したら、記号と連続した回数に置き換えよう」という連長圧縮の考えはずっと前からあったでしょう。

ハフマン符号化については記事中にも「当時最先端だった」と触れているので著者が誤解していたわけではないと思いますが、それにしても誤解を招く書き方です。LZ77と78の画期的だった点は、これまでの方式とは全く異なる、辞書と呼ばれる考えを導入した部分なので、記事でもここを強調すればよかったのにと思います。

ある意味LZ77は連長圧縮の発展形とみなすこともできるのですが。

ビットを削除?

非可逆圧縮についての説明で以下のような文があります。

非可逆圧縮は、「デジタルデータからビットを削除する」という方法を用います。

ん?ビットを削除ってなんだ?

非可逆圧縮は、人間の知覚しづらい部分(サウンドの高音域とか画像の色が連続的に変化する部分とか)をちょっとくらい違っていてもバレやしないと正確さを犠牲にして圧縮に都合のいいデータに置き換えるものであって、10100100の中央2ビットを削除して101100にするとかそういうことじゃないぞ?

多分非プログラマー向けにわかりやすく書いたんだと思いますが、逆にわかりにくいというか変な理解をしてしまう書き方になってしまってます。

ハフマン符号化について

ハフマン符号化の説明もなんかおかしい。

ハフマン符号のアプローチはデータファイル内のビットの並びを検索し、頻出順に並び替えることから始まります。

並び替えるって何を?ハフマン符号化にソートは関係ないよ!


最も頻出する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当て、エンコーダーが符号化の辞書を作成します。

言葉の選び方の問題なんだろうけど、「辞書」は誤解を招く表現です。データ圧縮の分野で辞書といったら上で出てきたLZ77とか78の辞書(今までに出てきたビット列を管理するもの)を真っ先に思い浮かべますが、ハフマン符号化で使われているのは辞書ではなく、単なる記号の出現頻度(Aが100回、Bが50回など)です。


データの読み込みを「データの頻出度を計算するため」と「データをエンコードするため」の2回にわけて行わなければならないという点が欠点です。またエンコードされたデータとともに符号の「辞書」を保存すると圧縮ファイルのサイズが大きくなる点も問題として指摘されていました。

(「辞書」という表現はさておき)静的ハフマン符号化ではそのとおりですが、データを一度だけ読み込み、頻度表を必要としない適応的ハフマン符号化という方法も存在します。

ただ、このあたりの歴史的な順序がわかっておらず申し訳ないのですが、もし適応的ハフマン符号化がLZ77や78の後に発明されていたのなら記事の内容で問題ありません。


全体的にプログラミングのことを知らない人にもわかるように書いたことを差し引いても、正確さに欠ける内容です。「本筋ではない細かい部分を端折っている」のではなく「間違えている」とか「誤解を招く」なので、非プログラマー向けならこれでOK、というものでもないと思います。特に生みの親関連。

0 件のコメント:

コメントを投稿