Простым языком о том, как работает сжатие файлов


Оглавление (нажмите, чтобы открыть):

Методы сжатия информации

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

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

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

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

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

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

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

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

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

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

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась — это был конец пары: «Что-то тут концом пахнет». 8370 — | 8000 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Алгоритмы сжатия: описание, основные приемы, характеристики

Сжатие является частным случаем кодирования, основной характеристикой которого является то, что результирующий код меньше исходного. Процесс основан на поиске повторений в информационных рядах и последующем сохранении только одного рядом с количеством повторений. Таким образом, например, если последовательность появляется в файле, как «AAAAAA», занимая 6 байтов, он будет сохранен, как «6A», который занимает только 2 байта, в алгоритме сжатия RLE.

История возникновения процесса

Азбука Морзе, изобретенная в 1838 году — первый известный случай сжатия данных. Позже, когда в 1949 году мейнфрейм-компьютеры начали завоевывать популярность, Клод Шеннон и Роберт Фано изобрели кодирование, названного в честь авторов — Шеннона-Фано. Это шифрование присваивает коды символам в массиве данных по теории вероятности.

Только в 1970-х с появлением интернета и онлайн-хранилищ, были реализованы полноценные алгоритмы сжатия. Коды Хаффмана динамически генерировались на базе входной информации. Ключевое различие между кодированием Шеннона-Фано и кодированием Хаффмана состоит в том, что в первом дерево вероятности строилось снизу вверх, создавая неоптимальный результат, а во втором — сверху вниз.

В 1977 году, Авраам Лемпель и Джейкоб Зив издали свой инновационный метод LZ77, использующий более модернизированный словарь. В 1978 году, та же команда авторов, издала усовершенствованный алгоритм сжатия LZ78. Который использует новый словарь, анализирующий входные данные и генерирующий статический словарь, а не динамический, как у 77 версии.

Формы исполнения компрессии

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

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

Для передачи процесс выполняют в блоке передачи, включая данные заголовка. Когда информация отправляется или принимается через интернет, заархивированные по отдельности или вместе с другими большими файлами, могут передаваться в ZIP, GZIP или другом «уменьшенном» формате.

Преимущество алгоритмов сжатия:

  1. Значительно уменьшает объем памяти. При степени сжатия 2:1 файл в 20 мегабайт (МБ) займет 10 МБ пространства. В результате администраторы сети тратят меньше денег и времени на хранение баз данных.
  2. Оптимизирует производительность резервного копирования.
  3. Важный метод сокращения данных.
  4. Практически любой файл может быть сжат, но важно выбрать нужную технологию под конкретный тип файла. Иначе файлы могут быть «уменьшены», но при этом общий размер не изменится.

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

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

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

Этот процесс, который можно использовать для «уменьшения» или шифрования.

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

