bzip2
bzip2 — бесплатная свободная утилита командной строки с открытым исходным кодом для сжатия данных, реализация алгоритма Барроуза — Уилера.
| bzip2 | |||
|---|---|---|---|
 | |||
| Тип | Сжатие данных | ||
| Разработчик | Джулиан Сюард | ||
| Написана на | Си | ||
| Операционная система | Кроссплатформенное ПО | ||
| Первый выпуск | 18 июля 1996 | ||
| Последняя версия | |||
| Репозиторий | sourceware.org/git/bzip2… | ||
| |||
| |||
| Лицензия | Лицензия BSD[2] | ||
| Сайт | sourceware.org/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 года.