Когда возникает потребность в сжатии информации кратко

Обновлено: 04.07.2024

Цель работы: изучить способы сжатия информации; свойства алгоритма сжатия; основные понятия технологии сжатия информации; основные форматы упаковки данных; приёмы работы с программой WinRar.
Краткие теоретические сведения

Основы сжатия информации.

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

Иногда в текстах, но чаще в таблицах и графике повторяются коды. Например, если число 0 повторяется 20 раз, то нет смысла ставить 20 нулевых байтов, вместо них ставят один ноль и коэффициент 20. Алгоритмы, основанные на выявлении повторов, называются методами RLE (Run Length Encoding).

Основные свойства алгоритмов сжатия.

У всякого сжатия есть предел. Уплотнение ранее уплотнённого файла или не даёт выигрыша или приводит к проигрышу.
Для всякого метода сжатия можно подобрать файл, применительно к которому данный метод является наилучшим. И наоборот: можно подобрать файл, который в результате сжатия не уменьшится, а увеличится.
Из вышесказанного следует, что программы – упаковщики до начала работы должны выполнять предварительный просмотр обрабатываемых файлов и выбирать тот метод упаковки, который даёт наилучший результат.

Основные понятия технологии сжатия данных.

Исходный файл . Файл, подвергаемый сжатию.

Архивный файл. Файл, полученный в результате сжатия исходного.

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

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

Основные форматы упаковки данных.

Существует большое количество форматов упаковки. Каждая программа использует свой формат, но чаще всего встречаются форматы .ZIP, .ARJ, .RAR.

Формат .ZIP. Этому формату около 20 лет. Для упаковки и распаковки файлов в таком формате используется программа WinZip. Она работает под управлением ОС Windows.

Формат .ARJ. Упаковка и распаковка производится программой ARJ.EXE. По степени сжатия превосходит формат .ZIP. Но изначально была ориентирована на операционную систему MS – DOS.

Формат .RAR. У программы WinRar российский автор – Евгений Рошаль, поэтому она очень популярна в России. Превосходит многие зарубежные аналоги, потому что позволяет работать с архивами в других форматах, например, .ZIP и .ARJ.
Основы работы с программой WinRar.

Программа WinRar имеет два режима работа: режим работы с файлами и режим работы с архивами.

а) WinRAR не ищет вирусы самостоятельно, а лишь вызывает для этой цели антивирусное ПО, уже установленное в вашем компьютере. Если такого ПО в вашей системе нет, вы не сможете воспользоваться этой командой WinRAR;

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

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

Откройте диск D, папку BANK, найдите свою папку.
На значке своей паки щёлкните правой кнопкой мыши и выберите команду Добавить в архив. Появится диалоговое окно, представленное на рисунке 1. Задайте имя создаваемому архиву Мой архив.
Установите следующие флажки: Создать SFX-архив, Добавить электронную подпись, Заблокировать архив, Протестировать файлы после упаковки.
На вкладке Комментарий напишите комментарий вручную о том, что Вы изучаете основы работы с программой – архиватором.
На вкладке Дополнительно нажмите команду Установитьпароль. Задайте пароль и запомните его. Изучите остальные вкладки и нажмите ОК.

Запишите результаты выполнения пункта 9.

Задание 2 Запишите результаты выполнения пункта 10.

Задание 3 Запишите результаты выполнения пункта 15.

Задание 4 Запишите, какие кнопки есть на панели инструментов программы WinRar.

Задание 5 Запишите, какие форматы архива может поддерживать программа WinRar.

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

Теоретические основы работы:

Основы сжатия информации.

Потребность в сжатии данных возникает по двум причинам:

информация не умещается на диске и её нужно уплотнить (особенно, если есть диаграммы, рисунки, графики);

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

Все методы сжатия информации можно условно поделить на два класса: сжатие с потерей информации и сжатие без потери информации.

Сжатие с потерей информации означает, что после распаковки уплотнённого архива мы получим документ, отличный от первоначального. Чем больше сжатие, тем больше потеря информации. Особенно незначительны потери информации в фотографических и музыкальных файлах. К алгоритмам сжатия с потерей информации относятся JPEG и MPEG. Сжатые графические файлы имеют расширение .JPG, а сжатые музыкальные файлы имеют расширение .MPG для видео или .MP3 для музыки.

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

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

Иногда в текстах, но чаще в таблицах и графике повторяются коды. Например, если число 0 повторяется 20 раз, то нет смысла ставить 20 нулевых байтов, вместо них ставят один ноль и коэффициент 20. Алгоритмы, основанные на выявлении повторов, называются методами RLE ( Run Length Encoding ).

Основные свойства алгоритмов сжатия.

Существует немало различных методов сжатия, но есть некоторые принципы и правила, которые являются общими для всех методов сжатия:

У всякого сжатия есть предел . Уплотнение ранее уплотнённого файла или не даёт выигрыша или приводит к проигрышу.

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

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

Основные понятия технологии сжатия данных.

Исходный файл . Файл, подвергаемый сжатию.

Архивный файл. Файл, полученный в результате сжатия исходного.

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

Основные форматы упаковки данных.

Формат . ZIP . Этому формату около 20 лет. Для упаковки и распаковки файлов в таком формате используется программа WinZip. Она работает под управлением ОС Windows.

Формат . ARJ . Упаковка и распаковка производится программой ARJ.EXE. По степени сжатия превосходит формат .ZIP. Но изначально была ориентирована на операционную систему MS – DOS.

Формат . RAR . У программы WinRar российский автор – Евгений Рошаль, поэтому она очень популярна в России. Превосходит многие зарубежные аналоги, потому что позволяет работать с архивами в других форматах, например, .ZIP и .ARJ.

Основы работы с программой WinRar.

Программа WinRar имеет два режима работа: режим работы с файлами и режим работы с архивами.

Основные операции с архивами.

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

Извлечение в заданную папку . Команда Извлечь в указанную папку.

Проверка архивных файлов. Выполняется командой Протестировать файлы в архиве. Если архи повреждён (часто это бывает на дискете), то его необходимо реставрировать.

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

Удаление файлов. Выполняется командой Удалить файлы или соответствующей кнопкой на панели инструментов.

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

Защита архива от изменений. Выполняется командой Заблокировать архив. В архив, защищённый подобным образом, нельзя внести комментарии и изменения.

Преобразование архивного файла в самораспаковывающийся. Команда Операции/Преобразовать архив в SFX . Такие архивы очень удобны в работе.

Просмотр информации об архиве. Выполняется командой Операции/Показать информацию.

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

ЗАМЕЧАНИЕ! Остальные возможности программы изучите во время выполнения практического задания!

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Откройте диск D, папку BANK, найдите свою папку .

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

Установите следующие флажки: Создать SFX-архив, Добавить электронную подпись, Заблокировать архив, Протестировать файлы после упаковки.

На вкладке Комментарий напишите комментарий вручную о том, что Вы изучаете основы работы с программой – архиватором.

На вкладке Дополнительно нажмите команду Установить пароль . Задайте пароль и запомните его. Изучите остальные вкладки и нажмите ОК.

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

Откройте программу WinRar командой Пуск/Программы Главного меню.

Командой Файл/Выбрать диск найдите папку BANK, в которой найдите архивную копию своей папки и выделите её одним щелчком мыши.

На панели инструментов программы WinRar нажмите кнопку Информация и изучите все вкладки открывшегося диалогового окна. Содержимое каждой вкладки выпишите в отчёт.

Выполните команду Операции/Создать отчёт. Данные созданного отчёта выпишите в тетрадь.

Выделите свою архивную папку и на панели инструментов нажмите кнопку Просмотр .

Вставьте свою дискету в дисковод и на панели инструментов программы WinRar нажмите кнопку Извлечь, в появившемся диалоговом окне выберите Диск 3,5А.

Создайте в папке BANK какую-нибудь папку и попробуйте заархивировать её по-другому: щёлкните на ней ПКМ и в контекстном меню выберите команду Добавить в архив ----.rar. Появилось диалоговое окно Имя и параметры архива?

Щёлкните на архивном файле Мой архив. Какие новые команды есть в контекстном меню? Запишите в отчёт.

Попробуйте разные команды для извлечения папки Мой архив из архивного файла: Извлечь, Извлечь с помощью команды WinRar и т. д. Всегда ли программа требует ввести заданный пароль?

Требования к отчёту:

Запишите, для чего используются программы – архиваторы?

Как установить пароль на извлекаемый файл?

Запишите результаты выполнения пункта 9.

Запишите результаты выполнения пункта 10.

Запишите результаты выполнения пункта 15.

Запишите, какие кнопки есть на панели инструментов программы WinRar.

Запишите, какие форматы архива может поддерживать программа WinRar.

Какие параметры можно установить на вкладке Резервные копии диалогового окна Имя и параметры архива ?

Когда возникает потребность в сжатии информации ?

Как происходит сжатие с потерей информации и без потери информации?

Сформулируйте основные свойства алгоритмов сжатия.

Дайте определение основных понятий теории сжатия информации.

Какие форматы сжатия данных Вы знаете?

Перечислите основные возможности программы WinRar.

Чем удобны самораспаковывающиеся архивы?

Какой архив труднее восстановить: сплошной или несплошной? Почему?

Рабочая программа учебная дисциплина б информатика Направление подготовки

. ходе практических занятий и самостоятельной работы.. Способность самостоятельно формулировать цели, . На практических занятиях осуществляется работа со специализированными библиографическими программами и онлайн . Apple Safari). Архивация веб-страниц. .

Образовательная программа основного общего образования Муниципального бюджетного общеобразовательного учреждения

. занятий физическими упражнениями. Выпускник получит возможность научиться: • характеризовать цель . . Хранение и архивация данных. Часть . практической работы. Для понимания учащимися сущности биологических явлений в программу введены лабораторные работы .

Пояснительная записка Рабочая программа по информатике в 7 классе составлена на основе следующих нормативных документов: Федеральный компонент государственного образовательного стандарта (2011г.)

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

Доброго времени суток.
Сегодня я хочу коснуться темы сжатия данных без потерь. Несмотря на то, что на хабре уже были статьи, посвященные некоторым алгоритмам, мне захотелось рассказать об этом чуть более подробно.
Я постараюсь давать как математическое описание, так и описание в обычном виде, для того, чтобы каждый мог найти для себя что-то интересное.

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

Сжатие. Нужно ли оно в наше время?

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

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

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

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

Универсальные методы сжатия без потерь

В общем случае можно выделить три базовых варианта, на которых строятся алгоритмы сжатия.
Первая группа методов – преобразование потока. Это предполагает описание новых поступающих несжатых данных через уже обработанные. При этом не вычисляется никаких вероятностей, кодирование символов осуществляется только на основе тех данных, которые уже были обработаны, как например в LZ – методах (названных по имени Абрахама Лемпеля и Якоба Зива). В этом случае, второе и дальнейшие вхождения некой подстроки, уже известной кодировщику, заменяются ссылками на ее первое вхождение.

Вторая группа методов – это статистические методы сжатия. В свою очередь, эти методы делятся на адаптивные (или поточные), и блочные.
В первом (адаптивном) варианте, вычисление вероятностей для новых данных происходит по данным, уже обработанным при кодировании. К этим методам относятся адаптивные варианты алгоритмов Хаффмана и Шеннона-Фано.
Во втором (блочном) случае, статистика каждого блока данных высчитывается отдельно, и добавляется к самому сжатому блоку. Сюда можно отнести статические варианты методов Хаффмана, Шеннона-Фано, и арифметического кодирования.

Общие принципы, на которых основано сжатие данных

Все методы сжатия данных основаны на простом логическом принципе. Если представить, что наиболее часто встречающиеся элементы закодированы более короткими кодами, а реже встречающиеся – более длинными, то для хранения всех данных потребуется меньше места, чем если бы все элементы представлялись кодами одинаковой длины.
Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon's source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.

Немного математики

Если вероятность появления элемента s_i равна p(s_i), то наиболее выгодно будет представить этот элемент — log₂p(s_i) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log₂p(s_i) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F = i)> неизменно, и вероятности элементов взаимно независимы, то средняя длина кодов может быть рассчитана как

Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.
Однако обычно вероятность появления элемента не может быть независимой, напротив, она находится в зависимости от каких-то факторов. В этом случае, для каждого нового кодируемого элемента s_i распределение вероятностей F примет некоторое значение F_k, то есть для каждого элемента F= F_k и H= H_k.

Иными словами, можно сказать, что источник находится в состоянии k, которому соответствует некий набор вероятностей p_k(s_i) для всех элементов s_i.

Поэтому, учитывая эту поправку, можно выразить среднюю длину кодов как

Где P_k — вероятность нахождения источника в состоянии k.

Итак, на данном этапе мы знаем, что сжатие основано на замене часто встречающихся элементов короткими кодами, и наоборот, а так же знаем, как определить среднюю длину кодов. Но что же такое код, кодирование, и как оно происходит?

Кодирование без памяти

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

Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a₁, a₂,… ,a_n) словом, а число n — длиной этого слова.

Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.

Введем еще два обозначения для множества всех непустых слов в алфавите. Пусть — количество непустых слов в первом алфавите, а — во втором.

Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием.

Поскольку слово может состоять и из одной буквы, то мы можем выявить соответствие букв первого алфавита и соответствующих им слов из второго:
a₁ B₁
a₂ B₂
…
a_n B_n

Это соответствие называют схемой, и обозначают ∑.
В этом случае слова B₁, B₂,…, B_n называют элементарными кодами, а вид кодирования с их помощью — алфавитным кодированием. Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.

Итак, мы определились с понятиями алфавит, слово, код, и кодирование. Теперь введем понятие префикс.

Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять — это префиксное множество. Схема ∑ обладает свойством префикса, если для любых 1≤i, j≤r, i≠j, слово B_i не является префиксом слова B_j.
Проще говоря, префиксное множество – это такое конечное множество, в котором ни один элемент не является префиксом (или началом) любого другого элемента. Простым примером такого множества является, например, обычный алфавит.

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

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

Алгоритм Хаффмана использует частоту появления одинаковых байт во входном блоке данных, и ставит в соответствие часто встречающимся блокам цепочки бит меньшей длины, и наоборот. Этот код является минимально – избыточным кодом. Рассмотрим случай, когда, не зависимо от входного потока, алфавит выходного потока состоит из всего 2 символов – нуля и единицы.

Для лучшей иллюстрации, рассмотрим небольшой пример.
Пусть у нас есть алфавит, состоящий из всего четырех символов — < a₁, a₂, a₃, a₄>. Предположим также, что вероятности появления этих символов равны соответственно p₁=0.5; p₂=0.24; p₃=0.15; p₄=0.11 (сумма всех вероятностей, очевидно, равна единице).

Итак, построим схему для данного алфавита.

Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p'.
Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p''.
Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.

Если сделать иллюстрацию этого процесса, получится примерно следующее:

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

Поскольку ни один из данных кодов не является префиксом какого-нибудь другого (то есть, мы получили пресловутое префиксное множество), мы можем однозначно определить каждый код в выходном потоке.
Итак, мы добились того, что самый частый символ кодируется самым коротким кодом, и наоборот.
Если предположить, что изначально для хранения каждого символа использовался один байт, то можно посчитать, насколько нам удалось уменьшить данные.

Пусть на входу у нас была строка из 1000 символов, в которой символ a₁ встречался 500 раз, a₂ — 240, a₃ — 150, и a₄ — 110 раз.

Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ∑p_il_i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.

Напомню, что согласно Шеннону, средняя длина кодов составляет . Подставив в это уравнение наши значения вероятностей, мы получим среднюю длину кодов равную 1.75496602732291, что весьма и весьма близко к полученному нами результату.
Тем не менее, следует учитывать, что помимо самих данных нам необходимо хранить таблицу кодировки, что слегка увеличит итоговый размер закодированных данных. Очевидно, что в разных случаях могут с использоваться разные вариации алгоритма – к примеру, иногда эффективнее использовать заранее заданную таблицу вероятностей, а иногда – необходимо составить ее динамически, путем прохода по сжимаемым данным.

Заключение

Итак, в этой статье я постарался рассказать об общих принципах, по которым происходит сжатие без потерь, а также рассмотрел один из канонических алгоритмов — кодирование по Хаффману.
Если статья придется по вкусу хабросообществу, то я с удовольствием напишу продолжение, так как есть еще множество интересных вещей, касающихся сжатия без потерь; это как классические алгоритмы, так и предварительные преобразования данных (например, преобразование Барроуза-Уилира), ну и, конечно, специфические алгоритмы для сжатия звука, видео и изображений (самая, на мой взгляд, интересная тема).

Все методы сжатия информации можно условно разделить на два больших непересекающихся класса:

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

· сжатие без потери информации.

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

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы как JPEG и MPEG. Алгоритм JPEG используется при сжатии фотоизображений. Графические файлы, сжатые этим методом, имеют расширение JPG. Алгоритмы MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются .MPG для видео и .МРЗ для музыки.

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

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

обычное явление. Так, например, если число 0 повторяется двадцать раз подряд, то нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20. Такие алгоритмы, основанные на выявлении повторов, называют методами RLE (Run Length Encoding).

Основные свойства алгоритмов сжатия

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

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

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