Er wollte vor 70 Jahren der Prüfung entgehen, doch er beeinflusste das gesamte Internet

Wer hätte gedacht, dass der „Willen“ eines Studenten, eine Prüfung nicht ablegen zu wollen, später Auswirkungen auf das gesamte Internet haben würde.

In einem Informationstheoriekurs am MIT vor 70 Jahren stellte ein Lehrer eine Multiple-Choice-Frage, um den Stress der Schüler zu „reduzieren“.

Legen Sie entweder die Abschlussprüfung ab oder schreiben Sie eine Arbeit, um den vorhandenen Algorithmus zu verbessern, ganz nach Ihrer Wahl.

Der Name des Lehrers war Robert Fanno. Was er den Schülern nicht sagte, war, dass es sich bei diesem „existierenden Algorithmus“ genau um die „Shannon-Fanno-Kodierung“ handelte, die er gemeinsam mit „Shannon“, dem Begründer der Informationstheorie, verfasst hatte. Um die Mängel des Algorithmus zu verbessern, hat er selbst viel Zeit in die Forschung investiert. (Das innere Betriebssystem des Lehrers: Das habe ich nicht erwartet.)

Obwohl es ein bisschen schädlich ist, funktioniert dieser Trick wirklich. Diese Gruppe von Studenten musste die Prüfung nicht ablegen, sobald sie „eine Arbeit abgeben“ hörte, und beschloss, sofort eine Arbeit zu schreiben, einschließlich David Huffman.

Sie werden es nicht wissen, wenn Sie sich nicht entscheiden, aber Sie werden schockiert sein, wenn Sie sich entscheiden. Huffman, der gerade erst angefangen hatte, erkannte schnell die Falle, die der Lehrer gegraben hatte – diese Arbeit war zu schwierig zu lösen. Es hat mehrere Monate gedauert, dies zu schreiben, und trotz Schwierigkeiten hat Huffman immer noch nichts bekommen.

Aber das Schicksal ist manchmal sehr seltsam. Gerade als Huffman es schließlich aufgab, „die Prüfung zu schwänzen“ und die Papiernotizen in den Mülleimer werfen wollte, hatte er plötzlich eine Idee! Die Antwort erscheint!

Huffman gab die Forschung an vorhandener Codierung auf und wandte sich neuen Erkundungen zu und entdeckte schließlich eine Methode, die auf der Binärbaumcodierung mit geordneter Frequenz basiert.

Die Effizienz dieser Idee, die er erfolgreich vorschlug, übertraf die Methodik seines Lehrers. Auch in der darauffolgenden Entwicklung veränderte die nach ihm benannte Codierungsmethode -

Huffman-Codierung

- direkt

das Paradigma der Datenkomprimierung. Der damalige Abschlussbericht wurde fast 10.000 Mal zitiert. Ineffiziente traditionelle Codierungsmethode

Im Jahr 1951 dachte Robert Fanno, der am MIT lehrte, über ein schwieriges Problem der Informationstheorie nach:

Wie kann man Binärcode

effizient

verwenden, um Zahlen, Buchstaben oder andere Symbole darzustellen?

Die damals gebräuchlichste und direkteste Methode bestand darin, jedem Zeichen eine eindeutige Binärzahl zuzuordnen. Zum Beispiel kann der Buchstabe A als 01000001 dargestellt werden! Dargestellt als 00100001, entspricht jede achtstellige Zahl einem Zeichen.

Dadurch lässt sich der Code leicht analysieren, die Effizienz ist jedoch äußerst gering.

Es gibt auch eine Optimierungsmethode, ähnlich dem Morsecode. Der gewöhnliche Buchstabe E wird nur durch einen Punkt dargestellt, aber das ungewöhnliche Q erfordert ein längeres und aufwändigeres „————··——“.

Diese Methode führt zu unterschiedlichen Codelängen und die Informationen sind nicht leicht zu verstehen; außerdem müssen bei der Übertragung Lücken zwischen den Zeichen hinzugefügt werden, da sonst unterschiedliche Zeichenkombinationen nicht unterschieden werden können.

Fanno erkannte, dass sich vielleicht die Vorteile dieser beiden Methoden kombinieren ließen – die Darstellung von Zeichen in Binärcodes unterschiedlicher Länge. Um Code-„Überschneidungen“ zu vermeiden, erstellte er außerdem einen Binärbaum.

Bilder

Er hat die Möglichkeit jeder Permutation auf maximale Effizienz getestet und schließlich eine effektive Situation gefunden:

