для чего сжимают файлы
Алгоритмы сжатия данных без потерь
Часть первая – историческая.
Введение
История
Иерархия алгоритмов: 
Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ), можно привести несколько более ранних примеров сжатия. Морзе, изобретая свой код в 1838 году, разумно назначил самым часто используемым буквам в английском языке, “e” и “t”, самые короткие последовательности (точка и тире соотв.). Вскоре после появления мейнфреймов в 1949 году был придуман алгоритм Шеннона — Фано, который назначал символам в блоке данных коды, основываясь на вероятности их появления в блоке. Вероятность появления символа в блоке была обратно пропорциональна длине кода, что позволяло сжать представление данных.
Дэвид Хаффман был студентом в классе у Роберта Фано и в качестве учебной работы выбрал поиск улучшенного метода бинарного кодирования данных. В результате ему удалось улучшить алгоритм Шеннона-Фано.
Ранние версии алгоритмов Шеннона-Фано и Хаффмана использовали заранее определённые коды. Позже для этого стали использовать коды, созданные динамически на основе данных, предназначаемых для сжатия. В 1977 году Лемпель и Зив опубликовали свой алгоритм LZ77, основанный на использования динамически создаваемого словаря (его ещё называют «скользящим окном»). В 78 году они опубликовали алгоритм LZ78, который сначала парсит данные и создаёт словарь, вместо того, чтобы создавать его динамически.
Проблемы с правами
Рост популярности Deflate
Большие корпорации использовали алгоритмы сжатия для хранения всё увеличивавшихся массивов данных, но истинное распространение алгоритмов произошло с рождением интернета в конце 80-х. Пропускная способность каналов была чрезвычайно узкой. Для сжатия данных, передаваемых по сети, были придуманы форматы ZIP, GIF и PNG.
Том Хендерсон придумал и выпустил первый коммерчески успешный архиватор ARC в 1985 году (компания System Enhancement Associates). ARC была популярной среди пользователей BBS, т.к. она одна из первых могла сжимать несколько файлов в архив, к тому же исходники её были открыты. ARC использовала модифицированный алгоритм LZW.
Фил Катц, вдохновлённый популярностью ARC, выпустил программу PKARC в формате shareware, в которой улучшил алгоритмы сжатия, переписав их на Ассемблере. Однако, был засужен Хендерсоном и был признан виновным. PKARC настолько открыто копировала ARC, что иногда даже повторялись опечатки в комментариях к исходному коду.
Но Фил Катц не растерялся, и в 1989 году сильно изменил архиватор и выпустил PKZIP. После того, как его атаковали уже в связи с патентом на алгоритм LZW, он изменил и базовый алгоритм на новый, под названием IMPLODE. Вновь формат был заменён в 1993 году с выходом PKZIP 2.0, и заменой стал DEFLATE. Среди новых возможностей была функция разбиения архива на тома. Эта версия до сих пор повсеместно используется, несмотря на почтенный возраст.
Формат изображений GIF (Graphics Interchange Format) был создан компанией CompuServe в 1987. Как известно, формат поддерживает сжатие изображения без потерь, и ограничен палитрой в 256 цветов. Несмотря на все потуги Unisys, ей не удалось остановить распространение этого формата. Он до сих пор популярен, особенно в связи с поддержкой анимации.
Слегка взволнованная патентными проблемами, компания CompuServe в 1994 году выпустила формат Portable Network Graphics (PNG). Как и ZIP, она использовала новый модный алгоритм DEFLATE. Хотя DEFLATE был запатентован Катцем, он не стал предъявлять никаких претензий.
Сейчас это самый популярный алгоритм сжатия. Кроме PNG и ZIP он используется в gzip, HTTP, SSL и других технологиях передачи данных.
К сожалению Фил Катц не дожил до триумфа DEFLATE, он умер от алкоголизма в 2000 году в возрасте 37 лет. Граждане – чрезмерное употребление алкоголя опасно для вашего здоровья! Вы можете не дожить до своего триумфа!
Современные архиваторы
ZIP царствовал безраздельно до середины 90-х, однако в 1993 году простой русский гений Евгений Рошал придумал свой формат и алгоритм RAR. Последние его версии основаны на алгоритмах PPM и LZSS. Сейчас ZIP, пожалуй, самый распространённый из форматов, RAR – до недавнего времени был стандартом для распространения различного малолегального контента через интернет (благодаря увеличению пропускной способности всё чаще файлы распространяются без архивации), а 7zip используется как формат с наилучшим сжатием при приемлемом времени работы. В мире UNIX используется связка tar + gzip (gzip — архиватор, а tar объединяет несколько файлов в один, т.к. gzip этого не умеет).
Прим. перев. Лично я, кроме перечисленных, сталкивался ещё с архиватором ARJ (Archived by Robert Jung), который был популярен в 90-х в эру BBS. Он поддерживал многотомные архивы, и так же, как после него RAR, использовался для распространения игр и прочего вареза. Ещё был архиватор HA от Harri Hirvola, который использовал сжатие HSC (не нашёл внятных объяснений — только «модель ограниченного контекста и арифметическое кодирование»), который хорошо справлялся со сжатием длинных текстовых файлов.
В 1996 году появился вариант алгоритма BWT с открытыми исходниками bzip2, и быстро приобрёл популярность. В 1999 году появилась программа 7-zip с форматом 7z. По сжатию она соперничает с RAR, её преимуществом является открытость, а также возможность выбора между алгоритмами bzip2, LZMA, LZMA2 и PPMd.
В 2002 году появился ещё один архиватор, PAQ. Автор Мэтт Махоуни использовал улучшенную версию алгоритма PPM с использованием техники под названием «контекстное смешивание». Она позволяет использовать больше одной статистической модели, чтобы улучшить предсказание по частоте появления символов.
Будущее алгоритмов сжатия
Конечно, бог его знает, но судя по всему, алгоритм PAQ набирает популярность благодаря очень хорошей степени сжатия (хотя и работает он очень медленно). Но благодаря увеличению быстродействия компьютеров скорость работы становится менее критичной.
С другой стороны, алгоритм Лемпеля-Зива –Маркова LZMA представляет собой компромисс между скоростью и степенью сжатия и может породить много интересных ответвлений.
Ещё одна интересная технология «substring enumeration» или CSE, которая пока мало используется в программах.
В следующей части мы рассмотрим техническую сторону упомянутых алгоритмов и принципы их работы.
Как работает сжатие файлов?
Сжатие файлов является основной частью работы Интернета. Это позволяет нам передавать файлы, которые в противном случае потребовали бы слишком большой пропускной способности и времени. Всякий раз, когда вы получаете доступ к файлам ZIP или просматриваете изображения в формате JPEG, вы получаете выгоду от сжатия файлов.
Таким образом, в какой-то момент вы, вероятно, задали вопрос: как работает сжатие файлов? Вот основной взгляд на то, как работает сжатие.
Что означает сжатие?
Проще говоря, сжатие файла (или сжатие данных) является актом уменьшения размера файла при сохранении исходных данных. Это позволяет файлу занимать меньше места на устройстве хранения данных, а также облегчает его передачу через Интернет или другим способом.
Важно отметить, что сжатие не бесконечно. Хотя сжатие файла в ZIP-файл уменьшает его размер, вы не можете продолжать сжимать файл, чтобы еще больше уменьшить его размер до нуля.
Обычно сжатие файлов делится на два основных типа: с потерями и без потерь. Давайте посмотрим, как они оба работают по очереди.
Как работает сжатие файлов: сжатие с потерями
Сжатие с потерями уменьшает размер файла, удаляя ненужные биты информации. Это чаще всего встречается в форматах изображений, видео и аудио, где нет необходимости в идеальном представлении исходного медиа. Многие распространенные форматы для этих типов носителей используют сжатие с потерями; MP3 и JPEG — два популярных примера.
MP3 не содержит всю аудиоинформацию из оригинальной записи — вместо этого он выбрасывает некоторые звуки, которые люди не слышат. В любом случае вы не заметите, что они пропали, поэтому удаление этой информации приведет к меньшему размеру файла, практически без недостатков.
Аналогично, файлы JPEG удаляют ненужные части изображений. Например, в изображении, содержащем голубое небо, сжатие JPEG может изменить все пиксели неба на один или два оттенка синего вместо использования десятков различных оттенков.
Однако чем сильнее вы сжимаете файл, тем заметнее становится снижение качества. Вы, вероятно, испытали это с грязными файлами MP3, загруженными на YouTube. Например, сравните этот высококачественный музыкальный трек:
С этой сильно сжатой версией той же песни:
Сжатие с потерями подходит, когда файл содержит больше информации, чем нужно для ваших целей. Например, предположим, у вас есть огромный файл изображения RAW. Хотя вы, вероятно, хотите сохранить это качество при печати изображения на большом баннере, бессмысленно загружать файл RAW в Facebook.
Картинка содержит так много данных, что не заметно при просмотре в социальных сетях. Сжатие изображения в высококачественный JPEG выбрасывает некоторую информацию, но изображение выглядит почти невооруженным глазом. Смотрите наше сравнение популярных графических форматов для более глубокого взгляда на это.
Сжатие с потерями в общем использовании
Как мы уже упоминали, сжатие с потерями отлично подходит для большинства видов носителей. В связи с этим жизненно важно, чтобы такие компании, как Spotify и Netflix, постоянно передавали огромные объемы информации. Максимальное уменьшение размера файла при сохранении качества делает их работу более эффективной. Можете ли вы представить, было ли каждое видео YouTube храниться и передаваться в оригинальном несжатом формате?
Но сжатие с потерями не работает так хорошо для файлов, где вся информация имеет решающее значение. Например, использование сжатия с потерями в текстовом файле или электронной таблице приведет к искаженному выводу. Вы действительно не можете ничего выбросить без серьезного вреда для конечного продукта.
При сохранении в формате с потерями, вы часто можете установить уровень качества. Например, многие графические редакторы имеют ползунок для выбора качества JPEG от 0 до 100.
Экономия на уровне 90 или 80 процентов приводит к небольшому уменьшению размера файла, с небольшой разницей в глазах. Но сохранение в плохом качестве или повторное сохранение одного и того же файла в формате с потерями ухудшит его.
Ниже вы можете увидеть пример этого (нажмите, чтобы увидеть увеличенные изображения). Слева оригинальное изображение, загруженное с Pixabay в формате JPEG. Среднее изображение является результатом сохранения его в формате JPEG с 50-процентным качеством. И самое правое изображение показывает исходное изображение, сохраненное вместо этого в формате JPEG с 10-процентным качеством.
На первый взгляд среднее изображение выглядит не так уж плохо. Вы можете заметить артефакты по краям коробок только при увеличении. Конечно, самое правое изображение сразу выглядит ужасно.
Перед кадрированием для загрузки размеры файлов составляли 874 КБ, 310 КБ и 100 КБ соответственно.
Как работает сжатие файлов: сжатие без потерь
Сжатие без потерь — это способ уменьшить размер файла, чтобы вы могли идеально восстановить исходный файл. В отличие от сжатия с потерями, он не выбрасывает никакой информации. Вместо этого сжатие без потерь по существу работает за счет устранения избыточности.
Давайте рассмотрим простой пример, чтобы показать, что это значит. Ниже стопка из 10 кирпичей: два синих, пять желтых и три красных. Этот стек — простой способ проиллюстрировать эти блоки, но есть и другой способ сделать это.
Вместо того, чтобы показывать все 10 блоков, мы можем удалить все цвета, кроме одного. Затем, если мы используем цифры, чтобы показать, сколько кирпичей каждого цвета было, мы представили точно такой же бит информации, используя гораздо меньше кирпичей. Вместо 10 кирпичей нам теперь нужно только три.
Это простая иллюстрация того, как возможно сжатие без потерь. Он хранит ту же информацию более эффективным способом, удаляя избыточность. Рассмотрим реальный файл, где строка ниже:
Можно «сжать» до следующей, гораздо более короткой формы:
Это позволяет нам использовать семь символов вместо 24 для представления одних и тех же данных, что является значительной экономией.
Сжатие без потерь в повседневном использовании
Как мы упоминали выше, сжатие без потерь важно в тех случаях, когда вы не можете удалить исходный файл. Если вам интересно, как работают ZIP-файлы, это ответ.
Когда вы создаете ZIP-файл из исполняемой программы Windows, он использует сжатие без потерь. Сжатие файла ZIP является более эффективным способом хранения программы, но когда вы распаковываете (распаковываете) ее, вся оригинальная информация присутствует. Если вы использовали сжатие с потерями для сжатия исполняемых файлов, распакованная версия будет повреждена и непригодна для использования.
Распространенные форматы без потерь включают PNG для изображений, FLAC для аудио и ZIP. Форматы видео без потерь редки, потому что они занимают огромное количество места.
Когда использовать сжатие с потерями против сжатия без потерь
Теперь, когда мы рассмотрели обе формы сжатия файлов, вы можете задаться вопросом, когда следует использовать одну или другую. Как выясняется, «лучшей» формы сжатия не существует — все зависит от того, для чего вы используете файлы.
В общем, вы должны использовать сжатие без потерь, если вы хотите получить идеальную копию исходного материала, и сжатие с потерями, если недостаточно хорошая копия. Давайте посмотрим на другой пример, чтобы увидеть, как они могут работать в гармонии.
Скажем, вы только что откопали свою старую коллекцию компакт-дисков и хотите оцифровать ее. чтобы у вас была вся музыка на вашем компьютере. Когда вы копируете свои компакт-диски, имеет смысл использовать такой формат, как FLAC, который без потерь. Это позволяет вам иметь мастер-копию на вашем компьютере, которая так же хороша, как и оригинальный компакт-диск.
Позже, возможно, вы захотите поставить музыку на телефон или старый MP3-плеер, чтобы вы могли слушать на ходу. Возможно, вы не заботитесь о том, чтобы ваша музыка была в идеальном качестве, поэтому вы можете конвертировать файлы FLAC в MP3 Это дает вам аудиофайл, который по-прежнему идеально подходит для прослушивания, но не занимает много места на вашем мобильном устройстве. Качество MP3, преобразованного из FLAC, будет таким же хорошим, как если бы вы создали сжатый MP3 прямо с оригинального CD.
Тип данных, представленных в файле, также может определять, какой тип сжатия является лучшим. Поскольку в PNG-изображениях используется сжатие без потерь, они предлагают небольшие размеры файлов для изображений с большим равномерным пространством, например, компьютерные снимки экрана. Тем не менее, вы заметите, что PNG занимают гораздо больше места, когда они представляют собой смесь цветов на реальных фотографиях.
Проблемы во время сжатия файлов
Как мы уже видели, преобразование форматов с потерями в формат потерь — это хорошо, равно как и преобразование одного формата без потерь в другой. Однако вы никогда не должны конвертировать формат с потерями в без потерь и должны остерегаться преобразования одного формата с потерями в другой.
Преобразование форматов с потерями в без потерь просто пустая трата пространства. Помните, что форматы с потерями выбрасывают данные; невозможно восстановить эти данные.
Скажем, у вас есть 3MB MP3-файл. Преобразование этого в FLAC может привести к 30-мегабайтному файлу, но эти 30-мегабайтные содержат точные звуки, которые сделал гораздо меньший MP3. Преобразование обратно в формат без потерь не «восстанавливает» информацию, которую выбросило сжатие MP3.
Наконец, как упоминалось ранее, преобразование одного формата с потерями в другой (или многократное сохранение в том же формате) приведет к дальнейшему снижению качества. Каждый раз, когда вы применяете сжатие с потерями, вы теряете больше деталей. Это становится все более и более заметным, пока файл по существу не разрушен.
Как работает компрессия? Теперь ты знаешь
Мы рассмотрели как сжатие с потерями, так и сжатие без потерь, чтобы увидеть, как они работают. Теперь вы знаете, как можно сохранить файл в меньшем размере, чем его оригинальная форма, и как выбрать лучший метод для ваших нужд.
Конечно, алгоритмы, которые определяют, какие данные выбрасываются в методах с потерями и как лучше хранить избыточные данные при сжатии без потерь, намного сложнее, чем мы объясняли здесь. На эту тему можно найти гораздо больше, если вам интересно.
Простым языком о том, как работает сжатие файлов
Авторизуйтесь
Простым языком о том, как работает сжатие файлов
Сжатие файлов позволяет быстрее передавать, получать и хранить большие файлы. Оно используется повсеместно и наверняка хорошая вам знакомо: самые популярные расширения сжатых файлов — ZIP, JPEG и MP3. В этой статье кратко рассмотрим основные виды сжатия файлов и принципы их работы.
Что такое сжатие?
Сжатие файла — это уменьшение его размера при сохранении исходных данных. В этом случае файл занимает меньше места на устройстве, что также облегчает его хранение и передачу через интернет или другим способом. Важно отметить, что сжатие не безгранично и обычно делится на два основных типа: с потерями и без потерь. Рассмотрим каждый из них по отдельности.
Сжатие с потерями
Такой способ уменьшает размер файла, удаляя ненужные биты информации. Чаще всего встречается в форматах изображений, видео и аудио, где нет необходимости в идеальном представлении исходного медиа. MP3 и JPEG — два популярных примера. Но сжатие с потерями не совсем подходит для файлов, где важна вся информация. Например, в текстовом файле или электронной таблице оно приведёт к искажённому выводу.
MP3 содержит не всю аудиоинформацию из оригинальной записи. Этот формат исключает некоторые звуки, которые люди не слышат. Вы заметите, что они пропали, только на профессиональном оборудовании с очень высоким качеством звука, поэтому для обычного использования удаление этой информации позволит уменьшить размер файла практически без недостатков.
20–22 декабря, Онлайн, Беcплатно
Аналогично файлы JPEG удаляют некритичные части изображений. Например, в изображении с голубым небом сжатие JPEG может изменить все пиксели на один или два оттенка синего вместо десятков.
Чем сильнее вы сжимаете файл, тем заметнее становится снижение качества. Вы, вероятно, замечали такое, слушая некачественную музыку в формате MP3, загруженную на YouTube. Например, сравните музыкальный трек высокого качества с сильно сжатой версией той же песни.
Сжатие с потерями подходит, когда файл содержит больше информации, чем нужно для ваших целей. Например, у вас есть огромный файл с исходным (RAW) изображением. Целесообразно сохранить это качество для печати изображения на большом баннере, но загружать исходный файл в Facebook будет бессмысленно. Картинка содержит множество данных, не заметных при просмотре в социальных сетях. Сжатие картинки в высококачественный JPEG исключает некоторую информацию, но изображение выглядит почти как оригинал.
При сохранении в формате с потерями, вы зачастую можете установить уровень качества. Например, у многих графических редакторов есть ползунок для выбора качества JPEG от 0 до 100. Экономия на уровне 90 или 80 процентов приводит к небольшому уменьшению размера файла с незначительной визуальной разницей. Но сохранение в плохом качестве или повторное сохранение одного и того же файла в формате с потерями ухудшит его.
Посмотрите на этот пример.
Оригинальное изображение, загруженное с Pixabay в формате JPEG. 874 КБ:
Результат сохранения в формате JPEG с 50-процентным качеством. Выглядит не так уж плохо. Вы можете заметить артефакты по краям коробок только при увеличении. 310 КБ:
Исходное изображение, сохранённое в формате JPEG с 10-процентным качеством. Выглядит ужасно. 100 КБ:
Где используется сжатие с потерями
Как мы уже упоминали, сжатие с потерями отлично подходит для большинства медиафайлов. Это крайне важно для таких компаний как Spotify и Netflix, которые постоянно транслируют большие объёмы информации. Максимальное уменьшение размера файла при сохранении качества делает их работу более эффективной.
Сжатие без потерь
Сжатие без потерь позволяет уменьшить размер файла так, чтобы в дальнейшем можно было восстановить первоначальное качество. В отличие от сжатия с потерями, этот способ не удаляет никакую информацию. Рассмотрим простой пример. На картинке ниже стопка из 10 кирпичей: два синих, пять жёлтых и три красных.
Вместо того чтобы показывать все 10 блоков, мы можем удалить все кирпичи одного цвета, кроме одного. Используя цифры, чтобы показать, сколько кирпичей каждого цвета было, мы представляем те же данные используя гораздо меньше кирпичей — три вместо десяти.
Это простая иллюстрация того, как осуществить сжатие без потерь. Та же информация сохраняется более эффективным способом. Рассмотрим реальный файл: mmmmmuuuuuuuoooooooooooo. Его можно сжать до гораздо более короткой формы: m5u7o12. Это позволяет использовать 7 символов вместо 24 для представления одних и тех же данных.
Где используется сжатие без потерь
ZIP-файлы — популярный пример сжатия без потерь. Хранить информацию в виде ZIP-файлов более эффективно, при этом когда вы распаковываете архив, там присутствует вся оригинальная информация. Это актуально для исполняемых файлов, так как после сжатия с потерями распакованная версия будет повреждена и непригодна для использования.
Другие распространённые форматы без потерь — PNG для изображений и FLAC для аудио. Форматы видео без потерь встречаются редко, потому что они занимают много места.
Сжатие с потерями vs сжатие без потерь
Теперь, когда мы рассмотрели обе формы сжатия файлов, может возникнуть вопрос, когда и какую следует использовать. Здесь всё зависит от того, для чего вы используете файлы.
Скажем, вы только что откопали свою старую коллекцию компакт-дисков и хотите оцифровать её. Когда вы копируете свои компакт-диски, имеет смысл использовать формат FLAC, формат без потерь. Это позволяет получить мастер-копию на компьютере, которая обладает тем же качеством звука, что и оригинальный компакт-диск.
Позже вы, возможно, захотите загрузить музыку на телефон или старый MP3-плеер. Здесь не так важно, чтобы музыка была в идеальном качестве, поэтому вы можете конвертировать файлы FLAC в MP3. Это даст вам аудиофайл, который по-прежнему достаточно хорош для прослушивания, но не занимает много места на мобильном устройстве. Качество MP3, преобразованного из FLAC, будет таким же, как если бы вы создали сжатый MP3 с оригинального CD.
Тип данных, представленных в файле, также может определять, какой вид сжатия подходит больше. В PNG используется сжатие без потерь, поэтому его хорошо использовать для изображений, в которых много однотонного пространства. Например, для скриншотов. Но PNG занимает гораздо больше места, когда картинка состоит из смеси множества цветов, как в случае с фотографиями. В этом случае с точки зрения размера файлов лучше использовать JPEG.
Проблемы во время сжатия файлов
Бесполезно конвертировать формат с потерями в формат без потерь. Это пустая трата пространства. Скажем, у вас есть MP3-файл весом в 3 МБ. Преобразование его в FLAC может привести к увеличению размера до 30 МБ. Но эти 30 МБ содержат только те звуки, которые имел уже сжатый MP3. Качество звука от этого не улучшится, но объём станет больше.
Также стоит иметь в виду, что преобразовывая один формат с потерями в аналогичный, вы получаете дальнейшее снижение качества. Каждый раз, когда вы применяете сжатие с потерями, вы теряете больше деталей. Это становится всё более и более заметно, пока файл по существу не будет разрушен. Помните также, что форматы с потерями удаляют некоторые данные и их невозможно восстановить.
Заключение
Мы рассмотрели как сжатие файлов с потерями, так и без потерь, чтобы увидеть, как они работают. Теперь вы знаете, как можно уменьшить размер файла и как выбрать лучший способ для этого.
Алгоритмы, которые определяют, какие данные выбрасываются в методах с потерями и как лучше хранить избыточные данные при сжатии без потерь, намного сложнее, чем описано здесь. На эту тему можно почитать больше информации здесь, если вам интересно.