The Eastleigh projectArithmetic coding: 574 steps of height in under 900 bits
Sample the ground along two lines, turn heights into steps, and see how few bits each way of writing them needs.
The learner draws two straight lines over Eastleigh on a map: one from west to east along latitude 50.969 north, 7.7 km long, and one from south to north along longitude 1.353 west, 6.7 km long. An open elevation model gives the height of the ground every 25 m or so along each, 576 heights in total, rounded to whole metres. The first line runs between 9 m and 49 m above sea level and the second between 2 m and 76 m. Instead of storing heights, the program stores the step from each point to the next. There are 574 steps, and they are dull in a useful way: 348 of them, 60.6%, are no change at all, 130 are one metre up, 71 one metre down, and only 25 are anything bigger.
Bits needed to store the two Eastleigh height profiles, by method (our Python run)| Method | Total bits | Bits per step |
|---|
| Each height as a 7-bit number | 4,032 | 7.00 |
| Each step as a 3-bit number | 1,722 | 3.00 |
| Whole-bit code, short codes for common steps | 936 | 1.631 |
| Arithmetic coding, fixed table of step frequencies | 896 | 1.561 |
| Arithmetic coding, learning, previous step as context | 884 | 1.540 |
A whole-bit code, the kind named after David Huffman, gives the flat step the shortest code there is: one bit. But a step that turns up 60.6% of the time carries only about 0.72 of a bit of surprise, so a quarter of every such bit is wasted. Arithmetic coding removes the waste. It begins with the range from 0 to 1 and, for each step in turn, shrinks the range to a slice whose width matches that step's probability. Common steps shrink it slightly and rare ones a lot. At the end, any number inside the final sliver identifies the whole sequence, and the narrower the sliver, the more bits that number needs. Our coder used exact fractions and wrote the 574 steps in 896 bits, against a theoretical floor of 894.7 for that table. A decoder then rebuilt every step correctly from the 896 bits alone.
The last row is where prediction enters. Ground that was flat a moment ago tends to stay flat: after a flat step the next is flat 67.5% of the time, not 60.6%. A coder that keeps a separate tally for each previous step, and updates the tallies as it reads, reaches 884 bits. That is below the floor of the fixed table, and it needs no table sent in advance, because the decoder builds the same tallies as it goes. Pushing further backfired. With two previous steps as context the total rose to about 928 bits, because 574 steps are too few to fill so many tallies with reliable counts. A sharper model only pays if there is enough data to train it.
Ages 8 to 11
Guess a friend's up, down or flat moves on a paper hill. Keep score, and notice that flat is nearly always the safe bet.
Ages 11 to 15
Fetch the heights in Python, count each kind of step, and work out the 3-bit and whole-bit totals.
Ages 15 and up
Write the coder and decoder with Python's Fraction type, then add the learning model and compare contexts.
Where the heights come from, and the limits
Heights are from the EU-DEM v1.1 elevation model, produced using Copernicus data and information funded by the European Union, and were read through the OpenTopoData service. The model has a 25 m grid and its heights can be a few metres out, more so among buildings and trees. The lines, the rounding and all bit counts are ours, and the totals leave out the few bits needed to say how long the message is. Different lines would give different numbers.
