bzip2

«Bzip» перенаправляется сюда. Чтобы узнать о домене белка, см. Домен bZIP .

bzip2

Оригинальный автор(ы)	Джулиан Сьюард
Разработчики)	Марк Вилаард, Федерико Мена , Мика Снайдер
Начальная версия	18 июля 1996 г ( 18 июля 1996 )
Стабильная версия	1.0.8 / 13 июля 2019 г ( 13.07.2019 )
Репозиторий	https://gitlab.com/bzip2/bzip2/
Операционная система	Кросс-платформенный
Тип	Сжатие данных
Лицензия	Модифицированная лицензия zlib
Веб-сайт	исходное программное обеспечение .org /bzip2 /

bzip2

Расширение имени файла	.bz2
Тип интернет-СМИ	application/x-bzip2
Введите код	Bzp2
Единый идентификатор типа (UTI)	public.bzip2-архив
Магическое число	BZh
Разработан	Джулиан Сьюард
Тип формата	Сжатие данных
Открытый формат ?	Да

bzip2 — с открытым исходным кодом файлов бесплатная программа сжатия , использующая алгоритм Берроуза-Уиллера . Он сжимает только отдельные файлы и не является файловым архиватором . Он использует отдельные внешние утилиты для таких задач, как обработка нескольких файлов, шифрование и разделение архивов.

bzip2 был первоначально выпущен в 1996 году Джулианом Сьюардом . Он сжимает большинство файлов более эффективно, чем старые LZW и Deflate, алгоритмы сжатия но работает медленнее. bzip2 особенно эффективен для текстовых данных, а распаковка происходит относительно быстро. Алгоритм использует несколько уровней методов сжатия, таких как кодирование по длине серии (RLE), преобразование Берроуза-Уиллера (BWT), преобразование движения вперед (MTF) и кодирование Хаффмана . bzip2 сжимает данные в блоки размером от 100 до 900 КБ и использует преобразование Берроуза-Уиллера для преобразования часто повторяющихся последовательностей символов в строки одинаковых букв. Затем применяются преобразование движения вперед и кодирование Хаффмана. Производительность сжатия асимметрична: распаковка происходит быстрее, чем сжатие.

Алгоритм прошел несколько сопровождающих с момента его первого выпуска, при этом Мика Снайдер был сопровождающим с июня 2021 года. В алгоритм были внесены некоторые модификации, такие как pbzip2, который использует многопоточность для повышения скорости сжатия на многопроцессорных и многопроцессорных системах. -ядерные компьютеры.

bzip2 подходит для использования в больших данных приложениях для обработки кластерных вычислений с такими средами , как Hadoop и Apache Spark , поскольку сжатый блок можно распаковать без необходимости обработки более ранних блоков.

История

Сьюард выпустил первый публичный выпуск bzip2 версии 0.15 в июле 1996 года. Стабильность и популярность компрессора росли в течение следующих нескольких лет, и Сьюард выпустил версию 1.0 в конце 2000 года. После девятилетнего перерыва в обновлении проекта с 2010 года 4 июня 2019 года Федерико Мена принял на себя поддержку проекта bzip2. С июня 2021 года сопровождающим является Мика Снайдер.

Реализация

bzip2 использует несколько слоев методов сжатия, наложенных друг на друга, которые выполняются в следующем порядке во время сжатия и в обратном порядке во время распаковки:

1. Кодирование длин серий (RLE) исходных данных.
2. Преобразование Берроуза – Уиллера (BWT) или сортировка блоков.
3. Преобразование «Перемещение вперед» (MTF).
4. Кодирование длины серии (RLE) результата MTF.
5. Кодирование Хаффмана .
6. Выбор между несколькими таблицами Хаффмана.
7. Унарная кодировка по основанию 1 для выбора таблицы Хаффмана.
8. Дельта-кодирование (Δ) битовых длин кода Хаффмана.
9. Разреженный битовый массив , показывающий, какие символы используются.

Любая последовательность из 4–255 последовательных повторяющихся символов заменяется первыми 4 символами и длиной повтора от 0 до 251. Таким образом, последовательность AAAAAAABBBBCCCD заменяется на AAAA\3BBBB\0CCCD, где \3 и \0представляют значения байтов 3 и 0 соответственно. Серии символов всегда преобразуются после 4 последовательных символов, даже если длина серии установлена ​​равной нулю, чтобы преобразование было обратимым.

