Сжатие информации. Алгоритм Хаффмана

в них содержания.

счет упрощения кодов, исключения из них постоянных битов или представления

повторяющихся символов в виде коэффициента повторения.
Важнейшая характеристика процесса сжатия – коэффициент сжатия.
Коэффициент сжатия – отношение объема исходного сообщения к объему сжатого.

используется, если в записи сообщения присутствует небольшая часть алфавита.
2. Сжатие

с использованием кодов переменной длины.
Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких — длинными.

отделения кодов символов друг от друга.
Решить эту проблему позволяет

условие, достаточное для однозначного декодирования сообщений с переменной длиной кодовых слов, условие Фано:
Никакое кодовое слово не является началом другого кодового слова.
По-другому условие Фано называют свойством префиксности, а код, удовлетворяющий этому условию, называют префиксным кодом.

ориентированный граф, определяющий этот код.
Например, кодовые слова 00, 01,

10, 011, 100, 101, 1001, 1010, 1111, кодируют соответственно буквы: a, b, c, d, e, f, g, h, i.

помеченные 0 и 1. Затем из конца каждой такой дуги

входят новые дуги, помеченные 0 и 1 так, чтобы, идя по этим дугам от корня, читалось начало какого-либо кодового слова.

у конца последней дуги пишется кодируемый символ.
Из получившихся вершин

снова проводятся дуги — и так далее, до тех пор, пока не будут исчерпаны все коды.

этому графу легко восстанавливается код каждого символа — надо просто,

идя от корня к листу, помеченному данным символом, выписать 0 и 1 в порядке их прочтения.
Идея префиксного кодирования была использована американским ученым Д.Хаффманом для создания эффективного алгоритма сжатия символьной информации. 

разработан 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В

настоящее время используется во многих программах сжатия данных.

равен количеству вхождений данного символа в сжимаемое сообщение.
2. Среди вершин

выбираются две с наименьшими весами (если таких пар несколько, выбирается любая из них).
3. Создается следующая вершина графа, из которой выходят две дуги к выбранным вершинам; одна дуга помечается цифрой 0, другая — символом 1.
Вес созданной вершины равен сумме весов, выбранных на втором шаге вершин.
4. К новым вершинам применяются шаги 2 и 3 до тех пор, пока не останется одна вершина с весом, равным сумме весов исходных символов.

+ 4·2 + 4·1 + 4·2 + 4·2 + 3·4

+ 4·2 + 4·2 + 3·5 = 95 бит.
Теперь подсчитаем объем этого сообщения, если каждый его символ кодировать цепочкой из 0 и 1 равной длины. Т.к. в сообщении 10 различных символов вес одного символа 4 бита. Поэтому после кодирования получится сообщение объемом 4·3 = 120 бит.
Коэффициент сжатия равен 120/95 =1,26.
Сообщение в памяти компьютера закодировано с помощью ASCII-кодов, каждый символ весит 8 бит. Значит, объем исходного сообщения 240 бит.
Коэффициент сжатия равен 240/95 = 2,53. 

и целым количеством бит, алгоритм Хаффмана обеспечивает наилучшее сжатие.

и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную

двоичную последовательность.
А–00, Б–010, В–011, Г–101, Д–111.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно?
Выберите правильный вариант ответа.
1) для буквы Б – 01 2) это невозможно
3) для буквы В – 01 4) для буквы Г – 01

Задача А9

отходит две ветки: 0 или 1.
Разместим на дереве буквы А,

Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах:

Д код можно сократить. Выберем ответ из предложенных вариантов:
1) для

буквы Б – 01 2) это невозможно
3) для буквы В – 01 4) для буквы Г – 01

Ответ: 4.

А, Б, В, Г, решили использовать неравномерный по длине код:

A=0, Б=10, В=110.
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 1 2) 1110 3) 111 4) 11

Для самостоятельной работы

коды представлены в таблице:
Задача А9
Определить, какой набор букв закодирован двоичной

строкой 0110100011000

А, Б, В, Г, решили использовать неравномерный по длине код:

A=0, Б=10, В=110.
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

Задача А9