Информатика. Элементы теорий вероятностей и информации

Август 1, 2022

Главная
Информатика
Информатика. Элементы теорий вероятностей и информации

Содержание

2. План лекции Алфавит, кодирование, код Типы кодирования, однозначное декодирование Метод кодирования Хафмана Метод кодирования Фано Элементы
3. Алфавитом называется конечное множество символов Сообщением алфавита А называется конечная последовательность символов алфавита А Множество всех
4. Кодом называется отображение К : Алф1* —> Алф2*, согласованное с конкатенацией, т.е. удовлетворяющее равенству К(с1с2...сN) =
5. Кодированием сообщения называется вычисление кода сообщения Декодированием (дешифровкой) сообщения называется вычисление его прообраза под действием кода
6. Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 01, К(с) = 10, К(d)
7. Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 10, К(с) = 110, К(d)
8. Кодовое дерево Кодовым деревом кода К:Алф1 ->Алф2 называется такое дерево Т, с рёбрами помеченными символами из
9. Пример кодового дерева Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 01, К(с)
10. Пример кодового дерева Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) = 10, К(с)
11. Префиксный код Код К называется префиксным, если для любых двух сообщений U и V код К(U)
12. Примеры префиксных кодов Пример 1 Алф1 = {a,b,c,d} Алф2 = {0,1} К(a) = 00, K(b) =
13. Примеры префиксных кодов Пример 2 Алф1 = {a,b,c,d} Алф2 = {0,1} К(а) = 0, К(b) =
14. Однозначная декодируемость префиксного кода Теорема Любой префиксный код однозначно декодируем Доказательство Пусть К – префиксный код.
15. Алф1 = {a,b,c,d} Алф2 = {0,1} К(a) = 0, К(b) = 101, К(c) = 110, К(d)
16. Пример азбука Морзе 1840 Alfred Vail по заказу телеграфной компании Samuel F.B. Morse Двоичный (точка, тире)
17. Понятие оптимального кода Обозначим Δ – множество кодов Алф1* -> Алф2* К – какой-то код из
18. Оптимальный двочиный префиксный код Как быстро построить оптимальный двоичный префиксный код для данного сообщения? Использование Сжатие
19. Свойства оптимального двоичного префиксного кода Пусть R -- сообщение в алфавите Алф1={c1,…,cn} сx входит в R
20. Свойства оптимального двоичного префиксного кода Символов с кодом длины L(K*,сn) (с самым длинным кодом) не менее
21. Свойства оптимального двоичного префиксного кода Оптимальный двоичный префиксный код к* для сообщения r, полученного из сообщения
22. Построение дерева оптимального префиксного двоичного кода Вход Кратности p1, …, pn вхождений симолов с1, ..., сn
23. кол около колокола o – 7; к – 4; л – 4; пробел – 2; a
24. пробел пробел о к л а Дерево после шага 1 Дерево после шага 2 л а
25. к пробел 0 0 0 1 1 1 1 Дерево после шага 4 0 о л
26. Пример построения кода по кодовому дереву Пометим дуги, исходящие из каждой вершины дерева, единицей и нулем
27. Для разобранного примера можно построить другое дерево Закодированное сообщение длины L = 39 010010110000100100011001001000010010111
28. Теорема Длина кодового слова в оптимальном префиксном двоичном коде ограничена порядковым номером минимального числа Фибоначчи, превосходящего
29. Алфавит, кодирование, код Типы кодирования, однозначное декодирование Метод кодирования Хафмана Метод кодирования Фано Элементы теорий вероятностей
30. Роберт Марио Фано р. 1917 Один из первых алгоритмов сжатия на основе префиксного кода Метод Фано
31. Упорядочим входной алфавит по возрастанию частот p1 Обозначим Sk = p1+p2+…+pk, S0 = 0 Строим таблицу
32. K[i][j] заполняем 0 и 1 по след. правилу Для каждого максимального интервала строк [a, b], у
33. А = {a, b, c, d, e} Частоты pa = 0.11, pb = 0.15, pc =
34. Свойства кода Фано Кодовое дерево для кода Фано обладает следующим свойством Ребра, исходящие из корня, соответствуют
35. Свойства кода Фано Код Фано неоптимальный Пример Частоты p1=0.4, p2=p3=p4=p5=0.15 Фано: 00 01 10 110 111
36. Клод Шеннон 1916 – 2001, основоположник теории информации Упорядочим входные символы по возрастанию частот и образуем
37. nk разложение Sk код p(a) = 0.08 Sa = 0.08 4 0.0001 0001 p(b) = 0.12
38. Код Шеннона -- префиксный код Почему? Пусть pk – частота вхождения k-го символа в кодируемое сообщение
39. Элементы теории информации Лекция 15
40. The Bell System Technical Journal Vol. 27, pp. 379–423, 623–656, July, October, 1948 Имеются источник (кодер)
41. Каким должен быть канал, чтобы передать данное сообщение за данное время? За какое время можно передать
42. Как измерять пропускную способность канала? Если передача всех символов занимает одинаковое время, то можно использовать символы
43. За какое время нельзя передать данное сообщение по данному каналу без потерь? Как понять, что источник
44. Как измерить скорость, с которой источник порождает информацию? В процессе передачи сообщения источник "помогает" приемнику выбрать
45. Для случая , когда приемник и передатчик знают только частоты отдельных символов p1, p2, …, pn,
46. Теорема Все функции, удовлетворяющие условиям 1-3, имеют вид H = - c ∑ pk log(pk) Информационная
47. Будем говорить, что источник передал приемнику некоторую информацию о происшедшем событии, на основании которой изменилось представление
48. Пример 1 В семье должен родиться ребенок. Пространство элементарных исходов данной случайной величины — {мальчик, девочка},
49. log22 = 1 – ? 1 бит соответствует сообщению о том, что произошло одно из двух
50. Пример 2 Из колоды вытягивается карта. Пространство элементарных исходов — 52 карты. В отсутствие изначальной информации
51. Теорема об аддитивности информации Теорема Количество информации, переносимое сообщением m1 && m2 && … && mN,
52. Предположим теперь, что источник является генератором символов из некоторого множества {х1, х2, ...,хn} (назовем его алфавитом
53. Рассмотрим теперь модель, в которой элементарным исходом является текстовое сообщение. Таким образом, Ω — это множество
54. Понятно, что анализируя различные сообщения, мы будем получать различные экспериментальные частоты символов, но для источников, характеризующихся
55. Рассмотрим сообщение m, состоящее из n1 символов x1, n2 символов x2 и т. д. в произвольном
56. Количество информации, переносимой сообщением т длины N, определяется как Количество информации, приходящейся в среднем на каждый
57. Формула Шеннона Перейдем к пределу по длине всевозможных сообщений (N —> ∞): По формуле (14), вспоминая,
58. Формула Хартли Величина I0 (A) характеризует среднее количество информации на один символ из алфавита А с
59. Событие, которое может произойти или нет, называют случайным. Примеры: попадание стрелка в мишень, извлечение дамы пик
60. Определение Пространство элементарных событий (исходов) Ω – множество всех различных событий, возможных при проведении эксперимента. Элементарность
61. Примеры: Будем бросать монету до тех пор, пока не выпадет герб. После этого эксперимент закончим. «Элементарный
62. Формула ω∈Ω означает, что элементарное событие ω является элементом пространства Ω. Многие события естественно описывать множествами,
63. Определим формально меру события µ, как отображение из пространства Ω в N, обладающее следующими свойствами: 1)
64. Введем функцию p(S) вероятности события как численного выражения возможности события S на заданном пространстве элементарных исходов
65. Говорят, что заданы вероятности элементарных событий, если на Ω задана неотрицательная числовая функция p такая, что:
66. Вероятность того, что при бросании кости выпадет единица, равна Вероятность появления четного числа очков равна Паскаль
67. Теорема о сложении вероятностей Если пересечение событий А и В непусто, то р(А U В) =
68. Теорема об умножении вероятностей Рассмотрим теперь серию экспериментов, в которой некоторая случайная величина наблюдается последовательно несколько
69. Определим формально меру события µ, как отображение из пространства Ω в N, обладающее следующими свойствами:
70. КОНЕЦ ЛЕКЦИИ
71. Избыточность кодирования Оказывается, что величина I0(А) определяет предел сжимаемости кода: никакой двоичный код не может иметь
72. Заметив, что lim N->∞ L/N - есть средняя длина кодового слова K0(A), получим независимое от сообщения
73. Посчитаем информационную емкость кода: длина исходного сообщения N = 18, длина кода L = 39 битов.
74. Реализация проекта Архиватор должен вызываться из командной строки, формат вызова: harc.exe –[axdlt] arc[.ext] file_1 file_2 …
75. Проверка целостности архива _stat, _wstat, _stati64, _wstati64 int _stat(const char* path, struct _stat *buffer); #include CRC32
76. Построение дерева Хаффмана Вход: A – исходный набор символов , P= - распределение их частот; –
77. Алгоритм: Определить алфавит А = { с1, с2 , ... , сn } сообщения S и
78. Критерии качества кодирования: — минимальная длина кода; — однозначное декодирование.
80. Скачать презентацию