В худшем случае это может вызвать расширение до 1,25, а в лучшем — снижение до <0,02. Хотя спецификация теоретически допускает кодирование серий длиной 256–259, эталонный кодер не будет выдавать такой вывод.

Автор bzip2 заявил, что шаг RLE был исторической ошибкой и был предназначен только для защиты исходной реализации BWT от патологических случаев.

Преобразование Берроуза-Уилера — это обратимая блочная сортировка, лежащая в основе bzip2. Блок полностью автономен, входной и выходной буферы остаются одинакового размера — в bzip2 рабочий предел для этого этапа составляет 900 КБ. Для сортировки блоков создается (условная) матрица, в которой строка i содержит весь буфер, повернутый, начиная с i -го символа. После вращения строки матрицы сортируются в алфавитном (числовом) порядке. Сохраняется 24-битный указатель, обозначающий начальную позицию , когда блок не преобразован. На практике нет необходимости строить полную матрицу; скорее, сортировка выполняется с использованием указателей для каждой позиции в буфере. Выходной буфер — это последний столбец матрицы; он содержит весь буфер, но переупорядочен так, что он может содержать большие серии идентичных символов.

Преобразование «перемещение вперед» снова не меняет размер обрабатываемого блока. Каждый из символов, используемых в документе, помещается в массив. Когда символ обрабатывается, он заменяется своим местоположением (индексом) в массиве, и этот символ перемещается в начало массива. В результате сразу повторяющиеся символы заменяются нулевыми символами (таким образом, длинные серии любого произвольного символа становятся сериями нулевых символов), в то время как другие символы переназначаются в соответствии с их локальной частотой.

Многие «естественные» данные содержат идентичные символы, которые повторяются в ограниченном диапазоне (хорошим примером является текст). Поскольку преобразование MTF присваивает низкие значения символам, которые часто появляются повторно, это приводит к тому, что поток данных содержит множество символов в диапазоне младших целых чисел, многие из которых являются идентичными (разные повторяющиеся входные символы могут фактически сопоставляться с одним и тем же выходным символом). Такие данные могут быть очень эффективно закодированы любым устаревшим методом сжатия.

Длинные строки нулей на выходе преобразования «перемещение вперед» (которые происходят из повторяющихся символов на выходе BWT) заменяются последовательностью двух специальных кодов, RUNA и RUNB, которые представляют длину серии как двоичное число. Фактические нули никогда не кодируются в выходных данных; одинокий ноль становится РУНА. (Фактически этот шаг выполняется одновременно с MTF; всякий раз, когда MTF выдает ноль, он вместо этого увеличивает счетчик для последующего кодирования с помощью RUNA и RUNB.)

Последовательность 0, 0, 0, 0, 0, 1 будет представлен как RUNA, RUNB, 1; RUNA, RUNBпредставляет значение 5, как описано ниже. Код длины серии завершается при достижении другого нормального символа. Этот процесс RLE более гибок, чем начальный шаг RLE, поскольку он способен кодировать целые числа произвольной длины (на практике это обычно ограничивается размером блока, так что на этом шаге не кодируется серия размером более 900 000 байт ). . Длина серии кодируется следующим образом: присваивая значения позиций 1 первому биту, 2 — второму, 4 — третьему и т. д. в последовательности, умножьте каждое значение позиции в позиции RUNB на 2 и сложите все результирующие разряды (как для значений RUNA, так и для значений RUNB) вместе. Это похоже на биективную нумерацию по основанию 2 . Таким образом, последовательность RUNA, RUNB приводит к значению (1 + 2 × 2) = 5. В качестве более сложного примера:

РУНА РУНБ РУНА РУНА РУНБ (АБААБ)
    1 2 4 8 16
    1 4 4 8 32 = 49
 

Этот процесс заменяет символы фиксированной длины в диапазоне 0–258 кодами переменной длины в зависимости от частоты использования. Более часто используемые коды оказываются короче (2–3 бита), тогда как редким кодам может быть выделено до 20 бит. Коды выбираются тщательно, чтобы ни одну последовательность битов нельзя было спутать с другим кодом.

