text and the 0-order probability statistics -> longval, nbits The encoded number is rational(longval, 2**nbits)
(text, probs)
| 44 | |
| 45 | |
| 46 | def encode(text, probs): |
| 47 | """text and the 0-order probability statistics -> longval, nbits |
| 48 | |
| 49 | The encoded number is rational(longval, 2**nbits) |
| 50 | """ |
| 51 | minval = R(0) |
| 52 | maxval = R(1) |
| 53 | for c in text + "\x00": |
| 54 | prob_range = probs[c] |
| 55 | delta = maxval - minval |
| 56 | maxval = minval + prob_range[1] * delta |
| 57 | minval = minval + prob_range[0] * delta |
| 58 | |
| 59 | # I tried without the /2 just to check. Doesn't work. |
| 60 | # Keep scaling up until the error range is >= 1. That |
| 61 | # gives me the minimum number of bits needed to resolve |
| 62 | # down to the end-of-data character. |
| 63 | delta = (maxval - minval)/2 |
| 64 | nbits = 0L |
| 65 | while delta < 1: |
| 66 | nbits = nbits + 1 |
| 67 | delta = delta << 1 |
| 68 | if nbits == 0: |
| 69 | return 0, 0 |
| 70 | else: |
| 71 | avg = (maxval + minval)<<(nbits-1) # using -1 instead of /2 |
| 72 | # Could return a rational instead ... |
| 73 | return avg.n//avg.d, nbits # the division truncation is deliberate |
| 74 | |
| 75 | |
| 76 | def decode(longval, nbits, probs): |