Notes

Chapter 10: Processes of Perception and Analysis

Section 5: Data Compression


Run-length encoding

Data can be converted to run lengths by Map[Length, Split[data]]. Each number is then replaced by its representation.

With completely random input, the output will on average be longer by a factor Sum[2^-(n+1) r[n], {n,1,∞}] where r[n] is the length of the representation for n. For the Fibonacci encoding used in the main text, this factor is approximately 1.41028. (In base 2 this number has 1's essentially at positions Fibonacci[n]; as discussed on page 914, the number is transcendental.)


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