70年前、彼は試験を避けたかったが、インターネット全体に影響を与えた

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

試験を受けたくないという学生の「わがまま」が、後にインターネット全体に影響を及ぼすことになるとは誰が想像したでしょうか。

70年前、MITの情報理論の授業で、教師は「ストレスを軽減する」ために学生に多肢選択式の質問を与えました。

最終試験を受けるか、既存のアルゴリズムを改善するための論文を書くか、どちらかを選択してください。

その教師の名前はロバート・ファノだった。彼が学生たちに教えなかったのは、この「既存のアルゴリズム」が、情報理論の創始者であるシャノンと彼が共同で考案したシャノン・ファノ符号化だったということだ。アルゴリズムの欠点を改善するために、彼は研究に多くの時間を費やした。

（先生の心の声：そんなことは予想していませんでした。）

少しダメージはありますが、このトリックは本当に効果があります。デイビッド・ハフマン氏を含め、学生たちは「論文を提出する」だけで試験を受けなくてもよいと聞いて、ためらうことなく論文を書くことを決意した。

選択するまでは分かりませんが、選択すると驚くことになるでしょう。駆け出しのハフマンはすぐに先生が仕掛けた罠に気づいた。この論文は扱いにくいものだったのだ。

この執筆は数か月続き、大変な苦労にもかかわらず、ハフマンは何も達成できなかった。

しかし、運命というのは時々とても奇妙なものです。ハフマンがついに「試験をサボる」ことをあきらめて、論文ノートをゴミ箱に捨てようとしたとき、突然アイデアが浮かんだのです。答えはここにあります!

ハフマンは既存のコードの研究を断念し、新たな探求に目を向け、最終的に順序付けられた周波数バイナリツリー符号化に基づく方法を発見しました。

彼が提案したアイデアは、効率の点で彼の先生の方法論を上回りました。その後の開発においても、彼の名にちなんで名付けられたコーディング方式であるハフマンコーディングは、データ圧縮のパラダイムを直接変えました。

当時の最終報告書は、約１万回引用されています。

非効率的な従来のコーディング方法

1951 年、MIT で教鞭をとっていたロバート・ファノは、情報理論における難しい問題について考えていました。

バイナリコードを使用して数字、文字、その他の記号を効率的に表現するにはどうすればよいですか?

当時最も一般的で直接的な方法は、各文字に一意の 2 進数を割り当てることでした。

たとえば、文字 A は 01000001 と表される場合があります。これは 00100001 として表され、各 8 桁の数字が 1 文字に対応します。

これにより、コードの解析は容易になりますが、非常に非効率的になります。

モールス信号に似た最適化方法もあります。一般的な文字「E」はドットだけで表されますが、珍しい文字「Q」には、より長くて手間のかかる「—— —— · ——」が必要です。

この方法ではコードの長さが不一致になり、情報が理解しにくくなります。また、送信中に文字間にギャップを追加する必要があります。そうしないと、異なる文字の組み合わせを区別できなくなります。

Fanno は、おそらく両方の方法の利点を組み合わせて、さまざまな長さのバイナリ コードで文字を表現できることに気づきました。さらに、コードの「重複」を避けるために、バイナリツリーも構築しました。

写真

彼は最大限の効率を得るためにあらゆる可能な組み合わせを徹底的にテストし、最終的に機能する状況にたどり着きました。

各メッセージは頻度に応じて 2 つのブランチに分割され、両側の文字の使用頻度が可能な限り同じになります。

写真

こうすることで、頻繁に使用される文字は、より短く、密度の低い枝に配置されます。

1948 年、情報理論の父であるシャノンは、情報理論を紹介した論文「通信の数学的理論」でこの手法を提案しました。その後すぐに、ファノも技術レポートの形で独自にこの手法を発表しました。そのため、この方法はシャノン・ファノ符号化と呼ばれます。

しかし、この方法は常に機能するとは限りません。文字の出現確率が{0.35, 0.17, 0.17, 0.16, 0.15}の場合、理想的なコードを与えることはできません。

Fanno 氏は、より優れた圧縮戦略があるはずだと考えています。そこで、この重要な任務は彼の生徒たちに引き継がれました。

ひらめき、世紀の論文

むしろ、ファノは、枝のペア間の対称性をできるだけ維持しながら、キャラクターツリーを上から下へ構築するように教えました。

ハフマンの方法は、このプロセスを直接覆し、下から上へバイナリツリーを構築します。

彼は、何が起ころうとも、有効なコードでは、最も一般的でない 2 つの文字に最も長い 2 つのコードが割り当てられるはずだと推論しました。

したがって、最初に最も共通性の低い 2 つの文字を識別し、それらをブランチ ペアとしてグループ化し、次にこのプロセスを繰り返して、残りの文字と作成した文字ペアから最も共通性の低い文字 (ペア) を探します。

写真

教室を例にとると、O は 4 回、S、C、H、L、R、M はそれぞれ 1 回ずつ登場します。

