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

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

Блоком данных будем называть некоторую конечную последовательность слов, выданных источником данных.

Целью задачи сжатия является замена данного блока данных А другим блоком В, по возможности меньшего размера, по которому можно бы было однозначно восстановить исходный блок данных. В этом случае коэффициентом сжатия называется отношение длины блока В (в битах) к длине блока А.

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

Доказательство. Рассмотрим все блоки А_i длины N. Таких блоков всего 2^N. Если предположить, что для всех этих блоков коэффициент сжатия для данного алгоритма сжатия меньше 1, то получим что среди всех соответствующих блоков В_i (число которыхтоже равно 2^N) должны обязательно найтись хотя бы два одинаковых. Т.о., мы получили, что для двух одинаковых блоков В_i существуют два различных исходных блока А_i, по этой причине однозначно восстановить исходные блоки по блокам В_iневозможно.

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

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

Определение. Код называется дешифруемым, если из любой последовательности допустимых слов без разделителей (=последовательности символов) можно однозначно выделить слова данной последовательности.

Префиксный код по определению является дешифруемым, но не наоборот. Действительно, бинарный код {{0},{0,1}} является дешифруемым (если последовательность бит, полученную при рассмотрении последовательности слов из данного алфавита, перевернуть в обратном порядке и, соответственно, перевернуть в обратном порядке слова данного кода, то мы получим обычный префиксный код), но префиксным данный код не является.

Код Левенштейна. Неравенство Крафта

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

Его идея довольно проста. Допустим, мы хотим записать код некоторого целого числа x. Запишем все его биты, начиная со старшего значащего. Перед ним запишем длину бинарного представления x (опять, начиная со старшего значащего бита). Перед получившейся последовательностью бит запишем длину длины числа x. И т.д. до тех пор, пока длина очередной длины не станет равной 2. Перед записью этой последней длины запишем 0, а перед ним запишем столько единиц, сколько чисел всего мы записали (имеется в виду само число, его длину, длину длины и т.д.) плюс 1.

Осталось заметить, что старший значащий бит любого положительного числа равен 1, поэтому его можно вообще не писать.

Восстановить исходную информацию можно в обратном порядке. Последовательность единиц в начале (терминирующаяся нулем) определяет количество частей в последующей записи числа. Первая часть состоит из одной цифры (плюс единица старшего разряда `в уме’). Значение первой части задает длину следующей. И.т.д. Последняя часть является требуемым числом.

Будем обозначать код Левенштейна числа x с помощью L(x). Тогда

L(0) = {0}

L(1) = {10}

L(2) = {11 0 0}

L(3) = {11 0 1}

L(4) = {111 0 0 00}

…

Заметим, что любой код, кроме кода нуля начинается с 1, поэтому если мы рассматриваем только положительные целые числа, то либо первую единицу можно вообще не писать, либо писать код числа x-1.

Оказывается, что код Левенштейна в некотором смысле оптимален.

Утверждение (неравенство Крафта). Для существования префиксного кода, состоящего из слов длин l₁,…,l_N необходимо и достаточно выполнения следующего неравенства

S₁^N 2 ^-^lⁱ £ 1

Доказательство.

(<=)

Перепишем неравенство Крафта в следующей форме

S₁^l^N s_k2 ^-^k £ 1

где s_k – количество слов длины k.

Рассмотрим множества слов Z_i , состоящие из всех слов длины i.

Возьмем Z₁ и оставим в нем s₁ любых слов (это возможно, т.к. по неравенству s₁£ 2).

Рассмотрим все Z_i (i>1) и исключим из них все слова, начинающиеся на слова, оставшиеся в Z₁. Исключенных слов будет, соответственно, s₁2^i-1. Из оставшихся в Z₂ 2²- s₁2^2-1 слов оставим s₂ слов. Это возможно, т.к.

s₁2 ^–1+ s₂2 ^–2 £ 1 => s₂£ 2²- s₁2^2–1

Рассмотрим все Z_i (i>2) и исключим из них все слова, начинающиеся на слова, оставшиеся в Z₂. Исключенных слов будет, соответственно, s₂2^i-2. Из оставшихся в Z₃ 2³- s₁2^3-1- s₂2^3-2 слов оставим s₃ слов. Это возможно, т.к.

s₁2 ^–1+ s₂2 ^–2+ s₃2 ^–3 £ 1 => s₃£ 2³- s₁2^3–1- s₂2^3–2

Т.о. на каждом шаге k мы рассматриваем все Z_i (i>k) и исключаем из них все слова, начинающиеся на слова, оставшиеся в Z_k. Исключенных слов будет, соответственно, s_k2^i-^k. Из оставшихся в Z_k₊₁ 2^k- s₁2^k-1- s₂2^k-2-…- s₂2^k-(^k-1) слов оставляем s_k слов. Это возможно, т.к.

s₁2 ^–1+ s₂2 ^–2+ s₃2 ^–3+…+ s_k2 ^–k £ 1 => s_k£ 2^k- s₁2^k–1- s₂2^k–2-…- s₂2^k-(k-1)

Т.о. мы построили префиксный код со словами требуемой длины.

(=>)

Пусть задан некоторый префиксный код. Рассмотрим все слова длины l_N, начинающиеся с каждого слова данного префиксного кода. По условию, все эти слова различаются. Тогда, их общее число равно S₁^N 2 ^l^{N –}^lⁱ (т.к. для каждого слова префиксного кода таких слов 2 ^l^{N –}^lⁱ). Но общее число слов длины l_N равно 2^l^N, откуда получаем

S₁^N 2 ^l^{N –}^lⁱ£2^l^N => S₁^N 2 ^-^lⁱ £ 1

Стоит задаться вопросом: а когда вышеуказанное неравенство превращается в равенство?

Определение (напоминание). Два слова a и b называются подобными, если либо a является префиксом b, либо b является префиксом a.

Лемма 1. Неравенство Крафта превращается в равенство для множества слов кода Z, тогда и только тогда, когда любое целое x подобно некоторому слову из Z.

Доказательство. Рассмотрим случай конечного множества слов Z.

(<=)

Пусть M=MAX(l_i)+1. Рассмотрим все слова длины M, начинающиеся с каждого слова данного префиксного кода. По условию, все эти слова различаются. Тогда, их общее число равно S₁^N 2 ^{M –}^lⁱ (т.к. для каждого слова префиксного кода таких слов 2 ^{M –}^lⁱ).

Т.к. никакое слово длины M не может быть префиксом какого либо слова из Z, то, по условию любое слово длины M имеет префикс, совпадающий с одним из слов из Z. Но общее число слов длины M равно 2^M, откуда получаем

S₁^N 2 ^{M –}^lⁱ=2^M => S₁^N 2 ^-^lⁱ = 1

(=>)

Если найдется целое число x, такое что оно не является подобным ни одному слову из Z, то все слова, начинающиеся со слова x не окажутся посчитанными в сумме S₁^N 2 ^{M –}^lⁱ, поэтому равенство не будет выполняться.

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

Т.о., в силу алгоритма раскодирования кода Левенштейна мы получаем, что для кода Левенштейна (в силу алгоритма для любого целого x оно либо является префиксом некоторого кода Левенштейна, либо некоторый код Левенштейна является префиксом x) неравенство Крафта превращается в равенство.

Оказывается, что неравенство Крафта верно не только для префиксных кодов, но и для всех дешифруемых кодов.

Лемма 2. Для слов длин l₁,…,l_N любого дешифруемого кода выполняется неравенство

S₁^N 2 ^-^lⁱ £ 1

Доказательство. Без доказательства.

Оказывается, что код Левенштейна обладает не только свойством `глобальной’ оптимальности (см. выше), но и локальной, т.е. поведение функции скорости роста длины бинарного представления кода числа x от самого числа нельзя принципиально улучшить.

Заметим, что длина бинарного представления числа x равна [log₂x] (имеется в виду собственно бинарное представление, без представления длины числа).

Везде далее если мы не указываем основание логарифма, то это – двоичный логарифм.

Определим число единичек в начале двоичного представления код Левенштейна числа x через log^*(x). Данная функция растет крайне медленно.

Итак,

|L(x)|=[log(x)]+ [log log (x)]+…+ [log(x)]^(m) + 1 + log^*(x)

здесь под [log(x)]⁽^m) имеется в виду m раз применение функции [log(*)].

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