Порядок создания алгоритмы сжатия данных:

  1. Просчитывают, сколько раз каждый символ повторяется в файле для «уменьшения».
  2. Создают связанный список с информацией о символах и частотах.
  3. Выполняют сортировку списка от наименьшего к наибольшему в зависимости от частоты.
  4. Преобразуют каждый элемент в списке в дерево.
  5. Объединяют деревья в одно, при этом первые два образуют новое.
  6. Добавляют частоты каждой ветви в новый элемент дерева.
  7. Вставляют новое в нужное место в списке, в соответствии с суммой полученных частот.
  8. Назначают новый двоичный код каждого символа. Если берется нулевая ветвь, к коду добавляется ноль, а если первая ветвь, добавляется единица.
  9. Файл перекодируется в соответствии с новыми кодами.
  10. Например характеристики алгоритмов сжатия для короткого текста:»ata la jaca a la estaca»
  11. Подсчитывают, сколько раз появляется каждый символ и составляют связанный список:» (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
  12. Заказывают по частоте от низшей к высшей: e (1), j (1), s (1), c (2), l (2), t (2), » (5), a (9)


Как видно, корневой узел дерева создан, далее назначаются коды.

И осталось только упаковать биты в группы по восемь, то есть в байты:

Всего восемь байтов, а исходный текст был 23.

Демонстрация библиотеки LZ77

Алгоритм LZ77 рассмотрим на примере текста«howtogeek». Если повторить его три раза, то он изменит его следующим образом.

Затем, когда он захочет прочитать текст обратно, он заменит каждый экземпляр (h) на «howtogeek», возвращаясь к исходной фразе. Это демонстрирует алгоритм сжатия данных без потерь, поскольку данные, которые вводятся, совпадают с получаемыми.

Это идеальный пример, когда большая часть текста сжимается с помощью нескольких символов. Например, слово «это» будет сжато, даже если оно встречается в таких словах, как «этом», «их» и «этого». С повторяющимися словами можно получить огромные коэффициенты сжатия. Например, текст со словом «howtogeek», повторенным 100 раз имеет размер три килобайта, при компрессии займет всего 158 байт, то есть с 95% «уменьшением».

Это, конечно, довольно экстремальный пример, но наглядно демонстрирует свойства алгоритмов сжатия. В общей практике он составляет 30-40% с текстовым форматом ZIP. Алгоритм LZ77, применяется ко всем двоичным данным, а не только к тексту, хотя последний легче сжать из-за повторяющихся слов.

Дискретное косинусное преобразование изображений

Сжатие видео и аудио работает совсем по-другому. В отличие от текста, где выполняют алгоритмы сжатия без потерь, и данные не будут потеряны, с изображениями выполняют «уменьшение» с потерями, и чем больше %, тем больше потерь. Это приводит к тем ужасно выглядящим JPEG-файлам, которые люди загружали, обменивали и делали скриншоты по несколько раз.

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

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

Видео работает немного иначе, чем изображения. Обычно алгоритмы сжатия графической информации используют тем, что называется «межкадровым сжатием», которое вычисляет изменения между каждым кадром и сохраняет их. Так, например, если есть относительно неподвижный снимок, который занимает несколько секунд в видео, он будет «уменьшен» в один. Межкадровое сжатие обеспечивает цифровое телевидение и веб-видео. Без него видео весило бы сотнями гигабайт, что больше среднего размера жесткого диска в 2005 году.

Сжатие аудио работает очень похоже на сжатие текста и изображений. Если JPEG удаляет детали из изображения, которое не видны человеческим глазом, сжатие звука делает, то же самое для звуков. MP3 использует битрейт, в диапазоне от нижнего уровня 48 и 96 кбит/с (нижний предел) до 128 и 240 кбит/с (довольно хороший) до 320 кбит/с (высококачественный звук), и услышать разницу можно только с исключительно хорошими наушниками. Существуют кодеки сжатия без потерь для звука, основным из которых является FLAC и использует кодирование LZ77 для передачи звука без потерь.

Форматы «уменьшения» текста

Диапазон библиотек для текста в основном состоит из алгоритма сжатия данных без потерь, за исключением крайних случаев для данных с плавающей запятой. Большинство компрессорных кодеков включают «уменьшение» LZ77, Хаффмана и Арифметическое кодирование. Они применяемых после других инструментов, чтобы выжать еще несколько процентных точек сжатия.

Прогоны значений кодируются, как символ, за которым следует длина прогона. Можно правильно восстановить оригинальный поток. Если длина серии 15 января, 2020

Как сжать файл

Содержание статьи

  • Как сжать файл
  • Как уменьшить документ в word
  • Как сжать sql базу

Какими программами архивации воспользоваться

Наиболее популярными программами для сжатия файлов считаются WinRAR, 7-Zip, WinZip. Они различаются своими характеристиками, , степенью и скоростью сжатия файлов, количеством поддерживаемых форматов. Наибольшую степень сжатия предоставляет архиватор 7-Zip, а по количеству поддерживаемых форматов для архивации более распространен WinRAR. Эта программа имеет понятный интерфейс и большое количество полезных опций.

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

Как сжать файл

Коэффициент сжатия файлов можно установить в настройках архиватора. Минимальный размер сжатия равен 1,3-1,4, он доступен для стандартного архиватора Windows. Для сжатия файла с коэффициентом 4-5 потребуется воспользоваться одним из многочисленных сторонних архиваторов. Не стоит забывать о том, что при сильном сжатии файлов увеличится время обработки файлов, а для их последующего восстановления нужно добавить в настройки функцию самораспаковывания, можно добавить пароль и т.п. Эти опции доступны не для всех стандартных архиваторов, а лишь для программ, распространяющихся платно.

Больше всего экономии достигается при архивации текстовых файлов, а фото и картинки в форматах TIF,BMP, JPG или JPEG большой экономии места не дадут. Если нужно поместить в архив очень большой видеофайл, можно разбить его на отдельные части – тома, которые будут соответствовать заданным размерам. Если есть возможность сравнить степень сжатия файлов в разных архивных программах, нужно сделать это, тогда будет ясно, какой программой лучше воспользоваться.

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

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

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

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

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

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


Архивы можно использовать, например, для передачи данных по электронной почте, что очень удобно, так как к электронному письму во вложении можно прикрепить набор фотографий, документов и других объектов, используя всего один файл. Архивы также используются и для хранения информации, ну и конечно для сжатия данных, хотя для цифровых фотографий или видеофайлов процент сжатия не так велик, а вот, к примеру, для документов Microsoft Word или файлов Adobe Photoshop компрессия куда более существенна (несколько десятков МБ могут быть сжаты всего до нескольких мегабайт). Если тех или иных файлов достаточно много, то для экономии места на жёстком диске вполне было бы уместно добавить их в архив, если, конечно, они вам не понадобятся в самое ближайшее время, да и в любом случае, при необходимости, у вас не составит особого труда извлечь файлы из архива, используя для этого одну из популярных программ-архиваторов, например, WinRAR или WinZip. Обратите внимание, что, например, ВинРар является условно-бесплатным программным продуктом, т.е. бесплатно скачать и использовать WinRAR вы можете всего 40 дней с момента установки на компьютер, после истечения этого срока архиватор необходимо удалить или купить лицензию.

Как альтернативный вариант, вы можете использовать один из бесплатных архиваторов для Windows (32 и 64-бит), такой как 7-Zip.

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

Сжатие информации с потерями и без потерь

Еще вчера казалось, что диск размером в один гигабайт — это так много, что даже неясно, чем его заполнить, и уж конечно, каждый про себя думал: был бы у меня гигабайт памяти, я бы перестал «жадничать» и сжимать свою информацию какими-то архиваторами. Но, видимо, мир так устроен, что «свято место пусто не бывает», и как только у нас появляется лишний гигабайт — тут же находится чем его заполнить. Да и сами программы, как известно, становятся все более объемными. Так что, видимо, с терабайтами и экзабайтами будет то же самое.

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

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

Совсем немного теории для непрофессионалов

Позволю себе начать эту весьма серьезную тему со старой шутки. Беседуют два пенсионера:

— Вы не могли бы сказать мне номер вашего телефона? — говорит один.

— Вы знаете, — признается второй, — я, к сожалению, точно его не помню.

— Какая жалость, — сокрушается первый, — ну скажите хотя бы приблизительно…

Действительно, ответ поражает своей нелепостью. Совершенно очевидно, что в семизначном наборе цифр достаточно ошибиться в одном символе, чтобы остальная информация стала абсолютно бесполезной. Однако представим себе, что тот же самый телефон написан словами русского языка и, скажем, при передаче этого текста часть букв потеряна — что произойдет в подобном случае? Для наглядности рассмотрим себе конкретный пример: телефонный номер 233 34 44.

Соответственно запись «Двсти трцать три трицть четре сорк чтре», в которой имеется не один, а несколько пропущенных символов, по-прежнему легко читается. Это связано с тем, что наш язык имеет определенную избыточность, которая, с одной стороны, увеличивает длину записи, а с другой — повышает надежность ее передачи. Объясняется это тем, что вероятность появления каждого последующего символа в цифровой записи телефона одинакова, в то время как в тексте, записанном словами русского языка, это не так. Очевидно, например, что твердый знак в русском языке появляется значительно реже, чем, например, буква «а». Более того, некоторые сочетания букв более вероятны, чем другие, а такие, как два твердых знака подряд, невозможны в принципе, и так далее. Зная, какова вероятность появления какой-либо буквы в тексте, и сравнив ее с максимальной, можно установить, насколько экономичен данный способ кодирования (в нашем случае — русский язык).

Мастер Йода рекомендует:  Скандал с украденными паролями от аккаунтов «Яндекса»

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

Избыточность естественных языков

Теория информации гласит, что информации в сообщении тем больше, чем больше его энтропия. Для любой системы кодирования можно оценить ее максимальную информационную емкость (Hmax) и действительную энтропию (Н). Тогда случай Н

R = (Hmax — H)/ Hmax

Измерение избыточности естественных языков (тех, на которых мы говорим) дает потрясающие результаты: оказывается, избыточность этих языков составляет около 80%, а это свидетельствует о том, что практически 80% передаваемой с помощью языка информации является избыточной, то есть лишней. Любопытен и тот факт, что показатели избыточности разных языков очень близки. Данная цифра примерно определяет теоретические пределы сжатия текстовых файлов.

Кодирование информации

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

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

Сжатие с потерями

Говоря о кодах сжатия, различают понятия «сжатие без потерь» и «сжатие с потерями». Очевидно, что когда мы имеем дело с информацией типа «номер телефона», то сжатие такой записи за счет потери части символов не ведет ни к чему хорошему. Тем не менее можно представить целый ряд ситуаций, когда потеря части информации не приводит к потери полезности оставшейся. Сжатие с потерями применяется в основном для графики (JPEG), звука (MP3), видео (MPEG), то есть там, где в силу огромных размеров файлов степень сжатия очень важна, и можно пожертвовать деталями, не существенными для восприятия этой информации человеком. Особые возможности для сжатия информации имеются при компрессии видео. В ряде случаев большая часть изображения передается из кадра в кадр без изменений, что позволяет строить алгоритмы сжатия на основе выборочного отслеживания только части «картинки». В частном случае изображение говорящего человека, не меняющего своего положения, может обновляться только в области лица или даже только рта — то есть в той части, где происходят наиболее быстрые изменения от кадра к кадру.

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

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

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

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

Сжатие без потерь

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

Наиболее известны два алгоритма сжатия без потерь: это кодирование Хаффмена (Huffman) и LZW-кодирование (по начальным буквам имен создателей Lempel, Ziv, Welch), которые представляют основные подходы при сжатии информации. Кодирование Хаффмена появилось в начале 50-х; принцип его заключается в уменьшении количества битов, используемых для представления часто встречающихся символов и соответственно в увеличении количества битов, используемых для редко встречающихся символов. Метод LZW кодирует строки символов, анализируя входной поток для построения расширенного алфавита, основанного на строках, которые он обрабатывает. Оба подхода обеспечивают уменьшение избыточной информации во входных данных.

Кодирование Хаффмена

Кодирование Хаффмена [1] — один из наиболее известных методов сжатия данных, который основан на предпосылке, что в избыточной информации некоторые символы используются чаще, чем другие. Как уже упоминалось выше, в русском языке некоторые буквы встречаются с большей вероятностью, чем другие, однако в ASCII-кодах мы используем для представления символов одинаковое количество битов. Логично предположить, что если мы будем использовать меньшее количество битов для часто встречающихся символов и большее для редко встречающихся, то мы сможем сократить избыточность сообщения. Кодирование Хаффмена как раз и основано на связи длины кода символа с вероятностью его появления в тексте.

Статическое кодирование

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

Динамическое кодирование


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

LZW-сжатие

Алгоритм LZW [2], предложенный сравнительно недавно (в 1984 году), запатентован и принадлежит фирме Sperry.

LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов. Работа компрессора сводится к построению таблицы, состоящей из строк и соответствующих им кодов. Алгоритм сжатия сводится к следующему: программа прочитывает очередной символ и добавляет его к строке. Если строка уже находится в таблице, чтение продолжается, если нет, данная строка добавляется к таблице строк. Чем больше будет повторяющихся строк, тем сильнее будут сжаты данные. Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк — 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.

Какой же выбрать архиватор?

Наверное, читателю будет интересно узнать, какой же архиватор лучше. Ответ на этот вопрос далеко не однозначен.

Если посмотреть на таблицу, в которой «соревнуются» архиваторы (а сделать это можно как на соответствующем сайте в Интернете [3], так и на нашем CD-ROM), то можно увидеть, что количество программ, принимающих участие в «соревнованиях», превышает сотню. Как же выбрать из этого многообразия необходимый архиватор?

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

Если вас не волнуют меркантильные соображения, то прежде всего необходимо уяснить, что имеется целый ряд архиваторов, которые оптимизированы на решение конкретных задач. В связи с этим существуют различные виды специализированных тестов, например на сжатие только текстовых файлов или только графических. Так, в частности, Wave Zip в первую очередь умеет сжимать WAV-файлы, а мультимедийный архиватор ERI лучше всех упаковывает TIFF-файлы. Поэтому если вас интересует сжатие какого-то определенного типа файлов, то можно подыскать программу, которая изначально предназначена специально для этого.

Существует тип архиваторов (так называемые Exepackers), которые служат для сжатия исполняемых модулей COM, EXE или DLL. Файл упаковывается таким образом, что при запуске он сам себя распаковывает в памяти «на лету» и далее работает в обычном режиме.

Одними из лучших в данной категории можно назвать программы ASPACK и Petite. Более подробную информацию о программах данного класса, а также соответствующие рейтинги можно найти по адресу [4].

Если же вам нужен архиватор, так сказать, «на все случаи жизни», то оценить, насколько хороша конкретная программа, можно обратившись к тесту, в котором «соревнуются» программы, обрабатывающие различные типы файлов. Просмотреть список архиваторов, участвующих в данном тесте, можно на нашем CD-ROM.

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

Поддержка различных форматов

Большинство программ поддерживают один или два формата. Однако некоторые, такие, например, как программа WinAce, поддерживают множество форматов, осуществляя компрессию в форматах ACE, ZIP, LHA, MS-CAB, JAVA JAR и декомпрессию в форматах ACE, ZIP, LHA, MS-CAB, RAR, ARC, ARJ, GZip, TAR, ZOO, JAR.

Умение создавать solid-архивы

Создание solid-архивов — это архивирование, при котором увеличение сжатия возрастает при наличии большого числа одновременно обрабатываемых коротких файлов. Часть архиваторов, например ACB, всегда создают solid-архивы, другие, такие как RAR или 777, предоставляют возможность их создания, а некоторые, например ARJ, этого делать вообще не умеют.

Возможность создавать многотомные архивы

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

Возможность работы в качестве менеджера архивов

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

Возможность парольной защиты

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

Удобство в работе

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

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

Принципы сжатия информации

АРХИВАТОРЫ

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

Архивный файл – это специально созданный файл, содержащий в себе один или несколько файлов в сжатом виде.

достоинства недостатки
уменьшение занимаемого объема возможность потери данных при упаковке и распаковке
упрощение хранения и сортировки имеющихся данных требуется специальное программное обеспечение (в некоторых случаях –­ оборудование (MPEG, CD-I))
сокращение времени передачи данных по каналам связи загрузка ресурсов ПК на сжатие/распаковку данных, снижение быстродействия
позволяет защитить данные от несанкционированного доступа (при использовании пароля) невозможность непосредственно запускать сжатые программы на выполнение.

Kc – коэффициент сжатия, Vc– объем сжатого файла, Vo – исходный объем файла.

Степень сжатия зависит от:

1) используемой пограммы – архиватора,

