Pull to refresh
  • by relevance
  • by date
  • by rating

xz — сила сжатия LZMA уже в твоей консоли

Data compression *
Многие наверное уже знают про утилитку для компрессии/декомпрессии xz. Но еще больше не знают. Поэтому написал этот ознакомительный топик.

xz — формат сжатия данных, наряду с gzip, bzip2 вошедший в gnu-шные приложения.
Использует алгоритм LZMA, тот же что и в 7z, а это значит что можно сильнее сжать многие виды данных, типа текста, бинарные еще не сжатые данные по сравнению с стандартными, упомянутыми выше.
xz используется в новом rpm 4.7.2 для компрессии архивов .cpio в rpm-пакетах (используется с Fedora 12).
В ArchLinux вообще используется .tar.xz в качестве пакета.
В GNU tar появились опции -J --lzma, которые исполняют туже роль что и -z для gzip, -j для bzip2
Читать дальше →
Total votes 15: ↑11 and ↓4 +7
Views 10K
Comments 11

libral – слой абстракции доступа к библиотекам сжатия

C++ *
Привет Хабр! Хочу представить свою С/С++ библиотеку libral, которая с недавних пор стала open source под лицензией GPL3. Возможно кому-то она будет полезна. Библиотека предоставляет единый интерфейс к различным алгоритмам сжатия данных без потерь.
На данный момент поддерживаются библиотеки:

Читать дальше →
Total votes 45: ↑38 and ↓7 +31
Views 988
Comments 34

Алгоритмы используемые при сжатии данных

Algorithms *
Sandbox
Вступление

Одна из самых главных проблем при работе с данными — это их размер. Нам всегда хочется, что бы уместилось как можно больше. Но иногда этого не сделать. Поэтому нам на помощь приходят различные архиваторы. Но как они сжимают данные? Я не буду писать о принципе их работы, лишь расскажу о нескольких алгоритмах сжатия, которые они используют.
Читать дальше →
Total votes 70: ↑46 and ↓24 +22
Views 40K
Comments 8

Почти линейное увеличение производительности bzip2 на многопроцессорных системах

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

Но можно получить эффективность bzip2, при этом существенно увеличив скорость. Речь идёт об утилите pbzip2 — Parallel BZIP2. В обычном случае при использовании bzip2 задействуется только одно процессорное ядро, в то время как на современных системах их может быть 2, 4, или, например, 8.

Pbzip2 может использовать сразу несколько процессорных ядер, что приводит, по заявлению авторов, к почти линейному увеличению производительности. Сжатые файлы, которые создаёт pbzip2, полностью совместимы с bzip2 1.0.2 и более новыми версиями bzip2 (также есть утилита pigz, которая, в свою очередь, является многопоточной реализацией gzip — спасибо altexxx).

Ниже результат тестирования скорости сжатия участка SQL-файла размером 1000M (dd if=dump.sql of=testfile bs=1M count=1000) на компьютере с двумя процессорами Intel Xeon E5520 (4 ядра, 8 потоков, тактовая частота 2,26 ГГц):

Результаты тестирования

Как видно из результатов тестирования, pbzip2, работающий в 4 потока, приблизительно в 3,6 раз быстрее, чем bzip2, работающий в один поток — что действительно является почти линейным увеличением производительности.

При этом pbzip2, работающий в 16 потоков, оказался медленнее, чем pbzip2, использующий 4 потока — вероятно, из-за скорости выполнения операций ввода/вывода. Также смотрите дополнительные тесты в комментариях (спасибо tristan и bliznezz) — в том числе, с использованием tmpfs-раздела в оперативной памяти.

Используется pbzip2 примерно так же, как и просто bzip2, но есть некоторые дополнительные функции, например вывод прогресса выполнения операции в процентах.

Читать дальше →
Total votes 58: ↑51 and ↓7 +44
Views 14K
Comments 17

Сравнение программ сжатия в применении к передаче больших объёмов данных