Лемма 3. Для слов длин l₁, l₂,… любого дешифруемого кода K с бесконечным числом слов и для любого заданного целого p следующее неравенство будет выполняться для бесконечного числа слов:

|L(x)| ³ [log(x)]+ [log log (x)]+…+ [log(x)]^(p)

Доказательство. Допустим, это не так. Тогда начиная с некоторого x₀ для всех x>x₀

|L(x)| < [log(x)]+ [log log (x)]+…+ [log(x)]^(p)

но ряд

S _x0^¥ 2 ^–|^L(^x)| @ S _x0^¥1/x 1/log(x) …1/log⁽^p)(x)

расходится (по интегральному признаку: ò 1/x 1/log(x) …1/log⁽^p)(x) dx = log⁽^p+1)(x)), что сразу же противоречит неравенству Крафта.

Кодирование конечных вероятностных источников. Код Шеннона

Итак, у нас есть конечный вероятностный источник S. Т.е. он порождает слова a_i с вероятностью p_i. С помощью нашего дешифруемого префиксного взаимно-однозначного кодирования мы сопоставляем словам a_i код K(a_i). В результате мы можем оценить среднюю длину получившегося кода

C=S p_i |K(a_i)|

Введем понятие энтропии

H= -S p_i log p_i

Оказывается, что энтропия дает нижнюю оценку средней длине получившегося кода. Величина R=C-H называется избыточностью. Верна

Лемма 4. Избыточность дешифруемого кодирования неотрицательна.

Доказательство.

R=C-H=S p_i (|K(a_i)|+ log p_i)= -S p_i log(2^-|^K(^a^i)|/p_i)

Воспользуемся неравенство Иенсена для выпуклых вверх функций:

S p_ig(x_i)£ g(S p_ix_i) где S p_i=1

тогда имеем:

R= -S p_i log(2^-|K(aⁱ^)|/ log p_i)³ - log(S p_i 2^-|K(aⁱ^)|/ p_i)= - log(S 2^-|K(aⁱ^)|) ³ 0

Шенноном был предложен код, избыточность которого не превышает 1.

Переупорядочим слова, порождаемые источником S, в порядке убывания вероятностей их появления p_i. Т.о., мы будем иметь:

p₁£ p₂£…£ p_N

Определим суммы

s₁= 0

s₂= p₁

s₃= p₁+ p₂

_…

s_k= p₁+ p₂+…+ p_k-1

Для кода Шеннона в качестве K(a_i) будем брать первые é-log p_iù бит двоичного разложения числа s_k.

Например

p₁=0.5={0.1} é-log p₁ù =1

p₂=0.25={0.01} é-log p₂ù =2

p₃=0.125={0.001} é-log p₃ù =3

p₄=0.125/2={0.0001} é-log p₄ù =4

p₅=0.125/2={0.0001} é-log p₅ù =4

тогда

s₁=0.0={0.0} K(a₁)={0}

s₂=0.5={0.1} K(a₁)={10}

s₃=0.75={0.11} K(a₁)={110}

s₄=0.875={0.111} K(a₁)={1110}

s₅=0.125/2={1.1111} K(a₁)={1111}

Имеем

|K(a_i)| = é-log p_iù => |K(a_i)| ³ -log p_i => 2 ^|K(aⁱ^)| ³ 1/ p_i =>2 ^-|K(aⁱ^)| £ p_i

из чего сразу получаем, что один из первых |K(a_i)| бит разложения p_i отличен от нуля, а это гарантирует, что все s_iразличны, т.к. s_i₊₁отличается от s_iна p_i. Т.о., мы получили, что код Шеннона – префиксный.

Посчитаем среднюю длину кода Шеннона

C=S p_i |K(a_i)|= S p_i é-log p_iù

Избыточность

R=C-H=S p_i é-log p_iù +S p_i log p_i=S p_i( é-log p_iù +log p_i) £S p_i=1

Итак, мы доказали следующую лемму

Лемма 5. Избыточность кода Шеннона не превышает 1.

Код Хаффмана

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

Докажем начала следующую лемму.

Лемма 6. Пусть, как мы предполагали изначально, {p_i} представляют собой убывающую последовательность. Утверждается, что для кода с минимальной избыточностью среди всех префиксных кодов последовательность{|K(s_i)|} не убывает и для двух ее последних членов |K(s_N_-1)| и |K(s_N)| равны. Более того, последние члены последовательности с равными длинами можно переупорядочить так, чтобы два последних слова K(s_N_-1) и K(s_N) совпадали бы с точностью до последнего бита.

Доказательство.

1)Допустим, что для оптимального кода последовательность {|K(s_i)|} не является неубывающей, но тогда существуют i < j, такие что |K(s_i)|> |K(s_j)|. Поменяв местами коды слов a_i и a_j, получим, что длина кода уменьшится, что противоречит оптимальности кода.

2)Допустим, что |K(s_N_-1)| < |K(s_N)|. Из условия префиксности кода имеем, что ни один из K(s_i) не может быть префиксом K(s_N), но тогда мы можем отбросить последний бит из K(s_N), сохранив свойство префиксности кода. Получили противоречие с оптимальностью кода.

3)Рассмотрим K(s_N). Пусть слово K’(s_N) получено из K(s_N) путем замены последнего бита на противоположный. Допустим, что не нашлось K(s_i)= K’(s_N) (иначе все доказано). В таком случае мы можем отбросить последний бит из K(s_N), не нарушая префиксности кода, т.к., по условию, ни одно из слов длины меньше |K(s_N)| не может быть префиксом полученного слова. С другой стороны, полученное слово является префиксом только K(s_N).

Лекция 2

Алгоритмы сжатия данных. Форматы представления данных

Список литературы

Р.Е. Кричевский. Сжатие и поиск информации. М. Радио и связь. 1989.

Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. М. Диалог-МИФИ. 2002.

Гюнтер Борн. Форматы данных. Киев. Торгово-издательское бюро BHV. 1995.

Код Левенштейна. Неравенство Крафта

Везде далее если мы не указываем основание логарифма, то это – двоичный логарифм.

Итак,

|L(x)|=[log(x)]+ [log log (x)]+…+ [log(x)]^(m) + 1 + log^*(x)

здесь под [log(x)]⁽^m) имеется в виду m раз применение функции [log(*)].

|L(x)| ³ [log(x)]+ [log log (x)]+…+ [log(x)]^(p)

Доказательство. Допустим, это не так. Тогда начиная с некоторого x₀ для всех x>x₀

|L(x)| < [log(x)]+ [log log (x)]+…+ [log(x)]^(p)

но ряд

S _x0^¥ 2 ^–|^L(^x)| @ S _x0^¥1/x 1/log(x) …1/log⁽^p)(x)

Кодирование конечных вероятностных источников. Код Шеннона

C=S p_i |K(a_i)|

Введем понятие энтропии

H= -S p_i log p_i

Лемма 4. Избыточность дешифруемого кодирования неотрицательна.

Доказательство.

R=C-H=S p_i (|K(a_i)|+ log p_i)= -S p_i log(2^-|^K(^a^i)|/p_i)

Воспользуемся неравенство Иенсена для выпуклых вверх функций:

S p_ig(x_i)£ g(S p_ix_i) где S p_i=1

тогда имеем:

R= -S p_i log(2^-|K(aⁱ^)|/ p_i)³ - log(S p_i 2^-|K(aⁱ^)|/ p_i)= - log(S 2^-|K(aⁱ^)|) ³ 0

Шенноном был предложен код, избыточность которого не превышает 1.

p₁£ p₂£…£ p_N

Определим суммы

s₁= 0

s₂= p₁

s₃= p₁+ p₂

_…

s_k= p₁+ p₂+…+ p_k-1

Для кода Шеннона в качестве K(a_i) будем брать первые é-log p_iù бит двоичного разложения числа s_k.

Например

p₁=0.5={0.1} é-log p₁ù =1

p₂=0.25={0.01} é-log p₂ù =2

p₃=0.125={0.001} é-log p₃ù =3

p₄=0.125/2={0.0001} é-log p₄ù =4

p₅=0.125/2={0.0001} é-log p₅ù =4

