В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 150
Текст из файла (страница 150)
Вместо это- го вычисляются только подьпггервал, соответствующий теку ущему символу. Крат- ко эта операция описана далее. Введем следующие обозначения: + Х вЂ” наборсимволов(хьхъ-,хм); ( ) — символ, встретившиися на я-й итерации, то я-" бщения; и, то есть -и символ соо— + 1(я— ( ) — значение индекса Х(7»), например, если Х(я) = хи тогда 1(я) = 3; + М вЂ” количество воаможных символов; -(') — г[Х = »1 = Р, — функция плотности вероятности для Х; + Р(!)=ХР— к.м ,(') = ~~, — у улятивнаяфункцияраспределениявероятностейдляХ; 1» — нижняя граница подынтервала после 7»-й итерации алгоритма; + О» — верхняя граница подынтервала после я-й итерации алгоритма; + 11>»=Π— (в — » — ширина подынтервала после Й-»! итерации ал ни алгоритма. 20.3.
Арифметическое кодирование 647 итерация алгоритма включает следуюшие вычисления: 1« — 1.», + Рх (1(/г) — 1) 1(г . ! Р1 =1„, + Рх(1(7»))й>»->, 11; — 11 — 1.,= Рг [Х= Х(>>»)[»('» !. Ширина конечного подьнггервала равна произведению вероятностей каждого встретившегося за время работы алгоритма символа и поэтому представляет собой вероятность того, что данное сообшение и встретится в М" возможных сообшениях.
Это можно выразить таю Рг(т) = П Рг[Х = Х(Й)1. » ! Можно показать, что для уникальной идентификации интервала сооб»цения и требуется, самое большее, 2 + 1оя(1/Рг(т) ) бит. Чтобы продемонстрировать это на интуитивно понятном уровне, рассмотрим два первых интервала с соответствующими длинами Рг(1) и Рг(2), то есть интервалы [О, Рг(! )) и [Рг(1), Рг(1) + Рг(2)). Теперь предположим, что для определения интервала мы используем его нижнюю границу. При этом двоичная дробь, представляюшая Рг(1), будет кодом длн второго интервала. Существует некоторое числой такое, что 2-> будет наименьшеи величиной, удовлетворяющей неравенству 2» Рг(1). Это число представляет собой двоичную дробь, начинаюшук>ся с (1оя(1/Рг(т)) — 1) бит, за которыми следует 1.
При использовании этого значения в качестве кода для второго интервала гарантируется, что этот код уникально идентифицируется по отношению к первому интервалу. Обратите внимание на то, что в данной формулировке не делается предположений о стационарности или независимосп! переходов.
Пример Этот пример взят из [115]. Пусть имеются два символа, а и Ь, вероятности которых зависят от положения в трехсимвольном сообщении: Рг(а!) = 2/3, Рг(Ъ!) = 1/3, Рг(а!) = 1/2, Рг(Ь!) = 1/2, Рг(а») = 3/5, Рг(Ь;) = 2/5. Здесь Рг(а,) представляет собой вероятность того, что символ а встретится в »-й позиции сообшения. В данном случае кодируется сообщение «ЪаЪ». На рис. 20.5 показано арифметическое кодирование этого сообшения.
Данному сообщению соответствует конечный интервал [23/30, 5/6) = [0,766, 0,833). В двоичном виде конечный интервал выглядит следующим образом: [0,1 10001..., 0,110101...). Обратите внимание на то, что все числа, начинаю>цнеся с 0,110001, целиком попадают в интервал, но существуют некоторые числа, начинающиеся с 0,1100, не попадающие в этот интервал (например, 0,1100001 < 23/30). Поэтому кода 11001 достаточно, чтобы однозначно идентифицировать интервал и, следовательно однозначно идентифицировать сообщение.
В общем случае, чем меньше конеч ныи 649 Глава 20. Сжатие Без потерь 1/3 О,вт 1,0 ь1 1Г2 0,87 1,0 ьа о,вт з/5 о,тББ 0,8ЗЗ аз ьз 0,11001,= 0.78125 0,11010з= 0,8125 интервал (соответствующий менее вероятному сообщению), тем больше битов кода требуется для уникальной идентификации интервала. рис. 20.5. Пример чистого арифметического кодирования Декодирование П роцесс декодирования выполняется по той же общей поэтапной схеме. На этот раз обнаруживаются последовательные подынтервалы, приводящие к конечному интервалу и открытию соответствующих сообп1ений. Общие правила выглядят следующим образом.
Опять же, начнем с интервала [О, 1): 1. Разделим текущий интервал на подьштервалы, по одному для каждого символа. Длина каждого подынтервала пропорциональна вероятности появления соатветствукнцего символа. 2. Выберем подынтервал, содержащий код, выраженный в виде двоичной дроби. Выведем символ, определяющий этот код. Эти два шага повторяются до тех пор, пока не будет распаковано все сообщение. Существует несколько способов определить, что сообщение распаковано полностью. К исходному сообщению может быть добавлен символ конца сообщения.
Вэт этом случае процесс декодирования остановится при обнаружении этого символа. Другой способ состоит в там, чтобы при декодировании на каждом шаге проверятгч все ли двоичные дроби, начинакнциеся с кода, попадают в один интервал, и прекратить декодл1равание, когда ато условие перестанет выполняться. П роцесс декодирования, как и процесс кодирования, иллюстрирует рис. 20.5.
Численное значение конечного кода (0,78125 = 0,110012) обозначается кружком на каждой линии процесса. 20 З дрифметическое кодирование 648 Инкрементное арифметическое кодирование У только что описанного алгоритма чистого арифметического кодирования есть два недостатка. Во-первых, уменьшающиеся размеры текущего интервала требуют все более точных вычислений. Во-вторых, код не может быть послан, пока не обработана все сообщение. Метод инкрементного арифметического кодирования позволяет решить обе проблемы, При использовании этой техники перед вьпюлнением каждого следующего шага алгоритма текущий интервал всегда увеличивается, а кодовые биты генериую ся на каждом шаге и могут передаваться или сохраняться после каждого шага.
Описаниеалгоритма Каждый гиаг алгоритма начинается с полуоткрытого интервала [1., Н), который инициализируется значением [О, 1). Кроме тога, используется счетчик следования (1о11оь" соипгег), инициализируемый значением 0: 1. Текущий интервал разбивается на подынтервалы по одному для каждого возлюжного символа. Длина каждого подынтервала пропорциональна вероятности появления соответствующего символа.
2. Выбирается подынтервал, соответствующий текущему символу, 3. Следующие шаги выполняются в цикле до тех пар, пока не выполиится условие выхода из цикла: Если новый подынтервал не попадает целиком в один из следующих интервалов: [О, 0,5), [0,25, 0,75) или [0,5, 1), — выйти из цикла.
+ Если новый подынтервал попадает в интервал [О, 0,5), вывести бит О, после которого поль или более битов 1, соответствующих значению счетчика следования, после чего значение счетчика следования установить на ноль. Удвоить размер подынтервала, линейно расширив [О, 0,5) до [О, 1). То есть установить 1 = 2Л и Н = 2Н, + Если новый подынтервал попадает в интервал [0,5, 1,0), вывести бнт б 1, после которого ноль или более битов О, соответствующих значению счетчика следования, после чего значение счетчика следования установить на ноль.
Удвоить размер подынтервала, линейно расширив [0,5, 1) до [О, 1). То есть установить 7. = 2(Х вЂ” 0,5) и Н = 2(Н вЂ” 0,5). + Если новый подынтервал попадает в интервал [0,25 0,75), увеличить на единицу значение счетчика следования. Удвоить размер подынтервала, линейно расширив [0,25, 0,75) до [О, 1). Та есть установить Д = 2(7. — О, ) —,25) и Н= 2(Н вЂ” 0,25).
Шаги с 1 по 3 повторяются до тех пар, пока не будет обработано все сообщение. Вот что, по сути, выполняет данный алгоритм. Если новый подынтервал цели- ком попадает в интервал [О, 0,5) или [0,5, 1,0), алгоритм формирует велуший бит указывающий, в какую половину интервала попадает новый подынтервал, посте чего интервал удваивается, так что новый интервал отражает только неизвестную часть конечного интервала.
Посмотрим, как эта работает. Предположим, , что на первом шаге формируется подынтервал в верхней половине единичного интервала 660 Глава 20. Сжатие без потерь 20.4. Алгоритмы совпадения строк 661 0,67 1,О ье Выбирается ь ь выводятся 1; ' расширение, 1/2 0,33 0,67 Ье 1,0 ае Выбирается ак счетчик следования; расширение 2/5 О, [67 0,633 0,566 аэ Выбирается Ьл; выводится 10; расширение 0,667 0,133 0,10г = 0,5 0,01а= 0,25 пеппе«к Вееопипепбаппп 'т'.42»/е, 1990 (см., например, рис. 20.5). Таким образом мы узнаем, что конечный подынтервал также должен находиться в верхней половине единичного интервала, и поз поэтому старший бит конечного кода должен быть равен 1.
Котла этот бит становится известным, вторую половину единичного интервала можно проигнорировать, а по ва ь,аподынтервал удвоить для определения следующего бита кода. Если конечные точки текущего интервала близки к точке 0,5, но находя ,, н находятся по разные стороны от этой точки, тогда расположение следующего результата льтата еп1е не определено. Однако каким бы он ни был, следуюгцнй бит будет иметь противоположное значение.
Читатель может сам поэкспериментировать с несколькими зна чениями, чтобы убедиться, что это так. Поэтому алгоритм следит за еле у т за следующи:н битом и симметрично расширяет интервал вокруг значения 0,5, Пример На рис. 20.6 показан процесс кодирования, в котором используется то же самое сообщение «ЪаЪ», что и прежде. В данном примере интервал расширяется олин раз для каждого входного символа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
