Арифметическое кодирование, продолжение
Масштабирование (rescaling)

Идея простая:
пусть есть алфавит из n букв с вероятностями
    p0, p1, ..., p_n-1,
буквы
    0, 1, 2, ...    
В алфавите есть специальная буква EOF
(End Of File, или EOD of data, или EOI оf Information),
которая завершает исходную последовательность.
Обычно EOF -- это буква 0.
Входная последовательность всегда кончается нулем
и не содержит нулей внутри:
    210, 112210, 1122222120

   |-------|--------|---------|-------------|---------|
     p0      p1       p2        .  . .       p_n-1
Пусть первая буква кодируемого сообщения k,
тогда мы выбираем k-й интервал. Например, если
это буква 2, то выбираем интервал: 
   |-------|--------|=========|-------------|---------|
     p0      p1       p2        .  . .       p_n-1

Делим его на подинтервалы пропорционально вероятностям,
и среди этих интервалов выбираем интервал,
соответствующий второй букве, и т.д.
                    |=========|
                    
                    |==|==|...|                    
и продолжаем деление. Длины подинтервалов
после второго деления будут
        p2*p0, p2*p1, p2*p2, ..., p2*p_n-1

В конце-концов получаем интервал [a, b),
соответствующий последовательности букв
        i0, i1, i2, ... ik
его длина равна         
        p_i0 * p_i1 * ... * p_ik
        
Получив интервал [a, b), мы хотим его записать
последовательностью нулей и единиц.

Приступаем ко второму этапу -- последовательному 
делению пополам исходного отрезка [0, 1].
На каждом шаге мы делим текущий отрезок ровно пополам
и выбираем одну из его половин.
Наша цель -- получить бинарный интервал [f, g)
такой, что a <= f < g < b, то есть интервал [f, g)
целиком лежит внутри интервала [a, b).

При этом на каждом шаге длина интервала [f, g)
уменьшается вдвое. Чтобы не ошибиться из-за
потери точности при вычислениях с очень маленькими
числами, мы на каждом шаге выполняем масштабирование
(rescaling): отображаем текущий интервал на
интервал [0, 1) и пересчитываем границы
интервала [a, b), кодирующего сообщение, в соответствии
с этим отображением. Если выбрана левая половина 
[0, 1/2] отрезка [0, 1], то отображение масштабирования,
которое отображает отрезок [0, 1/2] на [0, 1],
задается формулой
    y = 2*x 
Вот схематическое изображение масштабирования
в случае, когда выбрана левая половина отрезка:
    0    a    b        1/2
    [====+====+=========|-------------------]      
    |     \     \            \              
    |      \      \               \               
    |       \       \                  \       
    [========+========+=====================]
    0        a        b                     1
    
Если выбрана правая половина отрезка, то отображение
масштабирования, которое отображает отрезок [1/2, 1]
на [0, 1], задается формулой
    y = 2*(x - 1/2) 
Вот схематическое изображение масштабирования:
в случае, когда выбрана правая половина отрезка:
    0                  1/2        a    b
    [-------------------|=========+====+====]      
                   /            /     /     |
              /               /      /      |     
         /                  /       /       |  
    [=====================+========+========]
    0                     a        b        1
    
Первый этап: делим отрезок [0, 1] пополам.
Если интервал [a, b) лежит целиком в одной из половин,
то выбираем ее; в выходную последовательность выдаем
0, если выбрали левую половину, и 1, если правую.

Если b < 1/2, то выдаем 0,
выбираем левую половину, масштабируем, пересчитываем
значения a и b:
    a = 2*a
    b = 2*b
    
Если a > 1/2, то выдаем 1,
выбираем правую половину, масштабируем, пересчитываем
значения a и b:
    a = 2*(a - 1/2)
    b = 2*(b - 1/2)

Продолжаем так, пока выполняется условие:
    b < 1/2 или a > 1/2

Цикл останавливается, когда середина очередного
отрезка (всегда 1/2 в результате масштабирования)
будет внутри интервала [a, b).
    
                       1/2
    |----------------+--|---------+---------------|
                     |            |
                    [a            b)
Положим счётчик S = 1
Имеем a < 1/2 и b > 1/2                   
Отрезок [0, 1] делим на 4 части                   
    0                a 1/2        b               1
    [----0-----------+--|---------+------1--------]
    [---00----|---01-+--|---10----+--|---11-------]
              [----|-+--|-----|---+--]             
              010 011|   100  101 | 
    масштабируем     a            b 
    середину        /                  \
    0              a   1/2                 b      1
    [--010---|-011-+----|==100=======|-101-+------]
                         результат
Если одна из четвертей целиком внутри [a, b),
то алгоритм завершается. Иначе делим середину
(вторую и третью четверти) снова на 4 части,
масштабируем, увеличиваем S, и так далее.
Останавливаемся, когда либо
    a < 1/4 (в любом случае b > 1/2),
            т.е. a в первой четверти,
либо
    b > 3/4 (в любом случае a < 1/2)
            т.е. b в четвертой четверти.

В первом случае a < 1/4 
            1/4       1/2
    |----a---|=========|-------b---|----------|
ответом будет интервал,
соответствующий второй четверти (добавляется 011...11)
                                              S единиц
Во втором случае b > 3/4
                     1/2        3/4 
    |-------|----a----|==========|---b------|
ответом будет интервал,
соответствующий третьей четверти (добавляется 100...00)
                                               S нулей