тогда

s₁=0.0={0.0} K(a₁)={0}

s₂=0.5={0.1} K(a₁)={10}

s₃=0.75={0.11} K(a₁)={110}

s₄=0.875={0.111} K(a₁)={1110}

s₅=0.125/2={1.1111} K(a₁)={1111}

Имеем

|K(a_i)| = é-log p_iù => |K(a_i)| ³ -log p_i => 2 ^|K(aⁱ^)| ³ 1/ p_i =>2 ^-|K(aⁱ^)| £ p_i

Посчитаем среднюю длину кода Шеннона

C=S p_i |K(a_i)|= S p_i é-log p_iù

Избыточность

R=C-H=S p_i é-log p_iù +S p_i log p_i=S p_i( é-log p_iù +log p_i) £S p_i=1

Итак, мы доказали следующую лемму

Лемма 5. Избыточность кода Шеннона не превышает 1.

Код Хаффмана

Докажем начала следующую лемму.

Доказательство.

Последняя Лемма, фактически, дает алгоритм построения кода Хаффмана. Процедура имеет рекурсивный характер. Один шаг заключается в следующем. Упорядочим исходные слова в порядке убывания p_i – вероятностей появления соответствующих слов. Для случая оптимального кода два последних слова в этой последовательности, согласно Лемме, имеют равную длину кода и отличаются только на последний бит. Поэтому мы можем объединить их в одно псевдо-слово с суммарной вероятностью появления, равной сумме вероятностей появления двух исходных слов, и с кодом, состоящим из общих бит исходных слов (по утверждению Леммы, у этих кодов отличается лишь последний бит). Следует, конечно, запомнить, что коды двух исходных слов получаются из кода псевдо-слова добавлением в конец, соответственно, 0 и 1. Т.о. задача свелась к исходной.

Отметим, что один шаг алгоритма Хаффмана сводит задачу минимизации

S=S p_i |K(a_i)|

к задаче минимизации другой величины

S’=S p_i’ |K(a_i’)|

при этом

S- S’=p_N+p_N_-1

т.к. мы сократили длины двух последних слов на 1 бит, сопоставив им одно слово. Т.о., S и S’ отличаются на константу и задачи их минимизации эквивалентны.

Приведем пример построения кода Хаффмана. Пусть есть слова из исходного словаря с вероятностями {0.4, 0.2, 0.15, 0.1, 0.06, 0.05, 0.03, 0.01}.

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

0.4 0.4 0.4 0.4 0.4 0.4 0.6

0.2 0.2 0.2 0.2 0.25 0.35 0.4

0.15 0.15 0.15 0.15 0.2 0.25

0.1 0.1 0.1 0.15 0.15

0.06 0.06 0.09 0.1

0.05 0.05 0.06

0.03 0.04

0.01

При восстановлении требуемого кода мы сопоставляем двум последним пседо-словам коды 0 и 1, соответственно. Далее, от каждого псевдо-слова текущего словаря по направлению, обратному движению стрелок, мы переходим к предыдущему словарю. При этом, если с данной псевдо-слово приходит одна стрелка, то мы просто переносим текущий код на предыдущее псевдослово. А если стрелок две, то мы переносим текущее псевдо-слово, дописывая в его конец 0 и 1, соответственно.

0 0 0 0 0 0 1

10 10 10 10 10 11 0

110 110 110 110 111 10

1110 1110 1110 1111 110

11110 11110 11111 1110

111111 111111 11110

1111101 111110

1111100

Получили, что теперь средняя длина одного слова есть

0.4*1+ 0.2*2+ 0.15*3+ 0.1*4+ 0.06*5+ 0.05*6+ 0.03*7+ 0.01*7=2.53

Исходных код требовал 3 бита на слово. Энтропия:

H=-S p_i log p_i≈2.41373

Избыточность:

C-H ≈0.11627

Сжатие с помощью стопки книг

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

Код K называется монотонным, если функция K(x) является монотонно возрастающей.

Пусть задан некоторый произвольный монотонный префиксный код K. Если размер исходного словаря не ограничен, то, например, можно использовать код Левенштейна (легко показать, что код Левенштейна - монотонен). Отметим, что из монотонности кода следует, что функция |K(x)| тоже монотонна (не строго).

На источнике и приемнике данных заведем одинаковою таблицу T, в которой, изначально, в ячейке i располагается текущее слово словаря a_i . Будем полагать, что слову, расположенному в ячейке таблицы T с номером i сопоставляется код K(i). Т.о. длина кода всегда будет монотонной функций от номера ячейка. При передаче очередного слова будем искать это слово в таблице (допустим, слово размещается в ячейке с номером i) и передавать его код, определенный на текущий момент (т.е. K(i)). После этого, слово из ячейки i переносится в первую ячейку таблицы, а часть таблицы с первой по i-1 позицию, соответственно, сдвигается на одну позицию впрваво:

tmp=T[i];

for(j=i-1;j>=0;j++)T[j+1]=T[j];

T[0]=tmp;

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

Отметим, что прямая реализация `стопки книг’ оказывается весьма дорогой, т.к. если реализовать ее в виде массива, то каждая из операций поиска слова в таблице и переноса слова в начало таблицы будут занимать время O(N), где – N размер массива.

`Стопку книг’, например, можно реализовать с помощью двух сбалансированных бинарных деревьев, в которых дополнительно хранятся информация о порядковом номере каждого элемента (напомним, что такую информацию можно хранить, поместив в каждую вершину число, равное количеству вершин дерева в левом поддереве, выходящем из данной вершины). Первое дерево будет задавать саму таблицу, используемую в алгоритме, а второе дерево будет содержать уже появившееся слова в лексикографическом порядке. Т.о. каждому слову будет соответствовать по одной вершине в каждом дереве. Между соответствующими вершинами должны быть ссылки друг на друга.

Если появляется очередное слово, то мы ищем его во втором дереве (в силу упорядоченности слов, это можно сделать за O(logN) операций). Если слово найдено в дереве, то берем соответствующую вершину в первом дереве и перемещаем ее на первую позицию в дереве (т.е. исключаем вершину из первого дерева и помещаем в самую левую позицию, проводя все необходимые балансировки). Это также потребует O(logN) операций. Если слово не найдено в дереве, то вставляем его во второе дерево и соответствующую вершину вставляем на первую позицию в первом дереве.

Т.о., кодирование методом стопки книг можно реализовать за время O(logN), где N – количество слов входной последовательности.

Автоматное сжатие

Напомним, что Конечным автоматом ранее мы называли объект, состоящий из пяти множеств:

Q – конечное множество состояний;

AÌ Q – подмножество принимающих состояний;

q₀Î Q – начальное состояние;

S – конечный входной алфавит;

d: Q ´ A ® Q – функция перехода.

Добавим к этому понятию функцию g: : Q ´ A ® {0,1}^*, сопоставляющую состоянию и символу некоторую, возможно пустую, последовательность букв выходного алфавита (т.е., в нашем случае, последовательность из нулей и единиц). Будем называть эту функцию выходной.

Предполагается, что функция перехода вычисляется за время O(1), т.к. обычно она задается таблицей.

Рассмотрим следующий алгоритм. Пусть источник данных выдает последовательность букв {x[i]}. Выделим из нее подряд идущие подпоследовательности букв X_i={x[n_i+1],…, x[n_i₊₁]}, такие что каждая подпоследовательность это - кратчайшая подпоследовательность, начинающаяся с x[n_i+1], которая не совпадает ни с одной X_j, j<i. Например:

0 01 1 10 11 111 1111 101 1011

Заметим, что для каждого слова длины больше 1 если из слова отбросить последнюю букву, то остаток должен обязательно встретиться среди предыдущих слов. Пусть функция p(i) задает номер слова, равного слову X_i без последней буквы. Имеем: p(i)<i.

Тогда для кодирования каждого слова этой последовательности X_i достаточно указывать значение функции p(i) и последнюю букву слова X_i, т.е.. Будем кодировать слово X_i с помощью числа

K(X_i ) = p(i)|S| + x[n_i₊₁]

Здесь мы предполагаем, x[n_i₊₁] задается своим порядковым номером (начиная с 0), |S| - количество символов в алфавите. Имеем

K(X_i ) = p(i)|S| + x[n_i₊₁] ≤ (i-1) |S| + |S|-1=i |S| -1

Т.о. для задания K(X_i ) достаточно élog(i |S|)ù бит. Суммарный размер получившегося кода равен для случая, когда мы имеем M подслов

L(x)=S₁^M+1 élog(i |S|)ù ≤ M log(M |S|)(1+o(1)) (по интегральному признаку)

Введем понятие продукционной сложности слова x. Продукционной сложностью слова x назовем максимально возможное количество различных подслов, на которое можно разбить слово x. Продукционная сложность не меньше числа подслов {X_i}, используемых выше. Тогда сразу получаем

L(x) ≤ C(x) log(C(x) |S|)(1+o(1))

Можно доказать, что для любого алгоритма кодирования, основанного на конечных автоматах данное соотношение также выполняется.

Осталось показать, что приведенный алгоритм можно реализовать с помощью конечных автоматов.

Пусть выходная функция при поступлении каждого символа выдает пустую строку, если очередное слово X_i еще не выведено полностью, иначе она должна выдавать K(X_i ).

Пусть в данный момент уже выданы коды слов X₁ , …, X_i_-1 и мы получаем от источника очередной символ x_k.

Состояние системы будет характеризоваться номером l слова {x[n_i_-1+1],…, x[n_k-1]} в последовательности подслов { X_j }.

Для быстрого определения номера слова {x[n_i_-1+1],…, x[n_k]}= { X_l, x[n_k]} в последовательности подслов { X_j } заведем бинарное дерево, каждая ветка которого задает некоторое слово X_j. В каждое вершине этого дерева будет также хранить номер слова, задаваемого вершинами дерева из ветки, завершающейся на эту вершину. В каждый момент мы будем хранить текущую вершину, задающую состояние системы.

Тогда если у текущей вершины есть потомок со значением x[n_k], то этот потомок станет следующим состоянием системы и функция g будет выдавать пустую последовательность символов. Если же такого потомка нет, то функция g должна подать на выход значение K(X_i ) (это не составляет проблем, т.к. значение функции p(i) хранится в текущей вершине), после чего состояние системы должно перейти к пустому слову.

Легко увидеть, что вычисление функций d, g будет требовать времени O(1).

Лекция 3

Алгоритмы сжатия данных. Форматы представления данных

Список литературы

Р.Е. Кричевский. Сжатие и поиск информации. М. Радио и связь. 1989.

Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. М. Диалог-МИФИ. 2002.

Гюнтер Борн. Форматы данных. Киев. Торгово-издательское бюро BHV. 1995.

Алгоритмы LZ

Алгоритмы Зива-Лемпела (Ziv-Lempel) появились во второй половине 70-х гг. в результате работ Зива и Лемпела. Можно говорить о двух подклассах этих алгоритмов – LZ77 и LZ78.

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

Автоматное сжатие. Семейство алгоритмов LZ78 (со словарем в виде дерева)

Напомним, что Конечным автоматом ранее мы называли объект, состоящий из пяти множеств:

Q – конечное множество состояний;

AÌ Q – подмножество принимающих состояний;

q₀Î Q – начальное состояние;

S – конечный входной алфавит;

d: Q ´ A ® Q – функция перехода.

Предполагается, что функция перехода вычисляется за время O(1), т.к. обычно она задается таблицей.

0 01 1 10 11 111 1111 101 1011

K(X_i ) = p(i)|S| + x[n_i₊₁]

K(X_i ) = p(i)|S| + x[n_i₊₁] ≤ (i-1) |S| + |S|-1=i |S| -1

L(x)=S₁^M+1 élog(i |S|)ù ≤ M log(M |S|)(1+o(1)) (по интегральному признаку)

L(x) ≤ C(x) log(C(x) |S|)(1+o(1))

Можно доказать, что для любого алгоритма кодирования, основанного на конечных автоматах данное соотношение также выполняется.

Осталось показать, что приведенный алгоритм можно реализовать с помощью конечных автоматов.

Пусть в данный момент уже выданы коды слов X₁ , …, X_i_-1 и мы получаем от источника очередной символ x_k.

Легко увидеть, что вычисление функций d, g будет требовать времени O(1).

Данный алгоритм был опубликован в 1978г. Он стал основой большого семейства алгоритмов сжатия.

Семейство алгоритмов LZ77 (с использованием исходных данных вместо словаря)

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

Источник выдает данные в виде последовательности символов. В данном алгоритме используется окно входных данных длины N символов. Из них W символов относятся к уже закодированной части данных (т.е. их код уже записан в выходной поток), а стальные– к незакодированной. Пусть на входе подается последовательность символов s_i. Пусть символы s_t_-_W,… , s_t_-1 уже закодированы.

Для нахождения продолжения кода последовательности ищется подстрока { s_t, s_t₊₁,… , s_t₊_k} (k< N-W ) максимальной длины, совпадающая с некоторой подпоследовательностью символов, которая расположена в данном окне и находится до подстроки { s_t, s_t₊₁,… , s_t₊_k}.

Более формально. Ищется максимальное k< N-W, такое что существует i (t-W ≤ i < t), для которого строки { s_t, s_t₊₁,… , s_t₊_k} и { s_i, s_i₊₁,… , s_i₊_k} совпадают.

На выход подается смещение к найденной строке (= t-i ), длина найденной строки (= k ) и символ s_t₊_k+1. Если найденных строк несколько, то берется строка с минимальным значением смещения t-i. Смещение 0 можно зарезервировать для признака конца блока.

Пример. Длина окна=7.

папа_у_васи_силен_в_математике

папа_у_васи_силен_в_математике

1 0 п

папа_у_васи_силен_в_математике

1 0 а

папа_у_васи_силен_в_математике

2 2 _

папа_у_васи_силен_в_математике

1 0 у

папа_у_васи_силен_в_математике

2 1 в

папа_у_васи_силен_в_математике

4 1 с

папа_у_васи_силен_в_математике

1 0 и

папа_у_васи_силен_в_математике

5 1 с

папа_у_васи_силен_в_математике

1 0 и

папа_у_васи_силен_в_математике

1 0 л

папа_у_васи_силен_в_математике

1 0 е

папа_у_васи_силен_в_математике

1 0 н

папа_у_васи_силен_в_математике

6 2 _

папа_у_васи_силен_в_математике

1 0 м

папа_у_васи_силен_в_математике

1 0 а

папа_у_васи_силен_в_математике

1 0 т

папа_у_васи_силен_в_математике

1 0 е

папа_у_васи_силен_в_математике

4 3 и

папа_у_васи_силен_в_математике

1 0 к

папа_у_васи_силен_в_математике

6 1 е

Итого 20 записей, в каждой из которых 3 бита отводится на смещение + 3 бита отводим под буфер предварительного просмотра (вообще говоря, его длину можно было сделать и больше) + 8 бит на символ = 14 бит.

Итого код занимает 14*20=280 бит. Против 30*8=240 бит в исходной строке. Т.о. сжатия мы не получили (коэффициент сжатия > 1). В реальности этот алгоритм, действительно, плохо работает на небольших последовательностях данных.

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

Алгоритм LZSS (=LZ77+признак прямой записи символа)

Простейшей модификацией алгоритма LZ77 является алгоритм LZS, в котором перед каждым записываемым кодом пишется бит, указывающий на то, что далее будет следовать либо просто один символ, либо код, аналогичный вышеописанному. Т.о., в вышеприведенном примере на каждый код добавляется 1 бит, но в ситуациях, когда очередной символ в последовательности данных ранее не встречался код сокращается на 6 бит (смещение и длина не пишутся). Итого, предыдущий пример будет выглядеть следующим образом

папа_у_васи_силен_в_математике

1 п

папа_у_васи_силен_в_математике

1 а

папа_у_васи_силен_в_математике

0 2 2 _

папа_у_васи_силен_в_математике

1 у

папа_у_васи_силен_в_математике

0 2 1 в

папа_у_васи_силен_в_математике

0 4 1 с

папа_у_васи_силен_в_математике

1 и

папа_у_васи_силен_в_математике

0 5 1 с

папа_у_васи_силен_в_математике

1 и

папа_у_васи_силен_в_математике

1 л

папа_у_васи_силен_в_математике

