Арифметическое кодирование, продолжение
Алгоритм кодирования в предположении, что мы можем выполнять точные операции с вещественными числами Повторим некоторые определения из прошлой лекции. Дл простоты мы считаем, что наш алфавит состоит из n букв, и буквы мы отождествляем с их индексами в алфавите. Например, в прошлый раз мы рассматривали алфавит из трех букв '0', '1', '2': A = {0, 1, 2} Их вероятности появления в произвольных сообщениях равны p = { 0.2, 0.4, 0.4 } Кроме того, мы условились считать букву 0 символом, завершающим любое сообщение (его часто обозначают как EOF, или End Of File). Таким образом, наши сообщения всегда заканчиваются символом 0 и не могут содержать 0 в середине сообщения. Примеры сообщений: 2 1 0, 1 2 2 0, 1 1 2 1 2 1 1 0 и т.п. Напомним, что процедура кодирования выполняется в два этапа. На первом этапе мы вычисляем полуинтервал, соответствующий сообщению. Мы начинаем с интервала [0, 1), делим его на сегменты пропорционально вероятностям букв, и выбираем сегмент, соответствующий первой букве. Затем полученный полуинтервал снова делим на сегменты пропорционально вероятностям букв и выбраем сегмент, соответствующий второй букве, и так далее, пока не исчерпаем все буквы сообщения. В примере мы рассматривали сообщение 210 и получили последовательность сегментов [0.6, 1.0) буква 2 [0.68, 0.84) буква 1 [0.68, 0.712) буква 0 Окончательно всему сообщению соответствует полуинтервал [a, b) = [0.68, 0.712) Затем на втором этапе мы находим бинарный сегмент [f, g) путем последовательного деления отрезка пополам и выбора одной из его половин. Начинаем с отрезка [0, 1), делим его пополам на два интервала [0, 0.5) и [0.5, 1.0) и выбираем одну из половин -- в зависмости от того, куда попадает наш интервал [a, b), представляющий кодируемое сообщение. При этом левая половина представляет все действительные числа вида 0.0xxxxxx... дробная часть которых в двоичной записи начинается с цифры 0, правая половина -- числа вида 0.1xxxxxx... дробная часть которых начинается с цифры 1. Если мы выбрали левую половину, то выдаем бит 0 в выходную последовательность, если правую, то выдаем бит 1. Полученный интервал снова делим пополам и так продолжаем до тех пор, пока одна из половин содержит целиком интервал [a, b). В рассмотренном примере получаем последовательность "бинарных" интервалов [0.5, 1.0) выдаем 1 [0.5, 0.75) выдаем 0 [0.625, 0.75) выдаем 1 При этом на каждом шаге длина интервала [f, g) уменьшается вдвое. Чтобы не ошибиться из-за потери точности при вычислениях с очень маленькими числами, мы на каждом шаге выполняем масштабирование (rescaling): отображаем текущий интервал на интервал [0, 1) и пересчитываем границы интервала [a, b), кодирующего сообщение, в соответствии с этим отображением. Например, на первом шаге мы выбрали интервал [0.5, 1.0), содержащий наш интервал [a, b) = [0.68, 0.712). Отображаем его на интервал [0, 1) растягивая его вдвое и смещая влево: 0.5 +----+----+-------------+ 1.0 | |====| | +----+----+-------------+ 0.68/ / 0.712 / / / / 0.0 / / 1.0 +--------+--------+------------------------+ | |========| | +--------+--------+------------------------+ 0.36 0.424 Здесь новое значение a = 0.36 вычисляется как a = (a - 1/2)*2 = (0.68 - 0.5)*2 = 0.36, аналогично новое значение b = 0.424 вычисляется как b = (b - 1/2)*2 = (0.712 - 0.5)*2 = 0.424 В результате в нашем примере после трех шагов с учетом масштабирования мы получаем интервал [0, 1) и полуинтервал [a, b) = [0.44, 0.696): 0.0 0.5 1.0 +------------------+-+--------+------------+ | |==========| | +------------------+-+--------+------------+ a=0.44 b=0.696 Полуинтервал [a, b) содержит середину текущего "бинарного" интервала, т.е. он уже не содержится ни в его левой, ни в правой половине, и мы уже не можем на следующем шаге выбрать одну из его половин. Как быть? Используется следующее решение. Делим текущий "бинарный" интервал уже не на две, а на 4 части. При масштабировании текущий интервал всегда равен [0, 1). Каждая из четвертей соответствует добавлению двух битов в выходную последовательность: 00 для первой четверти, 01 для второй, 10 для третьей и 11 для четвертой. Рассмотрим три случая. В первых двух "хороших" случаях мы сразу можем выдать окончательный ответ -- вычислить бинарный интервал, который целиком содержится внутри интервала [a, b), и завершить работу. В третьем случае следует продолжить итерационный процесс до достижения одного из первых двух случаев. Итак, первый случай определяется неравенством a <= 1/4 Поскольку всегда b >= 1/2, это означает, что вторая четверть бинарного интервала целиком содержится внутри интервала [a, b): 0 a 1/4 1/2 b 3/4 1 +---+-----+----------+------+---+----------+ | |=====+==========+======| | | | | |!!!!!!!!!!| | | | +---+-----+----------+------+---+----------+ На рисунке вторая четверть отмечена восклицательными знаками, а интервал [a, b) -- знаками равенства. Вторая четверть добавляет биты 01 к выходному сообщению, и алгоритм на этом завершается. Второй "хороший" случай определяется неравенством b >= 3/4, в этом случае третья четверть содержится целиком внутри полуинтервала [a, b): 0 1/4 a 1/2 3/4 b 1 +---------+------+---+----------+-----+----+ | | |===+==========+=====| | | | | |!!!!!!!!!!| | | +---------+------+---+----------+-----+----+ Третья четверть добавляет биты 10 к выходному сообщению, и алгоритм на этом завершается. "Плохой" (чуть более сложный случай) состоит в том, что числа a и b находятся во второй и третьей четвертях: 1/4 < a < 1/2 < b < 3/4, и ни одна из четвертей не содержится целиком внутри интервала [a, b). В этом случае мы отбрасываем первую и четвертую четверти и переходим к рассмотрению бинарного интервала [1/4, 3/4), масштабируем его до интервала [0, 1) и пересчитываем значения a, b: 0 1/4 a 1/2 b 3/4 1 +---------+------+---+------+---+----------+ | | |===+======| | | +---------+------+---+------+---+----------+ / / \ \ / / \ \ 0 / / 1/2 \ \ 1 +-------------+------+------------+--------+ | |======+============| | +-------------+------+------------+--------+ a b Эти шаги могут повторяться несколько раз, пока мы не придем к одному из "хороших" случаев 1 или 2. В счетчике S мы запоминаем, сколько таких шагов мы сделали. Каждый шаг добавит к выходной последовательности бит 1, если мы в конце-концов придем к первому "хорошему" случаю a <= 1/4, т.е. в конце выходной последовательности будут биты 0111...1, где число единиц будет равно S+1. Это потому, что мы в конце выберем вторую четверть, поэтому первые биты 01, а при каждом шаге мы приближаемся снизу к середине интервала, поэтому к битам 01 на каждом шаге добавляется бит 1. Если же мы в конце-концов придем к "хорошему" случаю 2, то к выходной последовательности добавляются биты 1000...0, где число нулей равно S+1. Это потому, что мы в конце выбираем третью четверть, поэтому первые биты 10, а каждый шаг приближает нас сверху к середине интервала, добавляя бит 0 к концу выходной последовательности. Выходная последовательность составит биты дробной части двоичной записи левой границы "бинарного" интервала [f, g), который целиком содержится внутри интервала [a, b), вычисленного на первом этапе алгоритма. Можно доказать, что такая последовательность декодируется однозначно и не требует дополнительной передачи длины исходной последовательности. Простой алгоритм декодирования в предположении, что операции с вещественными числами выполняются точно, мы рассмотрим на следующей лекции. Эту лекцию мы завершим записью алгоритма кодирования, изложенного выше неформально, на языке Python. def ariphmEncoder(p, message): '''p[i] is the probability of i-th symbol in the alphabet. Zero symbol terminates a message. The message is a 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] # Stage 1: define the interval [a, b) a = 0.; b = 1. for j in message: w = b - a b = a + c[j+1]*w a = a + c[j]*w # Stage 2: compute the binary interval # that lays in [a, b), # using the rescaling technique. # Emit the sequence of binary digits of # the fraction part of interval beginning. encodedMessage = [] assert a < b 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) else: assert 1/2 <= a # Select the right half and rescale a = (a - 1/2)*2 b = (b - 1/2)*2 encodedMessage.append(1) assert a < 1/2 and b > 1/2 # the middle of the current segment is in [a, b) s = 0 while 1/4 < a and b < 3/4: s += 1 # Rescale the segment [1/4, 3/4] a = (a - 1/4)*2. b = (b - 1/4)*2. s += 1 assert a < 1/2 and 1/2 <= b assert a <= 1/4 or 3/4 <= b 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 Вот пример использования этого алгоритма: >>> p = [0.2, 0.4, 0.4] >>> x = [2, 1, 0] >>> y = ariphmEncoder(p, x) >>> y [1, 0, 1, 1, 0, 0]