Слайд 2

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

теорий вероятностей и информации – лекция 15
Модель информационной системы Шеннона
Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов
Формулы Шеннона и Хартли для удельной емкости на символ
Избыточность кодирования

Слайд 3

Алфавитом называется конечное множество символов
Сообщением алфавита А называется конечная последовательность символов

алфавита А
Множество всех сообщений алфавита А обозначается А*

Понятие кода

Слайд 4

Кодом называется отображение К : Алф1* —> Алф2*, согласованное с конкатенацией,

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

Понятие кода

Слайд 5

Кодированием сообщения называется вычисление кода сообщения
Декодированием (дешифровкой) сообщения называется вычисление его

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

Кодирование и декодирование

Слайд 6

Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) = 01, К(с)

= 10, К(d) = 1
К-1(01101010) = {addbba, bссс, …} – прообраз 01101010
Данный код не является однозначно декодируемым

Пример 1

Слайд 7

Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) = 10, К(с)

= 110, К(d) = 111
Почему данный код является однозначно декодируемым?

Пример 2

Слайд 8

Кодовое дерево
Кодовым деревом кода К:Алф1 ->Алф2 называется такое дерево Т, с

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

Слайд 9

Пример кодового дерева
Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) =

01,
К(с) = 10, К(d) = 1
Почему у сообщения 01101010 два прообраза?