2) метода сжатия,

3) типа исходного файла: текстового, графического, видео, звукового и т.д.

Программы, осуществляющие упаковку и распаковку файлов называются архиваторами. Наиболее распространенными являются: ARJ, ZIP, RAR. Расширение архивных файлов совпадает с названием использованного для их создания архиватора.


Архиваторы позволяют создавать самораспаковывающиеся архивные файлы, т.е. для их распаковки не требуется запуска программы-архиватора, т.к. они сами содержат программу распаковки. Эти архивы называются SFX-архивы
(SelF-eXtracting). Расширение таких файлов *.EXE.

Принципы сжатия информации

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

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

1-й символ 2-й символ 3-й символ

3. В следующим принципе используется закономерность что в тексте буквы встречаются с разной частотой. Например в этом тексте пробел самый распространенный символ, очень часто встречаются символы «а», «и». Эти часто встречающиеся символы можно представлять короткой комбинацией битов, остальные символы возможно кодировать более длинной последовательностью. Например:

Символ пробел « »
Символ «а»
Символ «и»
? ? ? ? ? ? Остальные символы кодовой таблицы

4. Физически ПК выделяет место для размещения файлов на диске по кластерам — блоками по 4 кБ. Меньше выделить невозможно. Например если файл имеет размер 8193 байта (8 кБ и 1 байт), физически он будет занимать 16 кБ или 16384 байта. Объединение группы файлов в один позволяет сэкономить на этих остатков. При упаковки маленьких файлов это дает большую экономию.