Код конца потока особенно интересен. Если в несжатых данных используются n разных байтов (символов), то код Хаффмана будет состоять из двух кодов RLE (RUNA и RUNB), n - 1 кодов символов и одного кода конца потока. Благодаря объединенному результату кодирования MTF и RLE на предыдущих двух шагах никогда не возникает необходимости явно ссылаться на первый символ в таблице MTF (в обычном MTF он был бы нулевым), сохраняя таким образом один символ для конца. маркер потока (и объясняет, почему только n в дереве Хаффмана закодировано - 1 символов). В крайнем случае, когда в несжатых данных используется только один символ, в дереве Хаффмана вообще не будет кодов символов, а весь блок будет состоять из RUNA и RUNB (неявно повторяющих одиночный байт) и конца -маркер потока со значением 2.

0: РЕЧЬ,

1: РУНБ,

2–257: значения байтов 0–255,

258: конец потока, завершение обработки (может быть всего 2).

Несколько таблиц Хаффмана одинакового размера можно использовать с блоком, если выгода от их использования превышает затраты на включение дополнительной таблицы. Может присутствовать от 2 до 6 таблиц, причем наиболее подходящая таблица выбирается повторно перед обработкой каждых 50 символов. Преимущество этого метода состоит в том, что он имеет очень отзывчивую динамику Хаффмана без необходимости постоянно предоставлять новые таблицы, как это требуется в DEFLATE . Кодирование длин серий на предыдущем шаге предназначено для обработки кодов, обратная вероятность использования которых выше, чем у самого короткого используемого кода Хаффмана.

Если используется несколько таблиц Хаффмана, выбор каждой таблицы (с номерами от 0 до 5) осуществляется из списка с помощью бита с нулевым завершением, длина которого составляет от 1 до 6 бит. Выбор осуществляется в MTF списке таблиц . Использование этой функции приводит к максимальному расширению около 1,015, но обычно меньше. Это расширение, вероятно, будет сильно омрачено преимуществом выбора более подходящих таблиц Хаффмана, а общий случай продолжения использования той же таблицы Хаффмана представляется в виде одного бита. По сути, это крайняя форма дерева Хаффмана, а не унарное кодирование, где каждый код имеет половину вероятности предыдущего кода.

Разрядность кода Хаффмана необходима для восстановления каждой из используемых канонических таблиц Хаффмана . Длина каждого бита сохраняется как закодированная разница с длиной бита предыдущего кода. Нулевой бит (0) означает, что предыдущая длина бита должна быть дублирована для текущего кода, тогда как один бит (1) означает, что следующий бит должен быть прочитан, а длина бита увеличена или уменьшена на основе этого значения. В обычном случае на каждый символ в таблице используется один бит, а в худшем случае — при переходе от длины 1 к длине 20 — потребуется примерно 37 бит. В результате более раннего кодирования MTF длина кода начиналась с 2–3 битов (очень часто используемые коды) и постепенно увеличивалась, а это означает, что дельта-формат довольно эффективен и требует около 300 бит (38 байт) на полную таблицу Хаффмана. .

Растровое изображение используется, чтобы показать, какие символы используются внутри блока и должны быть включены в деревья Хаффмана. Двоичные данные, скорее всего, будут использовать все 256 символов, представленных байтом, тогда как текстовые данные могут использовать только небольшое подмножество доступных значений, возможно, охватывающее диапазон ASCII от 32 до 126. Хранение 256 нулевых битов было бы неэффективно, если бы они по большей части не использовались. Используется разреженный . метод: 256 символов делятся на 16 диапазонов, и только если символы используются внутри этого блока, включается 16-битный массив Наличие каждого из этих 16 диапазонов обозначается дополнительным 16-битным битовым массивом спереди. Всего растровое изображение использует от 32 до 272 бит памяти (4–34 байта). Напротив, алгоритм DEFLATE покажет отсутствие символов, кодируя символы как имеющие нулевую битовую длину с кодированием длины серии и дополнительным кодированием Хаффмана.

Формат файла

Официальной спецификации для bzip2 не существует, хотя неофициальная спецификация была разработана на основе эталонной реализации.

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

