CHAPTER 3 / UNIVERSAL CODES
73
Table 3.22 Some Goldbach
G 1
Representations, as Sums of Primes
Value Sums Indices Encode As Coding Length
18 1+17 1,7 1,7 1 00111
6
... 5 + 13 3,6 3,4 011 00100 8
... 7 + 11 4,5 4,2 00100 010 8
20 1 + 19 1,8 1,8 1 0001000 8
... 3 + 17 2,7 2,6 010 00110 8
... 7 + 13 4,6 4,3 00100 011 8
36 5 + 31 3,11 3,9 011 0001001 10
... 7 + 29 4,10 4,7 00100 00111 10
... 13 + 23 6,9 6,4 00110 00100 10
... 17 + 19 7,8 7,2 00111 010 8
42 1 + 41 1,13 1,13 1 0001011 8
... 5 + 37 3,12 3,10 011 0001010 10
... 11 + 31 5,11 5,7 00101 00111 10
... 13 + 29 6,10 6,5 00110 00101 10
... 19 + 23 8,9 8,2 0001000 010 10
Table 3.23 Basis Integers for Additive Code Add256
0 1 3 5 7 9 10 21
23 25 27 28 39 41 43 45
47 50 58 76 87 98 102 106
118 120 122 124 135 154 166 183
202 214 231 250
36 values(54 primes)Seeds = 10,28,50
as for the first Goldbach code. A typical set of basis integers to encode integers up to 256 is shown
in Table 3.23.
The Additive code Addm is designed to encode integers N < m (and might not encode N > m).
The set of basis integers is generated by a sieve, recording the values that can be generated by
adding members of the set-so-far. A value which cannot be formed is included as the next member
of the basis set. Suitable seeds are introduced to facilitate code generation; seed values are found
by a computer search to minimize, for example, the average length of the generated code.
3.13 WHEELER 1/2 CODE AND RUN-LENGTHS
The codes of this section are embedded in a character stream and encode the length of run-length
compressed strings.
A simple method, used in some Burrows-Wheeler compressors, triggers run-length encoding
by a succession of say four identical characters and then encodes the length in a base-64 g code.
For example, a run of 50 A's would have the hexadecimal coding "41 41 41 41 72" and
1000X's"58 58 58 58 28 4F."

Get Lossless Compression Handbook now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.