bzip2

bzip2

Оригинальный автор (ы)	Джулиан Сьюард
Разработчики)	Федерико Мена
изначальный выпуск	18 июля 1996 г . ; 24 года назад [1] ( 1996-07-18 )
Стабильный выпуск	1.0.8 / 13 июля 2019 г . ; 19 месяцев назад ( 2019-07-13 )
Репозиторий	https://gitlab.com/federicomenquintero/bzip2 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 ) и Deflate ( .zip и .gz ), но значительно медленнее. LZMA, как правило, более экономичен, чем bzip2, за счет еще меньшей скорости сжатия при гораздо более быстрой распаковке. ^[4]

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

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

Как и gzip, bzip2 - это только компрессор данных. Это не архиватор, такой как tar или 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 кБ. Для блочной сортировки создается (условная) матрица, в которой строка 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 не существует, хотя неофициальная спецификация была реконструирована из эталонной реализации. ^[8]

В качестве обзора .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 = контрольная сумма для этого блока.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 (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-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 - Информационный проект Linux (LINFO)
• bzip2 для Windows
• Графический bzip2 для Windows (WBZip2)
• MacBzip2 (для классической Mac OS ; в Mac OS X стандартный bzip2 доступен в командной строке)
• Доступны сравнение функций и тесты для различных типов параллельных реализаций bzip2
• 4 параллельных реализации bzip2 в новостном блоге о сжатии данных
• Оригинальный компрессор bzip - может быть ограничен патентами