Файл. 3 кБ 1 кБ Файл 1 кБ 3 кБ Файл 2 кБ 2 кБ
2 кБ
Длина объединенного файла 6 кБ

Итого, при отдельном размещении файлов не используются 6 кБ, что составляет 100% от содержания файлов. Во втором случае неиспользуемыми остается 2 кБ, 33%.

Архиватор zip

Запаковка файлов pkzip [ключи] [пути файлов]

Ключи: -rp архивация с подкаталогами с сохранением структуры

-sPWD защита архива паролем (PWD)

-a добавить файлы в архив

-m переместить файлы в архив

-v просмотр содержимого архива

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

Действие Команда
Запаковать все файлы текущего каталога pkzip test *.*
Запаковать перечисленные файлы текущего каталога pkzip test *.doc
Запаковать все файлы из текущего каталога и из всех его подкаталогах pkzip -rp arhiv
Запаковать файлы с паролем. Для примера введен пароль 1234 pkzip -s1234 test

Распаковка файлов pkunzip [ключи] [имена файлов]

Ключи: -d распаковка с подкаталогами с сохранением структуры

-sPWD пароль архива (PWD)

Действие Команда
Распаковать содержимое архива в текущий каталог pkunzip test
Распаковать только указанные файлы pkunzip test *.txt
Распаковать архив с восстановлением структуры запакованных каталогов pkunzip -d arhiv
Распаковать архив запакованный с паролем. pkunzip -s1234 test

Архиватор arj

arj [ключи] [имена файлов]

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

Команды: a архивация

e распаковка без сохранения структуры каталогов

x распаковка с сохранением структуры

l просмотр содержимого архива

m переместить файлы в архив

d удалить файлы из архива

Ключи: -r упаковка с подкаталогами с сохранением структуры

-v[vol] разбивка архива на тома с объемом vol(если указан)

размер для стандартных дискет (360, 720, 1200, 1440) указывается в килобайтах, размер нестандартных дискет указывается в байтах

