bzip2 - это бесплатная программа сжатия файлов с открытым исходным кодом, в которой используется алгоритм Берроуза – Уиллера . Он сжимает только отдельные файлы и не является файловым архиватором . Он разработан Джулианом Сьюардом и поддерживается Федерико Мена . Сьюард сделал первый публичный релиз bzip2, версия 0,15, в июле 1996 года стабильность компрессора и популярность росли в течение следующих нескольких лет, и Сьюард выпустил версию 1.0 в конце 2000 года [ не проверен в теле ] После девятилетнего перерыва обновления для проекта с 2010 года, 4 июня 2019 года Федерико Мена принял на себя сопровождение проекта bzip2. [3]
Автор (ы) оригинала | Джулиан Сьюард |
---|---|
Разработчики) | Федерико Мена |
Первый выпуск | 18 июля 1996 г . [1] |
Стабильный выпуск | 1.0.8 / 13 июля 2019 г . |
Репозиторий | https://gitlab.com/federicomenquintero/bzip2 https://sourceware.org/git/bzip2.git |
Операционная система | Кросс-платформенный [ какой? ] |
Тип | Сжатие данных |
Лицензия | BSD-подобная лицензия [2] |
Веб-сайт | исходное ПО |
Расширение имени файла | .bz2 |
---|---|
Тип интернет-СМИ | application/x-bzip2 |
Типовой код | Bzp2 |
Единый идентификатор типа (UTI) | public.archive.bzip2 |
Магическое число | BZh |
Разработано | Джулиан Сьюард |
Тип формата | Сжатие данных |
Открытый формат ? | да |
Эффективность сжатия
bzip2 сжимает большинство файлов более эффективно, чем старые алгоритмы сжатия LZW ( .Z ) и Deflate ( .zip и .gz ), но значительно медленнее. LZMA обычно более экономичен, чем bzip2, за счет еще более низкой скорости сжатия и гораздо более быстрой декомпрессии. [4]
bzip2 сжимает данные в блоки размером от 100 до 900 КБ и использует преобразование Барроуза – Уиллера для преобразования часто повторяющихся последовательностей символов в строки из идентичных букв. Затем он применяет преобразование «движение вперед» и кодирование Хаффмана . Предок bzip2 bzip использовал арифметическое кодирование вместо кода Хаффмана. Изменение было внесено из-за ограничения патента на программное обеспечение . [5]
Производительность bzip2 асимметрична, поскольку распаковка выполняется относительно быстро. В связи с большим объемом процессорного времени, необходимого для сжатия, в 2003 году была создана модифицированная версия под названием pbzip2, которая поддерживала многопоточность , обеспечивая почти линейное повышение скорости на многопроцессорных и многоядерных компьютерах. [6] По состоянию на май 2010 г.[Обновить], эта функциональность не была включена в основной проект.
Как и gzip, bzip2 - это только компрессор данных. Это не архиватор, такой как tar или ZIP; сама программа не имеет средств для множественных файлов, шифрования или разделения архивов, но, согласно традиции UNIX , вместо этого полагается на отдельные внешние утилиты, такие как tar и GnuPG для этих задач.
Инструмент на grep
основе -base bzgrep
позволяет осуществлять прямой поиск по сжатому тексту без необходимости предварительно распаковывать содержимое. [7]
Стек сжатия
Bzip2 использует несколько уровней методов сжатия, наложенных друг на друга, которые выполняются в следующем порядке во время сжатия и обратном порядке во время распаковки:
- Кодирование длин серий (RLE) исходных данных.
- Преобразование Барроуза – Уиллера (BWT) или блочная сортировка.
- Преобразование перемещения вперед (MTF).
- Кодирование длин серий (RLE) результата MTF.
- Кодирование Хаффмана .
- Выбор между несколькими таблицами Хаффмана.
- Унарное кодирование по основанию 1 для выбора таблицы Хаффмана.
- Дельта-кодирование (Δ) длин битов кода Хаффмана.
- Редкий битовый массив, показывающий, какие символы используются.
Кодирование исходной длины прогона
Любая последовательность от 4 до 255 последовательных повторяющихся символов заменяется первыми 4 символами и длиной повтора от 0 до 251. Таким образом, последовательность AAAAAAABBBBCCCD
заменяется на AAAA\3BBBB\0CCCD
, где \3
и \0
представляют значения байтов 3 и 0 соответственно. Ряды символов всегда преобразуются после 4 последовательных символов, даже если длина серии установлена на ноль, чтобы преобразование оставалось обратимым.
В худшем случае это может вызвать расширение 1,25, а в лучшем случае уменьшение до <0,02. Хотя спецификация теоретически допускает кодирование серий длиной 256–259, эталонный кодировщик не будет производить такой вывод.
Автор bzip2 заявил, что этап RLE был исторической ошибкой и был предназначен только для защиты исходной реализации BWT от патологических случаев. [8]
Преобразование Барроуза – Уиллера
Это обратимая блочная сортировка, которая лежит в основе bzip2. Блок полностью самодостаточен, с буферами ввода и вывода того же размера - в bzip2 рабочий предел для этого этапа составляет 900 кБ. Для блочной сортировки создается (условная) матрица, в которой строка i содержит весь буфер, повернутый, чтобы начать с i -го символа. После поворота строки матрицы сортируются в алфавитном (числовом) порядке. Сохраняется 24-битный указатель, обозначающий начальную позицию, когда блок не преобразован. На практике нет необходимости строить полную матрицу; скорее, сортировка выполняется с использованием указателей для каждой позиции в буфере. Буфер вывода - это последний столбец матрицы; он содержит весь буфер, но переупорядочен так, чтобы он мог содержать большие серии одинаковых символов.
Переход на передний план
Опять же, это преобразование не изменяет размер обрабатываемого блока. Каждый из символов, используемых в документе, помещается в массив. Когда символ обрабатывается, он заменяется его положением (индексом) в массиве, и этот символ перемещается в начало массива. Эффект заключается в том, что немедленно повторяющиеся символы заменяются нулевыми символами (длинные серии любого произвольного символа, таким образом, становятся сериями нулевых символов), в то время как другие символы переназначаются в соответствии с их локальной частотой.
Многие «естественные» данные содержат идентичные символы, которые повторяются в ограниченном диапазоне (хороший пример - текст). Поскольку преобразование MTF присваивает низкие значения символам, которые часто повторяются, это приводит к потоку данных, содержащему множество символов в диапазоне низких целых чисел, многие из которых идентичны (разные повторяющиеся входные символы могут фактически отображаться на один и тот же выходной символ). Такие данные могут быть очень эффективно закодированы любым устаревшим методом сжатия.
Кодирование длин серий результата 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 не существует, хотя неофициальная спецификация была реконструирована из эталонной реализации. [9]
Для обзора .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 (pi))..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 . [10]
Реализации
В дополнение к исходной эталонной реализации Джулиана Сьюарда следующие программы поддерживают формат bzip2.
- 7-Zip : Написанный Игорем Павловым на C ++ , пакет 7-Zip содержит свободно лицензируемый кодировщик / декодер bzip2. 7-Zip поддерживает многопоточность.
- micro-bzip2 : версия Роба Лэндли, разработанная для уменьшенного размера скомпилированного кода и доступная под лицензией GNU LGPL .
- PBZIP2 : реализация на C ++ на основе параллельных потоков pthreads Джеффом Гилкристом (и версией для Windows ).
- bzip2smp : Модификация, в
libbzip2
которой SMP- распараллеливание "взломано" Константином Исаковым. - smpbzip2 : Еще один переход к параллельному bzip2, автор - Нильс Веренштейн.
- pyflate : автономный декодер bzip2 и DEFLATE ( gzip ) на чистом Python от Пола Слэдена. Вероятно, полезен для исследований и создания прототипов, доступен по BSD / GPL / LGPL или любой другой DFSG- совместимой лицензии.
- bz2 : модуль Python 3 для поддержки сжатия bzip2 (стандартная библиотека Python).
- BZip Арно Буше : реализация с использованием библиотеки C или оптимизированного кода ассемблера i386.
- lbzip2 : Фильтр bzip2 / bunzip2 (компрессор / распаковщик bzip2) на основе параллельных потоков pthreads для последовательного доступа к вводу / выводу, автор Ласло Эрсек.
- mpibzip2 : Реализация с поддержкой MPI, которая сжимает / распаковывает параллельно, Джефф Гилкрист, доступная по лицензии в стиле BSD.
- Apache Commons Compress Проект 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 , Windows Phone , Xbox 360 , Silverlight , Mono и как переносимая библиотека классов.
Смотрите также
- Сравнение форматов архивов
- Сравнение файловых архиваторов
- Список форматов архивов
- Список файловых архиваторов
- Список команд Unix
- rzip
Рекомендации
- ^ bzip2 / README , 18 июля 1996 г. (версия 0.15)
- ^ "bzip2: Home" . Джулиан Сьюард . Проверено 21 июля 2019 .
Зачем мне это использовать? [..] Потому что это открытый исходный код (лицензия в стиле BSD) и, насколько мне известно, без патентов.
- ^ "Статьи с тегом" bzip2 " " " . People.gnome.org .
- ^ "7-zip vs bzip2 vs gzip" . Архивировано из оригинального 24 апреля 2016 года . Проверено 12 февраля 2019 .
- ^ "Домашняя страница bzip2" . Архивировано из оригинала 4 июля 1998 года . Проверено 5 марта 2009 года . - раздел «Как это соотносится с вашим предыдущим предложением (bzip-0.21)?»
- ^ "compressratings.com" . ww1.compressionratings.com .
- ^ «Команда bzgrep в Linux с примерами» . GeeksforGeeks . 4 января 2019.
- ^ «bzip2 и libbzip2, версия 1.0.8» . sourceware.org .
- ^ «Спецификация формата BZIP2» (PDF) .
- ^ «[HADOOP-4012] Обеспечение поддержки разделения для сжатых файлов bzip2 - ASF JIRA» . Фонд программного обеспечения Apache . 2009 . Проверено 14 октября 2015 года .
Внешние ссылки
- Команда bzip2 - от Информационного проекта Linux (LINFO)
- bzip2 для Windows
- Графический bzip2 для Windows (WBZip2)
- MacBzip2 (для классической Mac OS ; в Mac OS X стандартный bzip2 доступен в командной строке)
- Доступны сравнение функций и тесты для различных типов параллельных реализаций bzip2
- 4 параллельных реализации bzip2, заархивированных 18 октября 2006 г. на Wayback Machine в блоге новостей о сжатии данных
- Оригинальный компрессор bzip - может быть ограничен патентами