какие файлы сжимаются лучше всего
Сравниваем: какой формат сжатия файлов лучше?
Какие форматы сжатия файлов вы бы использовали? Скорее всего, именно Zip, RAR, 7z, ведь они самые популярные. Было проведено несколько тестов, которые помогут определиться, какой формат сможет дать максимальный уровень сжатия и какой самый удобный в использование.
Стоит заметить, что степень сжатия является не самым главным фактором по тому что некоторые форматы более удобны, или интегрированы в операционную систему, в тоже время другие могут являться частью стороннего программного обеспечения.
Сжатие файлов эталонов популярными архиваторами
На самом деле всё не так просто, как может показаться на первый взгляд. Степень достигаемого сжатия зависит больше от программы архиватора, её настроек и алгоритмов. В тестирование вместо обыкновенных файлов документов Microsoft Office, в свою очередь уже использующих сжатие, было решено использовать сжатие уже установленных компьютерных игр.
Но тут может возникнуть вопрос, почему именно игры? Но ответ на самом деле кроется совсем близко, ведь игры включают в себя графику, музыку, текстовые файлы, исполняемые файлы, не говоря уже о других типах файлов, игры сочетают в себе всю информацию, которая может использоваться для сжатия в повседневной жизни. Вы так же можете подробнее узнать что такое файл, перейдя по ссылке.
Первой стала Bastion (Бастион), установленная игра имела размер около 863 мегабайт: музыки, графических и исполняемых файлов, плюс ко всему этому разные типы документов и вот что было получено:
Следующей для проведения тестирования была выбрана игра Hotline Miami (Горячая линия Маями), которая имела размер 654 Мб:
Кто же стал лидером файлового сжатия на основе тестов
Лидером чистого сжатия становится формат 7z, что на самом деле это не является удивительным для этого популярного формата. Если вы хотите, что ни будь сжать и использовать при этом как можно меньше места для хранения, нужно использовать именно 7z. Если ко всему этому воспользоваться настройками программы для экономии ещё большего места, то сжать необходимый файл можно ещё лучше. При этом, время сжатия и дальнейшей распаковки тоже увеличится.
Результаты RAR и Zip были очень близки друг к другу, а для интегрированной в Windows 8.1 WinZip не составит труда открыть формат Zip.
Для максимально сжатия лучше использовать 7-Zip с 7z, а вот для большего удобства и максимальной совместимости лучшим будет создание Zip-файлов, с помощью интегрированного в операционной системе функционала.
Если вы используете сжатие для себя, то можно использовать любой формат, который вам захочется и ни каких проблем с дальнейшим открытием не возникнет. Но не у всех на компьютерах установлено то или иное ПО (программное обеспечение) для открытия запакованных файлов. Например, если вы размещаете архивы в интернете, то нужно использовать формат, которым скачавшие его люди смогут без труда воспользоваться, самый популярный.
Популярные форматы, которые уже интегрированные в операционные системы:
Windows по умолчанию поддерживает только Zip файлы, так как Zip наиболее популярный и универсальный формат, но, если вам приходится работать с Mac или Linux вы, конечно же, можете использовать такой формат сжатия как 7z, но тогда вам придётся установить приложение для его открытия.
Все же если целью является получение лучшего сжатия, то 7z – это путь в правильном направление, а вот если важнее удобство использования как для себя, так и для других, то самым распространённым и как следствие удобным в использование форматом сжатия будет, как написано ранее zip.
Результаты произведённых тестов являются обобщёнными. Получены разные результаты архивирования с разными типами данных, но благодаря общим результатам можно на наглядном примере убедиться в расходящихся результатах для разных форматов сжатия и определиться с подходящим.
Какие файлы сжимаются лучше всего
Главной целью этой статьи является выбор наиболее оптимального архиватора с высокой степенью сжатия различных реальных данных большого объёма. В тестировании принимали участие: самый распространенный и один из старейших ZIP, популярные архиваторы ACE, RAR, 7-zip. Кроме того, были протестированы некоторые перспективные архиваторы. Большинство из них являются экспериментальными, обладают низкой скоростью архивирования и разархивирования, требуют много оперативной памяти, имеют ошибки. Например, не удалось сжать все тестовые данные при помощи Slim 0.021 (ошибка приложения), показавшего очень хорошие результаты, скорость PAQ6 v2 достигала 15 КБ/с. В итоге были выбраны Compressia 1.0b, EPM r9, PAQ6 v2, RKC 1.02, которые на данный момент являются одними из лучших.
Стоит отметить, что в рейтинге www.maximumcompression.com, EPM r9, PAQ6 v2, RKC 1.02, Compressia 1.0b сжимают лучше, чем 7-zip 3.13, WinRAR 3.30b5 на 10%, а разница между 7-zip 3.13 и WinRAR 3.30b5 около 3%.
Поиск оптимального соотношения между степенью сжатия и скоростью – это предмет отдельного исследования. Кроме того, это соотношение не имеет четких границ и сильно зависит как от системы, на которой производится архивирование, так и от исходных данных. Можно привести такой пример: в max режиме при архивировании «Инсталляция Office XP» скорость 7-zip в 3 раза выше Compressia, а при архивировании «База данных 1С:Предприятие» скорость 7-zip в 9 раз ниже Compressia. В данной статье основной упор сделан на степень сжатия.
В качестве тестовых данных использовались большие объемы реальных неоднородных данных. Исключение составляет «Документы Word, Excel». Больше 9 МБ реальных «средних» документов найти не удалось, а тестировать документы по 13 МБ, в основном состоящие из отсканированных и несжимаемых изображений, неправильно. Дополнительно была добавлена книга TICSharp.DOC (11 МБ) с небольшими иллюстрациями.
Если необходимы результаты сжатия исключительно текстов, программ, изображений, звука, то лучше поискать в Интернете соответствующие тестирования, например на www.maximumcompression.com, www.compressio.ru, arctest.narod.ru.
Тестировались следующие архиваторы:
ZIP. Является старейшим и самым распространённым архиватором. Это почти стандарт. Преимущества – высокая скорость, распространённость, совместимость и бесплатность. Недостатки – низкий уровень сжатия, ограниченная функциональность.
Использовался встроенный в Total Commander 6.0 архиватор. Несмотря на то, что Total Commander является shareware, сам формат ZIP бесплатный. Существует много бесплатных программ, которые архивируют в формат ZIP, например 7-zip. Стоит отметить, что каждая реализация ZIP может иметь скорость и степень сжатия, отличающуюся от реализации ZIP в Total Commander 6.0. Например, 7-zip архивирует в ZIP с более высокой степенью сжатия, но значительно медленнее.
Настройки для тестирования:
Использовался WinACE 2.5. Настройки для тестирования:
RAR 2.9 www.rarlab.com. Преимущества – высокая функциональность, степень сжатия и скорость, распространённость. Недостатки – платный.
Использовался WinRAR 3.30 beta 5. По сравнению с предыдущей версией 3.11 степень сжатия незначительно увеличилась на всех видах данных, для текста прирост немного больше (вероятно, из-за улучшения в автоматическом определении параметров сжатия).
Настройки для тестирования:
Использовался 7-zip 3.12. Настройки для тестирования:
Compressia www.compressia.com. Преимущества – один из самых лучших по степени сжатия архиваторов. Недостатки – сильно ограниченная функциональность, только GUI версия, низкая скорость, скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования, платный.
Использовался Compressia v1.0 beta. Настройки для тестирования:
Настройки для тестирования:
RKC www.msoftware.co.nz. Преимущества – один из самых лучших по степени сжатия архиваторов. Недостатки – низкая скорость, скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования, для высокой степени сжатия необходимо относительно много оперативной памяти. В конце февраля 2004 ожидается выход полноценного архиватора WinRK.
Настройки для тестирования:
mmahoney/compression. Преимущества – один из самых лучших по степени сжатия архиваторов. Недостатки – очень низкая скорость, скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования, для высокой степени сжатия необходимо относительно много оперативной памяти.
Настройки для тестирования:
Для тестирования использовались следующие хорошо сжимающиеся данные:
Тестирование производилось на системе: CPU Athlon 2000 МГц, MB nForce2, RAM 512 МБ, HDD WD400JB, OS Windows 2000. Следует учитывать, что на аналогичных Pentium системах скорость сжатия может сильно отличаться.
Что можно архивировать?
Хорошо сжимаются почти все предварительно не сжатые данные, например, программные файлы, тексты, базы данных, простые несжатые изображения. Ограниченно сжимаются несжатый звук (WAV), сложные несжатые изображения (BMP). Не сжимаются (сжатие в пределах пары процентов за счет служебных тэгов и, возможно, небольшой избыточности) почти все уже сжатые данные, например, архивы (ZIP, CAB), сжатая графика и видео (JPG, GIF, AVI, MPG), сжатый звук (MP3).
Для сжатия некоторых специфических данных (текст, несжатые изображения, несжатый звук) существуют специализированные архиваторы, которые обеспечивают несколько лучшую степень сжатия и значительно более высокую скорость, чем универсальные архиваторы.
Несмотря на низкую степень сжатия, ZIP norm обладает самой высокой скоростью (быстрее RAR fastest в 2 раза). Его можно использовать на медленных машинах или для оперативного архивирования.
RAR и ACE приблизительно равны, с небольшим преимуществом у RAR. Их можно рекомендовать только из-за дополнительной функциональности (например, разбивка архива на части, запись дополнительной информации для восстановления при повреждении архива). По степени сжатия они уступают 7-zip. На некоторых наборах данных разница значительна. В max режиме размер архива RAR больше 7-zip от 5% до 34%, в среднем на 18%.
7-zip не является лидером в степени сжатия и имеет низкую скорость в max режиме. По сравнению с PAQ6, размер архива 7-zip больше от 2% до 23%, в среднем на 13%. Разница с результатами Compressia, EPM, RKC незначительна или даже отличается в лучшую сторону. В отличие от этих архиваторов, скорость разархивирования 7-zip (за исключением режима PPMd) значительно выше скорости архивирования. Требования к оперативной памяти во время разархивирования небольшие. Низкая скорость в max режиме все же значительно выше, чем скорость PAQ6 (в 10 раз). 7-zip может работать, используя 2 потока, что даёт значительное повышение скорости на мультипроцессорных системах или на системах с Hyper-Threading. С учетом регулярного обновления и бесплатности, 7-zip является наиболее оптимальным выбором для современных систем. В списке ближайших его изменений – разбивка архива на части, запись дополнительной информации для восстановления при повреждении архива.
PAQ6 показал самую лучшую степень сжатия со значительным отрывом от конкурентов. Но практически использовать его могут только экстремалы из-за очень низкой скорости (17 КБ/с). Несмотря на хорошие результаты на больших объёмах неоднородных данных, проведенное мини-тестирование по сжатию одного файла (1Cv7.MD.rpk, 7 МБ) показало, что RKC справился со сжатием на 1%, EPM на 4%, а Slim 0.021 slim-fb.by.ru на 8% лучше PAQ6 (7-zip на 20% хуже).
Дальнейшее увеличение степени сжатия архиваторов сильно ограничено возможностью современных компьютеров. Даже успехи 7-zip на фоне RAR достигнуты за счет уменьшения скорости. Более того, практическая реализация эффективных PPM алгоритмов, используемых RKC, PAQ, EPM, была обусловлена существенным повышением производительности компьютеров в последние годы. Поэтому не следует в ближайшее время ждать появления архиваторов, которые при высокой скорости показывали бы степень сжатия значительно выше рассмотренных.
Простым языком о том, как работает сжатие файлов
Авторизуйтесь
Простым языком о том, как работает сжатие файлов
Сжатие файлов позволяет быстрее передавать, получать и хранить большие файлы. Оно используется повсеместно и наверняка хорошая вам знакомо: самые популярные расширения сжатых файлов — ZIP, JPEG и MP3. В этой статье кратко рассмотрим основные виды сжатия файлов и принципы их работы.
Что такое сжатие?
Сжатие файла — это уменьшение его размера при сохранении исходных данных. В этом случае файл занимает меньше места на устройстве, что также облегчает его хранение и передачу через интернет или другим способом. Важно отметить, что сжатие не безгранично и обычно делится на два основных типа: с потерями и без потерь. Рассмотрим каждый из них по отдельности.
Сжатие с потерями
Такой способ уменьшает размер файла, удаляя ненужные биты информации. Чаще всего встречается в форматах изображений, видео и аудио, где нет необходимости в идеальном представлении исходного медиа. MP3 и JPEG — два популярных примера. Но сжатие с потерями не совсем подходит для файлов, где важна вся информация. Например, в текстовом файле или электронной таблице оно приведёт к искажённому выводу.
MP3 содержит не всю аудиоинформацию из оригинальной записи. Этот формат исключает некоторые звуки, которые люди не слышат. Вы заметите, что они пропали, только на профессиональном оборудовании с очень высоким качеством звука, поэтому для обычного использования удаление этой информации позволит уменьшить размер файла практически без недостатков.
27–28 ноября, Москва, Бе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. Качество звука от этого не улучшится, но объём станет больше.
Также стоит иметь в виду, что преобразовывая один формат с потерями в аналогичный, вы получаете дальнейшее снижение качества. Каждый раз, когда вы применяете сжатие с потерями, вы теряете больше деталей. Это становится всё более и более заметно, пока файл по существу не будет разрушен. Помните также, что форматы с потерями удаляют некоторые данные и их невозможно восстановить.
Заключение
Мы рассмотрели как сжатие файлов с потерями, так и без потерь, чтобы увидеть, как они работают. Теперь вы знаете, как можно уменьшить размер файла и как выбрать лучший способ для этого.
Алгоритмы, которые определяют, какие данные выбрасываются в методах с потерями и как лучше хранить избыточные данные при сжатии без потерь, намного сложнее, чем описано здесь. На эту тему можно почитать больше информации здесь, если вам интересно.
Тест архивов. Какой формат выбрать?
Эта тема будет посвящена сравнению алгоритмов сжатия. Для владельцев Медленного и Лимитного Интернета будет полезно, да и не только им.
Для сжатия использовался ZArchiver 0.9.5 для Android, настройки всех форматов на Ультра. Указаны Размер и Процент от Размера Оригинала. Для 7Z включён LZMA2 (В настройках ZArchiver)
Под первым Спойлером показаны исходные размеры (Смотрите в нижний левый угол, последняя строка).
Внимание! Много Картинок!
Есть 7 папок, под разные категории
Теперь начнём же сравнение!
1: Образ Windows 3.10
3: Jeanne d’Arc, Rus, PSP
4: 459 игр для NES aka Денди, Rus
6: Прошивка Navitel C500
7: Субтитры для Наруто: Ураганные Хроники! Кто помнит Акацуки и Мадару?
Вот и комментарии
Категория 1: Образ Windows 3.10
Форматы типа «Как у всех» (Далее будет указан как «Тип 1»)
ZIP: 8.89 МБ / 79% // Слабовато.
7Z: 8.05 МБ / 71% // Что и следовало ожидать от 7Z.
TAR.LZ4: 9.48 МБ / 84% // Слился от ZIP. Что ещё ожидать от формата, заточенного на скорость. Хотя.
TAR.ZST: 8.38 МБ / 74% // Очень быстрое сжатие и распаковка, размеры в основном между ZIP и 7Z, хотя возможны варианты. Известен как ZStandard или ZSTD
Категория 2: Война и мир, в формате FB2
7Z: 2.96 МБ / 32% // Классика жанра
TAR.LZ4: 4.57 МБ / 50% // LZ4 снова слился.
TAR.ZST: 3.31 МБ / 36% // И снова победа над ZIP!
TAR.XZ: 2.96 МБ / 32% // Тут 7Z и XZ равны.
7Z: 459.80 МБ / 38% // Вот это адекватные размеры!
TAR.LZ4: 701.92 МБ / 59% // Такой архив весит многовато.
TAR.ZST: 601.44 МБ / 50% // Архив меньше на
40 МБ, но скорость распаковки. Вы удивитесь, когда начнёте тесты на файлах больше 1 ГБ!
TAR.XZ: 459.80 МБ / 38% // Снова они равны!
Категория 4: Сборник из 459 игр для NES / Денди на русском языке!
ZIP: 38.30 МБ / 50% // Чётко и поровну!
7Z: 34.82 МБ / 45% // 5 Процентов разницы для кого-то могут значит.
TAR.LZ4: 46.15 МБ / 60% // Как всегда.
TAR.ZST: 33.80 МБ / 44% // 7Z гнут даже скоростные форматы!
TAR.XZ: 27.83 МБ / 36% // 7Z уложили на лопатки!
ZIP: 440.01 КБ / 31% // Классике всегда будет место!
7Z: 400.31 КБ / 28% // Немного лучше.
TAR.LZ4: 492.36 КБ / 35% // Не удивляйтесь!
TAR.ZST: 323.63 КБ / 23% // И снова 7Z пои. Победили, вот!
TAR.XZ: 273.11 КБ / 19% // Fatality!
Категория 6: Прошивка Navitel C500
ZIP: 47.39 МБ / 72% // Норм
7Z: 40.56 МБ / 62% //Вот так лучше!
TAR.LZ4: 51.56 МБ / 79% // ОК.
TAR.XZ: 40.51 МБ / 62% // Тут разница некритична.
Категория 7: Субтитры для Наруто: Ураганные Хроники! Кто помнит Акацуки, Мадару?
ZIP: 32.67 МБ / 24% // Тексты всегда сжимаются на ура!
7Z: 28.46 МБ / 21% // Кто-то сэкономит траффик.
TAR.LZ4: 39.68 МБ / 29% // Даже тексты. Сжимает хуже всего!
TAR.ZST: 19.53 МБ / 14% // 7Z нагибают аж от души!
TAR.XZ: 11.68 МБ / 8% // Ну. у 7Z нет шансов!
Вывод
7Z имеет высокое сжатие и низкую скорость сжатия / распаковки, но иногда его нагибают скоростные форматы, не говоря уже об XZ!
LZ4 до появления ZStandard мог быть пригоден благодаря скорости сжатия / распаковки, но после появления ZStandart его стоит использовать разве то для совместимости.
ZStandard имеет сжатие в основном между ZIP и 7Z, ОЧЕНЬ высокую скорость сжатия / распаковки, а иногда он по сжатию превосходит 7Z!
XZ имеет самое лучшее сжатие и низкую скорость сжатия / распаковки. Шикарный вариант для медленного и лимитного интернета.
Делайте свои выводы.
Upd: сделал дополнительные тесты и узнал, что:
1: LZ4 иногда сжимает ЛУЧШЕ, чем ZIP, притом НАМНОГО быстрее даже на ультра настройках!
Алгоритмы сжатия данных без потерь
Часть первая – историческая.
Введение
История
Иерархия алгоритмов:
Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы 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, которая пока мало используется в программах.
В следующей части мы рассмотрим техническую сторону упомянутых алгоритмов и принципы их работы.