-v указывается при распаковке многотомного архива

Сжатие информации


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

Содержимое разработки

Лекция №4. Сжатие информации

Принципы сжатия информации

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

Пусть у нас имеется файл размером 1 (один) мегабайт. Нам необходимо получить из него файл меньшего размера. Ничего сложного — запускаем архиватор, к примеру, WinZip, и получаем в результате, допустим, файл размером 600 килобайт. Куда же делись остальные 424 килобайта?

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

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

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

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

Методы сжатия этого класса не могут допустить утрату информа­ции, поэтому они основаны только на устранении ее избыточности, а информация имеет избыточность почти всегда (правда, если до этого кто-то ее уже не уплотнил). Если бы избыточности не было, нечего было бы и сжимать.

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих спе­циальных символов. Для текста, который записан только про­писными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов. Это первое осно­вание для избыточности. Для нашего «телеграфного» текста вполне хватило бы шести битов на символ.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо извест­но, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» (• • — -) и «Ц» (- • — •), кодиру­ются четырьмя знаками. Неэффективная кодировка — второе основание для избыточности. Программы, выполняющие сжа­тие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их груп­пы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

Мастер Йода рекомендует:  Разработчик C# .NET

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

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

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

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

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

В то же время, существуют материалы, в которых стоит пожерт­вовать несколькими процентами информации, чтобы получить сжатие в десятки раз. К ним относятся фотографические иллюстрации, видеоматериалы и музыкальные композиции. Потеря информации при сжатии и последующей распаковке в таких материалах воспринимается как появление некоторого дополнительного «шума». Но поскольку при создании этих мате­риалов определенный «шум» все равно присутствует, его неболь­шое увеличение не всегда выглядит критичным, а выигрыш в раз­мерах файлов дает огромный (в 10-15 раз на музыке, в 20-30 раз на фото- и видеоматериалах).

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

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

Величиной допустимой потери при сжатии обычно можно управ­лять. Это позволяет экспериментовать и добиваться оптималь­ного соотношения размер/качество. На фотографических иллюст­рациях, предназначенных для воспроизведения на экране, потеря 5% информации обычно некритична, а в некоторых случаях можно допустить и 20-25%.

Алгоритмы сжатия без потери информации

Для дальнейших рассуждений будет удобно представить наш исходный файл с текстом как источник символов, которые по одному появляются на его выходе. Мы не знаем заранее, какой символ будет следующим, но мы знаем, что с вероятностью p1 появится буква «а», с вероятностью p2 -буква «б» и т.д.

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

Давайте представим себе текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Теперь представим себе, что вероятности появления этих символов распределены следующим образом:

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

0.5 (рис). В нашем примере это будут группы символов А-В и Г-Р. Кружочки на рисунке, обозначающие группы символов, называются вершинами или узлами (nodes), а сама конструкция из этих узлов — двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой — цифрой 1.

Снова разобьем первую группу (А-В) на две подгруппы таким образом, чтобы их суммарные вероятности были как можно ближе друг к другу. Добавим к коду первой подгруппы цифру 0, а к коду второй — цифру 1.

Будем повторять эту операцию до тех пор, пока на каждой вершине нашего «дерева» не останется по одному символу. Полное дерево для нашего алфавита будет иметь 31 узел.

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность p=0.2, кодируется всего двумя битами, а буква Р (на рисунке не показана), имеющая вероятность p=0.013, кодируется аж шестибитовой комбинацией.

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

где ni — количество бит, кодирующих i-й символ, pi — вероятность появления i-го символа.

Алгоритм Хаффмана изящно реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:

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

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


3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо — 1, налево — 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис.).

Построим кодовое дерево для сообщения со следующим алфавитом:

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

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

Еще один недостаток кодов — это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Данные коды никак не учитывают взаимосвязей между символами, которые присутствуют практически в любом тексте. Например, если в тексте на английском языке нам встречается буква q, то мы с уверенностью сможем сказать, что после нее будет идти буква u.

Групповое кодирование — Run Length Encoding (RLE) — один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары «счетчик, значение». («красный, красный, . красный» записывается как «N красных»).

Одна из реализаций алгоритма такова: ищут наименнее часто встречающийся байт, называют его префиксом и делают замены цепочек одинаковых символов на тройки «префикс, счетчик, значение». Если же этот байт встретичается в исходном файле один или два раза подряд, то его заменяют на пару «префикс, 1» или «префикс, 2». Остается одна неиспользованная пара «префикс, 0», которую можно использовать как признак конца упакованных данных.

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt. которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW-код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселов.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат — GIF — более примитивен — он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксел. В начале GIF — файла находится палитра — таблица, устанавливающая соответствие между индексом цвета — числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

Алгоритмы сжатия с потерей информации

Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия — например, в Internet.

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так: изображение разбивается на квадраты 8*8 пикселов, а затем каждый квадрат преобразуется в последовательную цепочку из 64 пикселов. Далее каждая такая цепочка подвергается так называемому DCT-преобразованию, являющемуся одной из разновидностей дискретного преобразования Фурье. Оно заключается в том, что входную последовательность пикселов можно представить в виде суммы синусоидальных и косинусоидальных составляющих с кратными частотами (так называемых гармоник). В этом случае нам необходимо знать лишь амплитуды этих составляющих для того, чтобы восстановить входную последовательность с достаточной степенью точности. Чем большее количество гармонических составляющих нам известно, тем меньше будет расхождение между оригиналом и сжатым изображением. Большинство JPEG-кодеров позволяют регулировать степень сжатия. Достигается это очень простым путем: чем выше степень сжатия установлена, тем меньшим количеством гармоник будет представлен каждый 64-пиксельный блок.

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

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

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

Фрактальное сжатие изображений — это алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых функций (IFS, как правило являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры — до 1000 раз при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Из-за сложной ситуации с патентованием широкого распространения алгоритм не получил.

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

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

Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. Они запатентовали свою идею в 1990 и 1991 гг. Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

Идея заключается в следующем: предположим, что исходное изображение является неподвижной точкой некоего сжимающего отображения. Тогда можно вместо самого изображения запомнить каким-либо образом это отображение, а для восстановления достаточно многократно применить это отображение к любому стартовому изображению.

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

Далее, поставив чёрную точку в любой точке картинки, мы будем применять наши преобразования в случайном порядке некоторое (достаточно большое) число раз (этот метод ещё называют фрактальный пинг-понг).

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

Наиболее известны два изображения, полученных с помощью IFS: треугольник Серпинского и папоротник Барнсли. Первое задается тремя, а второе — пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.

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

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

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

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG. Сравним его с фрактальной компрессией.

Во-первых, заметим, что и тот, и другой алгоритм оперируют 8-битными (в градациях серого) и 24-битными полноцветными изображениями. Оба являются алгоритмами сжатия с потерями и обеспечивают близкие коэффициенты архивации. И у фрактального алгоритма, и у JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Кроме того, оба алгоритма очень хорошо распараллеливаются.

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG. Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.


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

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

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

Сжатие данных

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

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

Файлы разных форматов могут быть сжаты в различной степени. Например, текстовые файлы сжимаются очень хорошо. Набор файлов объемом, скажем, 100 Кбайт, часто может быть сжат где-то до 15-20 Кбайт. Хуже сжимаются изображения, почти не уменьшаются при сжатии музыкальные файлы.

Наиболее популярные форматы сжатия файлов:

Чтобы сжимать и разжимать файлы с использованием этих форматов, существуют различные программы.

Наиболее популярна сегодня программа WinRAR (рис. 21.2).

Рис. 21.2. Окно программы WinRAR.

Внутри этой программы можно перемещаться по файлам и папкам, как в обычном файловом менеджере. Для создания архива или добавления в него выделенных файлов следует нажать сочетание Alt+A или же выбрать из меню Команды пункт Добавить файлы в архив. Откроется окно (рис. 21.3), в котором можно указать название архива, выбрать формат архива, метод сжатия, а также настроить другие параметры.

Мастер Йода рекомендует:  Что такое CMS (1 часть)

Рис. 21.3. Добавление файлов в архив в программе.

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

Похожие главы из других книг

Сжатие файлов NTFS

Сжатие файлов NTFS При использовании разделов с файловой системой NTFS вы можете задействовать ее возможности для сжатия файлов. При этом происходит более слабое сжатие, чем при использовании архивов ZIP или RAR, но выполняется оно гораздо быстрее. Файлы, сжатые с помощью NTFS,

Сжатие звука

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

Экспорт данных из базы данных Access 2007 в список SharePoint

Экспорт данных из базы данных Access 2007 в список SharePoint Access 2007 позволяет экспортировать таблицу или другой объект базы данных в различных форматах, таких как внешний файл, база данных dBase или Paradox, файл Lotus 1–2–3, рабочая книга Excel 2007, файл Word 2007 RTF, текстовый файл, документ XML

Форматы графических файлов. Сжатие изображения

Форматы графических файлов. Сжатие изображения Работая с изображениями в Photoshop, можно хранить файл в одном из нескольких графических форматов. Наиболее популярными из них являются JPEG, TIFF и PSD.JPEG – это формат, позволяющий создать минимальный по размерам файл с наименьшей

Сжатие данных

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

4.7.1 Сжатие в PPP

4.7.1 Сжатие в PPP Может показаться не очень разумным включение одних и тех же октетов адреса и управления в каждый кадр. Партнеры на каждом конце связи PPP могут работать в режиме сжатия (compression) для исключения этих полей.Значения в поле протокола указывают, является ли

2.27. Сжатие строк

11. Меньше copy — меньше и вздору, или Избыточность текста и сжатие файла

11. Меньше copy — меньше и вздору, или Избыточность текста и сжатие файла Все знают, что большинству людей свойственно излишнее многословие. Гораздо менее широко известно, что даже самые лаконичные высказывания можно было бы значительно сократить. Вообще, естественные

Сжатие видео во Flash. Кодеки On2 VP6 и Sorenson Spark

Сжатие видео во Flash. Кодеки On2 VP6 и Sorenson Spark В главе 1 мы уже говорили о видео. Давайте кратко повторим все, что уже успели узнать и, возможно, уже забыли.Итак, видеоинформация, хранящаяся в файле, практически всегда сжимается. Иначе и не получится: данные, содержащие

Глава 11. Сжатие данных.

Глава 11. Сжатие данных. Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных.

Сжатие данных

Сжатие данных Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных. Заботу об

Сжатие с минимальной избыточностью


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

Сжатие с использованием словаря

Сжатие с использованием словаря Вплоть до 1977 года, основные усилия в области исследования алгоритмов сжатия концентрировались вокруг алгоритмов кодирования с минимальной избыточностью, подобных алгоритмам Шеннона-Фано или Хаффмана, и были посвящены либо

Сжатие LZ77

Сжатие данных

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

3.2. Размеры и сжатие файлов

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

Сжатие Windows: файлы, папки и диски. Ошибки сжатия.

Во времена моей юности сжатие являлось чуть ли не самой обращаемой к ней функцией – диски по 7 – 20 гБ никак не могли вместить в себя всю нужную информацию. И именно для этого сжатие и существует: освободить место на жёстком диске. Когда вы сжимаете файл или папку, данные, используя специальный алгоритм Windows, перезаписываются и после операции занимают меньшее количество кластеров. При обращении к файлу в следующем сеансе система производит обратный процесс, перед тем как вы сможете увидеть хоть бит нужной информации. А на это, как понимаете, нужно время и ресурсы системы.

Функция сжатия файлов с момента появления Windows находилась в составе утилиты очистки дисков. Но со времён Windows 7 перекочевала в отдельную струю: разработчики посчитали, что проблем с нехваткой пространства компьютера стало меньше, да и сжатие огромного количества файлов сильно замедляет функционал Windows: при активации этой функции система сжимала все файлы подряд, а это значит там могли оказаться и жизненно важные параметры, к которым обращение во время текущего сеанса сиюминутно… Сейчас освободить пространство легко с помощью других утилит, которые работают в другом направлении, отыскивая мусорные файлы и/или проводя дефрагментацию. В конце концов, любая программа-архиватор умеет гораздо больше, чем описываемая функция. Однако она есть, знакомимся с ней.

Кстати

Функция и подход к сжатию в Windows 10 серьёзно изменился и, кажется (пока, по крайней мере) в куда более лучшую сторону. Но об этом отдельной статьёй.

Пару абзацев теории…

Файловая система NTFS использует параметр “единица сжатия” с целью определить степень разбиения, гранулярности потока байтового диапазона, а также их выравнивание или группирование по блокам. Размер этой самой единицы зависит только от размера кластера в системе NTFS. До последнего момента для расчёта размера кластера используется такая таблица:

Как видите, начиная с определённого момента начинаются исключения: “родное” NTFS-сжатие перестаёт работать на томах и разделах, размер кластера которых выбран более чем 4 КБ. Для размеров от 8 КБ начинает использоваться сжатие для разреженных файлов. Такие файлы – очередной конёк файловой системы NTFS, который позволяет создавать приложениям файлы очень больших размеров, которые, как это ни странно звучит, могут превышать размер родительской директории. Это происходит потому, что львиная доля содержимого таких файлов (а порой и полностью) заполняется нолями или нолевыми цепочками. При этом файловая система логические кластеры таким цепочкам не предоставляет. А NTFS создаёт лишь “указатель места заполнения виртуального количества кластеров”. Причём здесь сжатие? NTFS, работая над сжатием файла или папки, разделяет поток данных по тому же принципу. При этом процесс сжатия для каждого файла индивидуален; степень сжатия и последующие с файлом операции очень зависят от его реального размера.

Сжатие файлов и папок

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

Активируем функцию, сжатие началось. После этого можно будет заставить Windows подсвечивать сжатые файлы. Это же легко проделать с целым диском. Найдём в Windows Explorer список томов и также вызовем контекстное меню правой мышкой:

Сжатие дисков и файлов. О чём нужно знать?

  • Сжатие доступно ТОЛЬКО для файловой системы NTFS
  • Если файл перемещается из обычной папки в сжатую папку ДРУГОГО ДИСКА, он также проходит процедуру сжатия
  • Если файл перемещается из обычной папки в сжатую папку ТОГО ЖЕ ДИСКА, сжатие аннулируется и файл/папка возвращаются к первоначальному своему размеру
  • Сжатые с помощью NTFS компрессии файлы зашифровать невозможно: дублирование процедур в любом виде в Windows исключено, и потому…
  • Сжать уже сжатый файл тоже не получится )))
  • Не путайте с архивацией (в zip, rar и т.п.)

