Презентация Кодирование. Оптимальный код Хаффмана. Лекция 14 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Кодирование. Оптимальный код Хаффмана. Лекция 14 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 39 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Кодирование. Оптимальный код Хаффмана. Лекция 14
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:39 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:393.97 kB
- Просмотров:86
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№4 слайд
![Понятие кода Кодом называется](/documents_6/c5874c5edff1f395289569593f9073da/img3.jpg)
Содержание слайда: Понятие кода
Кодом называется отображение К : Алф1* —> Алф2*, согласованное с конкатенацией, т.е. удовлетворяющее равенству К(с1с2...сN) = К(с1) К(с2)... К(сN) для любого сообщения с1с2...сN из Алф1*
Значение К(с1с2...сN) называется кодом сообщения с1с2...сN
Код К : Алф1* —> {0,1}* называется двоичным кодом
№5 слайд
![Кодирование и декодирование](/documents_6/c5874c5edff1f395289569593f9073da/img4.jpg)
Содержание слайда: Кодирование и декодирование
Кодированием сообщения называется вычисление кода сообщения
Декодированием (дешифровкой) сообщения называется вычисление его прообраза под действием кода
Код К называется однозначно декодируемым, если существует обратная функция К-1
Если вычисление К-1 требует большого количества времени, то говорят не о кодировании, а о шифровании
№8 слайд
![Кодовое дерево Кодовым](/documents_6/c5874c5edff1f395289569593f9073da/img7.jpg)
Содержание слайда: Кодовое дерево
Кодовым деревом кода К:Алф1 ->Алф2 называется такое дерево Т, с рёбрами помеченными символами из Алф2, что
Любой путь из корня Т совпадает с началом кода какого-то символа из Алф1
Код любого символа из Алф1 соответствует какому-то пути из корня Т
Почему не всегда до листа?
№11 слайд
![Префиксный код Код К](/documents_6/c5874c5edff1f395289569593f9073da/img10.jpg)
Содержание слайда: Префиксный код
Код К называется префиксным, если для любых двух сообщений U и V код К(U) не является началом (префиксом) кода К(V) и наоборот
Свойства префиксного кода
В дереве префиксного кода коды всех символов заканчиваются в листьях
Префиксный код позволяет выделять коды символов без использования разделителей
№14 слайд
![Однозначная декодируемость](/documents_6/c5874c5edff1f395289569593f9073da/img13.jpg)
Содержание слайда: Однозначная декодируемость префиксного кода
Теорема Любой префиксный код однозначно декодируем
Доказательство
Пусть К – префиксный код. Докажем, что у кода S=К(R) любого сообщения R ровно один прообраз
Индукция по длине L сообщений R
База L = 1
R восстанавливается однозначно в силу префиксности К
Что было бы, если бы коды двух разных символов являлись бы префиксом S
Шаг L > 1
К согласован с конкатенацией ==> найдётся символ с такой, что S = К(с) S'
Что бы было бы, если бы такого символа не было бы или бы он был бы не один бы?
К префиксный ==> символ с единственный
Длина прообраза S' строго меньше длины прообраза S
По предположению индукции S' декодируется однозначно
№17 слайд
![Понятие оптимального кода](/documents_6/c5874c5edff1f395289569593f9073da/img16.jpg)
Содержание слайда: Понятие оптимального кода
Обозначим
Δ – множество кодов Алф1* -> Алф2*
К – какой-то код из Δ
R – произвольное сообщение из Алф1*
L(К, R) – длина R после кодирования
p х – число вхождений символа cх в R
заодно мы пронумеровали символы из Алф1, х – номер символа сх
Длина кода сообщения R есть L(К,R) = ∑ pх∙L (К, cх)
Код К* называется оптимальным для сообщения R в множестве кодов Δ, если
L(К*,R) = min { длина(К,R) | K Δ }
№18 слайд
![Оптимальный двочиный](/documents_6/c5874c5edff1f395289569593f9073da/img17.jpg)
Содержание слайда: Оптимальный двочиный префиксный код
Как быстро построить оптимальный
двоичный префиксный код для
данного сообщения?
Сжатие данных при хранении и передаче
Устранение избыточности при шифровании данных
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.
№19 слайд
![Свойства оптимального](/documents_6/c5874c5edff1f395289569593f9073da/img18.jpg)
Содержание слайда: Свойства оптимального двоичного префиксного кода
Пусть 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)
№20 слайд
![Свойства оптимального](/documents_6/c5874c5edff1f395289569593f9073da/img19.jpg)
Содержание слайда: Свойства оптимального двоичного префиксного кода
Символов с кодом длины L(K*,сn) (с самым длинным кодом) не менее двух
Иначе удалим последний символ в коде сn -- длина L(K*, R) сократится, префиксность K* сохранится
Можно перенумеровать символы так, что
К*(сn) = P 0 и К*(сn-1) = P 1 и сохранив условие 2
Следует из свойства 3
№21 слайд
![Свойства оптимального](/documents_6/c5874c5edff1f395289569593f9073da/img20.jpg)
Содержание слайда: Свойства оптимального двоичного префиксного кода
Оптимальный двоичный префиксный код к* для сообщения 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
№22 слайд
![Построение дерева](/documents_6/c5874c5edff1f395289569593f9073da/img21.jpg)
Содержание слайда: Построение дерева оптимального префиксного двоичного кода
Вход
Кратности 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) }
№23 слайд
![Пример кол около колокола o к](/documents_6/c5874c5edff1f395289569593f9073da/img22.jpg)
Содержание слайда: Пример
кол около колокола
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(а))))) }
№26 слайд
![Пример построения кода по](/documents_6/c5874c5edff1f395289569593f9073da/img25.jpg)
Содержание слайда: Пример построения кода по кодовому дереву
Пометим дуги, исходящие из каждой вершины дерева, единицей и нулем
Проходя путь из корня дерева до символа и выписывая все пометки дуг на этом пути, получим код для этого символа
В нашем примере коды будут такими
о 0,
к 10 пробел 1110
л 110 а 1111
Закодированное сообщение
10011011100100110011101001001001101111
Длина закодированного сообщения L = 39
№28 слайд
![Теорема Длина кодового слова](/documents_6/c5874c5edff1f395289569593f9073da/img27.jpg)
Содержание слайда: Теорема
Длина кодового слова в оптимальном префиксном двоичном коде ограничена порядковым номером минимального числа Фибоначчи, превосходящего длину входного текста.
Доказательство – в качестве упражнения
Следствие
При кодировании по алгоритму Хаффмана текстов ASCII размером до 11Tб код любого символа короче 64 битов
№31 слайд
![Метод Фано Упорядочим входной](/documents_6/c5874c5edff1f395289569593f9073da/img30.jpg)
Содержание слайда: Метод Фано
Упорядочим входной алфавит по возрастанию частот p1 <= p2 <= … <= pn вхождения символов в сообщение
Обозначим Sk = p1+p2+…+pk, S0 = 0
Строим таблицу К с двоичными кодами символов входного алфавита
K[i][1] = i-й символ (по возрастанию частот)
K[i][2] = Sk
Остальные клетки – на след. слайде
№34 слайд
![Свойства кода Фано Кодовое](/documents_6/c5874c5edff1f395289569593f9073da/img33.jpg)
Содержание слайда: Свойства кода Фано
Кодовое дерево для кода Фано обладает следующим свойством
Ребра, исходящие из корня, соответствуют разбиению алфавита на две группы символов, близкие по частоте
Ребра, исходящие из вершины следующего «этажа», соответствуют разбиению соответствующей группы на близкие по частоте подгруппы и т. д.
Код Фано – префиксный код
Почему?
№35 слайд
![Свойства кода Фано Код Фано](/documents_6/c5874c5edff1f395289569593f9073da/img34.jpg)
Содержание слайда: Свойства кода Фано
Код Фано неоптимальный
Пример
Частоты 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
Как выглядят кодовые деревья кода Хаффмана т Фано?
№36 слайд
![Метод Шеннона Клод Шеннон ,](/documents_6/c5874c5edff1f395289569593f9073da/img35.jpg)
Содержание слайда: Метод Шеннона
Клод Шеннон 1916 – 2001, основоположник теории информации
Упорядочим входные символы по возрастанию частот и образуем частичные суммы Sk как в методе Фано
Для каждой частоты Sk находим nk т.ч. 1/2^nk ≤ Sk ≤ 2/2^nk --- нужно отделить одну Sk от другой
Sk разлагаем в двочную дробь 0.d1d2d3….
Первые nk цифр этой дроби задают код для k-го символа
№37 слайд
![Пример построения кода](/documents_6/c5874c5edff1f395289569593f9073da/img36.jpg)
Содержание слайда: Пример построения кода Шеннона
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
№38 слайд
![Свойства кода Шеннона Код](/documents_6/c5874c5edff1f395289569593f9073da/img37.jpg)
Содержание слайда: Свойства кода Шеннона
Код Шеннона -- префиксный код
Почему?
Пусть pk – частота вхождения k-го символа в кодируемое сообщение длины N.
Кодирование такого сообщения кодом Шеннона дает сообщение длины не более N*(p1*log2(p1) + p2*log2(p2) + … + pn*log2(pn))
Почему? Как Шеннон выбрал длины кодовых слов?
Скачать все slide презентации Кодирование. Оптимальный код Хаффмана. Лекция 14 одним архивом:
Похожие презентации
-
Свойства информации. Измерение информации. Кодирование информации. Помехоустойчивое кодирование. Код хемминга. (Лекция 2)
-
Кодирование основных типов алгоритмических структур на языках объектно — ориентированного и процедурного программирования
-
Цифровое кодирование. Сжатие RLE (Run Length Encoding)
-
Двоичная система кодирования
-
Двоичное кодирование. ( 6 класс)
-
QR-кодирование в распределительной логистике
-
Проектирование АСУ. Системы кодирования
-
Стандарт кодирования видео и звуковой информации. MPEG-4
-
Теория компиляторов. Часть II. Лекция 3. Общие методы распараллеливания кода
-
Теория кодирования