GIF 圧縮アルゴリズムの発明者が IEEE の最高栄誉賞を受賞

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載しています。転載の際は出典元にご連絡ください。

イスラエルの科学者ジェイコブ・ジブ氏（90歳）は、「情報理論とデータ圧縮技術への根本的な貢献と、卓越した研究リーダーシップ」が認められ、2021年のIEEE名誉賞を受賞した。

△ ジェイコブ・ジヴ

IEEE 名誉賞は IEEE によって毎年授与され、世界の電気電子工学コミュニティにおける最高の栄誉です。

1977 年と 1978 年に、Jacob Ziv 氏ともう一人のイスラエル人科学者Abraham Lempel 氏が、彼らの名前にちなんでLZ77とLZ78 と名付けられた汎用ロスレス圧縮アルゴリズムを発明しました。

このアルゴリズムは 2004 年にIEEE マイルストーンとして認定されました。

LZ アルゴリズムは後に、LZW、LZSS、LZMA など、ロスレス圧縮アルゴリズムの多くのバリエーションを形成しました。

これらの派生アルゴリズムは、 GIFやPNG画像圧縮、 RARやZIPファイル圧縮など、現在でもコンピューターで使用されています。

「LZ アルゴリズムは、初めて成功した汎用圧縮アルゴリズムです」と、Ziv 氏の受賞を支持したエンジニアは述べています。「これらのアルゴリズムと、Jacob 氏の分析は、その後の汎用アルゴリズムに関するほとんどの研究の基礎となりました。」

LZ アルゴリズムは、圧縮されたデータの完全な再構築を可能にし、以前の圧縮アルゴリズムよりも効率的です。

他のアルゴリズムと比較すると、Ziv が開発したこのユニバーサル ソース コードは、データの固有情報を知らなくてもデータを圧縮できるため、データから画像を再構築するために必要なデータ レート要件が削減されます。

さらに、Ziv は、計算複雑度の低い誤り訂正符号の復号化の理論にも貢献しました。

LZ圧縮アルゴリズムの紹介

LZ77 と LZ78 は、Abraham Lempel と Jacob Ziv が 1977 年と 1978 年に論文で発表した 2 つのロスレス データ圧縮アルゴリズムです。それぞれ LZ1 および LZ2 とも呼ばれます。

LZ アルゴリズムは、文字列を単一のトークンに置き換えることによって機能します。アルゴリズムは新しい文字列を認識するたびに、その文字列を出力し、テーブルまたは辞書に追加します。

△ LZW圧縮アルゴリズム

次回この文字列に遭遇したときには、テーブル内のトークン コードに置き換えられます。これにより、データ圧縮と伝送効率の向上という目的が達成されます。

簡単な例を見てみましょう。

私はエンジニアです。だから私はエンジニアであり、私がエンジニアである場合に限ります。

圧縮後、この文は次のようになります。

私はそこでのエンジニアであり、*の場合のみです。

上記の段落では、最初に出現する「I am an engineer」は「*」に圧縮され、「re」は「&」に圧縮されています。したがって、後で同じ文字列が出現したときには、「*」と「&」を使用して置き換えるだけで済みます。

元の文字列が長く冗長であるほど、達成される圧縮率は高くなります。

LZ アルゴリズムは最初に文字列とトークンを送信するため、逆圧縮アルゴリズムは元のメッセージを再構築することができ、追加情報 (辞書自体など) は必要ありません。

LZ アルゴリズムはシンプルで使いやすいため、広く使用されています。現在、その重要な用途の 1 つは、GIF 画像ファイルの保存と送信です。

ジェイコブ・ジヴ

ジェイコブ・ジブは1931年にイスラエルのティベリアで生まれました。1954年にイスラエル工科大学で電気工学の学士号、1957年に修士号を取得しました。その後、アメリカに留学し、1962年にマサチューセッツ工科大学で博士号を取得しました。

1968 年、ジヴは AT&T ベル研究所に技術スタッフの一員として入社しました。 1970年にイスラエルに戻り、母校であるイスラエル工科大学の教授となり、後に電気工学部の学部長となった。

これまでに、Ziv は IEEE から数々の栄誉を受けています。

1995 年、彼は「情報理論とデータ圧縮の理論と実践への貢献」によりIEEE ハミング メダルを受賞しました。 1997 年、彼は通信理論の分野で最高の賞である IEEE 情報理論学会のシャノン賞を受賞しました。