Сжатие. Чего делать нельзя.

Как вы уже поняли, сжатие Windows – это не та функция, с которой стоит баловаться. Однако понимание функции сжатия (хотя бы в пределах абзацев вверху статьи) может помочь вам определить корень появившихся ошибок. Самые типичные из них, и в этом может быть вина именно функции сжатия:

  • Недостаточно места на диске. Эта ошибка может вас подстеречь именно в момент копирования файла/папки или на этапе создания резервной копии
  • Ошибка копирования файлов больших размеров в сжатую папку
  • Сжатые файлы виртуальных дисков VHD снижают производительность виртуальной машины

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

После сжатия система не загружается…

Если я с советами опоздал, и вы уже столкнулись с отказом запуска системы после сжатия, знайте, что сжатыми оказались те немногие, но архиважные для загрузки системы файлы. А во время запуска системы процедура “де-сжатия” не предусмотрена. Как итог: система не запускается или идёт постоянный перезапуск Windows. Возможно появление ошибок типа

“Какой-то там файл” is compressed

Press Ctrl+Alt+Del to restart


Самый простой способ, который не всегда, к сожалению, работает, это загрузочный диск с Windows. Если его под рукой нет, его вполне легально можно скачать из сети (начиная с версии 7 и позднее), имея рабочий компьютер и выход в сеть. Вот утилита, которая вам в этом поможет (а вот здесь я восстанавливаю Windows после повреждения с её помощью):

Я в таких случаях всегда пользуюсь универсальным вариантом – это внешний бокс с установленным внутри жёстким диском, на котором всегда наготове целая куча образов загрузочных дисков Windows любой модели и разрядности: от Windows XP до Win10 32-х и 64-х. И не парюсь по поводу бесчисленных дисков и флешек.

выберите язык и в окне установки выберите пункт Восстановление системы:

Утилита найдёт вашу систему, продолжите кнопкой Загрузить драйверы:

Появится окно с выбором места хранения драйверов и по нажатии кнопки ОК появится Проводник Windows – он-то нам и нужен:

Выберите Компьютер в любом расположении ярлыка окна и появится знакомый вам список видимых системой томов. Нам остаётся снять галочку у атрибута Сжимать этот диск для экономии места нужного диска (он системный) из контекстного меню, проводя декомпрессию:

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

Как работает сжатие файлов? — Нажмите — 2020

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

Итак, как это работает?

Чтобы ответить на этот вопрос, нужно объяснить очень сложную математику, конечно, больше, чем мы можем рассказать в этой статье, но вам не нужно точно понимать, как она работает математически, чтобы понять основы.

