bzip2

bzip2
bzip2
	<img onError="this.style.display='none'" alt="Изображение логотипа" src="//xn--b1aeclack5b4j.su/save/png/wikipedia/commons/thumb/4/41/Bzip2-logo.svg/204px-Bzip2-logo.svg.png" decoding="async" width="204" height="80" data-file-width="244" data-file-height="96">
Расширение	.bz2
Сигнатура	BZh
Разработчик	Сюард, Джулиан
Последний выпуск	1.0.8 (13 июля 2019);
Тип формата	Сжатие данных
Открытый формат?	Да: Лицензия BSD
Сайт	sourceware.org/bz… (англ.)

bzip2
bzip2
Тип	Сжатие данных
Разработчик	Сюард, Джулиан
Написана на	Си
Операционная система	Кроссплатформенное ПО
Первый выпуск	18 июля 1996
Последняя версия	1.0.8 (13 июля 2019);
Читаемые форматы файлов	bzip2[d]
Создаваемые форматы файлов	bzip2[d]
Лицензия	Лицензия BSD
Сайт	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 — распаковка любых блоков, которые только можно распаковать.

Формат файлаПравить

Архив «.bz2» содержит поток (англ. stream) сжатых данных. Слово «поток» употребляется, так как данные нельзя разделить логически и блоки данных сжимаются независимо друг от друга. Сжатые данные состоят из следующих полей:

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

Название поля	Размер поля в битах	Описание
.magic	16	`BZ` — константа, сигнатура, магическое число.
.version	8	Байт, кодирующий номер версии. `0` Версия 1 (bzip1). Устарел, не используется. `h` Версия 2 (bzip2). «h» от англ. Huffman coding.
.hundred_k_blocksize	8	Размер блока несжатых данных в сотнях килобайт. `1` Одна сотня КБ (100 КБ). `2` Две сотни КБ (200 КБ). … И так далее `9` Девять сотен КБ (900 КБ).
.compressed_magic	48	`0x314159265359` — константа, число π, записанное в двоично-десятичном коде (BCD).
.crc	32	Контрольная сумма, рассчитанная для текущего блока.
.randomised	1	`0` нормальная `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	`0` следующий символ `1` изменить длину { 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 : 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 года.
↑ ¹ ² https://sourceware.org/pub/bzip2/
↑ 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 (англ.)

[bzip2-license-1] zip2 : 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 года.

[_39aeda0e5cf5053b-2] ¹ ² https://sourceware.org/pub/bzip2/

[3] zip2 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)»

[paqnote-4] На данный момент наиболее эффективно сжимают различные реализации метода PAQ. Однако, использование данного метода крайне затруднено по причине низкой производительности (сжатие требует больших временных затрат).

[5] 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 года.

[6] Dbzip2 - MediaWiki (неопр.). Дата обращения: 17 августа 2018. Архивировано 18 августа 2018 года.

[2]

[1]

[3]

[4]

[5]

[6]

bzip2

Расширение	`.bz2`
Сигнатура	`BZh`
Разработчик	Сюард, Джулиан
Последний выпуск	1.0.8 (13 июля 2019)^[2]
Тип формата	Сжатие данных
Открытый формат?	Да: Лицензия BSD
Сайт	sourceware.org/bz… (англ.)