Arithmetic coding allows you to make a prediction and only provide bits for correction.
Have the de-compressor predict the next data based on the outcome so far (a statistical prediction of next data will be lossy as it won't always be correct). If the prediction is correct you need to spend very little to confirm that. If it's incorrect you'll need to spend data to correct it. Arithmetic coding is the best way to make this work.
It's also been used by all winning entries of the Hutter prize so far.
Technically you’re correct. If you can rebuild the original losslessly then all the original information is present, just in a different configuration.