1 е

папа_у_васи_силен_в_математике

1 н

папа_у_васи_силен_в_математике

0 6 2 _

папа_у_васи_силен_в_математике

1 м

папа_у_васи_силен_в_математике

1 а

папа_у_васи_силен_в_математике

1 т

папа_у_васи_силен_в_математике

1 е

папа_у_васи_силен_в_математике

0 4 3 и

папа_у_васи_силен_в_математике

1 к

папа_у_васи_силен_в_математике

0 6 1 е

Итого код занимает 280+20-6*13=222 бит. Против 30*8=240 бит в исходной строке. Т.о. коэффициент сжатия =222/240.

Алгоритм LZH (=LZ77+кодирование длин и смещений алгоритмом Хаффмана)

Алгоритм LZH является естественной модификацией алгоритма LZ77. В нем используется код Хаффмана для сжатия смещений и длин повторяющихся последовательностей, появляющихся в алгоритме LZ.

Алгоритм Deflate (вариант LZH, использующийся в PKZIP)

Известный архиватор PKZIP использует некоторую модификацию алгоритма LZH. Дадим лишь общее описание данного алгоритма, не вдаваясь в подробности.

Каждая последующая порция кода в нем записывается либо в виде {длина, смещение,символ} либо в виде {символ}, где под символом подразумевается 8-битное слово. Для объединения этих двух форм записи вводится алфавит, состоящий из 286 символов. Первые 256 символов отводятся под кодирование одного 8-битного слова, код 256 отводится под признак конца блока, а символы с кодами от 257 до 285 – под кодирование длины. Естественно, что данный символ имеет длину более 8 бит.

Т.о. если требуется напрямую закодировать одно 8-битное слово, то пишется символ с кодом, равным значению данного 8-битного слова. Если требуется задать ссылку на уже встретившийся кусок кода, то сначала записывается длина этого куска. При этом, для длин 3,4,…,10 используются коды 257,258,264. Если требуется закодировать длину 11 или 12, то записывается код 265, после чего дописывается еще один дополнительный бит, уточняющий значение длина (0 соответствует длине 11, а 1 – длине 12). Все дальнейшие кодировки длин строятся аналогичным образом: число из созданного выше алфавита задает диапазон значений длины, а последующие дополнительные биты уточняют длину. Количество дополнительных бит определяется значением символа из созданного алфавита, называемого, в этой ситуации базой.

Итак, длина кодируется в виде базы и некоторого количества дополнительных бит, число которых задается значением базы. Смещение кодируется аналогичным способом: в виде базы и некоторого количества дополнительных бит.

Наконец, полученные выше коды сжимаются, если это эффективно, либо фиксированным кодом Хаффмана (сам код задается заранее, т.е. является стандартным), либо классическим кодом Хаффмана, требующим передачи частот появления различных символов во входном потоке.

Для фиксированного кода используется код, в котором для кодирования слов с номерами от 0 до 143 используется 8 бит, от 144 до 255 – 9 бит, от 256 до 279 – 7 бит, от 280 до 287 – 8 бит.

Для классического кода Хаффмана перед самим кодом записывается таблица данного кода (на самом деле, при ее написании также используется сжатие методом Хаффмана).

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

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

В качестве хеш-функции используется функция, которая может быть посчитана при вводе каждого последующего символа по предыдущему значению функции и по значению нового символа:

int hash(int LastValue, unsigned char c)

{

return ((LastValue<<H_SHIFT)^c)&HASH_MASK;

}

Легко увидеть, что значение данной хеш-функции не может превзойти HASH_MASK.

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

Одним из вариантов улучшения данного алгоритма является вариант ``ленивого’’ сравнения. Для него мы сначала находим наиболее длинное встретившееся слово, совпадающее со словом, начинающимся на символ s_t , затем сразу находим наиболее длинное встретившееся слово, совпадающее со словом, начинающимся на символ s_t₊₁. Если второе слово оказалось длиннее, то символ s_t выводится в выходной поток как просто символ и процедура повторяется для s_t₊₁.

Арифметическое сжатие

Арифметическое сжатие основано на весьма красивой идее. Пусть на входе нашего алгоритма подаются символы входной последовательности {a_i}, появляющиеся с вероятностями {p_i} (i=1,…,N). Под символами входной последовательности будем подразумевать натуральные числа от 1 до M.

Разобьем полуинтервал [0,1) на интервалы с длинами p_iи сопоставим первому символу из входной последовательности a₁ интервал с номером a₁ – [x₁,y₁).

Разобьем далее полуинтервал [x₁,y₁) на интервалы с длинами (y₁- x₁)p_iи сопоставим второму символу из входной последовательности a₂ интервал из последнего разбиения с номером a₂ – [x₂,y₂].

И.т.д. На каждом шаге разбиваем полуинтервал [x_i_-1,y_i_-1) на интервалы с длинами (y_i_-1– x_i_-1)p_iи сопоставляем очередному символу из входной последовательности a_i интервал из последнего разбиения с номером a_i – [x_i,y_i).

Кодом всей последовательности исходных символов является наикратчайшее число в двоичной системе представления изо всех чисел, находящихся в полуинтервале [x_N,y_N).

Легко увидеть, что длина конечного интервала равна |x_N,y_N|=П p_i. Тогда, если |x_N,y_N|≥2^-^K, то на полуинтервале [x_N,y_N) обязательно найдется число, в двоичной системе представления которого после K-ой цифры после запятой идут лишь нули.

Действительно, если для числа x_N после K-ой цифры после запятой идут лишь нули, то все доказано. Иначе рассмотрим K первых цифр после запятой двоичного представления числа x_N и к получившемуся числу x_N’ прибавим 2^-^K. Имеем: x_N -x_N’>2^-^K, следовательно x_N >x_N’+2^-^K, а в силу того, что |x_N,y_N|≥2^-^K плучаем: x_N’< y_N. Что и требовалось доказать.

Т.о., для случая |x_N,y_N|=2^-^K получаем, что длина кода

L= -log|x_N,y_N|=-log П p_i= -S₁^N log p_i.

Если мы имеем на входе N символов, то в качестве вероятностей можно рассмотреть величины p_j=s_j/N, где s_j – количество появлении символа j во входном потоке данных. Тогда длину кода можно выписать иначе:

L = -S₁^M s_jlog p_j.

И для средней длины кодирования одного символа получаем:

L/N = -S₁^M s_j/N log p_j= -S₁^M p_j log p_j= H

Т.е. в случае |x_N,y_N|=2^-^K в точности достигается значение энтропии.

Легко увидеть, что в произвольном случае избыточность не превышает 1/N. А это существенно лучше, чем в алгоритме Хаффмана, где максимальная избыточность может быть сколь угодно близкой к 1 (с одной стороны, см. Пример, а с другой – больше 1 она быть не может, т.к. существует код Шеннона, избыточность которого не превышает 1).

Пример. Во входной последовательности данных символ a встречается 1 раз, а символ b встречается N-1 раз. Код Хаффмана требует 1 бит для кодирования одного символа.

Длина кода L=N. Средняя длина одного символа =1.

Энтропия

H=-(N-1) /N log((N-1)/N)-1/N log(1/N)=- (N-1)/N log(1-1/N)) + 1/N log(N) @

@(N-1)/N²+ 1/N log(N) @ 1/N log(N)® 0 (N®¥)

Избыточность H-L @ 1- 1/N log(N)® 1 (N®¥)

Закодируем последовательность {a,b,…,b} (b встречается N-1 раз)методом арифметического сжатия.

Символ a дает интервал [1/N, 1).

Символ b дает интервал [1/N,1/N+((N-1)/N)²).

…

Символ b дает интервал [1/N,1/N+((N-1)/N)^N).

Лекция 4

Алгоритмы сжатия данных.

Список литературы

Р.Е. Кричевский. Сжатие и поиск информации. М. Радио и связь. 1989.

Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. М. Диалог-МИФИ. 2002.

Гюнтер Борн. Форматы данных. Киев. Торгово-издательское бюро BHV. 1995.

Адаптивный алгоритм Хаффмана

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