Data recovery *
Sandbox
Всё началось с простой задачи: скачать по 100-мегабитной сети большой объём данных с помощью rsync. Возник вопрос, можно ли ускорить этот процесс. Утилита top показала, что на сервере-источнике шифрование занимает не более 10 процентов процессора, поэтому было решено что можно попробовать сжатие данных. Тогда мне было неясно, будет ли хватать производительности процессора для упаковки данных с необходимой скоростью, поэтому была выставлена самая маленькая степень сжатия, а именно использовался флаг --compress-level=1 для rsync. Оказалось, что загрузка процессора не превысила 65%, то есть производительности процессора хватило, при этом скорость скачивания данных несколько повысилась.

После этого возник вопрос о анализе применимости распространённых программ сжатия
для передачи данных по сети.
Читать дальше →
Total votes 28: ↑24 and ↓4 +20
Views 9.8K
Comments 17

Алгоритмы сжатия данных без потерь

Algorithms *
Translation
Часть первая – историческая.

Введение


Существующие алгоритмы сжатия данных можно разделить на два больших класса – с потерями, и без. Алгоритмы с потерями обычно применяются для сжатия изображений и аудио. Эти алгоритмы позволяют достичь больших степеней сжатия благодаря избирательной потере качества. Однако, по определению, восстановить первоначальные данные из сжатого результата невозможно.
Алгоритмы сжатия без потерь применяются для уменьшения размера данных, и работают таким образом, что возможно восстановить данные в точности такими, какие они были до сжатия. Они применяются в коммуникациях, архиваторах и некоторых алгоритмах сжатии аудио и графической информации. Далее мы рассмотрим только алгоритмы сжатия без потерь.
Основной принцип алгоритмов сжатия базируется на том, что в любом файле, содержащем неслучайные данные, информация частично повторяется. Используя статистические математические модели можно определить вероятность повторения определённой комбинации символов. После этого можно создать коды, обозначающие выбранные фразы, и назначить самым часто повторяющимся фразам самые короткие коды. Для этого используются разные техники, например: энтропийное кодирование, кодирование повторов, и сжатие при помощи словаря. С их помощью 8-битный символ, или целая строка, могут быть заменены всего лишь несколькими битами, устраняя таким образом излишнюю информацию.
Читать дальше →
Total votes 56: ↑52 and ↓4 +48
Views 122K
Comments 71

Алгоритмы сжатия данных без потерь, часть 2

Algorithms *
Часть 1

Техники сжатия данных


Для сжатия данных придумано множество техник. Большинство из них комбинируют несколько принципов сжатия для создания полноценного алгоритма. Даже хорошие принципы, будучи скомбинированы вместе, дают лучший результат. Большинство техник используют принцип энтропийного кодирования, но часто встречаются и другие – кодирование длин серий (Run-Length Encoding) и преобразование Барроуза-Уилера (Burrows-Wheeler Transform).
Читать дальше →
Total votes 47: ↑45 and ↓2 +43
Views 83K
Comments 10

Файл 420 байт разжимается в картинку PNG на 40 гигапикселей (141 ГБ ОЗУ)

Demoscene
В старые времена были популярны zip-бомбы и рекурсивные архивы, которые распаковываются сами в себя. Zip-бомбу иногда можно использовать для DoS-атаки. Например, пресловутый файл 42.zip имеет размер 42 килобайта. Если начать его распаковку, то процесс будет идти до тех пор, пока набор данных не достигнет верхнего предела распаковки в 4,3 гигабайта. При этом процесс займет более 4,5 петабайт в оперативной памяти (4 503 599 626 321 920 байт).

Программист и хакер Дэвид Фифилд (David Fifield) задумался, где ещё можно применить «архивные бомбы». Сразу на ум приходит графический формат PNG, в котором используется алгоритм сжатия DEFLATE в библиотеке zlib.
Читать дальше →
Total votes 35: ↑30 and ↓5 +25
Views 12K
Comments 13