Войти
 | |
| Автор (ы) | Джулиан Сьюард |
|---|---|
| Разработчик (и) | Федерико Мена |
| Первый выпуск | 18 июля 1996 г.; 24 года назад (1996-07-18) |
| Стабильный выпуск | 1.0.8 / 13 июля 2019 г.; 15 месяцев назад (13.07.2019) |
| Репозиторий | https://sourceware.org/git/bzip2.git |
| Операционная система | Кросс-платформенный |
| Тип | Сжатие данных |
| Лицензия | BSD-подобная лицензия |
| Веб-сайт | исходное ПО.org / bzip2 / |
| Расширение имени файла | .bz2 |
|---|---|
| Тип Интернет-носителя | application / x-bzip2 |
| Код типа | Bzp2 |
| Универсальный идентификатор типа (UTI) | public.archive.bzip2 |
| Магический номер | BZh |
| Разработано | Джулиан Сьюард |
| Тип формата | Сжатие данных |
| Открытый формат ? | Да |
bzip2 - это бесплатный файл с открытым исходным кодом программа сжатия, использующая алгоритм Барроуза – Уиллера. Он сжимает только отдельные файлы и не является файловым архиватором . Он разработан Джулианом Сьюардом и поддерживается Федерико Мена. Сьюард выпустил первый общедоступный выпуск bzip2 версии 0.15 в июле 1996 года. Стабильность и популярность компрессора выросли в течение следующих нескольких лет, и Сьюард выпустил версию 1.0 в конце 2000 года. После девятилетнего перерыва в обновлении проекта с 2010 года, 4 июня 2019 г. Федерико Мена принял на себя сопровождение проекта bzip2.
bzip2 сжимает большинство файлов более эффективно, чем старые алгоритмы сжатия LZW (.Z ) и Deflate (.zip и .gz ), но значительно медленнее. LZMA обычно более экономичен, чем bzip2, за счет еще меньшей скорости сжатия и гораздо более быстрой декомпрессии.
bzip2 сжимает данные в блоках размером от 100 до 900 kB и использует преобразование Барроуза – Уиллера для преобразования часто повторяющихся последовательностей символов в строки идентичных букв. Затем он применяет преобразование перемещения вперед и кодирование Хаффмана. Предок bzip2 bzip использовал арифметическое кодирование вместо Хаффмана. Изменение было внесено из-за ограничения патента на программное обеспечение.
bzip2 работает асимметрично, так как распаковка происходит относительно быстро. В связи с тем, что для сжатия требуется большое процессорное время, в 2003 году была создана модифицированная версия под названием pbzip2, которая поддерживала многопоточность, обеспечивая почти линейное повышение скорости на многопроцессорных и многоядерных компьютерах. По состоянию на май 2010 года эта функция не была включена в основной проект.
Как и gzip, bzip2 - это только компрессор данных. Это не архиватор, такой как tar или ZIP; сама программа не имеет средств для множественных файлов, шифрования или разделения архивов, но, в традиции UNIX, вместо этого полагается на отдельные внешние утилиты, такие как tar и GnuPG для этих задач.
Bzip2 использует несколько уровней методов сжатия, накладываемых друг на друга, которые выполняются в следующем порядке во время сжатия и обратном порядке во время распаковки:
Любая последовательность от 4 до 255 последовательных повторяющихся символов заменяется первыми 4 символами и длиной повтора от 0 до 251. Таким образом, последовательность AAAAAAABBBBCCCDзаменяется на AAAA \ 3BBBB \ 0CCCD, где \ 3и \ 0представляют байтовые значения 3 и 0 соответственно. Ряды символов всегда преобразуются после 4 последовательных символов, даже если длина серии установлена на ноль, чтобы преобразование оставалось обратимым.
В худшем случае это может вызвать расширение 1,25, а в лучшем случае уменьшение до <0.02. While the specification theoretically allows for runs of length 256–259 to be encoded, the reference encoder will not produce such output.
Автор bzip2 заявил, что шаг RLE был исторической ошибкой и был предназначено только для защиты оригинальной реализации BWT от патологических случаев.
Это обратимая блочная сортировка, которая лежит в основе 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, поскольку он может кодировать произвольно длинные целые числа (на практике это обычно ограничивается размером блока, поэтому этот этап не кодирует серию более 900000 байт). Длина серии кодируется следующим образом: присвоение значений разряда 1 первому биту, 2 второму, 4 третьему и т. Д. В последовательности, умножение каждого значения разряда в месте RUNB на 2 и сложение всех итоговые разрядные значения (для значений RUNA и RUNB) вместе. Это похоже на двуъективное исчисление по основанию 2 . Таким образом, последовательность RUNA, RUNBдает значение (1 + 2 × 2) = 5. В качестве более сложного примера:
RUNA RUNB RUNA RUNA RUNB (ABAAB) 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 не существует, хотя неофициальная спецификация была реконструирована на основе эталонной реализации.
В качестве обзора .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 =>normal, 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 на первом этапе (см. выше) максимальная длина открытого текста, равная 900 Блок bzip2 kB может содержать около 46 МБ (45 899 236 байт). Это может произойти, если весь открытый текст полностью состоит из повторяющихся значений (результирующий файл .bz2в этом случае имеет длину 46 байтов). Еще меньший размер файла в 40 байт может быть получен при использовании ввода, содержащего целые значения 251, кажущийся коэффициент сжатия 1147480,9: 1.
Сжатые блоки в bzip2 можно независимо распаковать, без необходимости обрабатывать более ранние блоки. Это означает, что файлы bzip2 можно распаковывать параллельно, что делает их хорошим форматом для использования в приложениях больших данных с кластерными вычислительными средами, такими как Hadoop и Apache Spark.
В дополнение к исходной эталонной реализации Джулиана Сьюарда следующие программы поддерживают формат bzip2.
libbzip2, имеющая SMP распараллеливание "взломано" Константином Исаковым.
Портал бесплатного программного обеспечения с открытым исходным кодом 