Сжатие информации и эффективное кодирование

1.

СЖАТИЕ ИНФОРМАЦИИ И
ЭФФЕКТИВНОЕ
КОДИРОВАНИЕ

2.

ПРИНЦИПЫ СЖАТИЯ ИНФОРМАЦИИ

3.

◦ В основе любого способа сжатия информации лежит
модель источника информации или модель
избыточности.
◦ Для сжатия информации используются некоторые
сведения о том, какого рода информация сжимается не обладая никакими сведениями об информации
нельзя сделать никаких предположений, какое
преобразование позволит уменьшить объём
сообщения. Эта информация используется в процессе
сжатия и разжатия.
◦ Модель избыточности может строиться или
параметризоваться на этапе сжатия.

4.

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

5.

◦Любой метод сжатия информации включает в
себя два преобразования обратных друг
другу:
1. преобразование сжатия;
2. преобразование разжатия.
◦Преобразование сжатия обеспечивает
получение сжатого сообщения из исходного.
◦Разжатие обеспечивает получение исходного
сообщения (или его приближения) из сжатого.

6.

Два основных класса методов сжатия
1. без потерь,
2. с потерями.
◦ Сжатие без потерь обеспечивает возможность точного
восстановления исходного сообщения.
◦ Сжатие с потерями позволяет получить только некоторое
приближение исходного сообщения, то есть отличающееся от
исходного, но в пределах некоторых заранее определённых
погрешностей.
◦ Эти погрешности должны определяться моделью приёмника,
определяющей, какие данные и с какой точностью
представленные важны для получателя, а какие допустимо
выбросить.

7.

Понятие процесса архивации файлов

8.

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

9.

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

10.

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

11.

◦ Степень сжатия файлов характеризуется
коэффициентом Кс, определяемым как отношение
объема сжатого файла Vc к объему исходного
файла Vо, выраженное в процентах:
Кс=(Vc/Vo)*100%
◦ Наиболее хорошо сжимаются файлы графических
образов, текстовые файлы и файлы данных. Почти
не сжимаются архивные файлы.
◦ Программы для архивации отличаются
используемыми методами сжатия, что
соответственно влияет на степень сжатия.

12.

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

13.

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

14.

◦ В 1952 году Дэвидом Хаффманом был предложен более сложный,
но в то же время показывающий большую эффективность на
текстовых данных метод энтропийного кодирования.
◦ Основой энтропийного кодирования является замена часто
повторяющихся фрагментов или символов коротким кодом, причем
чем чаще встречается в исходном коде символ, тем короче
соответствующий ему код. Данный алгоритм широко применяется
как в программных так и в аппаратных средствах в (сканеры) в
частности это один из методов сжатия, применяющийся в форматах
png и jpg.
◦ Таким образом архиваторов не стало меньше, просто они стали
незаметнее, большинство современных форматов данных, таких как
jpg, MP3 , уже сжаты и подвергаются распаковке при их открытии и
просмотре.

15.

◦В большинстве программ сжатия для сокращения
размера файлов используется вариант алгоритма
Зива-Лемпела на базе адаптивного словаря.
Алгоритм Зива-Лемпела, "LZ", назван в честь его
создателей, а под словарем подразумевается
метод каталогизации фрагментов данных.
◦Система, по которой составляются словари,
меняется, но в простейшем варианте она может
представлять собой нумерованный список.

16.

Если применить такой метод к цитате из речи Кеннеди «Ask not
what your country can do for you, ask what you can do for your
country». Следует выбрать повторяемые слова и поместить их в
нумерованный список. Затем вместо целого слова
записывается всего лишь его номер.
если составлен следующий словарь:
1
ask
5
сan
2
what
6
do
3
your
7
for
4
country
8
you,
закодированное предложение примет такой
вид:
1 not 2 3 4 5 6 7 8 – 1 2 8 5 6 7 3 4

17.

◦Если система известна, можно по словарю и
шаблону номера легко восстановить исходную
фразу. Именно этим занимается на компьютере
программа развертывания, когда
восстанавливает загруженный файл.
◦Есть также сжатые самораспаковывающиеся
файлы. Для создания такого файла
программист к сжатому файлу добавляет
небольшую программу восстановления. Эта
программа после загрузки восстанавливает
исходный файл.

18.

◦ Принцип работы практически всех программ-архиваторов
основан на поиске в файле так называемой «избыточной»
информации и последующем ее кодировании с целью
получения минимального объема.
◦ Самый простой алгоритм – заменить длинную
последовательность одинаковых символов одним таким
символом с указанием количества его повторов. Например,
имея в исходном файле строку NNNNNNNNNNNNNNN,
удобнее записать ее «15N». При такой записи даже
«невооруженным глазом» видно, что она занимает
значительно меньше места, чем первая – в исходном
файле.

19.

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

20.

пример. Пусть внутри файла находится последовательность
байтов, которые часто повторяются
◦ Такой исходный (называемый – архивируемый) файл занимает
15 байт и состоит из следующих символов в
шестнадцатеричной системе представления информации:
◦ Для архивации такого файла, чтобы не хранить каждый байт,
программой-архиватором фиксируется
повторяющихся символов и их позиция, и программаархиватор может представить этот файл в следующем виде:

21.

пример
◦ Такая запись означает: в файле с первой позиции пять раз
повторяется символ «F», с позиции 6 пять раз повторяется
символ «M» и с позиции 11 пять раз повторяется символ «V».
Для хранения файла в такой форме потребуется уже всего 9
байт, что на 6 байт меньше исходного.
◦ Рассмотренный метод является простым и очень
эффективным способом сжатия файлов только в том
случае, если обрабатываемый файл содержит большое
количество последовательностей повторяющихся в файле.
◦ Если исходный файл содержит небольшое количество
последовательностей повторяющихся символов, такой метод
не обеспечивает большой экономии объема.

22.

Групповое кодирование (учет повторений)
◦ Еще одна идея, используемая при упаковке данных, наиболее
хорошо подходит к сжатию простых контурных графических
изображений с небольшим числом цветов. Рассмотрим ее на
примере простейшего рисунка, на котором на синем небе
находится желтое солнышко.
◦ Фрагмент в увеличенном виде вместо хранения
информации о каждой точке, можно просто
закодировать, что 22 точки имеют синий цвет,
1 – желтый и т.п.
В результате в нашем случае вместо 38 чисел,
характеризующих цвет каждого пикселя,
оказывается достаточно всего трех пар,
указывающих количество точек и их цвет.

23.

Программы-архиваторы и их
назначение

24.

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

25.

Программные архиваторы
◦ Позволяют упаковать за один прием один
единственный файл — исполняемую программу
EXE-типа, заархивированная программа будет
сразу после ее запуска на исполнение
самораспаковываться в оперативной памяти и тут
же начинать работу.
◦ Программа становится вполовину меньше по
размеру и ее работоспособность сохраняется.
Кроме того, достигается и некоторая защита от
постороннего глаза.

26.

Дисковые архиваторы
◦ Позволяют программным способом увеличить почти вдвое
доступное дисковое пространство на жестком или гибком
диске. Это такие программы, как "Стекер", DblSpace из
комплекта DOS, DrvSpase из комплекта Windows 95 и др.
◦ Типичный дисковый архиватор представляет собой
резидентный драйвер, который архивирует любую
записанную на диск информацию и распаковывает ее
обратно при чтении. При этом на физическом диске
создается огромный архивный файл (обычно с атрибутом
"скрытый"), а для пользователя его содержимое
показывается как содержимое еще одного, созданного
при инсталляции архиватора, логического раздела диска.

27.

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

28.

Файловые архиваторы
◦ Для долговременного хранения или передачи по
компьютерным сетям файлы архивируются с помощью
файловых менеджеров и специализированных
приложений − архиваторов. Такие архиваторы позволяют
упаковывать один или несколько файлов в единый
архивный файл.
◦ Размер архивного файла меньше, чем суммарный
размер исходных файлов, но воспользоваться
запакованными программами или данными, пока они
находятся в архиве, нельзя пока они не будут распакованы.

29.

Файловые архиваторы
◦ Существует большое количество
специализированных программ — архиваторов
файлов (WinZip, WinRAR, RowerArchiver и др.).
◦ Одним из наиболее популярных средств создания
архивов и управления ими является полностью
русифицированный архиватор WinRAR, версии
которого существуют для различных операционных
систем: MS-DOS, Windows, Linux и др.