(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy

Глава 4. Статистическая избыточность дискретизированных данных

ксимволу «е» контекст сократился до «в». Контекст «в» встречался два раза. Вероятность символа «esc» без учета правила исключений равна 1/3, а с учетом этого факта — 1/2 . Пустой контекст встречался 22 раза. Значит, вероятность pˆ(a|¯c) = 1/23, а с учетом двух исключений (символы «а» и «о») — 1/21 .

Используя значения pˆ(¯c) и pˆ(a|¯c), можно подсчитать количество битов, тре-

буемых для передачи данной информации:

" #

Вданном случае I = 34,47 + 149,83 = 185 битов (операция · — округление вверх).

Втакже широко применяемомалгоритме PPMD [2.41] используются следующие принципы оценки условных вероятностей появления символов алфавита источника и esc-символов:

где Mn(¯c) — число различных символов, появившихся в последовательности длины n вслед за контекстом ¯c.

Здесь также используется правило исключений (4.14), причем число различных символов Mn(¯c) также должно быть пересчитано с учетом правила исключений. Результаты работы алгоритма PPMD с параметром D = 8 по шагам приведены в табл. 4.11.

Таблица 4.11. Пример работы алгоритма PPMD

4.2. Виды статистического кодирования

Таблица 4.11 (окончание)

Рассчитанное с использованием соотношения (4.15) количество битов, требуемых для передачи данной информации, равно:

I = 23,78 + 158,32 = 183 бита.

Как следует из рассмотренных вариантов реализации метода РРМ, при их прак-

Глава 4. Статистическая избыточность дискретизированных данных

тической эффективности основным требованием является обеспечение хранения большого массива статистической информации, что вызывает необходимость использования значительного объема оперативной памяти.

Метод CTW (Context-Tree Weighting — взвешивание с использованием контекстных деревьев) [2.44–2.49] представляет собой одну из возможных альтернатив методу PPM, в этом методе оценка вероятности появления символа осуществляется с учетом весов контекстов, организованных в бинарное дерево.

Рассматриваются информационные источники, генерирующие двоичные последовательности длины N . Последовательность xN1 = x1x2 . . . xN генерируется с вероятностью pˆa(xN1 ). Для источника без памяти:

$N

Параметр θ (вероятность генерации 1), лежит в диапазоне от 0 до 1. Если последовательность содержит a нулей и b единиц, то pˆa(xN1 ) = (1 − θ)a · θb.

Кумулятивная вероятность Qa(xN1 ), используемая для арифметического кодирования, определяется следующим образом:

Рассмотрим оценку распределения вероятностей pˆe(xN1 ), сформулированную Кричевским и Трофимовым [2.60]. Распределение Кричевского–Трофимова (КТ-

При этом оценка вероятности двоичной последовательности xN1 = x1x2 · · · xN связана условными вероятностями так:

Из этих соотношений нетрудно вывести выражения для оценочной вероятности последовательности из a нулей и b единиц:

4.2. Виды статистического кодирования

Построение контекстного дерева

Контекстное дерево состоит из узлов, соответствующих контекстам s вплоть до заданной глубины D (память источника не более D). Корень контекстного дерева соответствует пустому контексту. Каждый узел s в контекстном дереве связывается с подпоследовательностью символов источника, которые появляются после контекста s.

Требуется оценить взвешенную вероятность символов pˆsw в каждом узле контекстного дерева. Статистика источника неизвестна. Если источник не обладает памятью, то хорошей оценкой вероятности будет оценка по КТ-распределению. В противном случае необходимо расщепление последовательности на две подпоследовательности нулей — 0s и единиц — 1s, и хорошей оценкой вероятности будет служить произведение взвешенных вероятностей pˆ0ws и pˆ1ws. Вероятность в каждом узле контекстного дерева подсчитывается как взвешенная сумма этих двух вариантов:

pˆsw = [pˆe(as, bs) + pˆ0ws · pˆ1ws]/2,

где as, bs — количество нулей и единиц в контексте s.

Полученные таким образом вероятности используются для арифметического кодирования данных источника.

Например, предположим, что глубина контекста D = 3 и пусть источник данных породил последовательность 010011011 после последовательности . . . 110:

Пустому контексту соответствуют все символы от первого до девятого; символы 3, 6, 7, 9 имеют контекст «1»; контексту «0» соответствуют символы с номерами 1, 2, 4, 5, 8; контекст «11» имеет символ номер 7 и т. д. (см. табл. 4.12). На рис. 4.4б приведено соответствующее контекстное дерево.

Таблица 4.12. Пример расчета вероятностей для контекстного дерева в методе CTW

Глава 4. Статистическая избыточность дискретизированных данных

Рис. 4.4. К построению деревьев последовательностей при кодировании методом CTW: а) структура дерева при расчете оценки pˆe(01110); б) структура контекстного дерева для последовательности . . . 110|010011011; в) принцип обновления контекстного дерева при появлении следующего символа источника, равного «1»