Идея адаптивного алгоритма Хаффмана логично вытекает из исходного алгоритма. Вместо того, чтобы хранить таблицу появлений различных символов, давайте сделаем ее динамической. В начальный момент можно задать все вероятности равными, т.е. в таблице частот появлений символов в каждую ячейку мы можем поместить 1. Далее, при поступлении каждого следующего символа мы

1. выводим его код Хаффмана в соответствии с деревом кода Хаффмана

2. увеличиваем на 1 число появлений данного символа в таблице частот появлений символов

3. модифицируем дерево Хаффмана в соответствие с новой таблицей частот

Разархивацию данных производим аналогично (важно, что дерево Хаффмана модифицируется уже после занесения кода символа в выходной поток данных, поэтому при разархивации мы сначала извлекаем символ, а потом модифицируем дерево Хаффмана).

Данный алгоритм слишком медленно работает. Но его несложно модифицировать так, чтобы процедура исправления дерева (только она тормозит процесс) выполнялась бы достаточно быстро.

Напомним приведенный ранее пример построения кода фиксированного Хаффмана для случая 100 входных символов. Пусть есть слова из исходного словаря с количеством их появлений {40, 20, 15, 10, 6, 5, 3, 1}.

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

40 40 40 40 40 40 60

20 20 20 20 25 35 40

15 15 15 15 20 25

10 10 10 15 15

6 6 9 10

5 5 6

3 4

Пусть на данный момент (введено 100 символов) мы имеем указанное дерево. Пусть мы получили еще один символ во входом потоке данных и пусть, для определенности, это – самый редко встречающийся символ. Покажем, как модифицировать построенное дерево для новых вероятностей.

Итак, мы добавляем 1 к соответствующему числу в первом столбце и, соответственно, рекурсивно модифицируем значение родительской вершины:

40 40 40 40 40 40 61

20 20 20 20 25 35 40

15 15 15 15 20 25

10 10 10 16 15

6 6 10 10

5 5 6 ???

3 5

Данное дерево не является деревом Хаффмана, но в ситуации, когда над исправленным числом стоит число не меньше исправленного ничего менять вообще не нужно, т.к. условие упорядоченности столбцов на рисунке сохраняется.

Если это не так (четвертый столбец слева в примере), то нужно поменять местами измененную вершину v’= v+1 (здесь и далее в формулах вершина и ее значение будут отождествляться) с самой верхней вершиной со значением, равным v (числа во всех вершинах целые, из чего следует что после обмена местами указанных вершин, над новой позицией вершины стоит число не менее v):

40 40 40 40 40 40 61

20 20 20 20 25 36 40

15 15 15 16 20 25

10 10 10 15 16

6 6 10 10

5 5 6

3 5

Объясним, почему должна произойти именно эта замена. Пусть длина кода для измененной вершины v равна m, длина кода для вершины, с которой мы хотим поменять ее местами, равна l. Тогда уменьшение длины суммарного кода при перестановке данных вершин равно

D= ((v+1)m+ vl) - ((v+1)l+ vm) =(v+1)(m-l) – v(m-l)=m-l

Т.о. для обмена нам следует выбрать вершину с минимальным l среди вершин с длиной кода равной v.

Т.к. при обмене местами двух вершин смещаться мы будем только вверх, то суммарное количество операций по обмену местами вершин не будет превышать M, где M =количеству слов в исходном словаре. Т.о. максимальное время, затрачиваемое на кодирование одного слова, равно O(M) .

Контекстное сжатие

Идея метода появилась в публикации в 1981г.

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

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

Действительно, например, если мы знаем, что декодируем текст русского языка, то количество букв, которые могут следовать после строки `строк’ не так уж и велико, чем можно воспользоваться при сжатии текста.

Контекстом символа x_i будем называть последовательность символов, предшествующих x_i (вообще говоря, существуют левосторонние и правосторонние контексты; мы будем пользоваться лишь левосторонними контекстами).

Контекстом порядка N символа x_i будем называть последовательность из N символов, предшествующих x_i : { x_i_-_N,…, x_i_-1}. Контекстом моделированием порядка N будем называть построение таких моделей, которые для оценки появления очередного символа используют контексты порядка не более чем N.

Конкретные контексты, относящиеся к очередному символу из входной последовательности данных, принято называть активными контекстами.

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

1. как выбирать оптимальный порядок контекста для оценки вероятности появления конкретного символа

2. что делать, если данный контекст еще ни разу не появлялся

С точки зрения проблемы 1 существует подразделение методов контекстного моделирования на чистые методы и смешанные. Под чистыми методами подразумевается, что используются контексты только одного порядка. Под смешанными методами подразумевается, что выполняется т.н. процесс смешивания, в котором суммарная вероятность появления символа оценивается сразу по нескольким контекстам данного символа.

Будем обозначать P_i(x_i) оценку вероятности появления символа x_i в позиции i входных данных. Оценку именно этой величины нам надо получить.

Простейший алгоритм смешивания представляется следующей формулой P_i(x_i)=S_l=0^Nw(l)P(x_i|{ x_i_-_l ,…, x_i_-1 })

где P(x_i|{ x_i_-_l ,…, x_i_-1 }) - вероятность появления символа x_i в позиции i после подпоследовательности { x_i_-_l ,…, x_i_-1 }, т.е. условная вероятность появления символа x_i (при i=0 рассматривается просто вероятность появления символа x_i , т.е. безусловная вероятность появления). w(l) представляют собой некоторые веса.

Условная вероятность вычисляется по следующей формуле

P(x_i|{ x_i_-_l ,…, x_i_-1 }) = P({ x_i_-_l ,…, x_i_-1, x_i }) / P({ x_i_-_l ,…, x_i_-1 })=

=S({ x_i-l ,…, x_i-1, x_i }) / S({ x_i-l ,…, x_i-1 })

где S({ x_i_-_l ,…, x_i_-1, x_i }) – число появлений последовательности { x_i_-_l ,…, x_i_-1, x_i } во входном потоке данных.

Приведенный алгоритм вычисления вероятностей является примером явного смешивания. Кроме этого, существует понятие неявного смешивания. При использовании контекстного моделирования с неявным смешиванием в выходной алфавит добавляется дополнительный символ – символ ухода. Для данного текущего символа x_i оценка вероятности его появления вычисляется исходя из контекста максимального порядка N . Если данный контекст еще не встречался, то на выход выдается символ ухода и происходит попытка оценить вероятность появления символа исходя из модели порядка N-1. Так порядок понижается до того момента, пока не станет возможным оценить вероятность появления символа. Наличие модели 0 порядка гарантирует, что данный процесс когда-то прервется.

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

Преобразование Барроуза-Уилера (циклический сдвиг блока)

Преобразование Барроуза-Уилера само по себе не сжимает данные, но оно помогает представить их в таком виде, что степень их сжатия существующими архиваторами существенно улучшается. Отметим, что появилось оно недавно (первая ссылка – 1994г., хотя идея появилась раньше).

Пусть на входе есть некоторое слово из символов входного алфавита, например

параграф

Запишем матрицу из всех его циклических перестановок:

параграф

араграфп

раграфпа

аграфпар

графпара

рафпараг

афпарагр

фпарагра

Упорядочим строки полученной матрицы в лексикографическом порядке:

аграфпар

араграфп

афпарагр

графпара

параграф

раграфпа

рафпараг

фпарагра

Исходному слову сопоставляется код, состоящий из символов последнего столбца полученной матрицы (назовем ее Z) и номера строки в полученной матрице, в которой содержится исходное слово:

рпрафага4

Оказывается, что по полученным данным можно восстановить исходную последовательность символов.

Действительно, т.к. мы знаем все символы исходной последовательности, то отсортировав их мы получим первый столбец матрицы Z:

а……р

а……п

а……р

г……а

п……ф

р……а

р……г

ф……а

Теперь, если для каждой строки произвести циклический сдвиг вправо на одну позицию, то мы получим, что в строках матрицы Z есть слова, начинающиеся уже на пары символов: {ра, па, ра, аг, фп, аг, гр, аф}. Опять отсортировав их, мы получим уже пары символов, стоящих в первых двух столбцах матрицы Z:

аг…..р

ар…..п

аф…..р

гр…..а

па…..ф

ра…..а

ра…..г

фп…..а

И т.д. На каждом шаге мы будем получать еще один столбец матрицы Z.

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

Основным достоинством данного преобразования является то, что если в исходной последовательности символов встречаются повторяющиеся слова {a₀,…a_N}, то соответствующие строки в матрице Z, начинающиеся на {a₁,…a_N} будут идти подряд, а во всех этих строках в правом столбце будет стоять один и тот же символ a₀. Например, для строки папапапапа получим следующую матрицу Z:

апапапапап

папапапапа

Тогда на выходе алгоритма имеем следующий код:

пппппааааа5

Вышеописанный алгоритм неприменим на практике из-за требования большого объема памяти и вычислительных ресурсов. На самом деле можно модифицировать алгоритм так, чтобы требовалась O(N) памяти и O(N) времени на его реализацию, где N – количество символов в кодируемом блоке.

На каждом шаге описанного алгоритма мы переносим последнюю букву h_i из каждой строки полученного массива i в начало строки. При этом строки были уже упорядочены, поэтому после переупорядочивания взаимное расположение строк с равным первым символом h_i не изменится. Следовательно, в первой строке будет стоять строка с первым по счету минимальным h_i, далее пойдет строка со вторым по счету минимальным h_i (если есть несколько равных минимальных h_i). Далее пойдут строки со вторым по величине h_i, и т.д.

Т.о. функция t(i), сопоставляющая номеру строки i после сортировки ее номер до сортировки зависит только от последовательности { h_i }. Например, для случая слова параграф имеем первый шаг алгоритма:

а……р

а……п

а……р

г……а

п……ф

р……а

р……г

ф……а

и функцию h в виде следующей таблицы:

i	*0 1 2 3 4 5 6 7*
*h(i)*	*3 5 7 6 1 0 2 4*

Исходя из полученного кода, мы знаем, что исходное слово завершается на символ ф в позиции 4. Исходя из значения функции h(4) , мы знаем, что в данную строку после сортировки перешла строка с номером h(4)=1, а значит после буквы ф должна стоять буква п (`после’ – имеется в виду – циклически). Действительно на одном шаге алгоритма кодирования мы сдвигали строку вправо и сортировали строки, а при раскодировании мы должны сделать перестановку, обратную сортировке, и применить сдвиг влево. Получим, что интересующий нас символ стоит сразу после ф в строке с номером h(4)=1. Данный процесс можно аналогично продолжить

