Эффективное кодирование сообщений презентация

длины
Неравномерные коды
Методы оптимального кодирования без памяти
Методы трансформации данных
Методики сравнения алгоритмов. Наборы тестовых данных

f последовательность ui преобразуется в конечную последовательность (кодовое слово) xi = (x1, x2, ..., xk), формируемую из букв алфавита D=(d1, ..., dm) кодового словаря X. Если множество конечных последовательностей источника обозначить как U*, а множество конечных кодовых слов – как X*, то кодирование – это отображение
f : U* → X*,
а код последовательности ui или кодовое слово xi – как xi = f(ui).

ni -> кодовые слова xi одинаковой длины ki=k=const;
- слова источника ui одинаковой длины ni=n=const -> кодовые слова xi одинаковой длины ki=k=const;

- слова источника ui одинаковой длины ni=n=const -> кодовые слова xi различной длины ki;
- слова источника переменной длины ui -> кодовые слова xi переменной длины ki.

Коды фиксированной длины

Коды переменной длины

Эффективное кодирование обеспечивает увеличение средней информационной нагрузки на кодовое слово (символ кодового словаря).

с данными
- поточное, когда статистика постоянно обновляется

2. Трансформация потока (словарные методы)

3. Трансформация блока

символов каждому из L символов дискретного источника.
Число двоичных символов кодера на один символ источника
R=[log2L]+1.

Поскольку H(X)≤log2L, то R≥H(X). Эффективность кодирования определяется отношением H(X)/R.
Если L равно степени 2 и символы источника равновероятны, то R=H(X).
Если L не является степенью 2, но символы источника все еще равновероятны, R отличается от H(X) самое большее на 1 символ.

цифр от 0 до 9 (L=10).
Каждая цифра может содержать информацию, равную самое большее log210 ≈ 3,32193 бит.

Теорема о кодировании источника кодами фиксированной длины

однозначности (единственности декодирования);
- отсутствие префикса (возможность мгновенного декодирования).

Условие существование мгновенного кода – неравенство Крафта:
Необходимое и достаточное условие для существования двоичного кода с кодовыми символами длины k1≤k2≤...≤kL, удовлетворяющего условию отсутствия префикса

или

то код является неэффективным.

из L букв A=(a1,...,aL) с вероятностями p(a1), ..., p(aL).
Обозначим через m количество возможных символов в кодовом алфавите, а ki – число букв в кодовом слове, соответствующем ai. Тогда среднее число букв в кодовом слове на одну букву источника будет определяться как


При заданном конечном ансамбле источника U с энтропией H(U) и кодовом алфавите из m символов существует возможность создать код, который отвечает префиксному требованию условию и имеет среднюю длину, удовлетворяющую условию

порядке убывания их вероятностей, пусть это будут вероятности p1, p2, ..., pN, где N=LJ – число сообщений ui. Пусть - накопленная вероятность до ps-1 включительно. Закодируем сначала все сообщения в двоичную систему (m=2). Двоичный код для сообщения us получается путем записи дробной части разложения Qs как двоичного числа (с учетом того, что при S=1 Qs=0). Разложение производится до позиции ms, где ms – целое число, удовлетворяющее соотношению

источника упорядочены по убыванию

p(a1) ≥ p(a2) ≥... ≥ p(aL).

Тогда существует оптимальный код, длина слов которого не убывают, а две наименее вероятные буквы имеют коды одинаковой длины:

|f(a1)| ≤ |f(a2)| ≤ ... ≤ |f(aL-1)| = |f(aL)|.

кода равна
0,3*2+0,2*2+0,15*3+0,15*3+0,1*3+0,1*3= 0,6+0,4+0,45+0,45+0,3+0,3=1+0,9+0,6=2,5).

Вариант 2 (сбалансированное)






Средняя длина кодового слова одинакова: 2,2 бита

Дисперсии длин:
D1=0,4(1-2,2)2 + 0,2(2-2,2)2 + 0,2(3-2,2)2 + 0,1(4-2,2)2 + 0,1(4-2,2)2 = 1,36;
D2=0,4(2-2,2)2 + 0,2(2-2,2)2 + 0,2(2-2,2)2 + 0,1(3-2,2)2 + 0,1(3-2,2)2 = 0,16.

узла, N – порядковый номер):

этап: увеличивается вес листа дерева, соответствующего последнему считанному и закодированному символу. Затем увеличивается вес его родителя, родителя родителя и т.д. до тех пор, пока не дойдем до корня дерева;

После кодирования символа "А"

узлов дерева – требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности.

Перестановка

Нарушение упорядоченности после "АА"

После кодирования "АААА"

символы EOF и ESCAPE);
- переполнение.

Метод расширяющегося префикса (splay trees)

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