Fanno の方法は、まず O と別の文字を左のブランチに割り当て、両側で合計 5 回使用し、生成されるコードの合計が 27 ビットになるようにします。

写真

対照的に、たとえばハフマンのアプローチでは、珍しい r と m から始めて、それらを文字のペアに組み合わせます。

写真

組み合わせ後、既存の文字（ペア）には、O（4 回）、RM（2 回）、および単一の文字 S、C、H、L が含まれます。

頻度で割り、前の操作を繰り返します。つまり、一般的でない 2 つのオプションをグループ化し、ツリーと頻度グラフを更新します。

最終的に、「schoolroom」は 1110111110000110110000101 となり、これは Fano のトップダウン アプローチよりも1 ビット小さくなります。  

写真

ここでは 1 ビットは大したことないように思えますが、数十億バイトに拡大すると大幅な節約になります。

実際、ハフマンの方法は非常に強力であることが証明されています。Google Scholar によると、その論文はその年に 9,570 回引用されています。

写真

先生のやり方については、二度と使われることはほとんどなかった。

現在でも、ほとんどすべてのロスレス圧縮方式はハフマン方式を全体的または部分的に使用しており、画像、音声、表などを圧縮できます。 PNG 画像標準から、広く使用されているソフトウェア PKZip まで、あらゆるものをサポートします。

現代コンピュータサイエンスの先駆者でありチューリング賞受賞者のクヌースは、かつてハフマンの業績について次のように述べた。

ハフマン符号化は、コンピュータサイエンスやデータ通信で使用されてきた基本的な考え方です。

ハフマン氏は後に、紙のメモをゴミ箱に捨てようとした時に突然考えがまとまり、頭の中に答えが浮かんだときの「ひらめき」の瞬間を思い出した。

それは私の人生の中で最も奇妙な瞬間でした。

突然、稲妻がひらめいたように、あることが分かりました。

彼は、もし教授のファノ氏がその問題に苦労していたと知っていたら、25歳の時にその問題を解こうと試みることはおろか、挑戦しようとも思わなかったかもしれないと語った。

達成感と秩序感、数学を使って芸術を遊ぶ

ハフマン符号化はデータ圧縮のパラダイムを変え、数々の栄誉とメダルを獲得しました。

たとえば、1998 年にハフマン氏は IEEE 情報理論学会から技術革新に対するゴールデン ジュビリー賞を受賞し、1999 年には電気電子技術者協会 (IEEE) からリチャード ハミング メダルを受賞しました。

しかし、それでも彼が生涯でもっとも誇りに思っていたのは、ロスレス圧縮方式の発明ではなく、この博士論文だった。

タイトル:シーケンシャルスイッチング回路の合成。

写真

ハフマンは MIT で博士号取得のために勉強していたときに、シーケンシャル スイッチング回路について論じたこの重要な論文を発表しました。当時、ハフマンは非同期順次スイッチング回路の設計方法を説明したほぼ最初の学者であり、この理論は後にコンピューターの発展に重要な論理的サポートを提供しました。

この論文の発表により、彼はフランクリン研究所からルイス・E・レヴィ・メダルを受賞しただけでなく、同校でスイッチング回路に関する講座を教える職を得ることもできました。

写真

在学中、ハフマンは、情報を失うことなく、ある2進数列を別の2進数列に変換できる革新的な数式も提案しました。この研究は当時重要な役割を果たし、彼に重要な地位をもたらしました。

当時ベル研究所の研究担当副社長だったウィリアム・O・ベイカーは、国家安全保障局の将来の技術計画を検討する委員会に彼を採用した。ベイカー博士は、アイゼンハワー、ケネディ、ジョンソン、ニクソン、レーガンの 5 人の大統領の科学顧問を務めました。

1967年、すでに教授であったホフマンはMITを離れ、カリフォルニア大学サンタクルーズ校（UCSC）に入学し、そこでコンピュータサイエンス学部の設立を主導し、学術コースの開発に参加して、その後のコンピュータサイエンス学部の発展のための重要な基盤を築きました。

数学はハフマンの生涯にわたる追求の一つであると言える。後に芸術に取り組んでいたときも、数学なしではやっていけないほどだった。

写真

ハフマンは1970年代から折り紙に強い関心を抱き、数学と折り紙芸術を同時に研究し、何百ものジグザグ折り紙作品を制作し、ジグザグ折り紙の数学的性質を分析した論文を発表し、折り紙数学の分野の先駆者となりました。

振り返ってみると、ハフマンは生涯を通じて数多くの栄誉と表彰を受けたが、自身の発明の特許を申請したことは一度もなかった。

最後に、ハフマン自身の言葉を借りたいと思います。

科学者として、そして教師として、私は本当に粘り強いです。問題に対する最も簡単な解決策が見つからなかったと感じると、私は非常に不満を感じ、最善の解決策が見つかるまでこの不満は続きます。私にとって、これが科学者であることの本質です。