Сжатие Двоичного Кода 10 класс. Сжатие двоичного кода. Сжатие двоичного кода 5 Подготовила Зарубина Дарья

• Название: Сжатие двоичного кода 5 Подготовила Зарубина Дарья
• Анкор: Сжатие Двоичного Кода 10 класс
• Дата: 08.09.2021
• Размер: 0.89 Mb.
• Имя файла: Сжатие двоичного кода.pptx
• Тип: Документы; #230510

Сжатие двоичного кода 1.4.5

Подготовила Зарубина Дарья

• Любая информация в компьютере представляется в форме двоичного кода. Чем больше длина этого кода, тем больше места в памяти компьютера он занимает, тем больше времени требуется для его передачи по каналам связи.
• Все это складывается на производительности компьютера, на эффективности использования компьютерных сетей.

• Для сокращения объема данных выполняется их сжатие.
• Сжатие данных – это процесс, обеспечивающий уменьшение объема данных за счет изменения способа их организации.
• Возможны две ситуации при сжатии:
• Потеря информации в результате сжатия недопустимы;
• Допустима частичная потеря информации в результате сжатия.

• При упаковке данных в файловые архивы производится их сжатие без потери информации.
• Файловые архивы создаются для временного хранения на носителях или передачи по каналам связи. Для работы с этими данными требуется их распаковка (разархивирование), т.е. приведение к первоначальному виду. При этом ни один бит не должен быть потерян.

Например:

• Если сжатию подвергается текст, то после распаковки в нем не должен быть искажен ни один символ.
• Сжатая программа также должна полностью восстанавливаться, поскольку малейшее искажение приведет ее в неработоспособное состояние.

Сжатие с частичной потерей информации

• Производится при сжатии кода изображения (графики, видео) и звука.

Сжатие кода графики.

• Объем кода можно сократить за счет того, что коды цвета хранить не для каждого пикселя, а через один, два и т.д. пикселей растра.
• Чем больше такие пропуски, тем больше сжимаются данные, но при этом ухудшается качество изображения

Сжатие кода видео.

• Быстро меняющиеся фрагменты фильма можно кодировать менее подробно, чем статические кадры.

Сжатие кода звука.

• Поддается труднее всего.
• При хорошем качестве записи его объем в несжатом виде очень большой, а избыточность относительно мала.
• Используется психофизиологические особенности человеческого слуха. Учитывается, к каким гармоникам естественного звука наш слух более восприимчив, а к каким – менее. Слабо воспринимаемые гармоники отфильтровываются путем математической обработки. Сжатию также способствует учет нелинейной зависимости между амплитудой звуковых колебаний и восприятием нашим ухом громкости звучания.

Сжатие без потери информации

• Первый подход: использование неравномерного кода.
• Второй подход: выявление повторяющихся фрагментов кода.

Использование неравномерного кода.

• Символы с меньшим информационным весом, т.е.часто встречающиеся, кодировать более коротким кодом по сравнению с реже встречающимися символами.
• При таком подходе можно существенно сократить объем общего кода текста и, соответственно, места, занимаемого им в памяти компьютера.

• Одним из простейших, но весьма эффективных способов построения двоичного неравномерно кода, является алгоритм Дэвида Хаффмана

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

Адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

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

Таблица Хаффмана

В этой таблице буквы расположены в порядке убывания частоты повторяемости в тексте. Самые часто используемые в текстах буквы «Е» и «Т» имеют коды размером 3 бита, а самые редкие буквы «Q» и «Z» – 10 битов.

Особенностью данного кода является его префиксная структура. Это значит, что код любого символа не совпадает с началом кода всех остальных символов.

Префиксные коды

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

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

Префиксные коды

Построим граф этого кода.

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

Префиксные коды

Если при этом какая-то последовательность оказывается прочитанной полностью, то у конца последней дуги пишется кодируемый символ.

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

В данном примере: коэффициент сжатия = 16/29  0,55

Раскодирование (распаковка) текста производится с помощью двоичного дерева кодирования Хаффмана.

Деревом называется графическое представление (граф) структуры связей между элементами некоторой системы.

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

Корнем дерева называется единственная вершина, не имеющая родительской вершины.

Листьями дерева называются вершины, не имеющие потомков.

Графическое изображение дерева Хаффмана, соответствующего табл. 1.8

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

у	р	л	ы	-	а	М
1	1	1	1	2	4	4

Пример: Предположим, что необходимо выполнить сжатие текстового документа с фразой “мама_мыла_раму”. Наш исходный текст “весит” 112 бит, так как каждый символ занимает 8 бит в кодовой таблице, а таких символов у нас 14 штук.

2. Сортируем значения в таблице по весам, в порядке спадания:

м	а	-	ы	л	р	у
4	4	2	1	1	1	1

3. Выбираем 2 значения с минимальными весами (“р” и “у”), суммируем их веса и заменяем эти значения в таблице одним объединенным значением:

м	а	-	ы	л	ру
4	4	2	1	1	2

Формируем дерево:

4. Снова выбираем 2 значения с минимальными весами (“ы” и “л”), делаем с ними то же, что и на предыдущем шаге:

М	А	-	ЫЛ	РУ
4	4	2	2	2

Дерево стало таким:

5. Снова выбираем 2 значения с минимальными весами (“ыл” и “ру”), делаем с ними то же, что и на предыдущем шаге:

М	Ф	-	ЫЛРУ
4	4	2	4

Дерево стало таким:

6. Снова выбираем 2 значения с минимальными весами (“_” и “ылру”), делаем с ними то же, что и на предыдущем шаге:

М	А	-ЫЛРУ
4	4	6

Дерево стало таким:

7. Снова выбираем 2 значения с минимальными весами (“м” и “а”), делаем с ними то же, что и на предыдущем шаге:

МА	-ЫЛРУ
8	6

Дерево стало таким:

Последний шаг:

МА_ЫЛРУ

14

РЕЗУЛЬТАТ:

м	а	-	ы	л	р	у
00	01	10	1100	1101	1110	1111
4	4	2	1	1	1	1

КОЭФФИЦИЕНТ СЖАТИЯ: 112/40=2,8