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..."

Comments

About that little "term paper" he wrote

[MalcolmT]

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?)

A former student's thoughts...

[ChadN]

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.