Арифметическое кодирование. Применение масштабирования
на обеих стадиях кодирующего алгоритма. Модификация
алгоритма кодирования, использующего арифметику
бесконечной точности так, чтобы его можно было бы
легко переделать при использовании ограниченной
точности (т.е. при работе с целыми числами ограниченной
величины)
Проблема при переходе от модельного алгоритма,
предполагающего арифметику неограниченной точности,
к реальному алгоритму, работающему с числами
ограниченной точности, состоит в том, что при
при арифметическом кодировании мы рассматриваем
всё более и более маленькие интервалы, которые
с некоторого момента уже непредставимы. В прошлой лекции
мы рассмотрели, как можно преодолеть эту трудность,
применяя масштабирование (rescaling) на втором этапе
алгоритма -- при вычислении бинарного интервала,
который целиком содержится внутри интервала [a, b),
вычисленного на первм этапе алгоритма. Но на первом
этапе масштабирование не применялось, что делает
невозможным применение этого алгоритма на реальном
компьютере.
Решение состоит в том, чтобы применять масштабирование
на обоих этапах. Вернее, нельзя разбивать алгоритм
на 2 этапа, нужно перемежать вычисление интервала
[a, b), представляющего "теоретически" закодированное
сообщение, и бинарного интервала, содержащегося
внутри интервала [a, b), двоичную запись левой
границы которого мы выдаем в качестве последовательности
битов, кодирующей сообщение. При этом масштабирование
действует как на вычисление интервала [a, b), так и
на вычисление бинарного интервала. Это возможно,
поскольку процедура разбиения интервала на подынтервалы
пропорцонально вероятностям символов и процедура
масштабирования коммутируют друг с другом.
Например, можно сначала разбить i-ю часть интервала
в соответствии с вероятностями символов на n
подынтервалов (n -- число символов алфавита) и потом
выполнить масштабирование второй половины отрезка [0, 1],
которая содержит разбиваемый подынтервал [a, b); а можно
сначала выполнить масштабирование и уже затем разбить
отображенный при масштабировании интервал, в обоих
случаях получим один и тот же результат. Пример:
рассмотрит тот же случай алфавита из 3-х букв
{0, 1, 2} с вероятностями [0.2, 0.4, 0.4] и
кодируемое сообщние "2 1 0". На первом этапе выбираем
третий интервал [0.6, 1) и разбиваем его на 3
подынтервала [0.6, 0.68), [0.68, 0.84), [0.84, 1):
разбиение
1 0.2 0.6 0.68 0.84 1
|--------|-----------------|===|======|=======|
И затем масштабируем вторую половину отрезка [0, 1]:
0.5 0.6 0.68 0.84 1
|----------------------|---|===|======|=======|
масштабирование / / / / |
/ / / / |
/ / / / |
|--------|=======|=============|==============|
0 0.2 0.36 0.68 1
Но можем сначала масштабировать вторую половину
отрезка [0, 1], отобразив соответственно интервал
[0.6, 1) внутрь масштабированного отрезка [0, 1],
а затем уже разбить полученный интервал [0.2, 1)
на 3 подынтервала пропорционально вероятностям
{0.2, 0.4, 0.4} -- получим то же самое:
0.5 0.6 1
|----------------------|---|==================|
масштабирование / / |
/ / |
0 / 0.2 / |
|--------|====================================|1
разбиение
|--------|=======|=============|==============|
0 0.2 0.36 0.68 1
В соответствии с этим напишем модифицированный
алгоритм в "модельном" случае арифметики бесконечной
точности, но когда масштабирование уже применяется к
обеим этапам алгоритма.
def ariphmEncoderRescaling_InfPrec(p, message):
'''An arithmetic encoder using infinite-precision arithmetic
with the rescaling technique.
Input: p[i] is the probability of i-th symbol in
the alphabet. Zero symbol terminates a message;
message is the list of indices of symbols.
Return the sequence of bits that encodes the message'''
n = len(p)
c = [0.]*(n + 1)
c[0] = 0.
for i in range(1, n+1):
c[i] = c[i-1] + p[i - 1]
encodedMessage = []
a = 0.; b = 1.; s = 0
for j in message:
w = b - a
b = a + c[j+1]*w
a = a + c[j]*w
while b <= 1/2 or 1/2 <= a:
if b <= 1/2:
# Select the left half and rescale
a = a*2; b = b*2
encodedMessage.append(0)
# Emit 111...1 (s units)
for i in range(s):
encodedMessage.append(1)
s = 0
else:
assert 1/2 <= a
# Select the right half and rescale
a = (a - 1/2)*2
b = (b - 1/2)*2
encodedMessage.append(1)
# Emit 000...0 (s zeros)
for i in range(s):
encodedMessage.append(0)
s = 0
while 1/4 < a and b < 3/4:
s += 1
# Rescale the middle segment [1/4, 3/4]
a = (a - 1/4)*2.
b = (b - 1/4)*2.
assert a <= 1/4 or 3/4 <= b
s += 1
if a <= 1/4:
# Select [1/4, 1/2)
# Emit 0111...1 (zero and s units)
encodedMessage.append(0)
for i in range(s):
encodedMessage.append(1)
else:
assert 3/4 <= b
# Select [1/2, 3/4)
# Emit 1000...0 (unit and s zeros)
encodedMessage.append(1)
for i in range(s):
encodedMessage.append(0)
return encodedMessage
Этот алгоритм уже с минимальными изменениями
переделывается к алгоритму, использующему арифметику
ограниченной точности -- точнее, ипользующего только
целые числа, причем ограниченного размера.
Рассмотрим окончательный алгоритм на следующей лекции.