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

by Lance Fisher

音楽のストリーミングや画像・動画の転送などは、現代社会でなくてはならない技術ですが、これらの技術を使うにはその前提として「巨大なファイルサイズを小さく圧縮する」ことが不可欠です。このような可逆圧縮技術は何が画期的で、どのように生み出されたのか、その生みの親であるジェイコブ・ジヴ氏の半生と功績についてIEEEスペクトラムのテクラ・ペリー氏が迫っています。

From WinZips to Cat GIFs, Jacob Ziv’s Algorithms Have Powered Decades of Compression - IEEE Spectrum
https://spectrum.ieee.org/geek-life/profiles/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression

◆可逆圧縮技術とは？

音楽や画像ファイルの圧縮は大きく分けて「可逆圧縮」と「非可逆圧縮」の2種類があります。一般的には非可逆圧縮の利用が多く、たとえば手に入れた音楽ファイルをMP3に変換したり、デジタル画像をJPEGファイルにすることが非可逆圧縮にあたります。

非可逆圧縮は、「デジタルデータからビットを削除する」という方法を用います。人間の感覚では知覚しにくい部分のデータを削除するため、劣化は目立ちませんが、圧縮によって一部のデータが欠落するので、圧縮データを元に戻すことはできません。

一方で「ロスレス圧縮」と呼ばれる可逆圧縮について、ペリー氏は「まるで魔法のようなもの」と記しています。可逆圧縮の「ビットを消してファイルサイズを小さくし、保存や転送を容易にする」という点は非可逆圧縮と同じですが、可逆圧縮は「コマンドによって消したビットを復活させることができる」という点が大きな違いです。

このような可逆圧縮を可能にするアルゴリズムの生みの親が、ジェイコブ・ジヴ氏です。

ジヴ氏は計算科学者であるエイブラハム・レンペル氏とともに、1977年に「連続的なデータ圧縮のための普遍的アルゴリズム(A universal algorithm for sequential data compression)」という論文を発表しました。

現代まで続く可逆圧縮技術はこの論文をベースとしており、論文で発表された「LZ77」というアルゴリズムがなければGIFやTIFFというフォーマットは生まれなかったかもしれません。人類はデータサイズの大きなファイルをメールで送信できずディスクに入れて発送したり、音楽配信ではなくCDを買い続けていたり、FacebookやTwitterで動画を見られなかった可能性もあります。

上記のように情報理論とデータ圧縮技術に大きく貢献し、研究において卓越したリーダーシップを発揮したとして、2021年にジヴ氏は「IEEE栄誉賞」を受賞しましました。

◆可逆圧縮技術の生みの親、ジェイコブ・ジヴの半生

ジヴ氏は1931年、イスラエルの都市ティベリアにロシア移民の子どもとして生まれました。バイオリンの練習中に譜面台をランプに変えることを思いつくような子どもだったというジヴ氏は、成長すると電気工学を研究するためにテクニオン-イスラエル工科大学に入学。1955年には理学の博士号を取得し、その後1959年までイスラエル国防省の主任研究員として通信システムの開発に従事しました。

イスラエル国防省での開発について、ジヴ氏は「グループ内のエンジニアは自分を含め、誰一人として電子工学について基礎以上の理解を持っていませんでした」と振り返っています。「我々6人は互いに教え合わなければなりませんでした。本を選んで一緒に勉強して……まるでヘブライ語の聖書を研究するユダヤ人みたいに。それでも十分ではありませんでした」とジヴ氏は語っています。

この研究グループの目標は、真空管の代わりにトランジスタを利用して遠隔測定システムを構築することでした。研究グループはアメリカのベル研究所に電話してトランジスタのサンプルを100個送ってもらったこともあったそうです。

その後、ジヴ氏はイスラエル国防省の中からアメリカに留学する数人の研究者のうちの1人に選ばれました。この留学プログラムは研究者が自由に研究分野を選べるものだったので、ジヴ氏は通信技術についてマサチューセッツ工科大学(MIT)で研究することにしたとのこと。

アメリカで2年にわたり情報理論や通信技術について学んだジヴ氏は、帰国後、イスラエル国防省で通信部門を担当。そして1970年にテクニオン-イスラエル工科大学の教員となります。

テクニオン-イスラエル工科大学でジヴ氏は、可逆圧縮アルゴリズムの論文の共著者となるレンペル氏と出会い、ロスレス圧縮の改善について語り合うようになりました。

◆全ての始まりとなったアルゴリズム「LZ77」

当時のロスレス圧縮の最先端はハフマン符号でした。ハフマン符号のアプローチはデータファイル内のビットの並びを検索し、頻出順に並び替えることから始まります。そして、最も頻出する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当て、エンコーダーが符号化の辞書を作成します。

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

この問題を解決しようと議論を重ねた2人は、「一意のビットのシーケンスを探しながら、同時にデータを圧縮する」というアルゴリズムのアイデアを生み出します。このアイデアをもとに生み出されたLZ77は、データを先頭から順番に符号化していき、その都度注目しているシーケンスが「以前現れたものか」を調べます。そして既出のシーケンスであれば記号列を既出のシーケンスへのポインタで置き換えます。この方法であればデータの読み込みが1回で済み、処理時間が大きく短縮される点が画期的でした。

その後、2人は1978年にLZ77を発展させたLZ78というアルゴリズムを開発。LZ78はデータを先頭から符号化していくという点はLZ77と共通しますが、予測を行いながら符号化を行うことがポイント。

当時、レンペル氏とジヴ氏はもテクニオン-イスラエル工科大学で教員を務めながらも、レンペル氏はスペリーランド社、ジヴ氏はベル研究所でも働いていました。ジヴ氏は開発したアルゴリズムで特許を取得することを考えましたが、アメリカでは1980年代までソフトウェアの特許が認められず、ハードウェアの一部としてしか特許は取得できませんでした。そして、ベル研究所がアルゴリズムをハードウェアの一部にして特許を取得することに興味を示さなかったとのこと。

一方で、レンペル氏の雇用主であるスペリーランド社はアルゴリズムをハードウェアに実装し、特許を取得することを快諾。2人は、1984年に発表されたLZWをハードウェアに実装することで、アルゴリズムの特許を取得しました。

◆ジヴ氏の多くの功績

ジヴ氏はLZ78の特許を直接取得できなかったことを残念に思っているものの、「LZWが人気になったという事実はうれしいものですし、LZWは私たちを有名にもしてくれました。これによってさらなる研究を楽しめました」と述べています。

実際に、ジヴ氏が発表した論文は1977年と1978年の論文が有名ですが、その後もジヴ氏は約100本の査読論文を発表しました。また1985年までテクニオン-イスラエル工科大学で講義を持ち、多くの学生に影響を与え、研究者の道を開いたとのこと。

記事作成時点で89歳のジヴ氏は緑内障を患ったことで視力が弱くなり、世に出る論文は2021年1月に発表したものが最後になると伝えられています。論文は2019年にスタートした研究についてのもので、被験者のDNAを過去のサンプルと比較し、変異が起こっているかを調べられるようにする技術について記されました。この技術により、医師が患者の遺伝子疾患について理解したり、研究者が新種のウイルスと既存のウイルスのDNAを比較したりが容易に可能になります。この技術でも、データ圧縮と同様のアプローチが用いられているとのことです。