Bzip2 - Bzip2

bzip2

Оригинальный автор (ы)	Джулиан Сьюард
Разработчики)	Федерико Мена
изначальный выпуск	18 июля 1996 г.; 24 года назад (1996-07-18)[1]
Стабильный выпуск	1.0.8 / 13 июля 2019 г.; 16 месяцев назад (2019-07-13)
Репозиторий	https://sourceware.org/git/bzip2.git
Операционная система	Кроссплатформенность[который? ]
Тип	Сжатие данных
Лицензия	BSD-подобная лицензия[2]
Интернет сайт	исходное ПО.org/ bzip2/

bzip2 это бесплатно и с открытым исходным кодом файл программа сжатия который использует Алгоритм Барроуза-Уиллера. Он сжимает только отдельные файлы и не файловый архиватор. Он разработан Джулиан Сьюард и поддерживается Федерико Мена. Сьюард выпустил первый публичный выпуск bzip2 версии 0.15 в июле 1996 года. Стабильность и популярность компрессора росли в течение следующих нескольких лет, и Сьюард выпустил версию 1.0 в конце 2000 года.^{[не проверено в теле ]} После девятилетнего перерыва в обновлении проекта с 2010 г., 4 июня 2019 г. Федерико Мена принял на себя сопровождение проекта bzip2.^[3]

Эффективность сжатия

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

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

Производительность bzip2 асимметрична, так как распаковка выполняется относительно быстро. В связи с большим объемом процессорного времени, необходимого для сжатия, в 2003 году была создана модифицированная версия под названием pbzip2, которая поддерживала многопоточность, что дает почти линейное повышение скорости на многопроцессорных и многоядерных компьютерах.^[6] По состоянию на май 2010 г.^{[Обновить]}, эта функциональность не была включена в основной проект.

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

Стек сжатия

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

Преобразование Барроуза – Уиллера

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

Переход на передний план

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

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

Кодирование длин серий результата MTF

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

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

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

Кодирование Хаффмана

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

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

0: РУНА,

1: РУНБ,

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

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

Несколько таблиц Хаффмана

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

Унарное кодирование выбора таблицы Хаффмана

Если используется несколько таблиц Хаффмана, выбор каждой таблицы (пронумерованной от 0 до 5) осуществляется из списка последовательностью битов с нулевым завершением длиной от 1 до 6 бит. Выбор в МОГ список таблиц. Использование этой функции приводит к максимальному расширению около 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 байта). Напротив, ВЫПУСКАТЬ Алгоритм показал бы отсутствие символов, кодируя символы как имеющие нулевую длину в битах с кодированием длин серий и дополнительным кодированием Хаффмана.

Формат файла

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

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

.magic: 16 = подпись 'BZ' / магический номер. версия: 8 = 'h' для Bzip2 ('кодирование Хаффмана),' 0 'для Bzip1 (устарело) .hundred_k_blocksize: 8 =' 1 '..' 9 'размер блока 100 кБ-900 кБ (без сжатия) .compressed_magic: 48 = 0x314159265359 (BCD (pi)). crc: 32 = контрольная сумма для этого блока. рандомизировано: 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.^[9]

Реализации

В добавление к Джулиан Сьюард Исходная эталонная реализация, следующие программы поддерживают формат bzip2.

• 7-молния: Написано Игорь Павлов в C ++, набор 7-Zip содержит кодировщик / декодер bzip2, который распространяется бесплатно. 7-Zip поддерживает многопоточность.
• micro-bzip2: Версия автора Роб Лэндли разработан для уменьшенного размера скомпилированного кода и доступен под GNU LGPL.
• PBZIP2: Параллельно pthreads -основанная реализация в C ++ Джеффа Гилкриста (и Версия для Windows ).
• bzip2smp: Модификация libbzip2 который имеет SMP распараллеливание "взломан" Константина Исакова.
• smpbzip2: Еще один переход на параллельный bzip2, автор: Нильс Веренштейн.
• пифлат: ЧистыйPython автономный bzip2 и ВЫПУСКАТЬ (gzip ) декодер Пола Слэйдена. Вероятно, полезен для исследований и прототипирования, доступен под BSD /GPL /LGPL, или любой другой DFSG -совместимая лицензия.
• bz2: Модуль Python 3 для поддержки сжатия bzip2 (Стандартная библиотека Python).
• BZip Арно Буше: Реализация с использованием библиотеки C или оптимизированного кода ассемблера i386.
• lbzip2: Параллельно pthreads основанный на bzip2 / bunzip2 (компрессор / декомпрессор bzip2) фильтр для последовательного ввода / вывода доступа, автор Ласло Эрсек.
• mpibzip2: An MPI -поддерживаемая реализация, которая сжимает / распаковывает параллельно, Джеффом Гилкристом, доступная под лицензией BSD.
• Сжатие Apache Commons Проект Apache Commons Compress содержит Java-реализации компрессора и декомпрессора Bzip2.
• jbzip2: Java-реализация bzip2, доступная под Лицензия MIT
• DotNetZip: Включает реализацию bzip2 на C #, полученную из реализации Java в Apache Commons Compress. Включает в себя многопоточную библиотеку кодировщика / декодера .NET bzip2 и инструмент командной строки bzip2 в управляемом коде.
• DotNetCompression: Потоковая реализация bzip2 в управляемом C #, соответствующая API System.IO.Compression и включающая сборки для .NET Framework, .NET Compact Framework, Xamarin.iOS, Xamarin.Android, Xamarin.Mac, телефон с операционной системой Виндоус, Xbox 360, Silverlight, Мононуклеоз и как переносимая библиотека классов.

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

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

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

внешняя ссылка

• Команда bzip2 - Информационный проект Linux (LINFO)
• bzip2 для Windows
• Графический bzip2 для Windows (WBZip2)
• MacBzip2 (за Классическая Mac OS; под Mac OS X, стандартный bzip2 доступен в командной строке)
• Сравнение функций и тесты для различных видов параллельных реализаций bzip2 доступны
• 4 Параллельные реализации bzip2 в блоге новостей о сжатии данных
• Оригинальный компрессор bzip - может быть ограничено патентами