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

An Explanation of Huffman Coding

[Azog]

Since several people have posted on "optimality", without knowing exactly how Huffman coding works and how it is optimal, I thought I'd post an explanation. This is based on the chapter in "Introduction to Algorithms" by Corman, Leiserson, and Rivest. (An excellent undergrad textbook.)

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:

HUFFMAN(C)
n = size of C
Q = C
for i = 1 to (n - 1)
{

z = new node()
x = z.left = Q.ExtractMin()
y = z.right = Q.ExtractMin()
f(z) = f(x) + f(y)
Q.Insert(z)

}
return Q.ExtractMin()

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)

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.