код с целым числом битов.

символов.

Сообщение: ДЛИННОШЕЕЕ

EOF)
Интервал = ВерхняяГраница – НижняяГраница;
НижняяГраница = НижняяГраница + Интервал * НижняяГраницаИнтервала(ОчереднойСимвол);
ВерхняяГраница = НижняяГраница + Интервал * ВерхняяГраницаИнтервала(ОчереднойСимвол);
КОНЕЦ ПОКА;
Выдать(НижняяГраница);

Выдать(Символ);
Интервал = ВерхняяГраницаИнтервала(Символ) – НижняяГраницаИнтервала(Символ);
Число = Число – НижняяГраницаИнтервала(Символ);
Число = Число / Интервал;
КОНЕЦ ВСЕГДА;

0;
delitel = b[clast]; // delitel = 10
FIRST_QTR = (High0+1) / 4; // 16384 = 010000000..
HALF = FIRST_QTR * 2; // 32768 = 100000000..
THIRD_QTR = FIRST_QTR * 3; // 49152 = 110000000..
cntr = 0;
while not eof()
{
c = ReadSymbol(); // Взять входной символ
j = IndexForSymbol(c); // Индекс по таблице
i++;
Interval = Highi-1 – Lowi-1 + 1; // Текущий интервал
Lowi = Lowi-1 + b[j-1]*Interval / delitel; // Нижняя граница
Highi = Lowi-1 + b[j]*Interval / delitel - 1; // Верхняя граница
for ( ; ; ) // Обрабатываем варианты
{
if (Highi < HALF) // у обоих границ старший бит = 0
OutputBitPlusFollow(0);
else if (Lowi > HALF) // у обоих границ старший бит = 1
{
OutputBitPlusFollow(1);
Lowi -= HALF; // обнуляем старший бит
Highi -= HALF;
}
else if ((Lowi >= FIRST_QTR) && (Highi <=THIRD_QTR)) // сближаются!
{
cntr ++; // наращиваем счетчик
Lowi -= FIRST_QTR; // расширяем интервал
Highi -= FIRST_QTR;
}
else // диапазон еще достаточно широк
break;
Lowi = 2 * Lowi;
Highi = 2 * Highi + 1;
}
}
void OutputBitPlusFollow(int bit)
{
WriteStreamBit(bit);
for (; cntr>0; cntr--)
WriteStreamBit(!bit);
}

Арифметическое кодирование. Кодер

i = 0;
delitel = b[clast]; // delitel = 10
FIRST_QTR = (High0+1) / 4; // 16384 = 010000000..
HALF = FIRST_QTR * 2; // 32768 = 100000000..
THIRD_QTR = FIRST_QTR * 3; // 49152 = 110000000..

Value = Read16Bit(); // Чтение из потока первого слова
Interval = Highi-1 – Lowi-1 + 1; // Текущий интервал
Cum = (Value – Lowi + 1) * delitel – 1) / Interval; // Накопленная сумма
for (j=1; b[j]
// Пересчитать границы
Lowi = Lowi-1 + b[j-1]*Interval / delitel; // Нижняя граница
Highi = Lowi-1 + b[j]*Interval / delitel - 1; // Верхняя граница
// Удаление символа из входного потока
for ( ; ; )
{
if (Highi < HALF) // старший бит = 0 – ничего не делать
{
}
else if (Lowi >= HALF)
{
Value -= HALF; // обнуляем старший бит
Lowi -= HALF;
Highi -= HALF;
}
else if ((Lowi >= FIRST_QTR) && (Highi <=THIRD_QTR)) // сближаются!
{
Value -= FIRST_QTR; // обнуляем второй слева бит
Lowi -= FIRST_QTR;
Highi -= FIRST_QTR;
}
else // диапазон еще достаточно широк
break;
Lowi = 2 * Lowi;
Highi = 2 * Highi + 1;
Value = 2 * Value + ReadNextBit(); // Читаем следующий бит из потока
}

и мантисс и т.п.)

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

Примеры (монотонных) кодов: код Левенштейна (1968), Райса (1979), Голомба (1966), Фибоначчи (1939), серия кодов Элайеса (1975).

из (n-1) нулей (единиц), за которыми следует одна единица (ноль), например, унарный код числа 4 = 0001 или 1110, числа 9 = 000000001 или 111111110.

Монотонный код представляет собой префиксно-свободный код с минимальными длинами кодовых слов, в котором если X1>X2, то длина кодового слова S(X1)≥S(X2) для любых X1, X2, принадлежащих алфавиту источника, т.е. малые значения получают более короткие кодовые слова, чем большие значения.

