Избыточность сообщений

от них одинаковое, т.е.
I = n1H1 = n2H2,
где

n1 и n2 - длина сообщения от первого и
второго источников

Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения

его энтропия.
Величина μ, называемая коэффициентом сжатия, характеризует степень укорочения

сообщения при переходе к кодированию состояний элементов, характеризующихся большей энтропией.

Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения

при одинаковых вероятностях появления всех 32 элементов алфавита, неопределенность ,

приходящаяся на один элемент, составляет Н0 = log 32 = 5 бит

Анализ показывает, что с учетом неравномерного появления различных букв алфавита H = 4,42 бит,
а с учетом зависимости двухбуквенных сочетаний H’ = 3,52 бит,
т.е. H’< H < H0

2) частная избыточность, зависящая от распределения r’’ = 1

- H/ H0;
3) полная избыточность r0 = 1 - H’/ H0
Эти три величины связаны зависимостью
r0 = r’ + r’’ - r’r’’

Обычно применяют три коэффициента избыточности:

также
смысловой зависимости между словами, избыточность русского языка (как и

других европейских языков) превышает 50%

(r0 =1 - H’/ H0 = 1 - 3,52/5 = 0,30).

помех. Это используют при помехоустойчивом кодировании

данных и преобразование кодов символов с соответствии с их частотой.

2) Алгоритмы корреляционного анализа - поиск корреляций (в простейшем случае точных повторов) между различными участками данных и замена коррелирующих данных на код(ы), позволяющая восстановить данные на основе предшествующих данных.

Алгоритмы обратимого сжатия делятся на две группы:

на коды неравной длины в соответствии с частотой появления символов

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

2) Метод Шеннона-Фано - сходен с методом Хаффмана, но использует другой алгоритм генерации кодов и не всегда дает оптимальные коды (оптимальный код - код дающий наибольшее сжатие данных из всех возможных для данного типа преобразования).

3) Арифметическое кодирование - усовершенствование метода Хаффмана, позволяющее получать оптимальные коды для данных, где частоты появления символов не являются степенью двойки (2n). Этот метод достигает теоретической энтропийной границы эффективности сжатия этого типа для любого источника.

Можно отметить следующие алгоритмы обратимого сжатия данных из первой группы:

на код символа и число повторов. Это пример элементарного и

очень понятного метода сжатия, но, к сожалению, он не обладает достаточной эффективностью.

2) Методы Лемпеля-Зива - это группа алгоритмов сжатия объединенная общей идеей: поиск повторов фрагментов текста в данных и замена повторов ссылкой (кодом) на первое (или предыдущее) вхождение этого фрагмента в данные. Отличаются друг от друга методом поиска фрагментов и методом генерации ссылок (кодов).

Для второй группы можно назвать следующие алгоритмы:

при наличии разрушений поверхности диска
корректирующие коды С1, С2, Q -

и Р - уровней восстанавливают все известные приводы, и их корректирующая способность может достигать двух ошибок на каждый из уровней С 1 и C 2 и до 86 и 52 ошибок на уровни Q и Р соответственно.
По мере разрастания дефектов, корректирующей способности кодов Рида—Соломона неожиданно перестает хватать, и диск без всяких видимых причин отказывает читаться.

Пример. CD-диск (Тема доклада!!)

используют при архивации данных. Действие средств архивации основано на использовании

алгоритмов сжатия, имеющих достаточно длинную историю развития, начавшуюся задолго до появления первого компьютера
—/еще в 40-х гг. XX века.

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

и Шеннона-Фано.
А в 1977 г. математики Якоб Зив и

Абрахам Лемпел придумали новый алгоритм сжатия (Зива-Лемпела), который позже доработал Терри Велч.
Основой для архивации послужили алгоритмы сжатия Я. Зива и А. Лемпела.

Алгоритмы сжатия

и пробелы),
кодируют их,
а при распаковке восстанавливают исходные файлы

по особым отметкам.

Суть работы архиваторов

популярность и другие программы:
RAR, ARJ, АСЕ, TAR, LHA и

т. д.