h(4)=1 п

h(1)=5 а

h(5)=0 р

h(0)=3 а

h(3)=6 г

h(6)=2 р

h(2)=7 а

h(7)=4 ф

Итак, для всего алгоритма декодирования нам потребовалось времени = O(M+N), где M – количество символов в алфавите, N – количество символов в дешифруемом блоке. Здесь имеется в виду, что сортировку массива можно произвести за время O(M+N), и оставшуюся часть декодирования – за время O(N).

Стоит еще раз вернуться к алгоритму кодирования. Легко увидеть, что нам не нужно отводить память под матрицу циклических сдвигов исходной строки. Нам достаточно иметь массив перестановок, обеспечивающий переход от исходного массива строк с циклическими сдвигами исходной строки к отсортированному массиву. Т.е. мы можем работать с массивом целых чисел r(i), где после сортировки r(i) равно номеру исходной строки. Т.о. в процессе сортировки для сравнения i и j-той строк сортируемого массива мы будем сравнивать строки, состоящие из последовательности символов исходного массива {s_i,…,s₍_i+_N)%_N} и {s_j,…,s₍_j+_N)%_N}.

Используя известные методы сортировки мы можем произвести сортировку за O(Nlog N) сравнений, но проблема заключается в том, что каждое сравнение требует до O(N) операций, что делает алгоритм слишком медленным в худшем случае: O(N²log N). Неприятности здесь обусловлены сравнением длинных совпадающих последовательностей символов. Поэтому требуются специальные алгоритмы сортировки. Одним из примеров таких алгоритмов является алгоритм модифицированной сортировки quick sort (алгоритм Бентли-Седжвика).

В алгоритме модифицированной сортировки используется следующая идея. В качестве медианы рассмотрим один из первых символов строк m. Разобъем массив строк на три подмассива –

1. подмассив строк, первый символ которых меньше m,

2. подмассив строк, первый символ которых больше m,

3. подмассив строк, первый символ которых равен m.

Для помассивов 1 и 2 применим тот же самый алгоритм, а для подмассива 3 применим тот же самый алгоритм, но сравнивать строки в нем будем сразу начиная со второго символа (первый символ у них совпадает).

В конце все три подмассива следует объединить в один упорядоченный массив (учитывая, что все строки из массива 1 < всех строк из массива 3 < всех строк из массива 2).

Функция, реализующая один шаг данного алгоритма будет иметь примерно следующее описание

void qsort3(char **str, int nstr, int l0, char **tmp1, char **tmp2, char **tmp3)

{char med; int l1=0,l2=0,l3=0,i;

if(nstr<=1)return;

med=str[0][l0];//или другой алгоритм выбора псевдо-медианы

//разбиение на 3 помассива :

for(i=0;i<nstr;i++)

if(str[i][l0]<med)tmp1[l1++]=str[i];

else if(str[i][l0]>med)tmp2[l2++]=str[i];

else if(str[i][l0]==med)tmp3[l3++]=str[i];

for(i=0;i<l1;i++)str[i]=tmp1[i];

for(i=0;i<l3;i++)str[i+l1]=tmp3[i];

for(i=0;i<l2;i++)str[i+l1+l3]=tmp2[i];

//рекурсия :

qsort3(str,l1,l0,tmp1,tmp2,tmp3);

qsort3(str+l1,l3,l0+1,tmp1,tmp2,tmp3);

qsort3(str+l1+l3,l2,l0,tmp1,tmp2,tmp3);

}

str – исходный массив строк длины nstr.

l0 – длина части равных префиксов строк из массива str

Используются три дополнительных массива указателей на строки длиной равной длине исходного массива строк.

Простейший пример использования данной процедуры:

int main()

{char *str[]={"papa","r","pama","baba","ba","b"},

*tmp1[60],*tmp2[60],*tmp3[60]; int i;

qsort3(str, 6, 0, tmp1,tmp2,tmp3);

for(i=0;i<6;i++) printf("%s\n",str[i]);

return 0;

}

Легко написать программу, имеющую меньшие требования к дополнительным массивам.

Алгоритмы сжатия изображений. Форматы представления изображений

Потоковый ввод-вывод в языке С

Понятие буферизации. Функция fflush(FILE *f);

Открытие файла:

FILE *fopen( const char *filename, const char *mode );

Значения mode:

”rt”

”wt”

”at”

”rt+”

”wt+”

”rb”

”wb”

”ab”

”rb+” позволяет модифицировать файл без обрезания хвоста; если файл существует, то он не уничтожается

”wb+” позволяет модифицировать файл с обрезанием хвоста; если файл существует, то он уничтожается и создается заново

fprint, fprintf, sprintf

scanf, fscanf, sscanf

char *fgets( char *string, int n, FILE *stream );

size_t fread( void *buffer, size_t size, size_t count, FILE *stream );

size_t fwrite( const void *buffer, size_t size, size_t count, FILE *stream );

//возвращают число реально прочитанных/записанных переменных

long ftell( FILE *stream );

int fseek( FILE *stream, long offset, int origin );

origin: SEEK_CUR, SEEK_END, SEEK_SET

fflush(FILE *f);

fclose(FILE *f);

t=текстовый режим

b=бинарный режим

По умолчанию обычно текстовый режим, но может задаваться параметром. Например, в Microsoft Visual C: глобальная переменная _fmode может принимать значения _O_TEXT или _O_BINARY, соответственно меняя режимы.

Существуют стандартные потоки stdin, stdout, stderr.

Лекция 5

Алгоритмы сжатия данных.

Список литературы

Р.Е. Кричевский. Сжатие и поиск информации. М. Радио и связь. 1989.

Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. М. Диалог-МИФИ. 2002.

Гюнтер Борн. Форматы данных. Киев. Торгово-издательское бюро BHV. 1995.

Алгоритмы сжатия изображений. Форматы представления изображений

Потоковый ввод-вывод в языке С

Понятие буферизации. Функция fflush(FILE *f);

Открытие файла:

FILE *fopen( const char *filename, const char *mode );

Значения mode:

”rt”

”wt”

”at”

”rt+”

”wt+”

”rb”

”wb”

”ab”

”rb+” позволяет модифицировать файл без обрезания хвоста; если файл существует, то он не уничтожается

fprint, fprintf, sprintf

scanf, fscanf, sscanf

char *fgets( char *string, int n, FILE *stream );

size_t fread( void *buffer, size_t size, size_t count, FILE *stream );

size_t fwrite( const void *buffer, size_t size, size_t count, FILE *stream );

//возвращают число реально прочитанных/записанных переменных

long ftell( FILE *stream );

int fseek( FILE *stream, long offset, int origin );

origin: SEEK_CUR, SEEK_END, SEEK_SET

fflush(FILE *f);

fclose(FILE *f);

t=текстовый режим

b=бинарный режим

Существуют стандартные потоки stdin, stdout, stderr.

Замечания о представлении чисел в ЭВМ

Следует отметить, что на разных ЭВМ целые числа (short, int, long) могут иметь различные варианты представления. Тем не менее, графические файлы в стандартных форматах должны иметь одинаковый формат представления вне зависимости от типа ЭВМ. Поэтому хорошая программа чтения/записи изображений обязана уметь определять формат данных на конкретной машине и, в соответствии с этим, преобразовывать целые числа при записи на диск/чтении с диска.

Например, формат BMP подразумевает, что переменные типа short должны состоять из двух байт, старший байт слева (формат Little-Endian, в отличие от формата Big-Endian, когда слева располагается старший байт), все биты по старшинству располагаются справа налево (старший слева). Тогда функция чтения переменной unsigned short в данном формате в переменную типа unsigned long на данной ЭВМ может выглядеть следующим образом

unsigned long ReadShort(FILE *f)

{unsigned char c[2]; fread(c,1,2,f); return c[0]+(c[1]<<8);}

Обратная функция записи может выглядеть следующим образом

int WriteShort(unsigned long i, FILE *f)

{unsigned char c[2];

c[0]=i%256; c[1]=i/256;

return fwrite(c,1,2,f);

}

Графические изображения. Пространства цветов

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

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

Растровые изображения представляются как набор пикселов, обычно, в прямоугольной матрице пикселов размером M×N, которую и называют изображением. Каждый пиксел задается своим цветом. Для представления различных цветов используются различные системы цветопередачи или пространства цветов.

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

Белый цвет (так же как и все градации серого) представляется в виде суммы равных по яркости компонент красного, синего и зеленого цветов. Для белого цвета яркость компонент должна быть максимальной, а для черного – нулевой.

Вообще, существуют и другие варианты получения цветов смешиванием нескольких цветов из заданного набора. Так, например, используется палитра CMY (cyan - голубой, magenta - пурпурный, yellow - желтый). В отличие от RGB, в палитре CMY используется не сложение цветов, а вычитание их из белого цвета. Т.о., нулевое значение компонент в палитре CMY соответствует белому цвету.

Существует простое соотношение между представлениями цвета в RGB и CMY палитрах:

RGB.r = 255-CMY.c

RGB.g = 255-CMY.m

RGB.b = 255-CMY.y

В силу своей специфики, RGB палитра широко используется в цветных мониторах, а CMY палитра используется в печати. В реальности часто вместо CMY палитры используется CMYK палитра, полученная из CMY добавлением черного цвета. Это дает возможность более точно отображать темные тона.

Способ представления цвета смешиванием стандартных цветов весьма естественен, но у него есть принципиальный недостаток: незначительные изменения отдельных компонент могут привести к существенному визуальному искажению цвета. Для устранения этого недостатка используются другие системы цветопередачи. Например, часто используется система HSV или HSB: hue – задает цвет, saturation – задает насыщенность, value (brightness) – яркость. Представим себе конус в пространстве RGB с вершиной в начале координат и осью r=g=b (ось вдоль равных значений компонент r,g,b). Угол раствора конуса задается величиной насыщенности (нулевая насыщенность соответствует серому цвету). Если спроецировать точку на конусе P на ось, то получим некоторую точку H. Тогда расстояние |OH| есть величина яркости в данной палитре. Наконец, угол между плоскостями (OHP) и (OHR), где R – точка с координатами (1,0,0) в координатах (r,g,b) задает значение цвета.

Illustration of HSM model with these callouts: A. Saturation B. Hue C. Brightness D. All hues

Система HSV. B=hue=цвет, A=saturation=насыщенность, C=value=яркость

В системе HLS: hue – задает цвет, saturation – задает насыщенность, lightness – яркость. hue=0 соответствует синему цвету, hu=60° соответствует пурпурному цвету, hue=120° соответствует красному цвету.

Форматы BMP и RLE

Формат BMP исторически является основным форматом представления изображений в ОС Microsoft Windows*. Постараемся дать, по возможности, полное описание формата.

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

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

unsigned char pal[256][4];

Каждая строка в массиве палитры задает один цвет с помощью указания его RGB составляющих, соответственно, в ячейках с номерами 0, 1, 2. Количество строк зависит от количества используемых цветов и, обычно, не превосходит 256 (что соответствует изображению, в котором на один пиксел отводится 8 бит).

Данные можно представлять в формате true color, когда каждый пиксел задается 4-мя байтами. Из них используется 3 байта для размещения RGB компонент цвета (по одному байту на каждую компоненту).

Возможно большое количество нестандартных вариаций данного формата. Например, отсутствие палитры в изображениях с толщиной 8 бит на пиксел может обозначать, что кодируется серое изображение, в каждом байте которого хранится яркость пиксела. Некоторые программы понимают форматы BMP в которых отводится 3 байта на пиксел (формат true color) или даже 2 байта на пиксел (в пикселе хранится только яркость, т.е. кодируется серое изображение).

Файл состоит из следующих разделов:

· Заголовка

· Возможно – палитры

· Собственно данных

Заголовок файла представляется следующей структурой

struct BMPHEAD

{

unsigned short int Signature ; // Must be 0x4d42 == ”BM” //0

unsigned long FileLength ; // в байтах //2

unsigned long Zero ; // Must be 0 //6

unsigned long Ptr ; // смещение к области данных //10

unsigned long Version ;// длина оставшейся части заголовка=0x28 //14

unsigned long Width ; // ширина изображения в пикселах //18

unsigned long Height ; // высота изображения в пикселах //22

unsigned short int Planes ; // к-во битовых плоскостей //26

unsigned short int BitsPerPixel ; // к-во бит на папиксел //28

unsigned long Compression ; // сжатие: 0 или 1 или 2 //30

unsigned long SizeImage ; // размер блока данных в байтах //34

unsigned long XPelsPerMeter ; // в ширину: пикселов на метр //38

unsigned long YPelsPerMeter ; // в высчоту: пикселов на метр //42

unsigned long ClrUsed ; // к-во цветов в палитре //46

unsigned long ClrImportant ; // к-во используемых цветов в палитре //50

} ;

Предполагается, что sizeof(unsigned long)==4, sizeof(unsigned short int)==2.

Соответствующие поля в файле с данным форматом непрерывно располагаются в указанном порядке.

Палитра (если она есть) следует сразу за заголовком. Данные начинаются с байта номер Ptr, начиная от начала файла.

BMP без сжатия.

Поле Compression определяет способ сжатия данных. Обычно значение этого поля=0, что соответствует отсутствию сжатия. При этом данные записываются по битам подряд. BMP формат со сжатием часто называется RLE форматом.

Длина каждой строки округляется в большую сторону до кратности 32 битам (4 байта). Т.о., например, при отсутствии сжатия если Width=3, то каждая строка на диске будет занимать

(Width* BitsPerPixel + 31)/8=4 байт.

Предполагается, что байты располагаются в порядке их нумерации, старший бит слева. Т.о., если BitsPerPixel =1, то самый первый пиксел ляжет в старший бит самого первого байта данных.

Для хранения всего изображения структуру struct BMPHEAD следует дополнить массивом палитры и массивом самих данных. Если предположить, что мы будем иметь дело с изображениями не более 8 бит на пиксел, то для данных можно завести, например, массив unsigned char **v . Пиксел с координатами (i,j) можно хранить в переменной v[i][j].

Итак, все изображение можно хранить в структуре

struct CBMP