унарного кода числа и бинарного кода числа n без старшей единицы: (гамма-код Элайеса для 1 равен 1).
Дельта-кодами Элайеса называются гамма-коды, в которых унарная часть также закодирована гамма-кодами.
Омега-коды Элайеса рекурсивно кодируют свой префикс, поэтому иногда называются рекурсивными кодами Элайеса.

( |bin' (|bin'(i)|)|+2 ), bin' (|bin'(i)|), bin'(i) )
где bin'(i) – двоичная запись натурального числа i без первой единицы. Унарный код unar(i) сопоставляет числу i двоичную комбинацию виде 1i-10 (например, unar(1) = 0, unar(2) = 10, unar(3) = 110 и т.д.).

обращения последовательности битов в двоичной записи этого числа и добавления перед каждым битом, кроме последнего, флагового бита "0". Последним флаговым битом является бит "1", который совпадает с самым старшим битом в исходной двоичной записи числа n.

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

Например: 13 = 1101 => 1011 => 0100011. Подчеркнуты флаговые биты, выделены информационные биты.

серии решено послать двоичное число, состоящее из k цифр.
В соответствии с алгоритмом кодирования, это можно сделать только в том случае, если длина серии находится между 0 и 2k-2. Приемник генерирует указанное число нулей и затем одну 1.
Если получено число 0, то приемник просто генерирует 1.
Если послано число 2k-1, приемник генерирует 2k-1 нулей, за которыми не следует 1. Если после этого послано 0, то генерируется 1; для любого другого числа генерируется указанное число нулей и затем единица (если это не снова 2k-1).
Таким образом, передав достаточное число k-значных двоичных чисел, можно указать любую длину серии, состоящей из нулей.

- сегмент xixi+1...xj слова.
Разобьем слово x последовательно на несовпадающие подслова (парсинг):


таким образом, что все слова, за исключением, возможно, последнего, различны и для каждого j=1,2,...,p+1 при nj-nj-1>1 существует i, i
Конкатенация кодов всех слов образует слово f(x), для длины которого имеем


С учетом того, что максимальное число C(x) слов, на которые разбивается x, может лишь превзойти p (C(x)≥p), имеем

сообщению окно, разделенное на две неравные части (словарь и lookahead-буфер).

Алгоритм LZ77 выдает коды, состоящие из трех элементов:
- смещение в словаре относительно начала буфера, совпадающей с содержимым буфера (i);
- длина подстроки (j);
- первый символ в буфере, следующий за подстрокой (s).

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

симв. х 8 бит = 168 бит
Размер кода LZ77 (без доп. компрессии кодов): 12 шагов х (5 + 3 + 8) бит = 192 бита

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

13х(1+8) + 4х(1+5+3) = 153 бита

фраза, которая представляет собой сцепление (конкатенацию) одной из фраз S словаря, имеющей самое длинное совпадение со строкой буфера, и символа s. Символ s является символом, следующим за строкой буфера, для которой найдена совпадающая фраза S.
В словаре не может быть совпадающих фраз.
Кодер порождает только последовательность кодов фраз. Каждый код состоит из номера (индекса) n "родительской" фразы S или префикса, и символа s. В начале обработки словарь пуст.

Дополнительные соглашения:
- фраза с номером 0 обозначает конец сжатой строки;
- фраза с номером 1 задает пустую фразу словаря.

доп. компрессии кодов): 13(4+8) = 156 битов.

символов) в более удобный для сжатия вид.

Вариант схемы кодирования (последовательное применение алгоритмов):
- преобразование BWT;
- преобразование MTF;
- статистический кодер для сжатия данных, полученных в результате последовательного применения двух предыдущих преобразований.

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

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

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

Полученные значения номеров строк T = {2,5,6,7,8,9,10,1,3,0,4} – и есть искомый вектор, содержащий номера позиций символов в строке, которую надо декодировать.

помощью стандартизованных наборов файлов:
- набор Calgary Compression Corpus (CalgCC) из 14 файлов (+4 дополнительных), большая часть из которых представляет собой тексты на английском языке (художественные, технические, с большим количеством опечаток и т.п.) или языках программирования (программы на С, Лисп, Pascal). Имеются также геофизические данные, объектные файлы, факсимильные изображения;
- Canterbury Compression Corpus (CantCC) – предложен той же группой исследователей, что и CalgCC и является альтернативой морально устаревшему CalgCC (с точки зрения типов обрабатываемых данных);
- наборы файлов из Archive Comparison Test (ACT) – текстовые файлы, исполняемые файлы, звуковые файлы, полноцветные изображения;
- наборы файлов из тестов Art Of Lossless Data Compression (ARTest) – полноцветные изображения, текстовые файлы, разнородные файлы;
- файлы из Compression Comparison Вадима Юткина (VYCCT) – 8 файлов разных типов.