Since a few days I am fighting my way through implementing arithmetic coding. I
ID: 654618 • Letter: S
Question
Since a few days I am fighting my way through implementing arithmetic coding. I found a really great source of information which made me understand how it should work. Long story short, it implements arithmetic coding on integers using two registers: HIGH and LOW. Those register store a fraction, ex.
HIGH = 98765 //means 0.98765(9)
LOW = 91234 // means 0.91234(0)
Then comes magic, when the most significant numbers match (in this case it would be 9s) they are printed out. It's all clear to me.
However, when we take the following example
HIGH LOW RANGE CUMULATIVE OUTPUT
Initial state 99999 00000 100000
Encode B (0.2-0.3) 29999 20000
Shift out 2 99999 00000 100000 .2
Encode I (0.5-0.6) 59999 50000 .2
Shift out 5 99999 00000 100000 .25
Encode L (0.6-0.8) 79999 60000 20000 .25 //here starts problems
Encode L (0.6-0.8) 75999 72000 .25 //how possible?
Shift out 7 59999 20000 40000 .257
Encode SPACE (0.0-0.1) 23999 20000 .257
Shift out 2 39999 00000 40000 .2572
Encode G (0.4-0.5) 19999 16000 .2572
Shift out 1 99999 60000 40000 .25721
Encode A (0.1-0.2) 67999 64000 .25721
Shift out 6 79999 40000 40000 .257216
Encode T (0.9-1.0) 79999 76000 .257216
Shift out 7 99999 60000 40000 .2572167
Encode E (0.3-0.4) 75999 72000 .2572167
Shift out 7 59999 20000 40000 .25721677
Encode S (0.8-0.9) 55999 52000 .25721677
Shift out 5 59999 20000 .257216775
Shift out 2 .2572167752
Shift out 0 .25721677520
I really don't know how the marked lines are achieved on computers, on paper it's easy, since:
/*
range, HIGH, LOw - integer
symbol->high, symbol->low - real
*/
HIGH = HIGH - (range - symbol->high*range)
LOW = LOW + range*symbol->low
But on computers? The real-number inaccuracy comes in and my intervals are much different.
[0; 99999) 100000 b [0.2; 0.3)
[20000; 29999) 100000 ===> 2
[0; 99999) 100000 i [0.5; 0.6)
[50000; 59998) 100000 ===> 5 //inaccuracy
[0; 99989) 99990 l [0.6; 0.8)
[59993; 79990) 19998 l [0.6; 0.8)
[71991; 75990) 19998 ===> 7
[19910; 59909) 40000 [0; 0.1)
[19910; 23908) 3999 g [0.4; 0.5)
[21509; 21908) 3999 ===> 2
[15090; 19089) 3999 ===> 1
[50900; 90899) 40000 a [0.1; 0.2)
[54900; 58898) 40000 ===> 5
[49000; 88989) 39990 t [0.9; 1)
[84991; 88988) 39990 ===> 8
[49910; 89889) 39980 e [0.3; 0.4)
[61904; 65900) 39980 ===> 6
[19040; 59009) 39970 s [0.8; 0.9)
[51016; 55011) 39970 ===> 5
zakodowano: 257215865
I would appreciate any help.
Explanation / Answer
You shouldn't use floating point in such cases.
Probabilities can be represented as rational numbers with denominator 10^something, this allows you to divide current interval exactly without rounding errors.
So in your case 0.6 becomes 6/10, 0.8 - 8/10. How you will store such things is your choice. Usually some kind of fixed point format is used. For example you store 60 and know that this is actually probability*100, so whenever you multiply by it, you also divide by 100.
Also note that later you will encounter another type of overflow - when you cannot shift out anything, but number of digits doesn't allow to divide interval without rounding errors. In such cases you either allow some inaccuracy in dividing interval or artificially narrow it to make shift out possible. If decode does everything in the same way, this doesn't impact correctness, but reduces compression a bit.