Слайд 10

Пример кодового дерева
Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b) =

10,
К(с) = 110, К(d) = 111
Почему у любого сообщения один прообраз?

Слайд 11

Префиксный код
Код К называется префиксным, если для любых двух сообщений U

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

Слайд 12

Примеры префиксных кодов
Пример 1
Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(a) = 00, K(b)

= 01, K(c) = 10, K(d) = 11
Как выглядит кодовое дерево этого кода?

Слайд 13

Примеры префиксных кодов
Пример 2
Алф1 = {a,b,c,d}
Алф2 = {0,1}
К(а) = 0, К(b)

= 10, К(с) = 110, К(d) = 111
Как выглядит кодовое дерево этого кода?

Слайд 14

Однозначная декодируемость префиксного кода
Теорема Любой префиксный код однозначно декодируем
Доказательство
Пусть К –

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

Слайд 15

Алф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

Пример

Слайд 16

Пример азбука Морзе
1840 Alfred Vail по заказу телеграфной компании Samuel F.B.

Morse
Двоичный (точка, тире) непрефиксный код – почему?
Троичный (точка, тире, пауза) префиксный код – почему?
Кодовое дерево азбуки Морзе как двоичного кода для латиницы

Слайд 17

Понятие оптимального кода
Обозначим
Δ – множество кодов Алф1* -> Алф2*
К – какой-то

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

Слайд 18

Оптимальный двочиный префиксный код
Как быстро построить оптимальный двоичный префиксный код для

данного сообщения?
Использование
Сжатие данных при хранении и передаче
Устранение избыточности при шифровании данных
Алгоритм построения оптимального двоичного префиксного кода -- 1951, David A. Huffman, Massachusetts Institute of Technology
Оптимальный двоичный префиксный код не зависит от порядка символов в сообщении, только от частот отдельных символов
Связь с теорией информации

Слайд 19

Свойства оптимального двоичного префиксного кода
Пусть 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

Свойства оптимального двоичного префиксного кода
Символов с кодом длины L(K*,сn) (с самым

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

Слайд 21

Свойства оптимального двоичного префиксного кода
Оптимальный двоичный префиксный код к* для сообщения

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

Построение дерева оптимального префиксного двоичного кода
Вход
Кратности 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 – 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(а))))) }

Пример

Слайд 24

пробел
пробел
о
к
л
а
Дерево после шага 1
Дерево после шага 2
л
а

Слайд 25

к
пробел
0
0
0
1
1
1
1
Дерево после шага 4
0
о
л
а

Слайд 26

Пример построения кода по кодовому дереву
Пометим дуги, исходящие из каждой вершины

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

Слайд 27

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

39
010010110000100100011001001000010010111

Слайд 28

Теорема
Длина кодового слова в оптимальном префиксном двоичном коде ограничена порядковым номером

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

Слайд 29

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

вероятностей и информации – лекция 15
Модель информационной системы Шеннона
Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов
Формулы Шеннона и Хартли для удельной емкости на символ
Избыточность кодирования

Слайд 30

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

префиксного кода

Метод Фано

Слайд 31

Упорядочим входной алфавит по возрастанию частот p1 <= p2 <= …

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

Метод Фано

Слайд 32

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]

Метод Фано

Слайд 33

А = {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

Пример

Слайд 34

Свойства кода Фано
Кодовое дерево для кода Фано обладает следующим свойством
Ребра, исходящие

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

Слайд 35

Свойства кода Фано
Код Фано неоптимальный
Пример
Частоты 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

Клод Шеннон 1916 – 2001, основоположник теории информации
Упорядочим входные символы по

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

Метод Шеннона

Слайд 37

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

Код Шеннона -- префиксный код
Почему?
Пусть pk – частота вхождения k-го символа

в кодируемое сообщение длины N. Кодирование такого сообщения кодом Шеннона дает сообщение длины не более N*(p1*log2(p1) + p2*log2(p2) + … + pn*log2(pn))
Почему? Как Шеннон выбрал длины кодовых слов?

Свойства кода Шеннона

Слайд 39

Элементы теории информации
Лекция 15

Слайд 40

The Bell System Technical Journal Vol. 27, pp. 379–423, 623–656, July, October,

1948
Имеются источник (кодер) и приемник (декодер)
Они связаны между собой каналом передачи символов
Символы – пример дискретного сигнала
Канал не искажает и не теряет символы
Какой нужен канал, чтобы передать данное сообщение (последовательность символов) за данное время?
За какое время можно передать данное сообщение по данному каналу?
За какое время нельзя передать данное сообщение по данному каналу без потерь?
Шеннон исследовал также передачу непрерывного сигнала и передачу с шумом