Slashdot Mirror
David Huffman is Dead
etphone writes "One of the Gods of information theory, David Huffman, has passed on:
here's the official the press release. Damn, he was a good professor too..."
← Back to Stories (view on slashdot.org)
← Back to Stories (view on slashdot.org)
I was lucky enough to have a class from Huffman and hear the story from him personally.
A few more details...
Nobody in the class but Huffman chose the term paper because they new it was a trap. The professors assigned Huffman a problem that many people believed was unproveable, though it could not be proved unproveable. It was a problem that they had worked on very hard and not been able to solve.
The assignment was to find a way to generate minimum spanning trees, given an arbitrary set of bytes. Now, humans could do this with brute force and then checking their results to test if the spanning tree was actually the minimum spanning tree, but it wasn't a very scientific process.
As the due date for the term paper came, Huffman still couldn't figure it out. He gave up, decided to bite the bullet and try his luck at the test he hadn't studied for. He told his wife to throw his papers away. She did, and as he was leaving he looked in the trash and saw his notes and drawings of minimum spanning trees **upside down**... and the rest is the history.
I heard somewhere that he got his Masters and PhD at the same time because of this, but I'm not sure about that one.
I had the priveledge of taking cmp80D, "Introduction to Cybernetics" (no, not Dianetics, Cybernetics) directly from Huffman at UCSC.
;o)
;O)
First of all, every class he ever tought was at 8:00am in the morning. For a Santa Cruzian, that's the equivalent of 4:00am since we normally don't wake up till 12
For the first two weeks of class, he was an absolute teddy bear. That was good, since the class was open to all majors (Modern Feminism and History of Conciousness included). Two weeks into the class, someone fell asleep in the front row. He wasn't a teddy bear anymore. From that point on, the entire class was in fear for their life whenever he turned around quickly.
The class was very hard. Homework was due every single class and there was a quiz almost every single class. Every class introduced brand new material. Miss a single class and you're totally screwed. Of course, after that class, most other CS theory courses were review
The class wasn't easy, but man could he teach.
ms
Who is David Huffman..? Good god man, read the article.
From it:
Huffman is probably best known for the development of the Huffman Coding Procedure, the result of a term paper he wrote while a graduate student at the Massachusetts Institute of Technology (MIT). "Huffman Codes" are used in nearly every application that involves the compression and transmission of digital data, such as fax machines, modems, computer networks, and high-definition television.
------
If a tree falls on an anonymous coward yelling 'first post' in the forest, does anybody hear?
You're thinking of Phil Katz, although he himself stood on the shoulders of giants.
Huffman code goes back to the 50s or 60s. Put very simply it's a way of representing information where the length of the code is short for more frequently occuring elements, and long for infrequently occuring elements.
Nobody uses Huffman compression alone these days, but it is still very popular as a back end after a dictionary compressor. Such an approach is used by Zip's deflation, LZH (where the "H" is you-know-who), etc.
---
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
I remember reading about Huffman encoding back in high school and it is probably largely responsible for me moving on from "computers as a game thingie" to "computers as something to program". The following is my recollection of how this term paper came about - although the details may be a little wrong, since the articles where I've read it are in boxes in the garage and I can't be bothered going down to hunt them out at the moment. :-)
:-)
Anyway, just thought I'd share my memories about them man.
Huffman and a few others were taking a graduate course from a professor who gave them a choice about how to be assessed. Either they could sit an end-of-term exam (there may have been some assignments involved throughout the semester as well), or they could write a term paper. Each student could make their own choice.
Most of the class members chose the end-of-term exam, but Huffman (he admitted later) was a slightly lazy student and so decided on the term paper, thinking he could knock it off in a couple of weeks and get an easy credit. Unfortunately (for him, luckily for computer science) he kept putting off the work and suddenly realised he was running out of time to write the paper and couldn't even think of a topic. To make matters worse, he had missed (or not concentrated in) so many of the lectures that the option of renegging and doing the exam was no longer really open to him.
In desperation, he asked the professor for a suggested topic. The professor (I wish I knew his name - he deserves a place in history as well!) posed a problem about compressing data. Huffman struggled with the topic for quite a while but eventually (quite close to the deadline, IIRC) came across a very elegant solution that worked beautifully. He was even able to prove that his solution was optimal, in the sense that no better byte-by-byte compression method was possible (this doesn't include things like LZW, etc, which use run-length compression techniques).
The rest, as they say, is history. As an aside, Huffman passed the course with top marks, since the professor had neglected to inform Huffman that he (the professor) and a colleague had already put extensive work into the problem and failed to solve it satisfactorily.
Just goes to show, sometimes the best work *is* done under pressure.
(OK, let the error-pointer-outers go to work. Where did I mess up?)
of Dr. Huffman doing what he loved can be found here.
/.
Dr. Huffman was another modest genius whose work doesn't fit in the hoary pigeonholes of Nobel candidates but is as ubiquitous as the DSP. It's no surprise he seems anonymous; these are the sort of stories that make me so often grateful for
Thanks David.
It's sad that more people don't know how much David Huffman shaped today's world. Here's a prime example of someone that will pass on, and no one will notice... they're too busy using the machines that he helped create.
It does make you wounder, who will be the "heros" of tomorrow?
B. Johannessen
Acts@core.mailboks.com Acrux@core.mailboks.com Adam@core.mailboks.com Adar@core.mailboks.com Ada@core.mailboks.com
I'm skeptical about the "proof" part of the story, since Huffman coding is really just a quick-n-dirty (but much easier to implement) approximation of arithmetic coding. Arithmetic coding will match or beat Huffman every single time, if compression ratio is all you care about. I'm not saying Huffman coding isn't extremely cool, but it's certainly not optimal. It sure is elegant, though.
---
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
If, say, your father had died, would you let some hack reporter write his obituary if you could do it yourself?
Eagles may soar, but weasels don't get sucked into jet engines.
In the geek/male world I think one of the highest complements to a person is to have their work talked about, criticized, etc.
For me it's the same as erecting a monument.
At least these comments weren't about PKzip 8(.
The above description is how I remember him telling us how he came across the solution. I was lucky that the teacher for our data compression class was out the first week of school. Prof. Huffman subbed and taught us about Huffman codes (imagine that). It is amazing how simple of a concept it is. He was a very intelligent guy and a very demanding teacher. I also had him for the undergraduate signal analysis class (about a 90% failure rate as I recall). I only lasted 4 weeks. That was the hardest class I have ever taken. You had to know calculus very good to have a chance to keep up with the rest of the material (and I hadn't taken calculus in over a year). People will probably start passing that class now but I dought they will learn as much. I knew people who took it knowing they would fail. But they knew they would learn more than in most other classes anyway. He will be missed.
And yeah, DH has the advantage where the tree starts out with all leaves being at the lowest level (basically being binary code, heh)... I guess a priority heap would be a good implementation to use, yeah... I just figured one would rebuild the tree after each character. It doesn't take *that* long. :) (Of course, for a large file that'd be real painful.) By removing the initial tree, however, you do lose the implicit encryption in the general case, but there's no reason you couldn't have a different starting tree, and then you could also use trees tuned for different applications and get a bit more compression anyway. Even with non-optimized initial trees (i.e. all characters at the bottom), you have about 8.578E506 initial trees to choose from, though admittedly that would start out with just your basic one-to-one replacement thing, and if anyone wanted to crack the code it'd be easy to just assume the trivial, ordered tree, decompress to trivially-compressed plaintext, and then work out the substitutions later. Ohwell.
---
"'Is not a quine' is not a quine" is a quine.
"'Is not a quine' is not a quine" is a quine.
Quine "quine?
Joe
and an article with a good exposition. Bricolage . . . fine word for this eulogy.
I know a bit about Huffman encoding. :)
Is it appropriate (or has this been done) to combine Huffman and run length encoding?
Like reserve a huffman symbol for specifying that "the next symbol" will repeat for a specified amount of time. You'd prolly reuse all the symbols that you've already generated for all 256 bytes to specify the length of the "run".
So if you encounter the RLE symbol (say "11") you'd know the next symbol after that specifies run length, and the one after that is the symbol that is running that length. It would be pretty efficient especially if the document didn't have too many characters that repeated over 256 times. Maybe a header to specify how many symbols represent a length for files that repeat too much (might be overkill)..
Am I stating the obvious? Cause I really think it would be pretty cool
Huffman encoding is darn elegant.
First, definitions:
A character code is a code in which each symbol of input is translated to one symbol of output. (Compression is achieved in character codes by using variable length codes. Short code symbols are used for frequently occuring inputs.)
A prefix code is a code in which no symbol is a prefix of another symbol. For example, if you have "10" as a symbol, then you can't have "101" as a symbol in a prefix code. Prefix codes are nice because they greatly simplify encoding and decoding.
It is possible to prove that the optimal data compression achievable by a character code can always be achieved with a prefix code. Furthermore, it is possible to represent codes as a binary tree, in which a symbol "1" represents the left branch, and "0" the right branch. So "101" would be left, right, left.
It is easy to prove that an optimal code for any particular file is represented by a full binary tree, i.e. one in which each node has two leaves. (This is the first exercise of the chapter).
Now, Huffman coding is a greedy algorithm that constructs an optimal prefix code. The algorithm builds the tree T corresonding to the optimal code in a bottom-up manner.
Pseudocode:
Assume C is a set of n characters, and each c in C is an object with a frequency f(c). A priority queue Q, keyed on f, is used to identify the two least-frequent objects to merge together. The result of the merger of two objects is a new object whose frequency is the sum of the frequencies of the two objects that were merged:
And that's it!
To prove this is correct, prove that the problem of determining an optimal prefix code: (a) exhibits the greedy-choice property, and (b) exhibits the optimal substructure property
From these two lemmas, the theorem
"Huffman coding produces es an optimal prefix code" is trivial to prove. The corollary is that Huffman encoding produces an optimal character code.
Torrey Hoffman (Azog)
Torrey Hoffman (Azog)
"HTML needs a rant tag" - Alan Cox
Well, I think I'd take exception to the statement that "it was clear he hated having to teach us". After all, the guy was teaching well into his 70's, and I don't think he had to. I asked him once whether he was employed as a researcher, and had to do teaching as well, and he said, "No, I'm employed to teach".
:), but I think he honestly did enjoy it when he saw his students begin to "get it." I know many didn't like his methods, but I enjoyed how he did NOT teach directly from a book, and instead, prepared class notes and assignments for each lecture; clearly he wasn't just phoning it in.
I do believe he was generally a bit annoyed by the many students who were unprepared to take his classes (in his mind). He was demanding, to be sure (I generally spent ~ 15 hours each week on his homework alone; but I was woefully unprepared
BTW. I'm class of '93; when were you there?
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
Well, I was fortunate enough to learn David Huffman's compression coding technique from the man himself. While at UC Santa Cruz, I took every course that he taught, and I think I learned more in those 4 classes than nearly all my other technical courses combined. Professor Huffman really was a genius, and taught me some amazing things about insight into a problem. I had no idea he was ill, and had been planning to talk to him about a few things (such as publishing his class notes and lectures; his problem sets were EXCELLENT teaching tools). He also wrote a recommendation for me to get into graduate school, and I never properly thanked him for it, which I deeply regret.
In any case, the story above seems mostly accurate; Huffman's teacher was in fact Richard Fano, who along with Claude Shannon, was one of the early architects of "information theory". Every aspect of our modern life, from our use of CD players, to wireless phones (to name but a few) came as a result of these ideas. In fact, Shannon-Fano compression coding is a related form that was developed before Hufmann's technique. However, since Shannon and Fano knew it wasn't "optimal" (a much abused word), and spent much time trying to come up with an optimal algorithm, they thought it was impossible. So, by giving the assignment to Huffman as a project, he hoped to show him how such as easy sounding question was in fact quite difficult (or impossible).
Well, Professor Huffman was brilliant at boiling problems down to their most basic nature, but after about a week of thinking about it on and off, he realized that he probably wouldn't be able to figure it out, and that it was a much harder problem than it at first seemed. So he crumbled up all his notes and began to prepare for the final, but as he tossed his notes into the garbage can, he says he had a moment of clarity, and suddenly realized the process was actually quite simple.
So when the time came to present his "project", Professor Fano called on David to discuss his method of producing minimum redundancy codes, assuming of course that David would have come up with a non-optimal method, or have to admit that it seemed very hard or impossible. Instead, Huffman went to the chalkboard and gave a quick explanation of how to produce what we now call "Huffman codes", then sat down. Fano apparently slapped his forehead in amazement and said (in French) something like, "It CAN'T be that easy!". But it was, and Huffman, never having been told that this problem was "impossible", dutifully solved it.
Huffman's achievements go well beyond his coding technique, and are well worth looking up (among other things, he produced some novelty papers about optical illusions that have become very useful in machine vision circles). I can tell you, as a former student, that he was both loved and loathed, but as someone who was willing to put in the work, his classes were incredibly enlightening.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
I really feel as though the nerd comunity (I prefer to think of us as geeks) is losing our role models quickly these days.
I just want to say that we all need to spend time studying the likes of Huffman, Greenspun, and Minsky, Mandelbrot, so that good ideas can stay alive.
Thanks.
David