a)It’s easy to see that the algorithm performs exactly the same steps in both cases. For a single Match token, the inner for loop is executed once and copies \(l\) bytes before incrementing \(p\) by \(l\):
\(\seteqnumber{0}{C.}{7}\)
\begin{align*}
\Id {output}[p+0] &= \Id {output}[p-\Id {offset}+0]\\ \Id {output}[p+1] &= \Id {output}[p-\Id {offset}+1]\\ &\dots \\ \Id {output}[p+l-1] &= \Id {output}[p-\Id {offset}+l-1]\\ p &= p + l
\end{align*}
For multiple Match tokens, the inner for loop is executed multiple times, each time copying a single byte and incrementing \(p\) by 1:
\(\seteqnumber{0}{C.}{7}\)
\begin{align*}
\Id {output}[p+0] &= \Id {output}[p-\Id {offset}+0]\\ p &= p + 1\\ \Id {output}[p+0] &= \Id {output}[p-\Id {offset}+0]\\ p &= p + 1\\ &\dots \\ \Id {output}[p+0] &= \Id {output}[p-\Id {offset}+0]\\ p &= p + 1
\end{align*}
b)The token represents multiple repetition of the previous offset bytes. For instance, the Match token in the sequence
Byte(A), Byte(B), Match(offset=2, length=5)
produces \(2.5\) additional copies of “AB”, which results in the final string “ABABABA”.
Solution to Exercise 10.2
Listing C.92 shows direct translation of LZ77-Compress and LZ77-Decompress. During decompression, we use the instanceof operator to determine the type of each token.
Listing C.92ch10β―/β―SimpleLZ77
static List<SimpleToken> compress(byte[] input, int maxOffset,
int minLength, int maxLength) {
var tokens = new ArrayList<SimpleToken>();
for (int k = 0; k < input.length; ) {
int bestLength = 0, bestOffset = 0;
for (int off = 1; off <= Math.min(k, maxOffset); off++) {
int len = 0;
while (len < Math.min(maxLength, input.length - k)
&& input[k - off + len] == input[k + len]) {
len++;
}
if (len > bestLength) {
bestLength = len;
bestOffset = off;
}
}
if (bestLength >= minLength) {
tokens.add(new SimpleToken.Match(bestOffset, bestLength));
k += bestLength;
} else {
tokens.add(new SimpleToken.Byte(input[k]));
k++;
}
}
return tokens;
}
static int decompress(List<SimpleToken> tokens, byte[] output) {
int k = 0;
for (SimpleToken token : tokens) {
if (token instanceof SimpleToken.Byte b) {
output[k++] = b.value();
} else if (token instanceof SimpleToken.Match m) {
for (int i = 0; i < m.length(); i++)
output[k + i] = output[k - m.offset() + i];
k += m.length();
}
}
return k;
}
See Table C.2 for a table of integers encoded using the Elias gamma code. The advantages of the code are that small integers are encoded very efficiently and that it can handle numbers of arbitrary size. Its main disadvantage is that large
integers are encoded using many bits.
Table C.2
Encoding of integers using the Elias gamma code
.
\(n\)
\(n\) in binary
\(\bitlen (n)-1\)
codeword
\(1\)
\(1_2\)
\(0\)
1
\(2\)
\(10_2\)
\(1\)
01 0
\(3\)
\(11_2\)
\(1\)
01 1
\(4\)
\(100_2\)
\(2\)
001 00
\(5\)
\(101_2\)
\(2\)
001 01
\(6\)
\(110_2\)
\(2\)
001 10
\(7\)
\(111_2\)
\(2\)
001 11
\(8\)
\(1000_2\)
\(3\)
0001 000
\(\vdots \)
\(\vdots \)
\(\vdots \)
\(\vdots \)
\(3410\)
\(110101010010_2\)
11
000000000001 10101010010
\(\vdots \)
\(\vdots \)
\(\vdots \)
\(\vdots \)
Solution to Exercise 10.4
Listing C.93 shows the outline of class LZHDecoder. The main constructor takes two arguments: the input data, which is a bit stream produced by LZHEncoder, and the output stream to
which the uncompressed sequence of bytes will be written. As with other Lempel-Ziv decoders, we store a certain number of previously decoded bytes in a cyclic bufferdictionary. The outLength field holds the
number of bytes that have been decoded so far. We start the decompression process in decompress() by reading the two parameters of the algorithm from the stream: maxOffset is the largest offset field that can occur and blockSize the number of tokens per block. We then initialize dictionary to a cyclic buffer of size maxOffset and read all
blocks until we reach the end of the input.
Listing C.93ch10β―/β―LZHDecoder
public class LZHDecoder {
private final BitInputStream input;
private final OutputStream out;
private CyclicBuffer dictionary; // current dictionary region
private int outLength = 0; // number of bytes decoded so far
public LZHDecoder(BitInputStream in, OutputStream out) {
this.input = in;
this.out = out;
}
public void decompress() throws IOException {
int maxOffset = (int) input.readBits(32);
int blockSize = (int) input.readBits(32);
dictionary = new CyclicBuffer(maxOffset);
while (decodeBlock(blockSize)) {
}
}
// ...
}
For each block, we first recover the two Huffman codes for tags and offsets and then decode one tag after the other until the entire block has been recovered (Listing C.94). If the tag is \(256\), we have reached the end of the input. If it
is less than \(256\), it represents a BYTE token that we write directly to the output; the write() method writes a single byte to the output stream and to dictionary. Every other tag represents a MATCH token, which we decode by recovering the offset and length fields and copying the requisite number of bytes from dictionary.
Listing C.94ch10β―/β―LZHDecoder
private boolean decodeBlock(int blockSize) throws IOException {
var tagCode = PrefixCode.readCode(input);
var offsetCode = PrefixCode.readCode(input);
for (int k = 0; k < blockSize; k++) {
int tag = tagCode.decodeSymbol(input);
if (tag == 256) {
return false; // end of input
} else if (tag < 256) {
write((byte) tag);
} else {
final int minLength = 3;
int length = decodeInteger(tag - 257) + minLength;
int offset = decodeInteger(offsetCode.decodeSymbol(input));
for (int i = 0; i < length; i++)
write(dictionary.get(outLength - offset));
}
}
return true;
}
private void write(byte b) throws IOException {
out.write(b);
dictionary.set(outLength++, b);
}
private int decodeInteger(int bitLength) throws IOException {
if (bitLength <= 1)
return bitLength;
return (1 << (bitLength - 1))
| (int) input.readBits(bitLength - 1);
}
The decodeInteger() method that is used to read the offset and length fields decodes a single variable-length integer. Given the integer’s bit length \(n\), the number is recovered by
reading the least significant \(n-1\) bits from input and then adding the most significant bit.
Solution to Exercise 10.5
Since Huffman’s algorithm only cares about frequencies and not the objects associated with them, a Huffman tree of tokens is constructed in the same way as a Huffman tree of characters or bytes. One possible result is shown in Fig. C.19.
Figure C.19 Huffman tree for LZ77 tokens.
Solution to Exercise 10.6
a)Two sequences are sufficient:
LZ4(“Around the world, a”, offset=18, length=15) LZ4(0xA, offset=35, length=105)
The first sequence encodes a single line without the terminating newline character. The second sequence adds the newline and three copies of the first line, each of which consists of 35 bytes.
b)The first sequence is encoded using 10 bytes. The header contains two 4-bit numbers: The first is the length of literal part (0111) and the second the length of the match 6 reduced by the minimal match length 4 (0010). The next 7 bytes contain the literal part of the
sequence, followed by 2 bytes for the offset of the match (0x0006, but in little-endian order).
.
Position
0
1–7
8–9
Bytes
01110010
YABBA␣D
0x060x00
The second sequence is similar, but since the match length 40 is too large for the header, an additional byte is used to encode the remainder, which is
\(\seteqnumber{0}{C.}{7}\)
\begin{equation*}
40-15-(\text {minimal match length}) = 21.
\end{equation*}
The result is
.
Position
0
1
2–3
4
Bytes
00011111
O
0x010x00
21
c)The output consists of a single sequence that contains all \(n\) bytes of the input. In addition to the \(n\) bytes required to encode the literal part of this sequence, the main contributor to the size of the output is the encoding of \(n\) itself, which requires \(\bigl \lceil
(n-15)/255\bigr \rceil \) bytes, or approximately \(n/255\) bytes. This corresponds to a \(100/255=0.39\,\%\) increase in file size.
d)The implementation shown in Listing C.95 includes additional error checking to ensure that the program doesn’t crash even if the input data isn’t well-formed. The ensure() method verifies that a certain
condition is met and throws a DecodeException if it isn’t. The top-level decode() method reads the header of the following sequence and then decodes its literal and match parts. The match part is ignored if the end of the input is
reached first.
Listing C.95ch10β―/β―LZ4Decoder
public static class DecodeException extends Exception {
}
private void ensure(boolean condition) throws DecodeException {
if (!condition)
throw new DecodeException();
}
public int decode() throws DecodeException {
while (inPos < inLength) {
int token = in[inPos++];
decodeLiteral(token);
if (inPos < inLength)
decodeMatch(token);
}
return outPos;
}
To decode the literal part of the sequence, the decodeLiteral() method in Listing C.96 first reads the remainder of the literal’s
llength field and then copies the requested number of bytes from in[] to out[]. The length field is decoded using decodeLength(). This method takes a single parameter startLength, which is either the mlength or the llength field stored in the sequence’s header. If startLength is 15, the
method reads additional bytes and add them to the length until it encounters a byte whose value is less than 255. Since bytes are signed values in Java, the expression in[inPos++] & 0xff is used to convert each byte to an unsigned
integer.
Listing C.96ch10β―/β―LZ4Decoder
private void decodeLiteral(int header) throws DecodeException {
int literalLength = decodeLength((header >> 4) & 0xf);
ensure(inPos + literalLength <= inLength
&& outPos + literalLength <= out.length);
System.arraycopy(in, inPos, out, outPos, literalLength);
inPos += literalLength;
outPos += literalLength;
}
private int decodeLength(int startLength) throws DecodeException {
if (startLength != 15)
return startLength;
int length = startLength;
while (inPos < inLength) {
int k = in[inPos++] & 0xff;
length += k;
if (k != 255)
return length;
}
throw new DecodeException(); // incomplete length
}
The decodeMatch() method in Listing C.97 decodes the match part of a sequence. It first reads two bytes for the offset and then
decodes the remainder of the match length using decodeLength(). Afterwards, it copies the matching bytes from a previous position in out to the current position; this
can usually be done using System.arraycopy(). However, if the length is greater than the offset — that is, if the match extends beyond the current position — the bytes must be copied one by one because arraycopy()’s handling of overlapping
regions is incompatible with LZ4.