Для каждого узла контекстного дерева подсчитывается количество нулей (a) и единиц (b), им соответствующих. Например, узлу с контекстом «1» соответствуют символы с номерами 3, 6, 7, 9, среди которых два нуля и две единицы.

Далее для каждого узла контекстного дерева рекурсивно рассчитываются вероятности. Расчет начинается с конечных веток и идет по направлению к корню. Вероятность в конечных ветках рассчитывается как pˆe(a, b), а для остальных узлов используется формула взвешенной вероятности pˆsw. В табл. 4.12 приведены соответствия символов (по номерам от 1 до 9) возможным контекстам.

Алгоритм обновления контекстного дерева при появлении следующего символа рассмотрим на том же примере (110|010011011). Пусть следующий, десятый, символ источника — «1». Тогда нужно:

–увеличить bs;

–обновить значение pˆe(as, bs);

4.2. Виды статистического кодирования

–обновить pˆsw для всех контекстов вплоть до глубины D = 3: {011, 11, 1, пустой}.

Структура обновления контекстного дерева приведена на рис. 4.4в.

Метод DMC (Dynamic Markov Compression — динамическая марковская компрессия) значительно отличается от двух предыдущих методов. Он связан с теорией конечных автоматов и использует моделирование с конечным числом состояний [2.50, 2.51]. Благодаря простоте этот метод обладает высокой производительностью, но невысокой эффективностью при обработке последовательности достаточно сложных символов, используемых для описания большинства реальных информационных источников.

По этой причине чаще всего метод DMC используется при побитовом вводе информации, поскольку при этом нет проблем следующего состояния и существуют только два перехода от одного состояния в другое.

Марковская модель является таким источником информации, при котором

вкаждом состоянии она помнит только об одном предыдущем своем состоянии.

Вкачестве примера представим марковскую модель, при которой источник информации порождает последовательность двоичных чисел [2.61, 2.62]:

–за 0 следует 0 с вероятностью 3/4;

–за 0 следует 1 с вероятностью 1/4;

–за 1 следует 0 с вероятностью 1/3;

–за 1 следует 1 с вероятностью 2/3.

При этом первая цифра может быть «0» или «1» равновероятно (1/2). Эта модель может быть описана с помощью ориентированного графа, каждой дуге которого приписываются соответствующие вероятности перехода (см. рис. 4.5а).

По мере поступления информации марковская модель переходит из одного своего состояния в другое в соответствии с ранее прочитанными символами. Если завести счетчики переходов по каждой дуге, то можно получить оценки вероятностей переходов. Если переход из состояния A по дуге для символа «0» проходил N0 раз, а по дуге для «1» — N1, то оценки условных вероятностей переходов таковы:

где c — положительная константа.

Для файлов большого размера (намного больше значения c) выбор конкретного значения c существенной роли не играет. Для файлов малого размера при малом значении c модель быстрее оценит характеристики источника, однако при этом увеличивается вероятность неправильного прогноза, что является типичной проблемой адаптивных алгоритмов. Алгоритм динамической реализации диаграммы состояний поясняется на примере уже построенной модели, содержащей состояния A, B, С, D и E (рис. 4.5б).

Глава 4. Статистическая избыточность дискретизированных данных

Рис. 4.5. Марковская модель источника информации: а) ориентированный граф источника заданной модели последовательности; б) исходная модель динамической реализации диаграммы состояний; в) измененная модель с разделением состояния С на две части; г) начальная модель с одним состоянием; д) начальная модель, представляющая 8-битовые последовательности

Из диаграммы следует, что в состояние C ведут две дуги из A и B; из состояния С также выходят две дуги — в D и E.

