An encoding of all binary strings in the range to all Binary strings in the domain, based on an expected probability distribution of bitstings. The encoder starts with the range [0,1) and to encode reach bit the encoder takes the expected distribution of the bit (maybe 20/80) and divides the range in those proportions and throws away the portion the bit didn't fall into (in this case either [[0,0.2) or [[0.8,1) ). When all bits have been seen the range is sent as the encoding.
ArithmeticDecoding is the reverse process.
ArithmeticEncoding has been shown to be the asymototical optimal way to encode such a string (only asymototical optimal because of the need to round up the range to the nearest bit).
ArithmeticEncoding and ArithmeticDecoding are used in bzip2(1) and but zip(1).
2 pages link to ArithmeticEncoding:
