Презентация Кодирование. Оптимальный код Хаффмана. Лекция 14 онлайн

Содержание слайда: Кодирование оптимальный код Хаффмана Лекция 14

Содержание слайда: План лекции Алфавит, кодирование, код Типы кодирования, однозначное декодирование Метод кодирования Хафмана Метод кодирования Фано

Содержание слайда: Понятие кода Алфавитом называется конечное множество символов Сообщением алфавита А называется конечная последовательность символов алфавита А Множество всех сообщений алфавита А обозначается А*

Содержание слайда: Понятие кода Кодом называется отображение К : Алф1* —> Алф2*, согласованное с конкатенацией, т.е. удовлетворяющее равенству К(с1с2...сN) = К(с1) К(с2)... К(сN) для любого сообщения с1с2...сN из Алф1* Значение К(с1с2...сN) называется кодом сообщения с1с2...сN Код К : Алф1* —> {0,1}* называется двоичным кодом

Содержание слайда: Кодирование и декодирование Кодированием сообщения называется вычисление кода сообщения Декодированием (дешифровкой) сообщения называется вычисление его прообраза под действием кода Код К называется однозначно декодируемым, если существует обратная функция К-1 Если вычисление К-1 требует большого количества времени, то говорят не о кодировании, а о шифровании

Содержание слайда: Пример 1 Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 01, К(с) = 10, К(d) = 1 К-1(01101010) = {addbba, bссс, …} – прообраз 01101010 Данный код не является однозначно декодируемым

Содержание слайда: Пример 2 Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 10, К(с) = 110, К(d) = 111 Почему данный код является однозначно декодируемым?

Содержание слайда: Кодовое дерево Кодовым деревом кода К:Алф1 ->Алф2 называется такое дерево Т, с рёбрами помеченными символами из Алф2, что Любой путь из корня Т совпадает с началом кода какого-то символа из Алф1 Код любого символа из Алф1 соответствует какому-то пути из корня Т Почему не всегда до листа?

Содержание слайда: Пример кодового дерева Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 01, К(с) = 10, К(d) = 1 Почему у сообщения 01101010 как минимум два прообраза?

Содержание слайда: Пример кодового дерева Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 10, К(с) = 110, К(d) = 111 Почему у любого сообщения один прообраз?

Содержание слайда: Префиксный код Код К называется префиксным, если для любых двух сообщений U и V код К(U) не является началом (префиксом) кода К(V) и наоборот Свойства префиксного кода В дереве префиксного кода коды всех символов заканчиваются в листьях Префиксный код позволяет выделять коды символов без использования разделителей

Содержание слайда: Примеры префиксных кодов Пример 1 Алф1 = {a,b,c,d} Алф2 = {0,1} К(a) = 00, K(b) = 01, K(c) = 10, K(d) = 11 Как выглядит кодовое дерево этого кода?

Содержание слайда: Примеры префиксных кодов Пример 2 Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 10, К(с) = 110, К(d) = 111 Как выглядит кодовое дерево этого кода?

Содержание слайда: Однозначная декодируемость префиксного кода Теорема Любой префиксный код однозначно декодируем Доказательство Пусть К – префиксный код. Докажем, что у кода S=К(R) любого сообщения R ровно один прообраз Индукция по длине L сообщений R База L = 1 R восстанавливается однозначно в силу префиксности К Что было бы, если бы коды двух разных символов являлись бы префиксом S Шаг L > 1 К согласован с конкатенацией ==> найдётся символ с такой, что S = К(с) S' Что бы было бы, если бы такого символа не было бы или бы он был бы не один бы? К префиксный ==> символ с единственный Длина прообраза S' строго меньше длины прообраза S По предположению индукции S' декодируется однозначно

Содержание слайда: Пример Алф1 = {a,b,c,d} Алф2 = {0,1} К(a) = 0, К(b) = 101, К(c) = 110, К(d) = 1110 Рассмотрим сообщение 01101010 01101010 = K(a) 1101010 1101010 = K(c) 1010 1010 = K(b) 0 0 = K(a) K(acba) = 01101010

Содержание слайда: Пример азбука Морзе 1840 Alfred Vail по заказу телеграфной компании Samuel F.B. Morse Двоичный (точка, тире) непрефиксный код – почему? Троичный (точка, тире, пауза) префиксный код – почему? Кодовое дерево азбуки Морзе как двоичного кода для латиницы

