Bzip2
bzip2 | |||
---|---|---|---|
![]() | |||
Тип | Сжатие данных | ||
Разработчик | Джулиан Сюард | ||
Написана на | Си | ||
Операционная система | Кроссплатформенное ПО | ||
Первый выпуск | 18 июля 1996 | ||
Последняя версия | |||
Репозиторий | sourceware.org/git/bzip2… | ||
| |||
| |||
Лицензия | Лицензия BSD[2] | ||
Сайт | sourceware.org/bzip2/ |
bzip2 — бесплатная свободная утилита командной строки с открытым исходным кодом для сжатия данных, реализация алгоритма Барроуза — Уилера.
Разработана и впервые опубликована Джулианом Сюардом (англ. Julian Seward) в июле 1996 года (версия 0.15). Стабильность и популярность компрессора росли в течение нескольких лет, и версия 1.0 была опубликована в конце 2000 года.
Эффективность
В соответствии с традициями UNIX, bzip2
единовременно может выполнять только одну операцию: либо сжатие, либо распаковку и только для одного файла. При сжатии bzip2
добавляет к имени файла расширение «.bz2
». Для упаковки нескольких файлов их сперва архивируют в один файл утилитой tar
, а затем сжимают при помощи bzip2
. Такие архивы обычно имеют расширение «.tar.bz2
».
bzip2
сжимает большинство файлов эффективнее, но медленнее, чем более традиционные утилиты gzip
или zip
. В этом отношении он похож на другие современные алгоритмы сжатия.
bzip2
выполняет сжатие данных с существенной нагрузкой на CPU (что обусловлено его математическим аппаратом). bzip2
применяют, если нет ограничений на время сжатия и на нагрузку на CPU, например, для разовой упаковки большого объёма данных.
В некоторых случаях bzip2
уступает по эффективности сжатия архиваторам 7-Zip
(метод сжатия LZMA) и rar
. Согласно данным автора программы от 2005 года, метод сжатия bzip2
уступает по эффективности сжатия на 10‑15 %[3] наилучшим методам, известным на тот момент (PPM)[4], но при этом в 2 раза быстрее при сжатии и в 6 раз быстрее при распаковке.
Описание алгоритма
Метод сжатия bzip2
работает следующим образом:
- несжатые данные делятся на блоки фиксированного размера;
- выполняется преобразование Барроуза — Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов;
- применяет преобразование MTF;
- используется кодирование Хаффмана.
Приблизительный размер блока можно выбрать при помощи аргументов командной строки («-1
» для 100 килобайт, «-2
» для 200 КБ, …, «-9
» для 900 КБ). Каждый блок сжимается независимо, сжатые блоки записываются последовательно друг за другом, в начале каждого используется 48-битная последовательность — магическое число 0x314159265359 (в кодировке ASCII при выравнивании на границу байта отображается как «1AY&SY»), то есть запись первых десятичных цифр числа π в формате BCD[5]. Конец файла помечается 48-битной константой 0x177245385090, представляющей собой корень из числа Пи. В начале файлов формата bzip2 используется следующий заголовок: двухбайтовая сигнатура «BZ», затем указание на метод энтропийного сжатия — «h» (Хаффман) и размер блока (десятичное число от 0 до 9).
За счет использования независимого сжатия отдельных блоков возможны реализации формата с параллельным сжатием или распаковкой (для распаковки может потребоваться индекс смещений для каждого блока)[6].
Использование
Примеры использования bzip2
.
# Команда для сжатия файла «file» bzip2 file # или bzip2 -z file # или bzip2 --compress file # Команда для распаковки файла «file.bz2» bzip2 -d file.bz2 # или bzip2 --decompress file.bz2 # или bunzip2 file.bz2 # bunzip2 - копия bzip2 или ссылка на bzip2
Аргументы командной строки bzip2
в основном такие же, как и у утилиты gzip
.
# Команда для распаковки архива tar, сжатого bzip2 bzip2 -cd file.tar.bz2 | tar -xvf - # или bzip2 --stdout --decompress file.tar.bz2 \ | tar --extract --verbose --file - # Команда для создания архива tar, сжатого bzip2 tar -cvf - files | bzip2 -9 > file.tar.bz2 # или tar --create --verbose --file - files \ | bzip2 -9 > file.tar.bz2
Версия GNU tar
поддерживает флаг «-j
» («--bzip2
»), который позволяет создавать и распаковывать файлы «tar.bz2» без использования перенаправлений ввода-вывода (англ. pipeline). Пример:
# Упаковка данных в архив tar и сжатие bzip2 при помощи GNU tar tar -cvjf file.tar.bz2 list_of_files # или tar --create --verbose --bzip2 --file file.tar.bz2 list_of_files # Распаковка архива tar, сжатого bzip2 при помощи GNU tar tar -xvjf file.tar.bz2 # или tar --extract --verbose --bzip2 --file file.tar.bz2
Современные версии GNU tar
могут автоматически определить метод сжатия данных, и поэтому флаг «-j
» («--bzip2
») можно не использовать. Пример:
tar -xvf file.tar.bz2 # или tar --extract --verbose --file file.tar.bz2
Кроме того, существует набор утилит для выполнения поиска, вывода, восстановления и сравнения данных в формате bzip2
:
bzcat
— распаковка данных и вывод на терминал;bzmore
,bzless
— распаковка данных и постраничный вывод на терминал;bzcmp
— распаковка двух файлов, сравнение содержимого и сообщение результата: «равно» или «не равно»;bzdiff
— распаковка двух файлов, сравнение содержимого и вывод различий;bzgrep
,bzegrep
,bzfgrep
— распаковка данных и поиск в распакованном;bzip2recover
— распаковка любых блоков, которые только можно распаковать.
Формат файла
bzip2 | |
---|---|
![]() | |
Сигнатура | BZh |
Разработчик | Джулиан Сюард |
Тип формата | Сжатие данных |
Открытый формат? | Да: Лицензия BSD |
Сайт | sourceware.org/bz… (англ.) |
Архив «.bz2
» содержит поток (англ. stream) сжатых данных. Слово «поток» употребляется, так как данные нельзя разделить логически и блоки данных сжимаются независимо друг от друга. Сжатые данные состоят из следующих полей:
- заголовок размером 4 байта;
- ноль или более блоков сжатых данных различного размера;
- маркер, обозначающий конец сжатых данных и контрольная сумма (CRC) размером 32 бита, вычисленная для всего потока;
- несколько неиспользуемых бит для дополнения размера потока до целого количества байт.
Название поля | Размер поля в битах | Описание |
---|---|---|
.magic | 16 | BZ — константа, сигнатура, магическое число. |
.version | 8 | Байт, кодирующий номер версии.
|
.hundred_k_blocksize | 8 | Размер блока несжатых данных в сотнях килобайт.
|
.compressed_magic | 48 | 0x314159265359 — константа, число π, записанное в двоично-десятичном коде (BCD). |
.crc | 32 | Контрольная сумма, рассчитанная для текущего блока. |
.randomised | 1 |
|
.origPtr | 24 | начальный указатель в массив BWT после преобразования |
.huffman_used_map | 16 | битовая маска диапазонов в 16 байт, «имеется»/«отсутствует» |
.huffman_used_bitmaps | 0..256 | битовая маска используемых символов, «имеется»/«отсутствует» (кратно 16) |
.huffman_groups | 3 | Число от 2 до 6, количество используемых таблиц Хаффмана. |
.selectors_used | 15 | Число, показывающее сколько раз выполнялась смена таблицы Хаффмана (каждые 50 байт). |
*.selector_list | 1..6 | битовые последовательности, дополненные нулевыми битами (0..62) для таблиц Хаффмана после MTF (*selectors_used) |
.start_huffman_length | 5 | 0..20 начальные битовые длины для дельт Хаффмана |
*.delta_bit_length | 1..40 |
{ 1=> уменьшить длину на 1; 0=> увеличить длину на 1} (*(symbols+2)*groups) |
.contents | 2..∞ | Поток данных, закодированный таблицами Хаффмана. Продолжается до конца блока. Максимальная длина равна 7 372 800 бит. |
.eos_magic | 48 | 0x177245385090 — константа, квадратный корень из числа π (sqrt(pi)) в двоично-десятичном коде (BCD). |
.crc | 32 | Контрольная сумма, рассчитанная для всего потока. |
.padding | 0..7 | Неиспользуемые биты (от 0 до 7). Назначение: увеличение размера архива до размера, кратного одному байту (8 битам) (выравнивание данных). |
Максимальный размер несжатого блока для классического формата равен 900 килобайтам. Если блок состоит из одного повторяющегося символа, после кодирования RLE блок займёт около 46 мегабайт (45 899 236 байт), а после выполнения всех операций размер файла .bz2
составит 46 байт. Если повторяющийся символ будет иметь код 251, размер файла .bz2
составит 40 байт, а коэффициент сжатия будет равен 1 147 480,9:1.
Примечания
- ↑ bzip2-1.0.8.tar.gz 2019-07-13 — 2019.
- ↑ bzip2 : Home (неопр.). Julian Seward. — «Why would I want to use it? [..] Because it's open-source (BSD-style license), and, as far as I know, patent-free.» Дата обращения: 27 сентября 2008. Архивировано из оригинала 15 февраля 2012 года.
- ↑ bzip2 and libbzip2 Архивная копия от 25 декабря 2006 на Wayback Machine, «It typically compresses files to within 10 % to 15 % of the best available techniques (the PPM family of statistical compressors)»
- ↑ На данный момент наиболее эффективно сжимают различные реализации метода PAQ. Однако, использование данного метода крайне затруднено по причине низкой производительности (сжатие требует больших временных затрат).
- ↑ Hakbeom Jang; Channoh Kim, Jae W. Lee.: Practical Speculative Parallelization of Variable-Length Decompression Algorithms (англ.). Конференция Languages, Compilers and Tools for Embedded Systems 2013 (June 20–21, 2013). — «The bzip2 file format defines a 48-bit pattern called magic header (0x314159265359), which signals the beginning of a new compressed block». Дата обращения: 3 июля 2015. Архивировано 28 января 2016 года.
- ↑ Dbzip2 - MediaWiki (неопр.). Дата обращения: 17 августа 2018. Архивировано 18 августа 2018 года.
Ссылки
- Официальный сайт bzip.org, Web Archive, копия от 2018-06-24 (англ.)
- Введение в bzip2 (англ.)