В операционной системе Windows обозначились два лидера:
WinZip (http://www.winzip.com )
и WinRAR, созданный российским программистом Евгением Рошалем
( http://www.rarlab.com).

Архиваторы

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

определяется их типом.

К примеру, степень избыточности у видеоданных обычно в несколько раз больше, чем у графических,

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

Архивация

файлов

Программы, используемые для сжатия любых видов файлов и каталогов.

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

Программы-архиваторы можно разделить на три категории

кодировании с целью получения минимального объема.

Самым известным методом архивации

файлов является сжатие последовательностей одинаковых символов.

Принцип работы архиваторов

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

их позиция.
Например, архивируемый файл занимает 15 байт и состоит из следующих символов:
В В В В В L L L L L А А А А А
В шестнадцатеричной системе
42 42 42 42 42 4С 4С 4С 4С 4С 41 41 41 41 41

Рассмотрим пример

0А 05 41
Это значит: с первой позиции пять раз

повторяется символ "В", с позиции 6 пять раз повторяется символ "L" и с позиции 11 пять раз повторяется символ "А".
Для хранения файла в такой форме потребуется всего 9 байт, что на 6 байт меньше исходного.
Этот подход не работает если обрабатываемый текст содержит небольшое количество последовательностей повторяющихся символов.

Архиватор может представить этот файл

это так называемый
оптимальный префиксный код и,
в частности,
кодирование

символами переменной длины (алгоритм Хаффмана).

Более изощренный метод сжатия данных

лишь несколькими битами, в то время как редкие символы и

фразы будут записаны более длинными битовыми строками.

Код переменной длины

а X и Q относятся к наименее встречающимся.
Таким образом,

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

Например

грамматического разбора предшествующего текста с расположением его на фразы, которые

записываются в словарь.

Указатели позволяют сделать ссылки на любую фразу в окне установленного размера, предшествующего текущей фразе. Если соответствие найдено, текущая фраза заменяется указателем на своего предыдущего двойника.

Архиваторы ARJ, РАК, PKZIP работают на основе алгоритма Лемпела-Зива

векторные.

(bitmap), состоящую из пикселей. (GIF и JPEG, BMP (стандартный формат

Windows) и TIFF, применяющийся в полиграфии. )

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

Файлы растровых форматов

координатами двух точек, а окружность — координатами центра и радиуса,

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

Файлы векторных форматов

форматов, к тому же
являющийся «родным» форматом Windows

Записанный в нем

файл представляет собой массив данных, содержащий информацию о цвете каждого пиксела

Основной недостаток формата, ограничивающий его применение, — большой размер BMP-файлов.

Конечно, можно попробовать сохранить
изображение в формате BMP со сжатием, однако это часто вызывает проблемы при работе с некоторыми графическими пакетами.

Формат ВМР

на основе алгоритма LWZ.

В нее были добавлены две функции:
альфа-канал,

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

чересстрочная развертка. Во время загрузки изображения создается эффект постепенного проявления картинки на экране.

GIF (CompuServe Graphics Interchange Format)

и
потому появилась идея сжатия с потерей качества.

Суть его

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

Таким образом, можно добиться
довольно большой степени сжатия данных —
в 10—20 раз вместо двукратного, производимого
без потерь.

более чем полувековой опыт исследований в области человеческого зрения, представила

первую спецификацию формата JPEG.

Через три года она была признана индустриальным стандартом кодирования неподвижных изображений, зарегистрированным как ISO/IEC 10918-1.

Впоследствии JPEG лег в основу
стандарта сжатия видео MPEG.

JPEG

результаты в соотношении размер/качество.

JPEG сжимает файлы весьма оригинальным образом:

он ищет не одинаковые пиксели, а вычисляет разницу между соседними квадратами размером 9x9 пикселей.

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

Естественно, чем выше уровень компрессии, тем ниже качество.

JPEG (Joint Photographic Experts Group) (тема доклада!!!)

не происходит потерь качества.
Формат поддерживают практически все программы как

PC, так и Macintosh.

TIFF — это наиболее универсальный формат, обеспечивающий среднюю степень сжатия файла.

Храня работы в TIFF, можно быть уверенным, что при просмотре файла вы увидите именно то изображение, которое сохраняли.
За качество придется расплачиваться достаточно большим объемом файлов.

Формат TIFF (Tagged Image File Format)

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

и
файлы, сжатые, например, кодеком DivX, которые также имеют расширение AVI.

Стандарт MPEG-4 (тема доклада!!!)

воспроизвести
Типы воспроизводимых файлов

разрабатывается исключительно фирмой Microsoft,
то кодек для сжатия цифрового звука

в стандарте МРЗ может создать любой программист.

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

В условиях конкурентной борьбы за качество МРЗ-файлов на первое место вышел проект нескольких программистов — Lame.

Кодеки (Тема доклада!!)

ликвидации проблем с отображением информации в файлах.

PDF использует

качественные алгоритмы сжатия (LWZ): если объем файла Word, содержащего пару картинок, вряд ли получится меньше мегабайта, то точно такой же PDF вполне уместится в 300-400 Кбайт.

PDF умеет встраивать в себя все используемые в документе шрифты.

в формат PDF можно преобразовать любой электронный документ.

ФОРМАТ PDF