Exercise 9.12.An alternative algorithm for constructing prefix codes was proposed by Claude Shannon and Robert Fano. The resulting Shannon-Fano codes tend to perform worse than Huffman codes but are easier to construct. Here is how the algorithm proceeds, given a set of symbols and their frequencies:
1. Sort the symbols by frequency.
2. Split the sorted list into two parts, so that each part accounts for approximately half of the total number of characters. (In other words, the sum of frequencies in both parts should be approximately equal.)
3. Recursively split the left and right half in the same manner until there just one symbol remains in each part.
The result of this subdivision process can be visualized as a binary tree with exactly one symbol in each of its leaves. The prefix code constructed from this tree is a Shannon-Fano code.
Construct the Shannon-Fano code for the word “ABRACADABRA”. How does the code compare to the Huffman code constructed in Section 9.3?
Bit Streams
Exercise 9.13.Most operating systems and programming languages treat files and network connections as long streams of bytes. This is a
reasonable compromise, but poses problems when the data being read or written doesn’t neatly fit into 8-bit packets. In this exercise we will implement two classes BitOutputStream and BitInputStream that lets use
write and read data in groups of bits instead of bytes. Both classes are built on top of regular byte-based streams.
BitOutputStream generates a bit sequence and provides a writeBits() method that appends a certain number of bits to the output. For instance, if out points to an instance of BitOutputStream, the
following code writes a total of 16 bits to the output, producing the bit sequence 1001100100000001:
BitInputStream consumes a bit sequence and provides a readBits() method that reads and returns the next few bits from its input. For example, the following sequence of calls divides the bit stream generated above into its
original parts:
a) Assume you read from a BitInputStream that contains the bit sequence 1001100100000001, as in the previous example. What should the following sequence of calls return?
BitOutputStream and BitInputStream provide the illusion of writing to or reading from a long sequence of bits, but internally both classes are wrappers around the standard byte-based input and output streams provided by Java.
Let’s start with BitOutputStream, which is defined as follows:
public class BitOutputStream {
public BitOutputStream(OutputStream output);
public void writeBits(long bits, int n);
public void writeBit(long bit);
public void flush();
}
The constructor takes the byte-based OutputStream to which all data is eventually written. The other methods behave as follows:
• As discussed, writeBits() outputs the least significant n bits of bits.
• The second method writeBit() is provided for convenience and outputs the least significant bit of bit; it is equivalent to
writeBits(bit, 1).
• The last method flush() writes all pending bits to the output. If the length of the bit sequence as a whole is not a multiple of 8, flush() adds as many zero bits as necessary to fill the last byte.
Consecutive calls to writeBits() must assemble the bit sequence and split it into bytes, which can then be written to the wrapped OutputStream. One option is to store incoming bits in a small buffer and emit the next byte
whenever this buffer contains 8 or more bits. We can represent such a buffer using two integers, one that stores the bits itself and another that tracks its size:
private long buffer = 0;
private int bufferSize = 0;
The 64-bit integer buffer holds up to 64 bits before they are written to the file, and bufferSize is the number of bits in buffer that haven’t been written to the output yet.
b) Implement a class BitOutputStream that has three methods writeBit(), writeBits() and flush() as described above.
Note: To simplify or speed up your implementation, you may limit the maximum number of bits that writeBits() can write at once to a number less than 64 bits.
c) The BitInputStream class wraps a byte-based InputStream and treats it as a long stream of bits that can be read from:
public class BitInputStream {
public BitInputStream(InputStream input);
public long readBits(int n);
public long readBit();
}
The readBits() method in BitInputStream reads the next \(n\) bits from the file and stores them in the least significant bits of the return value.
Implement BitInputStream.
Unicode and the UTF-8 Encoding
Exercise 9.14.The Unicode standard is an extension of the ASCII we saw in Fig. 9.2 and defines numeric codes for over 130 000 characters and symbols that
are used in most of the world’s writing systems. Among other things, it supports accented Latin characters, Greek and Cyrillic letters, the ideograms used in Chinese, Japanese, and Korean writing systems, mathematical symbols, historic scripts such as Egyptian hieroglyphs, and — perhaps most
importantly — emojis.
The numeric codes defined by Unicode are also referred to as code points. Since Unicode is a superset of ASCII, the code points between 0 and 127 coincide with the characters shown in Fig. 9.2. A few additional code points are
shown in the following table:
.
Symbol
Code point
Name
0x3D5
GREEK PHI SYMBOL
0x308B
HIRAGANA LETTER RU
0x13080
EGYPTIAN HIEROGLYPH D010
0x1F602
FACE WITH TEARS OF JOY
a) A popular emoticon for expressing anger or outrage is the table-flip emoticon which depicts a person flipping over a table. There are many variations, including the following angry table-flip
emoticon:
This emoticon consists of nine Unicode symbols with code points 0x30ce 0xca0 0x76ca 0xca0 0x30ce 0x5f61 0x253b 0x2501 0x253b. To familiarize yourself with the Unicode standard, look up the definitions of these symbols. Which languages or scripts do they come from?
Unicode text is often encoded in a format called UTF-8, which is backwards compatible with the common 8-bit encoding used for ASCII. In contrast to ASCII, however, UTF-8 is a variable-length code that represents all possible code
points as a sequence of one to four bytes. To achieve this, UTF-8 partitions the possible code points into four ranges, with each range using a certain number of bytes:
.
0x0000 to 0x007F
1 byte
0x0080 to 0x07FF
2 bytes
0x0800 to 0xFFFF
3 bytes
0x10000 to 0x10FFFF
4 bytes
The details of the encoding are shown in Fig. 9.4. Each row shows the bit patterns that represent a certain range of code points. The most significant bits of each byte are fixed, whereas the lower bits marked with a period (“.”) are
filled with the binary digits of the code point, from right to left. For example, the symbol “\(\phi \)” has the code point 0x3D5 and therefore falls into the second range. Since the binary representation of 0x3D5 is \(1111010101_2\), the UTF-8 encoding of \(\phi \) consists of the two bytes
11001111 and 10010101.
.
Code points
Byte 1
Byte 2
Byte 3
Byte 4
0x0000 to 0x007F
0.......
–
–
–
0x0080 to 0x07FF
110.....
10......
–
–
0x0800 to 0xFFFF
1110....
10......
10......
–
0x10000 to 0x10FFFF
11110...
10......
10......
10......
Figure 9.4 UTF-8 encodes code points using a variable number of bytes. The byte sequence is obtained by replacing the periods (“.”) with the binary representation of the code point.
b) Consider the “FACE WITH TEARS OF JOY” emoji with code point 0x1F602. What is the length of the UTF-8 encoding of this symbol? What is the resulting byte sequence?
c) Is UTF-8 a prefix code? Explain.
d) Implement a function that translates Unicode codepoints into their UTF-8 encoding. Use this function to compute the UTF-8 encoding of the table-flip emoticon discussed in part (a) of this exercise.
Binary Coded Decimals
Exercise 9.15.Suppose you are given a long string of decimal digits, say the first 10 million digits of \(\pi \). How do you store these digits
efficiently as a sequence of bits? Storing each digit as a full byte is clearly wasteful because it leaves 246 of the 256 possible bit patterns unused. A better solution is to use four bits to store each digit:
.
symbol
\(0\)
\(1\)
\(2\)
…
\(9\)
codeword
0000
0001
0010
…
1001
We can therefore fit two decimal digits into a single byte. Decimal numbers encoded in this way are are known as binary-coded decimals (BCD).
a) Implement two functions for reading and writing binary coded decimals, for example using the following two function signatures:
static void writeBCD(int[] digits, int n, OutputStream out)
throws IOException;
static void readBCD(InputStream in, int n, int[] result)
throws IOException;
The first method encodes n decimal digits that are stored as ordinary integers in digits as BCDs and writes them to out. The second method reads n BCDs from in and stores them as integers in result. How do you handle an odd number of decimal digits?
The 4-bit encoding of BCDs still wastes 6 of the 16 possible bit patterns. One way to encode decimal digits even more efficiently is to use a variable-length codevariable-length codes.
b) Assume that every decimal digit occurs equally often and design the corresponding Huffman code. How many bits per digit does the resulting code require?
Another way to store decimal digits more efficiently is to encode groups of digits. For example, if we group the digits into pairs, there are 100 different pairs, from \(00\) to \(99\), and each of those 100 values can be encoded using 7 bits per pair, which gives us 3.5 bits
per digit. Encoding decimal digits in triplets works even better: The 1000 different combinations of three digits can be encoded using 10 bits, so each digit requires only \(3.33\) bits. A group of three decimal digits is also called a declet.
c) Implement a function
void writeDeclets(int[] digits, int n, BitOutputStream out);
that encodes an array of decimal digits as declets. If the total number of digits is not a multiple of 3, devise a special encoding for the last one or two digits.
