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

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

Словарные методы отличаются друг от друга способом организации словаря, схемой поиска совпадений и видом ссылки на найденное совпадение [2.6, 2.9]. Впервые эти методы были описаны в работах А. Лемпела (Lempel A.) и Я. Зива (Ziv J.) [2.25, 2.26].

Первый вариант словарного алгоритма был описан в 1977 году [2.25] и был назван LZ77 по первым буквам фамилий авторов.

Классический алгоритм LZ-77 является родоначальником целого семейства схем, использующих алгоритмы со скользящим словарем или со скользящим окном. В скользящем окне помещается N символов, причем часть из них M N − n — уже закодированные символы, являющиеся словарем. Оставшаяся часть символов длины n существенно меньше количества символов, записанных в словаре, используется в буфере предварительного просмотра. Предположим, к текущему моменту закодировано m символов: s0, s1, s2, . . . , sm−1, часть из которых sm−M , . . . , sm−2, sm−1 записаны в словаре, а в буфере записаны ожидающие кодирования символы sm, sm+1, . . . , sm−1+n.

Принцип кодирования заключается в поиске самого длинного совпадения последовательности символов в строке буфера, начинающегося с символа sm, и закодированных фраз, размещенных в словаре. Эти фразы могут начинаться с любого символа sm−M , . . . , sm−2, sm−1 и выходить за пределы словаря, вторгаясь в область буфера.

Полученная в результате поиска фраза sm−i, sm−i+1, . . . , sm−i+j−1 кодируется с помощью двух чисел: i — смещения от начала буфера и j — длины совпадения последовательности символов. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.

Пример обработки информации в соответствии с алгоритмом LZ-77 приведен в табл. 4.7. Обработке подвергается фраза из 59 символов:

«на_дворе_трава_на_траве_дрова_на_дворе_трава_на_траве_дрова».

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

Установим длину буфера равной восьми символам, а размер словаря — больше длины кодируемой фразы.

Положим, для представления символов требуется использовать 1 байт. Следовательно, исходно фраза занимала 59 · 8 = 472 бита. Как следует из таблицы, при независимом кодировании значений коэффициентов i и j требуется использовать соответственно 5 битов и 4 бита. Тогда для представления кодированной информации требуется (5 + 4 + 8) · 20 = 340 битов.

Если же для кодирования коэффициентов i и j использовать наиболее простой алгоритм префиксного кодирования Шеннона–Фано, то можно подсчитать, что средняя длина кода для кодирования каждого коэффициента i составит 26/20 бита, а каждого коэффициента j — 22/20 бита. При этом для представления кодированной информации требуется (26/20 + 22/20 + 8) · 20 = 208 битов.

Как следует из табл. 4.7 алгоритм LZ-77 позволяет эффективно сжимать только сравнительно длинные последовательности, в которых имеет место повторение фраз.

Существует множество модификаций этого алгоритма. В частности, к алгоритмам семейства LZ-77 также относятся алгоритмы LZR [2.27], LZSS [2.28, 2.29].

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

Таблица 4.7. Пример работы алгоритма LZ-77

Алгоритмы LZB [2.30], LZH [2.31] представляют собой усовершенствования алгоритма LZSS с помощью использования кодов переменной длины.

Наиболее широкое распространение в компьютерных программах архивации получили в настоящее время так называемые комбинированные словарные алгоритмы семейства LZ-77, в которых статистический алгоритм устраняет недостатки способа кодирования базового словарного алгоритма.

Классический алгоритм LZ-78 [2.26], разработанный А. Лемпелом и Я. Зивом в 1978 году, положил начало другому семейству словарных алгоритмов. Алгоритм LZ-78 нередко уступает LZ-77 по эффективности кодирования, но превосходит его по скорости.

Алгоритм LZ-78 не использует скользящее окно, а в словарь помещают только «перспективные» с точки зрения вероятности последующего использования строки. При этом на каждом шаге в словарь вставляется новая фраза, пред-

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

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

Кодирующая схема порождает последовательность кодов фраз. Каждый код состоит из индекса (префикса) n «родительской» фразы и символа s.

Пример обработки информации в соответствии с алгоритмом LZ-78 приведен в табл. 4.8. Обработке подвергается та же последовательность из 59 символов, которая использовалась при пояснении работы алгоритма LZ-77. В начале обработки информации словарь пуст, номером «1» задается пустая фраза словаря.

Таблица 4.8. Пример работы алгоритма LZ-78

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

Если для представления символов требуется использовать 1 байт, то исходно фраза занимает 59 · 8 = 472 бита. Как следует из таблицы, при независимом кодировании значений префикса n требуется использовать 5 битов. Тогда для представления кодированной информации требуется (5 + 8) · 30 = 390 битов.

Если же для кодирования префикса n использовать алгоритм Шеннона–Фано, то можно подсчитать, что средняя длина кода для кодирования каждого коэффициента n составит 65/30 бита. При этом для представления кодированной информации требуется (65/30 + 8) · 30 = 305 битов.