Всякий раз, когда модель переходит в состояние C, теряется информация о контексте, т. е. неясно откуда пришли в это состояние — из A или B. Однако вполне может быть, что выбор следующего состояния (D или E) зависит от предыдущего состояния (A или B). Чтобы учесть эту зависимость, например в случае, когда переход из состояния А в С имеет большую частоту, чем переход из В в С, состояние C обычно разделяют на две части (С и С’).

Измененная модель приведена на рис. 4.5в. Значения счетчиков переходов из C в D или E делится между счетчиками C и C в новой модели пропорционально числу переходов из A в C и из B в C для старой модели. Следовательно, новая модель отражает степень зависимости между состояниями A, B и D, E. При этом выбор следующего состояния (D или E) не зависит от предыдущего состояния (A или B), но зависит от непосредственного предшественника A или B. В этом случае производится дополнительное деление состояний A, C и B, C. Следовательно, модель теперь будет учитывать эти зависимости. Процесс деления необходимо производить только в том случае, когда существует уверенность в наличии соответствующих зависимостей, иначе информация о контексте будет потеряна.

Поэтому желательно, чтобы деление состояния C проходило тогда, когда оба счетчика переходов A–C и B–C достаточно велики. Чем больше применяется делений состояний, тем больше увеличиваются зависимости, используемые моделью для прогноза.

4.2. Виды статистического кодирования

Для полного определения метода динамического сжатия Маркова необходимо определить начальную модель, которая затем будет изменяться в соответствии со спецификой поступающей информации. Простейшим случаем является модель с одним состоянием, приведенная на рис. 4.5г.

Несколько лучшее сжатие может быть достигнуто при побайтовом вводе информации при использовании начальной модели, представляющей 8-битовые последовательности в виде цепи, приведенной на рис. 4.5д. Впрочем, начальная модель не является особо решающей, поскольку DMC быстро приспосабливается к требованиям кодируемой информации.

Для оценки вероятностей появления символов на выходе информационного источника применяется искусственная нейронная сеть [2.52, 2.53].

Чаще всего используется многослойная нейронная сеть, обладающая одним нейроном выходного слоя на каждый символ информационного алфавита. На выходах этих нейронов формируются сигналы, определяющие вероятности появления различных символов в текущем контексте.

Преимуществом данного решения энтропийного кодирования является возможность адаптации системы к обрабатываемой информации с применением фиксированного объема памяти. Этот метод обладает высокой эффективностью, но очень низкой производительностью.

4.2.8. Контекстные методы энтропийного кодирования

Эта группа контекстных методов включает два алгоритма, которые рассматривают зависимости между последовательностью символов, предшествующих кодируемому (левосторонний контекст) и последовательность символов, следующих за кодируемым (правосторонний контекст). Первый из этих двух методов называется ассоциативным кодированием Буяновского (ACB) [2.54] и относится к поточным методам, т. е. он может применяться для кодирования данных, непрерывно порождаемых источником. Второй метод [2.55] основан на использовании преобразования Барроуза–Уиллера, он может применяться, если доступен весь объем кодируемой информации. Это самые современные методы, которые пока не получили заметного распространения из-за значительной сложности реализации, но имеют большие перспективы.

Ассоциативное кодирование Буяновского (ACB)

Алгоритм кодирования Буяновского поясняется на примере обработки битовой последовательности.

Предположим, что уже закодирована последовательность

.. . 111101011100001010010001010100101110

ипредстоит закодировать строку 0100010111. . . , обозначенную далее как «пакуемая строка». Закодированная последовательность представляет предысторию, пакуемая строка — постисторию:

. . . 111101011100001010010001010100101110|0100010111.. . (4.22)

Выпишем все подпоследовательности из предыстории, которые совпадают с первым и более начальными битами предыстории (отсчет битов ведется справа

4.2. Виды статистического кодирования

Затем этот список переупорядочивается в лексикографическом порядке постистории (в противоположном направлении — слева направо после «|», т. е. последовательность |110000. . . лексикографическибольшепоследовательности |001000. . . ):

В дальнейшем используются только две строки, примыкающие к пакуемой строке:

Код пакуемой строки состоит из трех частей.

Номер строки, максимально совпадающей с пакуемой строкой. В данном случае — 4. Этот номер кодируется любым эффективным префиксным или арифметическим кодом. В качестве эквивалента вероятности автор алгоритма предложил использовать длину совпадения строки предыстории пакуемой строки со строками предысторий из рассмотренного списка с соответствующей нормировкой. В данном случае: