4. Компрессия данных. Метод rle – класса в двоичной системе. Оптимизация.

5. Компрессия данных. Метод Huffman-а.

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

Алфавит = {00h…FFh} (256 символов – ASCII)

Message = { A=10 ; B=40 ; C=30 ; D=20 } (длина = 100 символов)

В задачах исходное сообщение может задаваться уже в виде набора символов и подсчитанных для них количеств вхождений. Тогда производить компрессию и записывать Code_message не нужно, достаточно лишь подсчитать Ratio.

Начинаем строить дерево Хаффмана: на каждом шаге ищем 2 свободные вершины, образующие наименьшую суммарную частоту – из них формируем новый узел.

В результате все начальные вершины сходятся к «корню» дерева с суммой 100.

Теперь нужно для каждой начальной вершины закодировать «обратный путь»: начиная от корня, каждый поворот соответствует одному биту: 0 или 1.

A = { влево - влево - влево } = 000  СЛОВАРЬ

B = { вправо } = 1

C = { влево - вправо } = 01

D = { влево - влево - вправо } = 001

Поскольку у дерева нет «висящих» ветвей, код получается полным.

Расчет компрессии:

6. Компрессия данных. Метод арифметического кодирования.

В отличие от предыдущих методов, здесь замена производится не по отдельным частям сообщения, а сразу целиком. Текст преобразуется в двоичную дробь, которая и является Code_message.

Перевод дробных чисел из одной системы счисления в другую

1. Чтобы перевести число в 10-ю систему, по-прежнему нужно найти сумму произведений веса каждой цифры на основание системы счисления в степени ее позиции (только в дробной части появляются отрицательные номера):

_{2 1 0 -1 -2 -3}

1 0 1 , 0 1 1 ₂ = 1*2² + 0*2¹ + 1*2⁰ + 0*2^-1 + 1*2^-2 + 1*2^-3 = 2² + 2⁰ + 2^-2 + 2^-3 = 5,375

2. Перевод из 10-ой системы претерпел минимальные изменения: целая часть числа переводится как и раньше – делением в столбик на 10, а вот дробная часть переводится по алгоритму последовательного удвоения.

12,125 ₁₀ = 1100, … ₂

0,125 ͯ 2 = 0,250 (целая часть идет в ответ)  0

0,250 ͯ 2 = 0,500 (целая часть идет в ответ)  0

0,500 ͯ 2 = 1,000 (целая часть идет в ответ)  1

… естественный конец алгоритма …

12,125 ₁₀ = 1100,001₂

7. Графические форматы. Алгоритмы сжатия графической информации.

BMP (Windows Bitmap – растровое изображение– до 16 млн цветов)

Название происходит от слов BitMaP – битовая карта или битовый массив. Он представляет собой несжатое (в основном) изображение, которое легко читается и выводится в ОС Windows через стандартные функции API. Поддерживается многими приложениями DOS, Windows и OS/2, но не поддерживается Mac OS.

Обычно BMP-файлы используются для иллюстраций в справочных системах, пиктограмм, а также в качестве фоновой картинки (обоев) для рабочего стола Windows. Если изображение невелико (пиктограмма), то BMP-файл оказывается меньше, чем аналог GIF- или JPEG-файл.

GIF (Graphics Interchange Format – формат графического обмена)

Формат GIF предложен фирмой CompuServe в качестве средства обмена растровыми изображениями между платформами и системами и поэтому поддерживается большинством программ, работающих с растровой графикой.

Использует алгоритм сжатия без потерь LZW и предназначен для сохранения растровых изображений с количеством цветов не более 256. Хорошо подходит для контрастных изображений без плавных цветовых переходов и шума: логотипы, баннеры, чертежи, схемы. Чем больше однородных по цвету областей в изображении, тем больше степень сжатия.

JPG (Joint Photographic Experts Group – объединенная группа экспертов по фотографии)

Формат JPEG предназначен для компактного хранения многоцветных изображений с фотографическим качеством. Он был разработан в 1995 г. специально для нужд Интернета. Для поиска лучшего способа записи больших объемов графической информации при международном комитете по стандартизации (750) была создана исследовательская группа Joint Photographic Experts Group. Ее работа завершилась предложениями по созданию файлового формата с высокой степенью сжатия данных. Файлы этого формата имеют расширение jpg, jpe или jpeg.

PNG (Portable Network Graphics – переносимая графика для сети)

Формат PNG позволяет сохранять изображения с глубиной цвета 24 и даже 48 бит, он также позволяет включать каналы масок для управления градиентной прозрачностью, но не поддерживает слои. Свободно распространяемых алгоритм сжатия Deflate (также используемый в ZIP) близок к LZW. Файлы PNG обычно имеют больший размер, чем аналоги GIF- и JPEG-файлы.