.magic:16 = подпись/магический номер 'BZ'
 .version:8 = 'h' для Bzip2 (кодирование 'H'uffman), '0' для Bzip1 (устарело)
 .hundred_k_blocksize:8 = '1'..'9' размер блока 100–900 КБ (несжатый)

 .compressed_magic:48 = 0x314159265359 (BCD (пи))
 .crc:32 = контрольная сумма для этого блока
 .randomized: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=>уменьшить длину;  0=>приращение длины } (*(символы+2)*группы)
 .contents:2..∞ = поток данных в кодировке Хаффмана до конца блока (макс. 7372800 бит)

 .eos_magic:48 = 0x177245385090 (BCD sqrt(pi))
 .crc:32 = контрольная сумма для всего потока
 .padding:0..7 = выравнивание по целому байту
 

Из-за сжатия RLE первого этапа (см. выше) максимальная длина открытого текста, который может содержать один блок bzip2 размером 900 КБ, составляет около 46 МБ (45 899 236 байт). Это может произойти, если весь открытый текст полностью состоит из повторяющихся значений (результирующий .bz2файл в данном случае имеет длину 46 байт). Файл еще меньшего размера (40 байт) можно получить, если использовать входные данные, полностью содержащие значения 251, с кажущейся степенью сжатия 1147480,9:1.

Сжатый блок в bzip2 можно распаковать без необходимости обработки предыдущих блоков. Это означает, что файлы bzip2 можно распаковывать параллельно, что делает его хорошим форматом для использования в приложениях для обработки больших данных с такими платформами кластерных вычислений, как Hadoop и Apache Spark .

Эффективность

bzip2 сжимает большинство файлов более эффективно, чем более старые алгоритмы сжатия LZW ( .Z ) и Deflate ( .zip и .gz ), но работает значительно медленнее. LZMA , как правило, более экономичен, чем bzip2, за счет еще более медленной скорости сжатия и гораздо более быстрой распаковки.

bzip2 сжимает данные в блоки размером от 100 до 900 КБ и использует преобразование Берроуза-Уиллера для преобразования часто повторяющихся последовательностей символов в строки одинаковых букв. Затем он применяет преобразование движения вперед и кодирование Хаффмана . Предок bzip2, bzip, использовал арифметическое кодирование вместо метода Хаффмана. Изменение было внесено из-за ограничения патента на программное обеспечение . бзип3, современный компрессор, имеющий общее происхождение и набор алгоритмов с bzip2, снова переключенный на арифметическое кодирование.

Производительность bzip2 асимметрична, поскольку распаковка происходит относительно быстро. Из-за длительного времени, необходимого для сжатия, в 2003 году была создана модифицированная версия под названием pbzip2, которая использовала многопоточность для кодирования файла несколькими частями, что давало почти линейное ускорение на многопроцессорных и многоядерных компьютерах. По состоянию на май 2010 г. , эта функциональность не была включена в основной проект.

Как и gzip , bzip2 является всего лишь компрессором данных. Это не архиватор типа tar или ZIP; Формат файла bzip2 не поддерживает хранение содержимого нескольких файлов в одном сжатом файле, а сама программа не имеет средств для хранения нескольких файлов, шифрования или разделения архивов. В традициях UNIX архивирование может выполняться отдельной программой, создающей архив, который затем сжимается с помощью bzip2, а разархивирование может выполняться с помощью bzip2, распаковывающего сжатый файл архива, и отдельной программы, распаковывающей его. Некоторые архиваторы имеют встроенную поддержку сжатия и распаковки, поэтому нет необходимости использовать программу bzip2 для сжатия или распаковки архива. GnuPG также имеет встроенную поддержку сжатия и распаковки bzip2.

The grep-основанный на bzgrep Инструмент позволяет осуществлять прямой поиск по сжатому тексту без необходимости предварительного распаковывания содержимого.

См. также

• Сравнение форматов архивов
• Сравнение файловых архиваторов
• Список форматов архивов
• Список файловых архиваторов
• Rzip

Внешние ссылки

• Команда bzip2 — Информационный проект Linux (LINFO)
• bzip2 для Windows
• Графический bzip2 для Windows (WBZip2)
• MacBzip2 (для классической Mac OS ; в Mac OS X стандартный bzip2 доступен в командной строке)
• Доступны сравнение функций и тесты для различных типов параллельных реализаций bzip2.
• 4 параллельные реализации bzip2. Архивировано 18 октября 2006 г. на Wayback Machine в блоге новостей о сжатии данных.
• Оригинальный компрессор bzip — может быть ограничен патентами.