bzip2 — это бесплатная программа сжатия файлов с открытым исходным кодом , которая использует алгоритм Барроуза–Уиллера . Она сжимает только отдельные файлы и не является архиватором файлов . Она использует отдельные внешние утилиты для таких задач, как обработка нескольких файлов, шифрование и разделение архивов.
bzip2 был первоначально выпущен в 1996 году Джулианом Сьюардом . Он сжимает большинство файлов эффективнее старых алгоритмов сжатия LZW и Deflate , но работает медленнее. bzip2 особенно эффективен для текстовых данных, а распаковка выполняется относительно быстро. Алгоритм использует несколько уровней методов сжатия, таких как кодирование длин серий (RLE), преобразование Барроуза-Уиллера (BWT), преобразование перехода вперед (MTF) и кодирование Хаффмана . bzip2 сжимает данные блоками размером от 100 до 900 КБ и использует преобразование Барроуза-Уиллера для преобразования часто повторяющихся последовательностей символов в строки одинаковых букв. Затем применяются преобразование перехода вперед и кодирование Хаффмана. Производительность сжатия асимметрична, при этом распаковка выполняется быстрее, чем сжатие.
С момента первоначального выпуска алгоритм сменил несколько разработчиков, а с июня 2021 года им стал Мика Снайдер. В алгоритм были внесены некоторые изменения, например pbzip2, который использует многопоточность для повышения скорости сжатия на многопроцессорных и многоядерных компьютерах.
bzip2 подходит для использования в приложениях для обработки больших данных с кластерными вычислительными фреймворками, такими как Hadoop и Apache Spark , поскольку сжатый блок можно распаковать без необходимости обработки предыдущих блоков.
Сьюард выпустил первый публичный релиз bzip2 версии 0.15 в июле 1996 года. Стабильность и популярность компрессора росли в течение следующих нескольких лет, и в конце 2000 года Сьюард выпустил версию 1.0. [ не проверено в тексте ] После девятилетнего перерыва в обновлениях проекта с 2010 года, 4 июня 2019 года Федерико Мена принял на себя обязанности по поддержке проекта bzip2. [4] С июня 2021 года ответственным за поддержку является Мика Снайдер. [5]
bzip2 использует несколько уровней методов сжатия, наложенных друг на друга, которые выполняются в следующем порядке во время сжатия и в обратном порядке во время распаковки:
Любая последовательность из 4–255 последовательных повторяющихся символов заменяется первыми 4 символами и длиной повтора от 0 до 251. Таким образом, последовательность AAAAAAABBBBCCCDзаменяется на AAAA\3BBBB\0CCCD, где \3и \0представляют значения байтов 3 и 0 соответственно. Серии символов всегда преобразуются после 4 последовательных символов, даже если длина серии установлена равной нулю, чтобы сохранить обратимость преобразования.
В худшем случае это может вызвать расширение на 1,25, а в лучшем случае — сокращение до <0,02. Хотя спецификация теоретически позволяет кодировать серии длиной 256–259, эталонный кодер не даст такого результата.
Автор bzip2 заявил, что этап RLE был исторической ошибкой и был предназначен только для защиты оригинальной реализации BWT от патологических случаев. [6]
Преобразование Барроуза–Уиллера — это обратимая блочная сортировка, которая лежит в основе bzip2. Блок полностью автономен, при этом входные и выходные буферы остаются того же размера — в bzip2 рабочий предел для этого этапа составляет 900 кБ. Для блочной сортировки создается (условная) матрица, в которой строка i содержит весь буфер, повернутым так, чтобы начать с i -го символа. После поворота строки матрицы сортируются в алфавитном (числовом) порядке. 24-битный указатель сохраняется, отмечая начальную позицию , когда блок не преобразован. На практике нет необходимости строить полную матрицу; вместо этого сортировка выполняется с использованием указателей для каждой позиции в буфере. Выходной буфер — это последний столбец матрицы; он содержит весь буфер, но переупорядочен так, что он, вероятно, будет содержать большие серии одинаковых символов.
Преобразование перемещения вперед снова не изменяет размер обрабатываемого блока. Каждый из символов, используемых в документе, помещается в массив. Когда символ обрабатывается, он заменяется на свое местоположение (индекс) в массиве, и этот символ перетасовывается в начало массива. Эффект заключается в том, что немедленно повторяющиеся символы заменяются нулевыми символами (длинные серии любого произвольного символа, таким образом, становятся сериями нулевых символов), в то время как другие символы переназначаются в соответствии с их локальной частотой.
Многие «естественные» данные содержат идентичные символы, которые повторяются в ограниченном диапазоне (текст — хороший пример). Поскольку преобразование MTF присваивает низкие значения символам, которые часто повторяются, это приводит к потоку данных, содержащему много символов в низком целочисленном диапазоне, многие из которых идентичны (различные повторяющиеся входные символы могут фактически соответствовать одному и тому же выходному символу). Такие данные могут быть очень эффективно закодированы любым устаревшим методом сжатия.
Длинные строки нулей в выходных данных преобразования перемещения вперед (которые возникают из повторяющихся символов в выходных данных BWT) заменяются последовательностью двух специальных кодов, RUNA и RUNB, которые представляют длину серии как двоичное число. Фактические нули никогда не кодируются в выходных данных; одинокий ноль становится RUNA. (Этот шаг фактически выполняется одновременно с 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.
Несколько таблиц Хаффмана одинакового размера могут использоваться с блоком, если выигрыш от их использования больше, чем стоимость включения дополнительной таблицы. Может присутствовать не менее 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 не существует, хотя неофициальная спецификация была создана на основе эталонной реализации. [7]
В качестве обзора, .bz2поток состоит из 4-байтового заголовка, за которым следует ноль или более сжатых блоков, за которыми сразу следует маркер конца потока, содержащий 32-битный CRC для всего обработанного потока открытого текста. Сжатые блоки выровнены по битам, и заполнение не происходит.
.magic:16 = подпись/магическое число «BZ».version:8 = 'h' для Bzip2 (кодирование Хаффмана), '0' для Bzip1 (устарело).hundred_k_blocksize:8 = '1'..'9' размер блока 100 кБ-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=>уменьшить длину; 0=>увеличить длину } (*(символы+2)*группы).contents:2..∞ = поток данных, закодированный по методу Хаффмана, до конца блока (макс. 7372800 бит).eos_magic:48 = 0x177245385090 (BCD sqrt(пи)).crc:32 = контрольная сумма для всего потока.padding:0..7 = выровнять по целому байтуИз-за сжатия RLE на первом этапе (см. выше) максимальная длина открытого текста, которую может содержать один блок bzip2 размером 900 кБ, составляет около 46 МБ (45 899 236 байт). Это может произойти, если весь открытый текст состоит полностью из повторяющихся значений (результирующий .bz2файл в этом случае имеет длину 46 байт). Еще меньший файл в 40 байт может быть получен при использовании входных данных, содержащих только значения 251, что соответствует очевидному коэффициенту сжатия 1147480,9:1.
Сжатый блок в bzip2 может быть распакован без необходимости обработки более ранних блоков. Это означает, что файлы bzip2 могут распаковываться параллельно, что делает его хорошим форматом для использования в приложениях больших данных с кластерными вычислительными фреймворками, такими как Hadoop и Apache Spark . [8]
bzip2 сжимает большинство файлов более эффективно, чем старые алгоритмы сжатия LZW ( .Z ) и Deflate ( .zip и .gz ), но работает значительно медленнее. LZMA , как правило, более эффективен с точки зрения пространства, чем bzip2, за счет еще более медленной скорости сжатия, при этом имеет более быструю распаковку. [9]
bzip2 сжимает данные в блоки размером от 100 до 900 КБ и использует преобразование Барроуза–Уиллера для преобразования часто повторяющихся последовательностей символов в строки одинаковых букв. Затем он применяет преобразование перемещения вперед и кодирование Хаффмана . Предок bzip2 bzip использовал арифметическое кодирование вместо Хаффмана. Изменение было сделано из-за патентного ограничения на программное обеспечение. [10] bzip3, [11] современный компрессор, имеющий общее происхождение и набор алгоритмов с bzip2, переключился обратно на арифметическое кодирование.
Производительность bzip2 асимметрична, поскольку распаковка происходит относительно быстро. В связи с длительным временем, необходимым для сжатия, в 2003 году была создана модифицированная версия под названием pbzip2, которая использовала многопоточность для кодирования файла в несколько частей, что давало почти линейное ускорение на многопроцессорных и многоядерных компьютерах. [12] По состоянию на май 2010 года [обновлять]эта функциональность не была включена в основной проект.
Как и gzip , bzip2 — это всего лишь компрессор данных. Это не архиватор, как tar или ZIP; формат файла bzip2 не поддерживает хранение содержимого нескольких файлов в одном сжатом файле, а сама программа не имеет средств для нескольких файлов, шифрования или разделения архива. В традиции UNIX архивирование может быть выполнено отдельной программой, создающей архив, который затем сжимается с помощью bzip2, а распаковка может быть выполнена с помощью bzip2, распаковывающего сжатый файл архива, и отдельной программы, распаковывающей его. Некоторые архиваторы имеют встроенную поддержку сжатия и распаковки, так что нет необходимости использовать программу bzip2 для сжатия или распаковки архива. GnuPG также имеет встроенную поддержку сжатия и распаковки bzip2.
Инструмент grepна основе .png bzgrepпозволяет осуществлять прямой поиск по сжатому тексту без необходимости предварительной распаковки содержимого. [13]
.svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}