Самые популярные библиотеки для сжатия текста основаны на двух алгоритмах сжатия, которые используются одновременно для достижения очень высоких коэффициентов сжатия. Этими двумя алгоритмами являются «LZ77» и «кодирование Хаффмана». Кодирование Хаффмана довольно сложно, и мы не будем здесь подробно останавливаться на этом. Прежде всего, он использует некоторую причудливую математику для назначения более коротких двоичных кодов отдельным буквам, сокращая при этом размеры файлов. Если вы хотите узнать больше об этом, ознакомьтесь с этой статьей о том, как работает код, или с этим объяснением от Computerphile.

LZ77, с другой стороны, относительно прост и о чем мы будем говорить здесь. Он стремится удалить повторяющиеся слова и заменить их меньшим «ключом», который представляет слово.

Возьмите этот короткий фрагмент текста, например:

Алгоритм LZ77 будет смотреть на этот текст, понимать, что он повторяет «howtogeek» три раза, и изменять его следующим образом:

Затем, когда он захочет прочитать текст обратно, он заменит каждый экземпляр (h) на «howtogeek», возвращая нас к исходной фразе.

Мы называем сжатие как «без потерь» — данные, которые вы вводите, совпадают с данными, которые вы получаете. Ничего не потеряно.

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

Так что теперь, когда он доберется до (h), он оглянется назад на «howtogeek» и прочитает это вместо этого.

Если вам интересно более подробное объяснение, это видео из Computerphile очень полезно.

Теперь это идеализированный пример. В действительности большая часть текста сжимается с помощью клавиш размером всего в несколько символов. Например, слово «the» будет сжато, даже если оно встречается в таких словах, как «там», «их» и «тогда». С повторяющимся текстом вы можете получить некоторые сумасшедшие коэффициенты сжатия. Возьмите этот текстовый файл со словом «howtogeek», повторенным 100 раз. Исходный текстовый файл имеет размер три килобайта. Однако при сжатии он занимает всего 158 байт. Это почти 95% сжатия.

Очевидно, это довольно экстремальный пример, так как мы повторяли одно и то же слово снова и снова. В общем, вы, вероятно, получите сжатие на 30-40%, используя формат сжатия, такой как ZIP, для файла, который в основном является текстовым.

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

Как работает сжатие изображений и видео?

Сжатие видео и аудио работает совсем по-другому. В отличие от текста, где вы можете иметь сжатие без потерь и данные не будут потеряны, с изображениями у нас есть то, что называется «сжатие с потерями», где вы теряете некоторые данные. И чем больше вы сжимаете, тем больше данных теряете.

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

Вот пример. Это снимок экрана, который я сделал, который не был сжат вообще.

Затем я сделал этот снимок экрана и несколько раз прогонял его через Photoshop, каждый раз экспортируя его в формате JPEG низкого качества. Вот результат.

Выглядит довольно плохо, верно?

Что ж, это только наихудший сценарий, каждый раз экспорт с качеством JPEG 0%. Для сравнения, вот JPEG с 50% качеством, который почти неотличим от исходного изображения PNG, если вы не взорвете его и не посмотрите внимательно.

Размер PNG для этого изображения составлял 200 КБ, но этот JPEG-файл с качеством 50% составляет всего 28 КБ.

Так как же сэкономить так много места? Ну, алгоритм JPEG — это инженерный подвиг. Большинство изображений хранят список чисел, каждый из которых представляет один пиксель.

JPEG не делает ничего из этого. Вместо этого он сохраняет изображения, используя нечто, называемое дискретным косинусным преобразованием, которое представляет собой совокупность синусоидальных волн, складывающихся вместе с различной интенсивностью. Он использует 64 различных уравнения, но большинство из них не используются. Это то, что делает слайдер качества для JPEG в Photoshop и других графических приложениях — выбирайте, сколько уравнений использовать. Затем приложения используют кодировку Хаффмана, чтобы еще больше уменьшить размер файла.

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

Это изображение ужасно. Но незначительное сжатие JPEG может оказать значительное влияние на размер файла, и это делает JPEG очень полезным для сжатия изображений на веб-сайтах. Большинство изображений, которые вы видите в сети, сжимаются, чтобы сэкономить время загрузки, особенно для мобильных пользователей с плохой передачей данных. Фактически, все изображения в How-To Geek были сжаты, чтобы ускорить загрузку страниц, и вы, вероятно, никогда этого не заметили.

Сжатие видео

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

Мы используем то, что называется «межкадровое сжатие», которое вычисляет изменения между каждым кадром и сохраняет их. Так, например, если у вас есть относительно неподвижный снимок, который занимает несколько секунд в видео, много места будет сэкономлено, потому что алгоритм сжатия не должен хранить все вещи в сцене, которые не меняются. Межкадровое сжатие является основной причиной, по которой у нас вообще есть цифровое телевидение и веб-видео. Без него видео было бы сотнями гигабайт, что больше среднего размера жесткого диска в 2005 году, когда был запущен YouTube.

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

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

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

Это увеличенный кадр, взятый из видео медузы. Один слева имеет скорость 3 Мбит / с, а другой справа — 100 Мбит / с.

30-кратное увеличение размера файла, но незначительное увеличение качества. Как правило, объем видео на YouTube составляет 2-10 Мбит / с, в зависимости от вашего соединения, так как, вероятно, больше ничего не будет замечено.

Это демо лучше работает с реальным видео, поэтому, если вы хотите проверить его сами, вы можете загрузить те же видео тесты битрейта, что и здесь.

Сжатие звука

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

MP3 также использует битрейт, начиная от нижнего уровня 48 и 96 кбит / с (нижний предел) до 128 и 240 кбит / с (довольно неплохо) до 320 кбит / с (высококачественный звук), и вы, скорее всего, услышите разницу только с исключительно хорошими наушниками ( и уши).

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

Добавить комментарий