stringtranslate.com

bzip2

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. [4] С июня 2021 года сопровождающим является Мика Снайдер. [5]

Выполнение

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 от патологических случаев. [6]

Преобразование Берроуза-Уилера — это обратимая блочная сортировка, лежащая в основе 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 не существует, хотя неофициальная спецификация была разработана на основе эталонной реализации. [7]

Вкратце, .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 . [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на основе - bzgrepпозволяет осуществлять прямой поиск по сжатому тексту без необходимости предварительной распаковки содержимого. [13]

Смотрите также

Рекомендации

  1. ^ bzip2/README, 18 июля 1996 г. (версия 0.15)
  2. ^ Сьюард, Джулиан. «bzip2 и libbzip2». исходное программное обеспечение.org .
  3. ^ "бз2". Документация разработчика Apple: унифицированные идентификаторы типов . Apple Inc.
  4. ^ "Статьи с тегом bzip2" . viruta.org .
  5. ^ «Экспериментальный репозиторий Bzip2 меняет поддержку - Блог Федерико» . viruta.org . Проверено 27 июля 2022 г.
  6. ^ «bzip2 и libbzip2, версия 1.0.8». исходное программное обеспечение.org .
  7. ^ «Спецификация формата BZIP2» (PDF) . Гитхаб . 17 марта 2022 г.
  8. ^ «[HADOOP-4012] Обеспечение поддержки разделения файлов, сжатых bzip2» . Фонд программного обеспечения Apache . 2009 . Проверено 14 октября 2015 г.
  9. ^ «7-zip против bzip2 против gzip» . Архивировано из оригинала 24 апреля 2016 года . Проверено 12 февраля 2019 г.
  10. ^ "Домашняя страница bzip2" . Архивировано из оригинала 4 июля 1998 года . Проверено 5 марта 2009 г.- раздел «Как это связано с вашим предыдущим предложением (bzip-0.21)?»
  11. ↑ Palaiologos (13 октября 2022 г.), kspalaiologos/bzip3 , получено 13 октября 2022 г.
  12. ^ "compressionratings.com" . www1.compressionratings.com .
  13. ^ «Команда bzgrep в Linux с примерами» . сайт die.net .

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