Содержание слайда: Понятие оптимального кода Обозначим Δ – множество кодов Алф1* -> Алф2* К – какой-то код из Δ R – произвольное сообщение из Алф1* L(К, R) – длина R после кодирования p х – число вхождений символа cх в R заодно мы пронумеровали символы из Алф1, х – номер символа сх Длина кода сообщения R есть L(К,R) = ∑ pх∙L (К, cх) Код К* называется оптимальным для сообщения R в множестве кодов Δ, если L(К*,R) = min { длина(К,R) | K  Δ }

Содержание слайда: Оптимальный двочиный префиксный код Как быстро построить оптимальный двоичный префиксный код для данного сообщения? Сжатие данных при хранении и передаче Устранение избыточности при шифровании данных David A. Huffman 1925-1999 "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September 1952, pp 1098–1102.

Содержание слайда: Свойства оптимального двоичного префиксного кода Пусть R -- сообщение в алфавите Алф1={c1,…,cn} сx входит в R px раз (х=1,...,n) К* -- оптимальный двоичный префиксный код для R Если px < py, то Lx(К*) >= Ly (К*) Иначе для кода К(сx) = К*(сy), К(сy) = К*(сx) и К(с) = К*(с) L(K,R) < L(K*,R) Можно занумеровать символы Алф1 так, чтобы p1>=p2>=…>=pn и L(K*,с1)<=L(K*,с2)<=…<=L(K*,сn)

Содержание слайда: Свойства оптимального двоичного префиксного кода Символов с кодом длины L(K*,сn) (с самым длинным кодом) не менее двух Иначе удалим последний символ в коде сn -- длина L(K*, R) сократится, префиксность K* сохранится Можно перенумеровать символы так, что К*(сn) = P 0 и К*(сn-1) = P 1 и сохранив условие 2 Следует из свойства 3

Содержание слайда: Свойства оптимального двоичного префиксного кода Оптимальный двоичный префиксный код к* для сообщения r, полученного из сообщения R заменой самого редкого символа сn на сn-1 , и К* связаны соотношениями к*(сn-1) = удалить из К*(сn-1) последний символ К*(сn) = к*(сn-1) 0 К*(сn-1) = к*(сn-1) 1 К*(с) = к*(с) для остальных символов с L(K*,R) = L(k*,r) + pn + pn-1

Содержание слайда: Построение дерева оптимального префиксного двоичного кода Вход Кратности p1, …, pn вхождений симолов с1, ..., сn в сообщение Выход Дерево оптимального двоичного префиксного кода для сообщения Алгоритм W = {p1(c1), …, pn(cn)} – множество деревьев Левая скобочная запись, кратности в качестве меток вершин пока в W два или более поддеревьев Найти в W деревья T = x(...) и U = y(...) с минимальными метками x и y W = ( W \ {T, U} ) U { (x+y)(T, U) }

Содержание слайда: Пример кол около колокола o – 7; к – 4; л – 4; пробел – 2; a – 1. Один из вариантов работы алгоритма Множество W До цикла {7(о), 4(к), 4(л), 2(пробел), 1(а) } После шага 1 {7(о), 4(к), 4(л), 3(2(пробел), 1(а)) } После шага 2 {7(о), 4(к), 7(4(л), 3(2(пробел), 1(а))) } После шага 3 {7(о), 11(4(к), 7(4(л), 3(2(пробел), 1(а)))) } После шага 4 {18(7(о), 11(4(к), 7(4(л), 3(2(пробел), 1(а))))) }

Содержание слайда:

Содержание слайда:

Содержание слайда: Пример построения кода по кодовому дереву Пометим дуги, исходящие из каждой вершины дерева, единицей и нулем Проходя путь из корня дерева до символа и выписывая все пометки дуг на этом пути, получим код для этого символа В нашем примере коды будут такими о 0, к 10 пробел 1110 л 110 а 1111 Закодированное сообщение 10011011100100110011101001001001101111 Длина закодированного сообщения L = 39

Содержание слайда: Для разобранного примера можно построить другое дерево Закодированное сообщение длины L = 39 010010110000100100011001001000010010111

