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

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

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

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

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

(教師の内なる OS: 期待していませんでした。)

少しダメージがありますが、このトリックは本当に効果があります。このグループの学生は、「論文を提出」と聞くとすぐに試験を受ける必要はなく、デビッド・ハフマンを含め、頭を撫でてから論文を書くことにしました。

選ばなければ分からないが、選んだ場合はショックを受けるだろう。勉強を始めたばかりのハフマンは、先生が掘った落とし穴にすぐに気づきました。この論文は難しすぎて解くことができませんでした。

これを書くのに数か月かかりましたが、苦労したにもかかわらず、ハフマンはまだ何も見つけられませんでした。

しかし、運命は時々非常に奇妙なものです。ハフマンはついに「試験をサボる」ことを諦め、紙のメモをゴミ箱に捨てようとしたとき、突然アイデアを思いつきました。答えが見えてきます！

ハフマンは、既存のコードの研究を諦めて新たな探求に目を向け、最終的に順序付け周波数二分木コーディングに基づく方法を発見しました。

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

当時の最終報告書については、1万回近く引用されています。

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

1951 年、MIT で教えていたロバート ファンノは、情報理論の難しい問題について考えていました。

バイナリ コードの使用方法 は数字、文字、その他の記号を効率的に表しますか?

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

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

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

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

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

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

写真

彼は最大限の効率を得るためにあらゆる順列の可能性を徹底的にテストし、最終的に有効な状況に到達しました。

各メッセージは頻度に応じて 2 つの分岐に分けられ、両側の文字の使用頻度は基本的に 同じになるようにします。

図

こうすることで、一般的に使用される文字が短く、密度の低い枝に配置されます。

1948年、情報理論の父シャノンが情報理論を紹介する論文「コミュニケーションの数学理論」でこの手法を提案し、その後すぐにファンノが独自に技術レポートの形で出版しました。したがって、この方法は Shannon-Fano 符号化 と呼ばれます。

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

Fanno は、より優れた圧縮戦略があるに違いないと考えています。それ以来、このような重要な任務は彼の生徒たちの手に委ねられました。

インスピレーションのひらめき、世紀の論文

ファンノ教授の手法が、上から下までキャラクター ツリーを構築し、枝のペア間で可能な限り対称性を保つことであるとします。

その後、ハフマンの方法はこのプロセスを直接覆すものです。ボトムアップでバイナリ ツリーを構築します。

彼は、何が起こっても、有効なコードでは 最も一般的でない 2 つの文字には 2 つの最も長いコードが含まれるはずだと信じています 。

したがって、最初に最も一般的でない 2 つの文字を決定し、それらを分岐ペアとして結合し、残りの文字と文字ペア (ペア) の中で最も一般的でない文字を見つけるプロセスを繰り返します。

写真

学校部屋を例に挙げます。O が 4 回出現し、S、C、H、L、R、M が表示されます。それぞれ1回ずつ出現します。

Fano の方法では、まず左側の枝に O と別の文字を割り当て、両側で合計 5 回の使用が行われ、生成されるコードは合計 27 ビットになります。

写真

対照的に、ハフマンの方法は、珍しい r と m で始まり、それらを 1 つの文字に結合します。

写真

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

出現頻度に従って分割し、前の操作を繰り返します。一般的ではない 2 つのオプションをグループ化し、数値ツリーと頻度図を更新します。

最終的に、「schoolroom」は 11101111110000110110000101 となり、Fano のトップダウン アプローチより 1 つ少なくなります。

図

ここでは 1 ビットは大した量ではありませんが、数十億バイトに拡張すると、これは大きな節約になります。

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

写真

彼の先生の手法に関しては、ほとんど使われることはありません。

今日まで、ほぼすべての可逆圧縮方式は、画像、音声、表などを圧縮できるハフマン方式を全体または部分的に使用しています。 PNG 画像標準からユビキタス ソフトウェア PKZip まで、あらゆるものをサポートしています。

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

コンピュータ サイエンスとデータ通信の分野では、ハフマン コーディングは人々が持っているものです。基本的な考え方を使っています。

その後、ハフマンはその「エウレカ」の瞬間を思い出しました。その時、彼は紙のメモをゴミ箱に捨てようとしていたのですが、突然彼の考えが一つになり、心の中に答えが現れました:

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

その気づきは突然、稲妻のように私に降りかかりました。

そして、ファノ教授がこの問題に苦しんでいることを知っていたら、ましてや 25 歳のときにこの問題を解決しようとは決してしなかったかもしれないと言いました。とにかく大胆に挑戦してください。

数学を芸術に利用した達成感と秩序感覚

ハフマン コーディングはデータ圧縮パラダイムを変え、多くの栄誉とメダルを獲得しました。

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

しかし、それでも、可逆圧縮方式の発明に比べて、彼の生涯で最も誇りに思ったのは、この博士論文でした。

タイトル:

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

写真

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

この論文の出版により、彼はフランクリン研究所からルイス E. レビー メダルを獲得しただけでなく、当然のことながら学校に滞在してスイッチング回路のコースを教える資格も得ることができました。

写真

ハフマンは、学生時代に、情報を失わずに # を変換できる革新的な数式も提案しました。別の 2 進数列に変換する . この研究は当時重要な役割を果たし、彼は重要な地位を獲得しました。

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

1967 年、すでに正教授だったホフマンは、MIT を辞めてカリフォルニア大学サンタクルーズ校 (UCSC) に入学することを選択し、この期間中、コンピューター サイエンス学部の設立を主導し、学術コースの開発に参加し、その後のコンピューターサイエンス学科の発展の基礎を築き、重要な基盤を築きました。

数学はハフマンの生涯にわたる追求の 1 つであると言え、後に彼が芸術に携わる際には数学なしではいられないほどでした。

写真

1970 年代初め、ハフマンは折り紙に興味を持ち、数学と折り紙芸術を同時に学び、数百枚の曲線折り紙を作りました。作品を制作し、特に曲線折り紙の数学的性質を分析した論文を発表し、折り紙の数学分野の先駆者となりました。

振り返ってみると、ハフマンは生涯を通じて数々の栄誉と賞賛を獲得してきましたが、彼の発明については特許を申請したことがありません。

最後に、ハフマン自身の一節を拝借させてください。

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

以上が彼は 70 年前の試験を避けたかったが、インターネット全体に影響を与えたの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。