Лабораторная работа 3.
Сжатие и распаковка данных. 4 задания для программирования.

Задание 1. Вычисление энтропии д. с.в. Х

Вход. Закон распределения д. с.в. Х (массив значений pi = P(X = Xi), i=1,N)

Выход. Величина НХ - энтропия д. с.в. Х

Задание 2-1. Сжатие по методу Шеннона-Фэно

Вход. Закон распределения д. с.в. Х (массив значений pi = P(X = Xi), i=1,N)

Выход. А) Код Шеннона-Фэно для значений д. с.в. Х

Б) Значение энтропии д. с.в.

В) Средняя длина построенного кода ML(X)

Задание 2-2. Сжатие файлов по методу Шеннона-Фэно

Вход. Файл данных (не обязательно текстовый). Определить частоты появления символов в файле. Считая, что символ файла – д. с.в. Х, построить закон распределения д. с.в. Х (массив значений pi = P(X = Xi), i=1,N, где N – число различных символов файла)

Выход. А) Код Шеннона-Фэно для значений д. с.в. Х

Б) Значение энтропии д. с.в.

В) Средняя длина построенного кода

Г) Сжатый файл

В алгоритме сжатия предположить, что М=2 (т. е. кодовые слова формируются из символов 0 и 1)

Алгоритм:

Задание 3-1. Сжатие по методу Хаффмена

Вход. Закон распределения д. с.в. X (массив значений pi = P(X = Xi), i=1,N)

Выход. А) Код Хаффмена для значений д. с.в.

Б) Значение HX - энтропия д. с.в. X

В) Средняя длина построенного кода ML(X)

Задание 3-2. Сжатие файлов по методу Хаффмена

Вход. Файл данных (не обязательно текстовый). Определить частоты появления символов в файле. Считая, что символ файла – д. с.в. Х, построить закон распределения д. с.в. Х (массив значений pi = P(X = Xi), i=1,N, где N – число различных символов файла)

Выход. А) Код Хаффмена для значений д. с.в. Х

Б) Значение НХ - энтропии д. с.в. Х

В) Средняя длина построенного кода ML(X)

Алгоритм Хаффмена

·  Код строится при помощи двоичного (бинарного) дерева. Вероятности значений д. с.в. приписываются его листьям; все дерево строится, опираясь на листья.

·  Величина, приписанная к узлу дерева, называется весом узла.

·  Два листа с наименьшими весами создают родительский узел с весом, равным сумме их весов; в дальнейшем этот узел учитывается наравне с оставшимися листьями, а образовавшие его узлы от такого рассмотрения устраняются.

·  После постройки корня нужно приписать каждой из ветвей, исходящих из родительских узлов, значения 0 или 1.

·  Код каждого значения д. с.в. - это число, получаемое при обходе ветвей от корня к листу, соответствующему данному значению.

Задание 4. Распаковка сжатых файлов

Вход. Сжатый файл (последовательность кодов)

Кодовая таблица с элементами вида (символ, код)

Выход. Распакованный файл (последовательность символов)