Содержание слайда: Теорема Длина кодового слова в оптимальном префиксном двоичном коде ограничена порядковым номером минимального числа Фибоначчи, превосходящего длину входного текста. Доказательство – в качестве упражнения Следствие При кодировании по алгоритму Хаффмана текстов ASCII размером до 11Tб код любого символа короче 64 битов

Содержание слайда: Алфавит, кодирование, код Типы кодирования, однозначное декодирование Метод кодирования Хафмана Метод кодирования Фано

Содержание слайда: Метод Фано Роберт Марио Фано р. 1917 Один из первых алгоритмов сжатия на основе префиксного кода

Содержание слайда: Метод Фано Упорядочим входной алфавит по возрастанию частот p1 <= p2 <= … <= pn вхождения символов в сообщение Обозначим Sk = p1+p2+…+pk, S0 = 0 Строим таблицу К с двоичными кодами символов входного алфавита K[i][1] = i-й символ (по возрастанию частот) K[i][2] = Sk Остальные клетки – на след. слайде

Содержание слайда: Метод Фано K[i][j] заполняем 0 и 1 по след. правилу Для каждого максимального интервала строк [a, b], у которых в столбце j-1 находятся одинаковые цифры Находим с  [a, b] такое, что Sc ближе всего к (Sa+Sb)/2 K[i][j] = 1 для i  [a, c], K[i][j] = 0 для i  [c+1, b]

Содержание слайда: Пример А = {a, b, c, d, e} Частоты pa = 0.11, pb = 0.15, pc = 0.20, pd = 0.24, pe = 0.30 0.46 ближе к 0.5 0.26 ближе всех к (0.00+0.46)/2=0.23 0.70 ближе всех к (0.46+1.00)/2=0.73 0.11 ближе всех к (0.00+0.26)/2=0.13

Содержание слайда: Свойства кода Фано Кодовое дерево для кода Фано обладает следующим свойством Ребра, исходящие из корня, соответствуют разбиению алфавита на две группы символов, близкие по частоте Ребра, исходящие из вершины следующего «этажа», соответствуют разбиению соответствующей группы на близкие по частоте подгруппы и т. д. Код Фано – префиксный код Почему?

Содержание слайда: Свойства кода Фано Код Фано неоптимальный Пример Частоты p1=0.4, p2=p3=p4=p5=0.15 Фано: 00 01 10 110 111 средняя длина кодового слова 2*0.4+(2+2)*0.15+(3+3)*0.15 = 2.3 Хаффман: 0 010 011 000 001 средняя длина кодового слова 1*0.4+ (3+3+3+3)*0.15 = 2.2 Как выглядят кодовые деревья кода Хаффмана т Фано?

Содержание слайда: Метод Шеннона Клод Шеннон 1916 – 2001, основоположник теории информации Упорядочим входные символы по возрастанию частот и образуем частичные суммы Sk как в методе Фано Для каждой частоты Sk находим nk т.ч. 1/2^nk ≤ Sk ≤ 2/2^nk --- нужно отделить одну Sk от другой Sk разлагаем в двочную дробь 0.d1d2d3…. Первые nk цифр этой дроби задают код для k-го символа

Содержание слайда: Пример построения кода Шеннона nk разложение Sk код p(a) = 0.08 Sa = 0.08 4 0.0001 0001 p(b) = 0.12 Sb = 0.20 4 0.0011 0011 p(c) = 0.15 Sc = 0.35 3 0.010 010 p(d) = 0.28 Sd = 0.63 2 0.10 10 p(e) = 0.37 Sd = 1.00 2 0.11 11 Пример вычисления na: 0.08 ~= 1/12; 1/2^4 ≤ 1/12 ≤ 2/2^4

Содержание слайда: Свойства кода Шеннона Код Шеннона -- префиксный код Почему? Пусть pk – частота вхождения k-го символа в кодируемое сообщение длины N. Кодирование такого сообщения кодом Шеннона дает сообщение длины не более N*(p1*log2(p1) + p2*log2(p2) + … + pn*log2(pn)) Почему? Как Шеннон выбрал длины кодовых слов?

Содержание слайда: Заключение Алфавит, кодирование, код Типы кодирования, однозначное декодирование Метод кодирования Хафмана Метод кодирования Фано