Jede Nachricht ist entsprechend der Häufigkeit in zwei Zweige unterteilt, und so viele wie möglich Lassen Sie die Häufigkeit von Die Verwendung der Buchstaben auf beiden Seiten ist grundsätzlich gleich

.

Bilder

Auf diese Weise befinden sich häufig verwendete Zeichen auf kürzeren, weniger dichten Zweigen. 1948 schlug Shannon, der Vater der Informationstheorie, diese Methode in dem Artikel „Mathematische Theorie der Kommunikation“ vor und veröffentlichte sie bald darauf auch unabhängig in Form eines technischen Berichts. Daher wird diese Methode „Shannon-Fano-Codierung“ genannt.

Aber diese Methode funktioniert nicht immer. Wenn beispielsweise die Wahrscheinlichkeit des Auftretens von Buchstaben {0,35, 0,17, 0,17, 0,16, 0,15} beträgt, kann die ideale Kodierung nicht angegeben werden.

Fano glaubt, dass es eine bessere Komprimierungsstrategie geben muss. Seitdem wurde eine so wichtige Aufgabe in die Hände seiner Schüler gelegt.

Ein Geistesblitz, ein Aufsatz des Jahrhunderts

Wenn überhaupt, besteht die Methode von Professor Fanno darin, einen Charakterbaum von oben bis unten aufzubauen und so viel Symmetrie wie möglich zwischen Zweigpaaren beizubehalten.

Dann untergräbt Huffmans Methode diesen Prozess direkt –

Erstellen Sie einen Binärbaum von unten nach oben

.

Er glaubte, dass in einem gültigen Codeabschnitt, egal was passierte, die

zwei am wenigsten verbreiteten Zeichen die beiden längsten Codes haben sollten

.

Identifizieren Sie also zunächst die beiden am wenigsten verbreiteten Zeichen, kombinieren Sie sie zu einem Zweigpaar und wiederholen Sie dann den Vorgang, um aus den verbleibenden Zeichen und dem soeben erstellten Zeichenpaar (Paar) das am wenigsten verbreitete Zeichen zu finden.

Bild

Nehmen Sie Schulzimmer als Beispiel, wo O viermal und S, C, H, L, R und M jeweils einmal vorkommen.

Fanos Methode besteht darin, dem linken Zweig zunächst O und einen weiteren Buchstaben zuzuweisen, sodass beide Seiten insgesamt fünfmal verwendet werden und der generierte Code insgesamt 27 Bit beträgt.

Bilder

Im Gegensatz dazu geht Huffmans Methode beispielsweise vom ungewöhnlichen r und m aus und kombiniert diese zu einem Buchstabenpaar.

Bilder

Nach der Kombination bestehen die vorhandenen Zeichen (Paare) aus: O (4-mal), RM (2-mal) und den einzelnen Buchstaben S, C, H und L.

Teilen Sie nach Häufigkeit des Auftretens, wiederholen Sie den vorherigen Vorgang – gruppieren Sie die beiden ungewöhnlichen Optionen und aktualisieren Sie dann den Zahlenbaum und das Häufigkeitsdiagramm.

Schließlich wurde aus „Schulzimmer“ 11101111110000110110000101, was 1 Bit weniger ist als Fanos Top-Down-Ansatz.

Bild

Obwohl 1 Bit hier nicht viel ist, ist dies bei einer Erweiterung auf Milliarden Bytes eine große Ersparnis.

Tatsächlich hat sich Huffmans Methode als sehr wirkungsvoll erwiesen. Laut Statistiken von Google Scholar wurde der Artikel in diesem Jahr 9570 Mal zitiert.

Bilder

Die Methode seines Lehrers wurde fast nie wieder angewendet.

Bis heute verwenden fast alle verlustfreien Komprimierungsmethoden ganz oder teilweise die Huffman-Methode, mit der Bilder, Audio, Tabellen usw. komprimiert werden können. Es unterstützt alles vom PNG-Bildstandard bis zur allgegenwärtigen Software PKZip.

Knuth, der Pionier der modernen Informatik und Gewinner des Turing-Preises, beschrieb Huffmans Leistungen einmal so:

In den Bereichen Informatik und Datenkommunikation ist die Huffman-Codierung eine Grundidee, die von Menschen genutzt wird.

Später erinnerte sich Huffman an diesen „Heureka“-Moment. Damals wollte er die Papiernotizen in den Mülleimer werfen, aber plötzlich kamen seine Gedanken zusammen und die Antwort erschien in seinem Kopf:

Das war das Seltsamste Ding in meinem Lebensmoment.

Plötzliche Erleuchtung, wie ein Blitz.

Und erklärte, wenn er gewusst hätte, dass sein Professor Fano mit diesem Problem zu kämpfen hatte, hätte er vielleicht nie versucht, es zu lösen, geschweige denn den Schritt im Alter von 25 Jahren gewagt.

Ein Gefühl von Leistung und Ordnung, Kunst mit Mathematik spielend

Huffman-Codierung veränderte das Datenkomprimierungsparadigma und gewann viele Auszeichnungen und Medaillen.

Zum Beispiel gewann Huffman 1998 den Golden Jubilee Award für technische Innovation der IEEE Information Theory Society und 1999 die Richard-Hamming-Medaille des Institute of Electrical and Electronics Engineers (IEEE).

Dennoch war er im Laufe seines Lebens im Vergleich zur Erfindung des verlustfreien Kompressionsverfahrens am stolzesten auf diese Doktorarbeit.

Titel: Die Synthese sequentieller Schaltkreise.

Bild

Während Huffman am MIT promovierte, veröffentlichte er diesen wichtigen Artikel über sequentielle Schaltkreise. Zu dieser Zeit war Huffman fast der erste Gelehrte, der erklärte, wie man einen asynchronen sequentiellen Schaltkreis entwirft. Diese Theorie lieferte später wichtige logische Unterstützung für die Entwicklung von Computern. Die Veröffentlichung dieses Papiers verhalf ihm nicht nur zum Erhalt der Louis E. Levy-Medaille des Franklin Institute, sondern ermöglichte ihm natürlich auch die Qualifikation, in der Schule zu bleiben und Kurse über Schaltkreise zu unterrichten.

BilderWährend seiner Schulzeit schlug Huffman auch eine innovative mathematische Formel vor, die eine

binäre Zahlenfolge in eine andere binäre Zahlenfolge umwandeln kann, ohne dass dabei Informationen verloren gehen. Diese Forschung spielte damals eine wichtige Rolle und brachte ihm ein eine wichtige Position.

William O. Baker, damals Vizepräsident für Forschung bei Bell Labs, rekrutierte ihn für einen Prüfungsausschuss, der hauptsächlich für die Prüfung zukünftiger Technologiepläne für die National Security Agency verantwortlich war. Dr. Baker fungierte als wissenschaftlicher Berater für fünf Präsidenten: Eisenhower, Kennedy, Johnson, Nixon und Reagan.

Hoffman, der bereits 1967 ordentlicher Professor war, entschied sich, das MIT zu verlassen und an die University of California, Santa Cruz (UCSC) zu gehen. Während dieser Zeit leitete er den Aufbau der Fakultät für Informatik und beteiligte sich an der Entwicklung akademischer Lehrpläne Damit wurde ein wichtiger Grundstein für die weitere Entwicklung des Fachbereichs Informatik gelegt.

Man kann sagen, dass Mathematik eine von Huffmans lebenslangen Beschäftigungen war, und zwar so sehr, dass er, als er sich später mit der Kunst beschäftigte, nicht ohne Mathematik auskommen konnte.

Bilder

Ab den 1970er Jahren interessierte sich Huffman sehr für Origami. Er studierte gleichzeitig Mathematik und Origami-Kunst, fertigte Hunderte von gebogenen Origami-Werken an und veröffentlichte Arbeiten , in denen er die mathematischen Eigenschaften von gebogenem Origami analysierte. , werden Sie ein Pionier auf dem Gebiet der Origami-Mathematik.

Rückblickend hat Huffman im Laufe seines Lebens zahlreiche Ehrungen und Auszeichnungen erhalten, aber er hat für keine seiner Erfindungen ein Patent angemeldet.

Lassen Sie mich abschließend noch ein Zitat von Huffman selbst ausleihen.

Als Wissenschaftlerin und Lehrerin bin ich wirklich hartnäckig. Wenn ich das Gefühl habe, für ein Problem nicht die einfachste Lösung gefunden zu haben, werde ich extrem unzufrieden, und diese Unzufriedenheit wird so lange anhalten, bis ich die beste Lösung gefunden habe. Für mich ist das die Essenz des Wissenschaftlerdaseins.

Das obige ist der detaillierte Inhalt vonEr wollte vor 70 Jahren der Prüfung entgehen, doch er beeinflusste das gesamte Internet. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!