Как следует из сравнения классических алгоритмов LZ-77 и LZ-78, последний в данном случае оказался менее эффективным. Однако алгоритм LZ-78 также имеет множество модификаций, позволяющих существенно повысить эффективность кодирования информации.

К этому семейству относятся алгоритмы LZW [2.32], LZC [2.33], LZT [2.34], LZMW [2.35], LZJ [2.36], LZFG [2.37].

Алгоритм LZW, реализованный Т. Уэлчем (Welch T.), получил широкое применение в компрессии графических компьютерных изображений (форматы GIF, TIFF) и для передачи по линиям связи (стандарт V.42bis [2.59]).

В этой модификации LZ-78 все символы алфавита входной последовательности предварительно заносятся в словарь, и результатом работы алгоритма является только выявление последовательности фраз словаря.

Пример обработки информации в соответствии с алгоритмом LZW приведен в табл. 4.9. Обработке подвергается та же последовательность из 59 символов, которая использовалась при пояснении работы алгоритмов LZ-77 и LZ-78. При этом предполагается, что исходно все символы входной последовательности, размер которых равен 8 битов (соответствующие числам от 0 до 255), занесены в словарь. Выявленные в процессе кодирования и вносимые в словарь фразы обозначим числами, начиная с 246. Ограничивая 9 битами закодированную информацию, обозначим код очистки словаря, например, числом 511.

Таблица 4.9. Пример работы алгоритма LZW

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

Таблица 4.9 (продолжение)

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

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

Так как для представления символов требуется использовать 1 байт, то исходно фраза занимает 59×8=472 бита. Как следует из таблицы, при независимом кодировании значений закодированных данных требуется использовать 9 битов. Тогда для представления кодированной информации требуется 9×37=333 бита.

Если же для кодирования данных использовать алгоритм Шеннона–Фано, то можно подсчитать, что средняя длина кода для кодирования каждого коэффициента n составит 119/37 бита и для представления кодированной информации требуется всего 119 битов.

4.2.7.Статистические методы моделирования дискретной информации

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

Статистические методы позволяют оценить вероятность появления в текущем контексте (последовательность символов, непосредственно предшествующих данному символу в информационном сообщении) символа или последовательности символов. Оценка вероятности определяет длину кода, который генерируется, как правило, с помощью префиксного или арифметического кодирования. Чаще

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

всего используются адаптивные статистические методы. Они различаются способом получения оценок условных вероятностей появления символов в различных контекстах. В настоящее время наиболее распространены четыре основных способа: PPM, DMC, CTW и метод нейронных сетей.

В методе PPM (Prediction by Partial Matching — предсказание по частичному совпадению), предложенном Дж. Клири (Cleary J.) и И. Уиттеном (Witten I.) и применяемом чаще всего при обработке текстовой информации, вероятность появления символа всегда оценивается в текущем контексте какого-то одного порядка. Порядком контекста называется длина последовательности символов в контексте.

Имеется множество реализаций метода РРМ [2.6, 2.9, 2.40–2.53, 2.90–2.93], которые, как правило, работают по приведенной ниже схеме.

Сначала для оценки вероятности появления символа используется контекст достаточно высокого порядка. Если кодируемый символ ранее в выбранном контексте не встречался, то кодирующее устройство генерирует код служебного символа перехода к контекстной модели следующего по убыванию порядка. Если новая модель также не обеспечивает получение вероятностной оценки, вновь генерируется служебный символ перехода к следующему меньшему по порядку контексту. Для гарантии завершения процесса переходов вводится дополнительная модель «минус 1-го» порядка, при котором появление всех символов информационного алфавита оценивается с равной вероятностью.

Предположим, что к текущему моменту передана последовательность из n символов источника информации x¯n1 = (x1, . . . , xn) и следует передать символ xn+1.

Для всех возможных значений символа xn+1 вычисляются условные вероятности появления этого символа при уже известном контексте, определяемом

последовательностью x¯n− = (xn−d+1, . . . , xn) наибольшей длины d, не пре-

n d+1

вышающей заданного значения D. При этом выбираемая последовательность

Значение символа xn+1 кодируется арифметическим кодом в соответствии с вычисленным условным распределением вероятностей и с учетом длины контекста d D.

Оценивается условная вероятность pˆ(a|¯c) появления символа xn+1a после кон- = (xn−d+1, . . . , xn) = ¯c. В случае, если эта условная вероятность оказывается равной нулю, pˆ(a|¯c) = 0, используется символ esc с вычисленной

определенным образом вероятностью его появления, и длина контекста d сокращается на единицу. Рекурсия продолжается до тех пор, пока символ не будет передан, либо длина контекста не окажется равной нулю. Это соответствует независимому кодированию символа xn+1 в соответствии с вычисленным по x¯n1 безусловным распределением вероятностей символов всего возможного алфавита X .

