Что такое сжатие. Как сжать файл
Пожалуй, каждый Интернет-пользователь хоть раз сталкивался с необходимостью отправки файла, вес которого значительно превышает размеры, допустимые при пересылке. И уж, во всяком случае, у каждого возникала необходимость отправить несколько файлов разом. Задача вдвойне усложняется в случае, если они большого размера.
На самом деле, ничего сложного нет. Достаточно лишь знать, как сжать файл. В первую очередь выясним, что под этим подразумевается.
Сжатие файлов - это процесс уменьшения повторяемых символов или оптимизации последовательности байтов, вследствие чего исходный документ получается меньших размеров. Такой процесс носит название архивирование, или создание архива.
С тем, чтобы добиться такого эффекта, потребуется обзавестись специальными программами. Например, для создания файла формата ZIP, достаточно установить на компьютере Windows любой версии. Программа-архиватор в нем носит встроенный характер. Также для открытия (и сжатия) файлов типа RAR подойдет программа Winrar. И, несмотря на то, что принцип их работы схож, большей популярностью пользуется последняя. Ее и изучим подробнее.
Итак, перед тем, как сжать файл любого вида и формата, качаем на просторах Интернета Winrar. Существуя длительное время на рынке, она не имеет аналогов, и, что самое приятное, является условно-бесплатной. Функционал этой программы и перечень поддерживаемых форматов постоянно пополняется, что не может не радовать простого пользователя. А существование так называемого "бесплатного пробного периода" (который плавно перетекает в период постоянного пользования) эту радость удваивает. Когда программа скачана и установлена, выбираем файл или список таковых, которые хотим заархивировать. После кликаем на него правой кнопкой мыши и в видим, что Winrar добавил в него некоторые свои функции. Среди них:
- добавить в архив;
- добавить в архив <имя объекта>;
- добавить в архив и отправить по Е-мэйл;
- добавить в архив <имя объекта> и отправить по Е-мэйл.
Под первым и третьим пунктом подразумевается возможность как сжать файл в единственном экземпляре, так и добавить еще несколько к архиву. В этом случае вы можете руководить процессом, то есть выбрать имя документа, степень и формат сжатия, а также выполнить некоторые действия с исходным материалом. Во втором и четвертом пунктах - сжать конкретный, выбранный вами файл, никаких манипуляций с вашей стороны не предполагается, программа все сделает сама в
Давайте на примере более подробно рассмотрим, как сжать PDF-файл. Поскольку этот формат предназначен, в первую очередь, для размещения полиграфической продукции, то есть журналов, книг и прочего в их первозданном виде, со всеми картинками, его "вес" нередко достаточно велик, поэтому его уменьшают путем архивации или сжатия. Процесс при этом не наносит урон качеству, то есть все картинки, да и сам текст, никак не изменятся после сжатия. После того, как файл обработан и отправлен адресату (если это являлось конечной целью), его следует распаковать той же программой. То есть у адресата также должен быть установлен Winrar. Распаковав документ, вы можете легко убедиться, что потери в качестве не было.
Перед тем, как сжать файл, имейте в виду: нужно чем-то жертвовать. А именно: желая сохранить прежнее качество, вы добьетесь сжатия всего на несколько мегабайт, в зависимости от размера исходного. То есть файл весом 20 мб может быть сжат до 17-18 без изменений в качестве. Если же уровень качества файла при последующем его извлечении из архива не представляет важности, можно будет использовать функцию "максимального сжатия". Файл станет гораздо меньше, чем исходник, но качество, что логично, пострадает.
Нередко сайт предлагает сжать файлы (в том числе PDF) в режиме онлайн и абсолютно бесплатно, но куда удобнее иметь соответствующую программу под рукой.
Что такое архивация и сжатие файлов
Сколько существуют компьютеры, столько их обладателям не хватает памяти на внутренних и съёмных дисках для размещения своих данных. Стремительный рост объёмов дисков не решает эту проблему. Если 10 лет назад нам не хватало 20 мегабайт на винчестере, то сегодня точно так же не хватает 20 гигабайт.
Размеры используемых нами программ и данных растут вместе с ростом объёмов винчестеров. Мы уже можем себе позволить хранить на винчестере библиотеку из нескольких десятков тысяч книг. Но музыкальных произведений можем хранить на винчестере пока несколько сот часов звучания, а видеофильмов – всего несколько десятков часов просмотра. Поэтому проблема архивирования или сжатия данных остаётся так же актуальна, как и 10, и 20 лет назад.
Как же происходит сжатие информации?
Приведём, как обычно, грубую, но понятную аналогию. Сжатие данных похоже на производство сухого молока или сухофруктов. То есть, это – процесс удаления воды, которую затем можно добавить, чтобы предать продукту первоначальный вид.
А какая в данных может быть вода? Это вода информационная. В данных встречается много повторов. Это можно использовать для сжатия данных.
Например, сжатие текстовых файлов происходит приблизительно так. Составляется таблица встречающихся в тексте слов и выражений. Затем всем словам и выражениям в этой таблице даются номера. И весь текст в файле заменяется номерами из таблицы слов и выражений. Такой способ позволяет уменьшить размер текстового файла в 2-3 раза. Иногда текст сжимается и в 10 раз, если в нём много повторов.
Программа, переводящая текстовый файл в "сжатый" вид, называется упаковщиком. А полученный в результате сжатия файл называется упакованным или сжжатым файлом.
Очень часто сжатые файлы называют архивами или архивными файлами, что, если подходить строго к терминологии, неверно. Изначально архивами назывались файлы, специально созданные во время процессов резервного копирования. В ходе такого процесса создавался один файл, который содержал в себе несколько исходных файлов и папок. Это и был архив. Никакого сжатия при этом не производилось. Подобная ситуация до сих пор существует в операционной системе Linux, где архивация данных и сжатие данных являются двумя независимыми процессами. В операционной системе MS-DOS, а затем и в MS Windows программы сжатия данных с самых первых своих версий стали поддерживать как сжатие, так и архивацию данных, то есть создавали сжатый файл, содержащий не один, а несколько исходных (архивируемых) файлов и папок. С той поры в этих операционных системах понятие "архивация" означает и архивацию (сбор в один файл-архив) , и одновременное сжатие данных.
Поскольку архивный файл записан не в текстовом формате, с ним не могут работать редакторы текстов. Перед открытием архивного файла редактором текстов этот файл необходимо разархивировать. Разархивацию производит та же самая программа – архиватор. После разархивации текстовый файл приобретает точно такой же вид и размер, как и до архивации.
Архиваторы текстов могут архивировать также файлы программ. Только программы гораздо меньше сжимаются, чем текст.
Упаковщики, применяемые для сжатия текстов и программ, не могут эффективно сжимать звуковые, графические или видео файлы. Для их сжатия были разработаны другие, более сложные, алгоритмы. Правда, после распаковки полученные файлы немного отличаются от оригиналов (такое сжатие называется сжатием с потерями). Но этого не улавливает обычное человеческое ухо и не замечает обычный глаз на экране монитора.
Краткая история архиваторов
Насколько я помню, первым популярным архиватором данных был архиватор под названием «ARJ». Он создавал архивные файлы с аналогичным расширением «ARJ». Это было ещё в конце 80-х – начале 90-х годов прошлого века. Такие файлы до сих пор ещё встречаются. Обычно они набраны в ДОСовской кодировке.
Затем появились два самых популярных на сегодняшний день на территории СНГ архиватора: «RAR» и «ZIP». Сейчас они представлены программами «WinRAR» и «WinZIP». Причём, программа «WinRAR» умеет создавать как «RAR», так и «ZIP» архивы. А разархивировать «WinRAR» умеет архивы полутора десятков форматов. В этом смысле «WinRAR» является для нас универсальным и удобным архиватором (но не бесплатным).
А как же другие, не текстовые данные?
Рассмотрим графические файлы. Незаархивированная графика – это рисунок, состоящий из множества разноцветных точек. В таком формате для каждой точки рисунка или фотографии задаётся цвет. Графический файл такого рисунка имеет расширение «BMP». Но такие файлы обладают довольно солидным размером. Даже небольшая фотография в формате «BMP» будет иметь размер в несколько мегабайт. То есть, она не поместится на дискету, и по сети Интернет передать её будет нелегко.
Для уменьшения размера графического файла его сжимают специальными математическими методами. Таким образом графический файл можно уменьшить в размере в 20-30 раз. Сжатый графический файл нельзя полностью восстановить. При распечатывании на хорошем принтере будет заметно ухудшение качества рисунка. Но на экране монитора этого видно не будет.
Наиболее распространённые форматы сжатия изображения – это «GIF» и «JPEG» (или «JPG»). Создать такие форматы графических файлов может, например, графический редактор «ФотоШоп» или уже знакомый нам «ФайнРидер». Чем глубже сжатие рисунка, тем больше теряет он в качестве.
Гораздо позже появились эффективные методы сжатия звука. Если Вы зайдёте на обычный музыкальный компакт-диск, то обнаружите там файлы с расширением «CDA». В таких файлах содержится несжатый цифровой звук. Такие файлы имеют очень большой размер. На компакт-диск помещается 80 минут музыки в незаархивированном виде. Сжатие звуковых файлов потребовало специальных исследований человеческого слуха. Оказалось, что часть звуков можно убрать из звукового файла, и это будет незаметно для слуха человека.
Самый распространённый формат сжатого звука – это «MPEG3» (или «MP3»). Его создают специализированные редакторы звука и программмы-перекодировщики из других звуковых форматов. Проигрывание на компьютере сжатых звуковых файлов в формате «MP3» требует мощности процессора не менее 100 мегагерц. Можно сжимать звуковой файл в десятки раз. Но при большом сжатии начинает безвозвратно теряться качество звука.
Видеофильм объединяет в себе звук и графику. Помимо звука – это ещё 24 кадра на каждую секунду. Отсюда понятны огромные размеры файлов с видеофильмами и необходимость их сжатия.
При появлении компакт-дисков художественный фильм не помещался на один диск. Эту задачу решил сжатый формат «MPEG4». Показ сжатого видео ещё больше повышает требования к мощности процессора. Для проигрывания MPEG4 уже недостаточно 200 мегагерц.
Надеюсь, Вас не будет пугать в дальнейшем большое количество форматов для текстовых, графических, звуковых и видео файлов. Обычно это сжатые или заархивированные данные. Для их просмотра нужно воспользоваться программой, знающей алгоритм разархивации файлов данного типа. Операционная система Windows XP содержит в себе программы для просмотра данных, записанных в различных форматах.
Упаковщик WinRAR
WinRAR применяется для упаковки текстов и программ. Причём, архив WinRAR может содержать как файлы, так и папки. WinRAR позволяет добавлять файлы и папки в архив и извлекать их оттуда.
Если на Вашем компьютере установлен упаковщик WinRAR и Вы откроете нажатием Enter архивный файл, то для обработки архива запустится программа WinRAR и раскроется её окно.
Курсор при этом попадёт в большое окно типа Просмотр списка, в котором будет отражено содержимое архива. Вы увидите все файлы и папки, упакованные в архиве. Перемещаться по архиву можно по правилам работы с Моим компьютером. Более того, мы можем выйти из текущего архива в родительскую папку и войти в любой другой архив, имеющийся на компьютере.
WinRAR имеет меню, в котором содержатся команды для работы с архивами.
Но мы подробнее остановимся на более простом способе работы с упаковщиком WinRAR .
Работа с упаковщиком WinRAR через контекстное меню
Когда мы устанавливаем на компьютере WinRAR , в контекстное меню внедряются некоторые команды этой программы. Это как раз и есть самые необходимые нам для обычной работы команды по созданию и распаковке архива.
Распаковка файлов
Допустим, курсор выделяет архив под названием Литература.rar , и мы вызываем контекстное меню нажатием комбинации Shift+F10 . Мы найдём в контекстном меню 3 команды:
- Извлечь файлы,
- Извлечь в текущую папку,
- Извлечь в Литература.
По команде Извлечь в текущую папку содержимое архива будет извлечено в ту же папку, где находится сам архивный файл. Этого нельзя будет сделать, если мы открыли архив на компакт-диске. Такой архив сначала нужно скопировать на винчестер.
По команде Извлечь в Литература в той же папке, где находится архив Литература.rar , будет создана папка с именем Литература. И уже во внутрь папки Литература будет извлечено содержимое архива Литература.rar . Так удобно распаковывать архив, содержащий много папок и файлов, чтобы они не перемешивались с содержимым текущей папки.
По команде Извлечь файлы будет открыт диалог Путь и параметры извлечения. В этом диалоге можно создать или выбрать папку для извлечения содержимого архива, а также установить различные дополнительные параметры процесса извлечения файлов из архива.
В любом случае, после извлечения файлов сам архив остаётся в неизменном виде.
Если у Вас установлена англоязычная версия программы WinRAR , то все команды и диалоговые окна будут представлены на английском языке.
Упаковка файлов и папок в общий архив
Если Вы хотите упаковать несколько файлов и папок в один общий архив, то предварительно их нужно выделить. Затем нужно вызвать контекстное меню комбинацией Shift+F10 . Среди пунктов контекстного меню Вы найдёте две интересные нам команды архивации.
Вторая из команд автоматически создаст rar-архив и занесёт в него выделенные Вами файлы и папки. Если был выделен один файл или одна папка, то rar-архив получит имя этого файла или этой папки. Если было выделено несколько файлов и папок, то rar-архив получит имя текущей папки, в которой расположены все выделенные только что Вами объекты.
Первая же из команд в контекстном меню называется Добавить в архив. Она вызывает многостраничный диалог под названием Имя и параметры архива. Рассмотрим его чуть подробнее.
Всё самое главное находится в этом диалоге на вкладке Общие, куда мы сразу и попадём.
При открытии диалога курсор находится в строке редактирования с памятью под названием Имя архива. Понятно, что здесь мы можем сменить имя создаваемого архива.
Следующей в порядке табуляции расположена кнопка Обзор. Нажав эту кнопку, мы сможем выбрать другую папку для создания архива, отличную от текущей папки.
Следующим расположен очень интересный список под названием Разделить на тома размером (в байтах) . Мы можем задать размер тома вручную или выбрать его из заготовленного списка. Здесь отражается очень важное свойство программы WinRAR . Она умеет разбивать архивный файл на несколько архивных файлов одинакового размера. Это позволяет разбить архив на куски, которые умещаются на дискете. Тогда Вы сможете унести в коробке дискет большой архивный файл. Честно говоря, с появлением Сидирайтеров и блоков флэш-памяти это свойство rar-архивов понемногу начинает утрачивать своё значение.
Из остальных флажков выделим только один. Он называется Создать SFX-архив. Вот это действительно важный флажок. Если его установить, WinRAR создаст самораспаковывающийся архив. Это значит, что вместо файла с расширением.RAR будет создан файл с расширением.EXE . А фактически в rar-архив встраивается программа по его распаковке. Запуск самораспаковывающегося архива на выполнение приводит к его распаковке. Это позволяет нам без труда распаковывать архив на компьютере, на котором не установлен соответствующий архиватор. По принципу самораспаковывающихся архивов устроены инсталляционные пакеты большинства приложений.
Если мы выберем создание самораспаковывающегося SFX-архива, то на вкладке Дополнительно активизируется кнопка Параметры SFX . Эта кнопка вызывает диалог, в котором можно задать путь для распаковки архива и установить, какие программы должны выполниться до и после распаковки архива. Практически – это возможность создать полноценный инсталляционный пакет. Представьте себе. Запущенный с компакт-диска самораспаковывающийся архив распаковывается на диск C: . После этого из вновь созданной папки запускается на выполнение программа, которая выполняет установку и настройку нашего пакета программ.
Пожалуй, это – всё, что нужно знать, чтобы начать уверенно и быстро работать с архивными данными.
Обзор урока
Программы-упаковщики или архиваторы позволяют упаковывать текстовые файлы и программы, высвобождая нам дополнительную память на встроенных и внешних дисках. Благодаря этому объём дисков как бы увеличивается.
Разные типы данных сжимаются разными программами по разным алгоритмам.
Универсальная программа для сжатия текстовых файлов и файлов программ – это WinRar . WinRAR умеет создавать самораспаковывающиеся и многотомные rar-архивы, а также обычные zip-архивы. Можно задавать путь для распаковки самораспаковывающегося архива.
Кроме того, WinRAR умеет распаковывать архивы многих других архиваторов.
Для работы с WinRAR не обязательно вызывать эту программу явно. После выделения группы файлов и папок можно воспользоваться контекстным меню. Здесь будут присутствовать все основные команды по архивации и разархивации данных.
Самый популярный формат сжатых графических изображений – это.GPEG . Для звука – это формат.MP3 , а для видео – MP4 .
Проигрывание на компьютере сжатых звуковых файлов и просмотр видеофайлов требует больших вычислительных ресурсов.
Задания к уроку
Установите на своём компьютере упаковщик данных WinRAR .
Создайте в корне диска D: или в каком-нибудь другом месте временную папку. Назовите её Литература. Скопируйте в эту папку несколько файлов и папок по Вашему усмотрению.
Выделите курсором папку Литература. Вызовите контекстное меню. Создайте архив Литература.rar , воспользовавшись командой Добавить в Литература.rar". Воспользовавшись диалогом свойств, сравните размеры папки Литература и архива Литература.rar .
Вызовите диалог создания архива для папки Литература, воспользовавшись командой Добавить в архив из контекстного меню. Исправьте имя архива с Литература на Библиотека. Измените формат архива с RAR на ZIP .. После создания архива Библиотека.zip сравните его размер и размер архива Литература.rar .
Вызовите диалог свойств папки Литература. Запомните размер этой папки. Для папки Литература воспользуйтесь командой Добавить в архив из контекстного меню. В диалоге создания архива задайте размер тома так, чтобы архив состоял из двух или трёх частей. Не забывайте, что размер тома задаётся в байтах, а не в килобайтах. Установите флажок создания самораспаковывающегося архива. Особо любознательные могут в Свойствах SFX архива установить в качестве пути для распаковки корень диска C:\ . Создайте многотомный самораспаковывающийся архив. Определите размер и название каждой из его частей. Сравните общий размер самораспаковывающегося архива и обычного rar-архива.
Создайте Новую папку и перенесите туда путём вырезания и вставки все созданные Вами архивы. Распакуйте архив Литература.rar командой Извлечь в Литература из контекстного меню. Распакуйте архив Библиотека.zip командой Извлечь в Библиотека из контекстного меню. Распакуйте самораспаковывающийся многотомный архив, запустив на выполнение файл Литература,part1.exe . Обследуйте Новую папку. Найдите три варианта восстановления папки Литература из трёх различных архивов.
Вызовите в явном виде программу WinRAR , открыв архив Литература.rar . Просмотрите содержимое архива при помощи курсорных клавиш. Оставаясь в окне программы WinRAR , выйдите за пределы архива Литература.rar при помощи клавиши BackSpace . Скопируйте в буфер обмена какой-нибудь файл или папку. Войдите вновь в архив Литература.rar , как входят в папку (Нажатием Enter), и вставьте вовнутрь архива скопированный файл или папку. Проверьте, что архив пополнился новым содержимым. Таким же образом вставьте в архив Литература.rar файл из какого-нибудь другого архива. Удалите какой-нибудь файл из архива Литература.rar , воспользовавшись меню Файл программы WinRAR или клавишей Del .
Список горячих клавиш к уроку
Горячие клавиши Windows
Shift+F10 – вызвать контекстное меню
Alt+Enter – вызвать диалог свойств
Горячие клавиши JAWS
Insert+Серый минус – Перейти к JAWS-курсору и совместить его с системным курсором.
Серый плюс – вернуться к системному курсору
Горячие клавиши WinRAR.
Control+C – скопировать объект в буфер обмена
Control+V – вставить объекты из буфера обмена в архив
"Сжатие данных"
Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.
Для человека избыточность данных часто связана с качеством информации, поскольку избыточность, как правило, улучшает понятность и восприятие информации. Однако, когда речь идет о хранении и передаче информации средствами компьютерной техники, то избыточность играет отрицательную роль, поскольку она приводит к возрастанию стоимости хранения и передачи информации. Особенно актуальной эта проблема стает в случае обработки огромных объемов информации при незначительных объемах носителей данных. В связи с этим, постоянно возникает проблема уменьшения избыточности или сжатия данных. Если методы сжатия данных применяются к готовым файлам, то часто вместо термина "сжатие данных" употребляют термин "архивация данных", сжатый вариант данных называют архивом , а программные средства, которые реализуют методы сжатия называются архиваторами .
В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:
Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;
Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;
Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).
Существует много практических алгоритмов сжатия данных, но все они базируются на трех теоретических способах уменьшения избыточности данных. Первый способ состоит в изменении содержимого данных, второй - в изменении структуры данных, а третий - в одновременном изменении как структуры, так и содержимого данных.
Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым , то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть:
JPEG - для графических данных;
MPG - для для видеоданных;
MP3 - для аудиоданных.
Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым . В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:
GIF, TIFF - для графических данных;
AVI - для видеоданных;
ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.
Существует много разных практических методов сжатия без потери информации, которые, как правило, имеют разную эффективность для разных типов данных и разных объемов. Однако, в основе этих методов лежат три теоретических алгоритма:
алгоритм RLE (Run Length Encoding);
алгоритмы группы KWE(KeyWord Encoding);
алгоритм Хаффмана.
Алгоритм RLE
В основе алгоритма RLE лежит идея выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения. Например, пусть задана такая последовательность данных, что подлежит сжатию:
1 1 1 1 2 2 3 4 4 4
В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле:
где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.
Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).
Алгоритмы группы KWE
В основе алгоритма сжатия по ключевым словам положен принцип кодирования лексических единиц группами байт фиксированной длины. Примером лексической единицы может быть обычное слово. На практике, на роль лексических единиц выбираются повторяющиеся последовательности символов, которые кодируются цепочкой символов (кодом) меньшей длины. Результат кодирования помещается в таблице, образовывая так называемый словарь.
Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.
Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения в коды фиксированной длины. Таблица имеет так называемое свойством опережения, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).
Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).
Алгоритм Хаффмана
В основе алгоритма Хаффмана лежит идея кодирования битовыми группами. Сначала проводится частотный анализ входной последовательности данных, то есть устанавливается частота вхождения каждого символа, встречащегося в ней. После этого, символы сортируются по уменьшению частоты вхождения.
Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Рассмотрим простой пример, иллюстрирующий работу алгоритма Хаффмана.
Пусть задан текст, в котором бурва "А" входит 10 раз, буква "В" - 8 раз, "С"- 6 раз, "D" - 5 раз, "Е" и "F" - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.
Таблица 1.
|
Частота вхождения |
Битовый код |
|
Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).
На практике программные средства сжатия данных синтезируют эти три "чистых" алгоритмы, поскольку их эффективность зависит от типа и объема данных. В таблице 2 приведены распространенные форматы сжатия и соответствующие им программыи-архиваторы, использующиеся на практике.
Таблица 2.
|
Формат сжатия |
Операционная система MS DOS |
Операционная система Windows |
||
|
Программа архивации |
Программа разархивации |
Программа архивации |
Программа разархивации |
|
Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются:
создание нового архива;
добавление файлов в существующий архив;
распаковывание файлов из архива;
создание самораспаковающихся архивов (self-extractor archive);
создание распределенных архивов фиксированного размера для носителей маленькой емкости;
защита архивов паролями от несанкционированного доступа;
просмотр содержимого файлов разных форматов без предварительного распаковывания;
поиск файлов и данных внутри архива;
проверка на вирусы в архиве к распаковыванию;
выбор и настройка коэффициента сжатия.
Контрольные вопросы
1. Какие факторы влияют на степень избыточности данных? 2. Что такое архив? Какие программные средства называются архиваторами? 3. Почему методы сжатия, при которых происходит изменение содержимого данных, называются необратимыми? 4. Приведите примеры форматов сжатия с потерями информации. 5. В чем состоит преимущество обратимых методов сжатия над необратимыми? А недостаток? 6. Которая существует зависимость между коэффициентом сжатия и эффективностью метода сжатия? 7. В чем состоит основная идея алгоритма RLE? 8. В чем состоит основная идея алгоритмов группы KWE? 9. В чем состоит основная идея алгоритма Хаффмана? 10. Какие вы знаете програми-архиваторы? Коротко охарактеризуйте их.
Информатика. Базовый курс. / Под ред. С.В.Симоновича. - СПб., 2000 г.
А.П.Микляев, Настольная книга пользователя IBM PC 3-издание М.:, "Солон-Р", 2000, 720 с.
Симонович С.В., Евсеев Г.А., Мураховский В.И. Вы купили компьютер: Полное руководство для начинающих в вопросах и ответах. - М.: АСТ-ПРЕСС КНИГА; Инфорком-Пресс, 2001.- 544 с.: ил. (1000 советов).
Ковтанюк Ю.С., Соловьян С.В. Самоучитель работы на персональном компьютере - К.:Юниор, 2001.- 560с., ил.
Здравствуйте! Не могли бы вы объяснить начинающему пользователю, как сжимаются файлы всякими архиваторами? Хотя бы в общих чертах. А то я с трудом себе представляю, как это вообще может быть.
Виталий
Совершенно верно, Виталий, это действительно не так просто себе представить, тем более, если не знаешь алгоритма. Но читателям журнала «Компьютер» повезло;), поскольку я в свое время много интересовался алгоритмами сжатия данных и, как программист, даже пробовал писать собственный архиватор.
Сжатие данных (англ. data compression) - алгоритмическое преобразование данных, производимое с целью уменьшения их объема. Применяется для более рационального использования устройств хранения и передачи данных. Процесс сжатия еще называют упаковкой данных или компрессией. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).
Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка).
Итак, давайте начнем с простого примера. Допустим, у нас есть текстовый файл, который содержит строку текста:
АААГГДЕЕЕЕЖЖУУУККККИИИ
Текст довольно странный, согласитесь, но сейчас мы его сожмем, и он у нас будет занимать меньше места. Основной принцип сжатия весьма прост и сводится к следующему: каждая комбинация подряд повторяющихся символов заменяется одним таким символом и числом его повторений. Т.е. наш исходный текст в сжатом виде будет выглядеть так:
А3Г2Д1Е4Ж2У3К4И3
Таким образом, вместо 22 символов мы получили 16 символов. Конечно, такие тексты как наш исходный встречаются довольно редко, не говоря уже о бессмыслице, которая заключена в нем. Но ведь файлы, подвергающиеся сжатию, бывают не только текстовые, но и всякие картинки, музыка, видео, программы.
Данный пример довольно упрощен и не отражает эффективность, которую обычно демонстрируют при сжатии архиваторы. Так у нас получилось сжатие в 22/16 = 1,375 раза, хотя архиваторы, как правило, способны сжимать файлы в 2-10000 раз. Все зависит от повторяемости значений байт в файле.
Какие архиваторы бывают
Например, во времена незабвенной MS-DOS были архиваторы ARJ, PKZIP, HA, RAR, ARC, ACE и упаковщики программ LZEXE и PKLITE. Позднее для операционной системы Windows были созданы WinAce, WinZIP, WinRAR, 7Zip и известный мне упаковщик UPX.
Сжатие бывает с потерями и без. Сжатие без потерь позволяет восстановить исходные данные с точностью до бита. Такое сжатие применяется для упаковки текста, программ, различных данных в купе и осуществляется всеми перечисленными выше архиваторами.
Сжатие с потерями можно назвать адаптивным сжатием, и применяется для упаковки изображений, видео и звука, поскольку такие данные сжатию без потерь поддаются весьма незначительно (всего примерно до 2 раз).
Благодаря сжатию с потерями можно добиться многократного уменьшения объема данных, и при отображении распакованных данных человек практически не ощутит разницы между оригиналом.
На сколько сжимаются разные файлы
Текстовые
Действительно, например, текстовые файлы могут сжиматься весьма плотно. Так, например, книга Аркадия и Бориса Стругацких «Трудно быть богом» размером 354 329 байт архиватором WinRAR сжимается до 140 146 байт, т.е. в 2,5 раза.
Программы
Файлы программ тоже могут подвергаться сжатию. При этом сжатию как для более плотного хранения на диске, так и сжатию, при котором программа остается программой, но при запуске разжимает сама себя.
Для этого существуют упаковщики программ на подобие UPX и др. Например, мой текстовый редактор Superpad.exe размером 524 288 байт упаковщиком UPX сжимается до 179 200 байт (в 2,9 раза) и при этом может по-прежнему запускаться самостоятельно как программа.
Изображения
Описанию методов сжатия этих данных можно посвятить целую статью, а то и не одну. Дело в том, что само по себе изображение сжимается очень плохо, если его сжимать байт за байтом. И, тем не менее, это удается. Особенно, если в картинке много однотонного фона.
Одним из первых алгоритмов сжатия изображений был алгоритм RLE, который я описал выше. Он применяется в формате хранения изображений PCX. RLE является алгоритмом сжатия без потерь. Но в некоторых случаях он мог приводить не к уменьшению объема данных, а к его увеличению.
Поэтому для сжатия изображений был предложен и используется до сих пор алгоритм побитового сжатия LZW. Сам по себе алгоритм уже гораздо эффективнее RLE и тоже не предусматривает потери. Но поскольку применяется для изображений с палитрой цветов, то за счет адаптации и оптимизации (уплотнения) палитры можно добиться существенного повышения эффективности сжатия.
Рис. 1. Красивый лягушонок в формате BMP
Для сравнения, возьмем красивого лягушонка (рис. 1) разрешение 799x599 пикселей (точек) и сохраним в разные форматы хранения изображений. Получим файлы:
frog.bmp - размер 1 437 654 байта и тут, по сути, никакого сжатия и никаких потерь качества, поскольку картинка занимает положенные ей байты в формате Ширина x Высота x 3 байта на пиксель + заголовок формата файла BMP согласно качеству True colors (24 бит/пиксель). Т.е. каждая точка представлена тремя компонентами RGB (Red-красный, Green-зеленый и Blue-синий), каждая из которых занимает один байт.
frog24.png - 617 059 байт, сжатие в 2,33 раза и без потерь - основное свойство формата PNG-24. Данные BMP и PNG практически идентичны.
Рис. 2. Файл frog_256colors.gif
frog_256colors.gif - 261 956 байт (рис. 2), сжатие в 5,48 раза с потерями, базовая палитра 256 цветов (8 бит/пиксель). Уловить разницу между этим файлом и оригиналом в BMP довольно сложно, как в той игре «Найди десять отличий».
Рис. 3. Файл frog_64colors.gif
frog_64colors.gif - 187 473 байта (рис. 3), сжатие в 7,67 раза с потерями, базовая палитра уплотнена до 64 цветов (6 бит/пиксель). А вот тут цвета уже блеклые, но вполне сходное с оригиналом изображение. Особенно это заметно, если посмотреть на глаз лягушонка.
JPEG
Особое место занимает в сжатии и хранении изображений формат JPEG. Поэтому ему хочу уделить особое внимание. Алгоритм JPEG в наибольшей степени пригоден для сжатия фотографий и картин, содержащих реалистичные сцены с плавными переходами яркости и цвета. Наибольшее распространение JPEG получил в цифровой фотографии и для хранения и передачи изображений с использованием сети Интернет.
С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселями приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF, GIF, PNG или RAW.
JPEG (как и другие методы искажающего сжатия) не подходит для сжатия изображений при многоступенчатой обработке, так как искажения в изображения будут вноситься каждый раз при сохранении промежуточных результатов обработки.
JPEG не должен использоваться и в тех случаях, когда недопустимы даже минимальные потери, например, при сжатии астрономических или медицинских изображений. В таких случаях может быть рекомендован предусмотренный стандартом JPEG режим сжатия Lossless JPEG (который, к сожалению, не поддерживается большинством популярных кодеков) или стандарт сжатия JPEG-LS.
Описание алгоритма сжатия JPEG довольно не простое, поэтому кто захочет, может ознакомиться с ним по ссылке http://el-izdanie.narod.ru/gl4/4-3.htm. Ну и для сравнения сожмем нашу исходную картинку с разным уровнем качества:
frog100%.jpg - 216 168 байт, сжатие в 6,65 раза, потери якобы 0%, т.е. 100%-е качество картинки, но даже на это рассчитывать я бы не стал. Поверьте, отличия есть, правда, на глаз абсолютно неотличимые.
frog60%.jpg - 85 910 байт, сжатие в 16,7 раза, т.е. качество картинки 60%, но картинка снова кажется одинаковой, хотя, если присмотреться к участкам с однородным фоном или мелким деталям, то заметны артефакты в виде смазанности или квадратных одноцветных сегментов.
frog20%.jpg - 36 426 байт, сжатие в 39,5 раз, качество картинки 20% от исходного изображения, но по-прежнему картинка еще способна обмануть неискушенный глаз, но на однородном фоне отчетливо видны одноцветные угловатые сегменты, а мелкие детали окончательно потеряли свои четкие очертания.
MPEG
Это один из самых первых и самых распространенных форматов хранения видео. Несколько раз модернизировался. Но в упрощенном виде, можно сказать, что алгоритм очень напоминает сжатие как в JPEG, но с учетом того, что первый кадр видео всегда является исходным и оригинальным, а последующие кадры хранят лишь разницу между предыдущим и следующим кадрами. Благодаря этому каждый последующий кадр является предсказуемым с точки зрения распаковки (рис. 4 и 5).
Рис. 4. Исходные кадры видео
Рис. 5. Межкадровая разница без применения алгоритмов компенсации движения
Одна из наиболее мощных технологий, позволяющая повысить степень сжатия - это компенсация движения. При любой современной системе сжатия видео последующие кадры в потоке используют схожесть областей в предыдущих кадрах для увеличения степени сжатия.
Однако, из-за движения каких-либо объектов в кадре (или самой камеры) использование подобия соседних кадров было неполным. Технология компенсации движения позволяет находить похожие участки, даже если они сдвинуты относительно предыдущего кадра.
Компенсация движения (англ. Motion Compensation) - один из основных алгоритмов, применяемых при обработке и сжатии видеоданных. Алгоритм использует сходство соседних кадров в видео последовательности и находит векторы движения отдельных частей изображения (обычно блоков 16x16 и 8x8).
Использование компенсации позволяет при сжатии многократно увеличить степень сжатия за счет удаления избыточности в виде совпадающих частей кадров. Используется не только при сжатии, но и при фильтрации видео, изменении частоты кадров и т.д.
Практически в любом видео соседние кадры похожи, имеют общие объекты, которые, как правило, смещаются друг относительно друга. И совершенно естественно желание закодировать видео так, чтобы объекты не кодировались многократно, а просто описывались некоторые их смещения.
При этом, изображение разбивается на так называемые ключевые кадры - это группы кадров, идущих подряд несколько секунд. Управляя длительностью таких ключевых кадров можно эффективно управлять сжатием.
Например, если сюжет фильма не динамичный, то длительность ключевых кадров может быть по несколько секунд. Если же фильм содержит динамичные сцены, то в такие моменты длительность ключевых кадров можно сделать короче и сжатие быстро изменяющегося изображения будет выполняться эффективнее.
Ключевые кадры к тому же упрощают и ускоряют перемотку в медиаплеерах, поскольку заголовок каждого ключевого кадра содержит ссылку (смещение в байтах относительно начала видеофайла) на начало следующего ключевого кадра.
Звук и музыка
Звук и музыка могут без потерь, либо с потерями храниться в формате WAV. Например, формат WAV (Windows PCM) не предусматривает сжатие и хранит звуковой сигнал в оригинале, если можно так выразиться.
Формат WAV (ACM Waveform), по сути, является контейнером и может хранить звук, сжатый по алгоритму MPEG layer 3, либо хранить музыку в формате MP3, хотя много и других форматов OGG, FLAC и д.р.
Рассказать об алгоритмах сжатия звука уже не успеваю, к тому же ранее в нашем журнале была замечательная статья на эту тему.
Загрузка...
