bzip2: Алгоритм и особенности сжатия файлов

Введение

Программное обеспечение для сжатия файлов

bzip2 — это бесплатная программа для сжатия файлов с открытым исходным кодом, использующая алгоритм Burrows–Wheeler. Она сжимает только отдельные файлы и не является архиватором. Для таких задач, как обработка нескольких файлов, шифрование и разделение архивов, она полагается на отдельные внешние утилиты. bzip2 была впервые выпущена в 1996 году Джулианом Сьюардом. Она сжимает большинство файлов эффективнее, чем более старые алгоритмы сжатия LZW и Deflate, но работает медленнее. bzip2 особенно эффективна для текстовых данных, а распаковка выполняется относительно быстро. Алгоритм использует несколько уровней методов сжатия, таких как кодирование длин серий (RLE), преобразование Burrows–Wheeler (BWT), перемещение в начало (MTF) и кодирование Хаффмана. bzip2 сжимает данные блоками размером от 100 до 900 кБ и использует преобразование Burrows–Wheeler для преобразования часто встречающихся последовательностей символов в строки из одинаковых букв. Затем применяются перемещение в начало и кодирование Хаффмана. Производительность сжатия асимметрична: распаковка происходит быстрее, чем сжатие. С момента первоначального выпуска алгоритм поддерживался разными разработчиками, а с июня 2021 года его поддерживает Мика Снайдер. Были внесены некоторые изменения в алгоритм, например, pbzip2, который использует многопоточность для повышения скорости сжатия на многопроцессорных и многоядерных компьютерах. bzip2 подходит для использования в приложениях для работы с большими данными и в средах кластерных вычислений, таких как Hadoop и Apache Spark, поскольку сжатый блок можно распаковать, не обрабатывая предыдущие блоки.

История

Сьюард сделал первый публичный релиз bzip2, версия 0.15, в июле 1996 года. Стабильность и популярность компрессора росли в течение следующих нескольких лет, и Сьюард выпустил версию 1.0 в конце 2000 года. После девятилетнего перерыва в обновлениях проекта, начавшегося в 2010 году, 4 июня 2019 года Федерико Мена принял на себя поддержку проекта bzip2. С июня 2021 года поддержку проекта осуществляет Мика Снайдер.

Эффективность

bzip2 сжимает большинство файлов эффективнее, чем более старые алгоритмы LZW (.Z) и Deflate (.zip и gz), но работает значительно медленнее. LZMA обычно обеспечивает лучшую степень сжатия, чем bzip2, ценой еще более низкой скорости сжатия, при этом распаковка происходит значительно быстрее. bzip2 сжимает данные блоками размером от 100 до 900 кБ и использует преобразование Бёрроуза — Уилера для преобразования часто встречающихся последовательностей символов в строки из одинаковых букв. Затем применяется преобразование "перемещение в начало" и кодирование Хаффмана. Предшественник bzip2, bzip, использовал арифметическое кодирование вместо кодирования Хаффмана. Этот переход был сделан из-за ограничений, связанных с патентными правами на программное обеспечение. bzip3, современный компрессор, имеющий общие корни и набор алгоритмов с bzip2, вернулся к использованию арифметического кодирования. Производительность bzip2 асимметрична, поскольку распаковка происходит относительно быстро. В 2003 году была создана модифицированная версия под названием pbzip2, которая использовала многопоточность для кодирования файла на несколько частей, обеспечивая почти линейный прирост скорости на многопроцессорных и многоядерных компьютерах. По состоянию на 2010 год эта функция не была включена в основной проект. Как и gzip, bzip2 является только программой для сжатия данных. Это не архиватор, такой как tar или ZIP; формат файла bzip2 не поддерживает хранение содержимого нескольких файлов в одном сжатом файле, и сама программа не предоставляет средств для работы с несколькими файлами, шифрования или разделения архивов. В соответствии с традициями UNIX, архивирование может выполняться отдельной программой, создающей архив, который затем сжимается с помощью bzip2, а для разархивации bzip2 распаковывает сжатый архивный файл, а затем отдельная программа его декомпрессирует. Некоторые архиваторы имеют встроенную поддержку сжатия и декомпрессии, поэтому нет необходимости использовать программу bzip2 для сжатия или декомпрессии архива. GnuPG также имеет встроенную поддержку сжатия и декомпрессии bzip2. Инструмент bzgrep, основанный на grep, позволяет напрямую искать текст в сжатых файлах без предварительной распаковки содержимого.

bzip2 compresses most files more effectively than the older LZW (. Z) and Deflate (. zip and gz) compression algorithms, but is considerably slower. LZMA is generally more space efficient than bzip2 at the expense of even slower compression speed, while having much faster decompression. bzip2 compresses data in blocks of size between 100 and 900 kB and uses the Burrows–Wheeler transform to convert frequently recurring character sequences into strings of identical letters. It then applies move to front transform and Huffman coding. bzip2's ancestor bzip used arithmetic coding instead of Huffman. The change was made because of a software patent restriction. bzip3, a modern compressor that shares common ancestry and set of algorithms with bzip2, switched back to arithmetic coding. bzip2 performance is asymmetric, as decompression is relatively fast. Motivated by the long time required for compression, a modified version was created in 2003 called pbzip2 that used multi threading to encode the file in multiple chunks, giving almost linear speedup on multi CPU and multi core computers. as of 2010, this functionality has not been incorporated into the main project. Like gzip, bzip2 is only a data compressor. It is not an archiver like tar or ZIP; the bzip2 file format does not support storing the contents of multiple files in a single compressed file, and the program itself has no facilities for multiple files, encryption or archive splitting. In the UNIX tradition, archiving could be done by a separate program producing an archive which is then compressed with bzip2, and un archiving could be done by bzip2 uncompressing the compressed archive file and a separate program decompressing it. Some archivers have built in support for compression and decompression, so that it is not necessary to use the bzip2 program to compress or decompress the archive. GnuPG also has built in support for bzip2 compression and decompression. The grep based bzgrep tool allows directly searching through compressed text without needing to uncompress the contents first.