В том случае, когда символ xn+1 еще не встречался в последовательности x¯n1 , вновь передается символ esc, а также символ xn+1 в соответствии с равномерным распределением вероятностей на множестве неиспользованных символов алфавита источника.

Резюмируя вышеизложенное, можно сказать, что кодер PPM обеспечивает передачу очередного символа в соответствии с вероятностью, определяемой кон-

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

текстом наиболее возможной длины. Если же этот символ еще не встречался с таким контекстом, передается символ esc, контекст укорачивается на один символ. В конечном счете символ будет передан с учетом контекста меньшей или нулевой длины, либо как «новый символ», если он не встречался в уже закодированной последовательности.

Различные реализации алгоритма кодирования PPM связаны с принципами оценки условных вероятностей появления символов алфавита источника и escсимвола.

Так, в алгоритме PPMA [2.40] используются следующие выражения:

где Nn(x¯) — количество появлений последовательности x¯ в обработанной последовательности длины n.

При расчете величины условной вероятности pˆ(a|¯c) дополнительно введено так называемое «правило исключений», принцип использования которого заключается в следующем.

Предположим, что при кодировании информации на некотором шаге контекст на интервале d имеет вид ¯cd = (xn−d+1, . . . , xn), а следующий за ним символ a, причем сочетание ¯cd, a = (xn−d+1, . . . , xn, a) ранее не встречалось. Предположим также, что предыдущие появления последовательности ¯cd имели своими продолжениями символы b и c. В соответствии с алгоритмом передается символ esc, и контекст укорачивается на один символ. Следовательно, теперь контекстом будет ¯cd−1 = (xn−d+2, . . . , xn).

Правило исключений требует принять во внимание тот факт, что не все сочетания ¯cd−1 следует использовать для подсчета условной вероятности появления символа a, поскольку благодаря передаче символа esc кодер и декодер уже знают, что символы b и c, например, не могут следовать за контекстом ¯cd−1. По этой причине формулы (4.13) следует уточнить, подставив в них вместо Nn(¯c)

После этой корректировки знаменатели в соотношениях (4.13) уменьшатся, что приводит увеличению вероятностей и уменьшению затрат на их передачу.

Применим алгоритм PPMA к кодированию используемой в предыдущем разделе фразы из 59 символов:

«на_дворе_трава_на_траве_дрова_на_дворе_трава_на_траве_дрова».

Результаты работы алгоритма PPMA с параметром D = 8 по шагам приведены в табл. 4.10. Знак # в графе «контекст» соответствует контексту нулевой длины, штрихом помечены вероятности, подсчитанные с учетом исключений. В графе Nn(¯c) дано число появлений данного контекста, и если этот контекст укорачивался в процессе кодирования, то через запятую приведено число появлений укороченных контекстов. Предполагается, что возможно использование 256 символов и исходно их появление равновероятно.

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

Таблица 4.10. Пример работы алгоритма PPMA

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

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

Поясним характерные шаги алгоритма.

Шаг 1. Число Nn(¯c) = 0. Следовательно, pˆ(esc|¯c) = 1 и pˆ(a|¯c) = 1/256.

Шаг 2. Число Nn(¯c) = 1. Следовательно, pˆ(esc|¯c) = 1. Учитывая, что символ на шаге 2 отличается от символа на шаге 1, pˆ(a|¯c) = 1/255.

Шаг 9. Пробел встретился второй раз. Поскольку предшествующий ему символ «е» встречался только один раз, контекст имеет нулевую длину, и пробел имеет вероятность 1/(8+1)=1/9.

Шаг 10. Пробел является контекстом длины 1 по отношению к символу «т». После пробела встречался только символ «д». Необходимо передать символ «esc» при его вероятности, равной 1/2, и перейти к контексту нулевой длины. Но и при контексте нулевой длины символ «т» не встречался, и поэтому вновь необходимо передать символ «esc», вероятность которого равна 1/10. Однако ясно, что среди возможных символов не может быть символа «д», и вероятность символа «esc» повышается до 1/9’.

Шаг 22. Контекстом по отношению к символу «в» является «_тра». Эта комбинация уже встречалась, и за ней следовал символ «в». Таким образом, следующими символами могут быть либо символ «в», либо символ «esc» с равными вероятностями. По этой причине для передачи символа «в» требуется всего 1 бит.

Шаг 23. Символу «е» предшествует контекст «_трав». При появлении этого контекста за ним следовал другой символ — «а». Поэтому передается символ «esc» при вероятности 1/2. Контекст укорачивается — «трав»; за ним ранее следовал только символ «а». Вновь необходимо передать символ «esc» при его вероятности без учета правила исключений, равной 1/2. Но при передаче предыдущего символа «esc» значение «а» уже было уже исключено, а значит, вероятность символа «esc» равна 1 . Контекст вновь сокращается до «рав», и аналогично предыдущему вновь следует символ «esc» с вероятностью 1 . Контекст еще сокращается до «ав», вновь следует символ «esc» с вероятностью 1 . И, наконец,