# Notes

## Section 5: Data Compression

Number representations

The sequence of 1's and 0's representing a number n are obtained as follows:

(a) Unary. Table[0, {n}]. (Not self-delimited.)

(b) Ordinary base 2. IntegerDigits[n, 2]. (Not self-delimited.)

(c) Length prefixed. Starting with an ordinary base 2 digit sequence, one prepends a unary specification of its length, then a specification of that length specification, and so on:

(Flatten[{Sign[-Range[1 - Length[#], 0]], #}] &)[Map[Rest, IntegerDigits[Rest[Reverse[NestWhileList[Floor[Log[2, #] &, n + 1, # > 1 &]]],2]]]

(d) Binary-coded base 3. One takes base 3 representation, then converts each digit to a pair of base 2 digits, handling the beginning and end of the sequence in a special way.

Flatten[IntegerDigits[Append[2 - With[{w = Floor[Log[3, 2n]]}, IntegerDigits[n - (3w + 1 - 1)/2, 3, w]], 3], 2, 2]]

(e) Fibonacci encoding. Instead of decomposing a number into a sum of powers of an integer base, one decomposes it into a sum of Fibonacci numbers (see page 902). This decomposition becomes unique when one requires that no pair of 1's appear together.

Apply[Take, RealDigits[(N[#, N[Log[10, #] + 3]] &)[n 5/GoldenRatio2 + 1/2], GoldenRatio]]

The representations of all the first Fibonacci[n] - 1 numbers can be obtained from (the version in the main text has Rest[RotateLeft[Join[#, {0, 1}]]] & applied)

Apply[Join, Map[Last, NestList[{#2], Join[Map[Join[{1, 0}, Rest[#]] & , #2], Map[Join[{1, 0}, #] &, #1]]} &, {{}, {{1}}}, n-3]]]

From Stephen Wolfram: A New Kind of Science [citation]