Institut for Matematik og Datalogi Odense Universitet April 29, 1996

JFB

DM11 – F96 – Lecture 12

Lecture, April 24

We covered up through page 389 in chapter 6. We also covered the subsection of section 2.6 dealing with zero-one matrices.

Lecture, May 1

We will finish chapter 6, skipping topological sort, which is covered in DM02. We will also cover Huffman codes. (See the notes for this below.)

Lecture, May 8

We will begin on some algebra. (There will be notes for this.)

Announcement

Both discussion sections will meet in U47 on Thursday, May 2. They will not meet in U10 or U13 as they usually do.

Problems to be discussed in week 19

• 28, and 32 from section 6.4.

• 3, 6, 15, 26, 32, 41, and 42 from section 6.5.

• 20, 24, 27, 33, 38, and 39 from section 6.6.

Notes on Huffman encoding

Representing text files in the most straightforward manner, using the ASCII representation of each character, wastes a considerable amount of space. Part of this is wasted simply because this ASCII representation uses 8 bits for every character.

In fact most text files would use no more than 64 different characters, so 6 bits per character would be sufficient. However, even more space is wasted because there is so much redundancy in all natural languages.

Notice that in English text (or in Danish text) some letters occur much more frequently than others. For example, in the previous paragraph, the letter “e” occurred 48 times, while the letters “j” and “z” did not occur at all. Representing the characters with variable length bit strings could save considerable space if the most frequently occurring characters had the shortest representations and the least frequently occurring characters the longest. Even more space can be saved by considering pairs of letters. In English, the pair th occurs most frequently, but the pairs tb and qp essentially do not occur. In fact, by using this idea and other methods, it is possible to represent English text using just over 1.5 bits per character on average.

One technique for using variable-length representations for different characters, depending on the frequency of their occurrence, is called Huffman encoding. Huffman codes are an example of the prefix codes described in section 8.2 of the textbook by Rosen. These prefix codes are more often called prefix-free. The idea is that no code representing a character is a prefix of another code. (A prefix of a string is a substring consisting of the first k consecutive characters, for some k.) For example, the bit strings “0110” and “011010” could not both be codes in a prefix-free encoding, because the first is a prefix of the second. The advantage to a prefix-free encoding is that decoding is so easy. There is never any doubt, when decoding a long string of zeros and ones, as to when one has reached the end of the code for one character or where the code for the next character begins. For example, if an encoding for the 5-letter alphabet {a, b, c, d, e} is given by the function f, and f(a) = 01, f(b) = 0010, f(c) = 0011, f(d) = 10, f(e) = 11, then the string 010011111000110111 can be decoded as acedcae, making just one pass through the string.

To do Huffman encoding, one builds a binary tree. Assume that there are k possible characters, and that the probability of character c_{i} is p_{i} (meaning more precisely that one expects a fraction p_{i} of the characters in the text to be c_{i}). Then, any of the k characters must occur with some positive probability, so 0 < p_{i} ≤ 1 for all i, and ∑_{i=1}^{k} p_{i} = 1. There will be one leaf in the binary tree for each character, and when that leaf node is created, a pointer to it is created so that during the encoding process, the node for any character can be accessed in constant time. There will also be a pointer to the root of the tree, plus parent, left and right child pointers for every node. Each node in the tree will contain a key which is a probability. The keys in the leaves will the probabilities of the associated characters, and the leaves will also contain the characters associated with them (or pointers to these characters).

Initially, all of the nodes for the leaves are viewed as individual trees, with root probability equal to the probability of the associated character. At any point in time the roots of all the existing trees are sorted according to their probabilities. One step consists of choosing the two roots with the smallest probabilities, p_{i} and p_{j}. These two trees are made the left and right subtrees of a new root which is given probability p_{i} +p_{j}. This decreases the number of existing trees by one. This step is repeated until there is only one tree. Then, the pointer to the root of that tree is created (and will be used for decoding).

Notice that the binary tree created by this process will have relatively short paths from the root to the leaves associated with frequently occurring characters, and longer paths from the root to the leaves associated with less frequently occurring characters. The path from the root to a leaf will define the encoding of the character at that leaf as follows. An edge on this path going to a left child will be a zero, and an edge going to a right child will be a one. Consider the following example:

A B C D E F G H I J
.17 .11 .04 .10 .31 .03 .02 .05 .16 .01
1.0 [figure] .62 [figure] .31 [figure] .15 [figure] .06 [figure] .03 [figure] .01 [figure]J [figure] [figure].02 [figure]G [figure] [figure].03 [figure]F [figure] [figure] .09 [figure] .04 [figure]C[figure] [figure].05 [figure]H [figure] [figure].16 [figure]I [figure] [figure].31 [figure]E [figure] [figure] .38 [figure] .17 [figure]A[figure] [figure].21 [figure] .10 [figure]D[figure] [figure].11 [figure]B

The encoding of the different characters is as follows:

A B  C  D E  F  G  H  I  J
10 111 00010 110 01 00001 000001 00011 001 000000

The fact that the codes are paths in the tree ensures that no code is a prefix of another. For one code to be a prefix of another, one leaf would have to be on the path from the root to another leaf. But that is impossible for two distinct leaves; the first one would not have been a leaf if it was on the path to the other.

In practice, the probabilities can either

1. be calculated from the known probabilities of the characters in text from the given language, in which case the Huffman tree can be a fixed tree shared by many users for many files, or

2. be calculated from the number of occurrences of the different characters in the file being compressed, in which case the Huffman tree would be included at the beginning of the compressed file.