Bzip2
Вика bzip2 — бесплатная свободное программное обеспечение утилита командной строки открытым исходным кодом сжатия данных, реализация алгоритма Барроуза — Уилера.
Разработана и впервые опубликована Джулианом Сюардом в июле 1996 года (версия 0.15). Стабильность и популярность компрессора росли в течение нескольких лет, и версия 1.0 была опубликована в конце 2000 года.
Эффективность
В соответствии с традициями UNIX, bzip2 единовременно может выполнять только одну операцию: либо сжатие, либо распаковку и только для одного файла. При сжатии bzip2 добавляет к имени файла расширение «.bz2». Для упаковки нескольких файлов их сперва архивируют в один файл утилитой tar, а затем сжимают при помощи bzip2. Такие архивы обычно имеют расширение «.tar.bz2».
bzip2 сжимает большинство файлов эффективнее, но медленнее, чем более традиционные утилиты gzip или zip. В этом отношении он похож на другие современные алгоритмы сжатия.
bzip2 выполняет сжатие данных с существенной нагрузкой на CPU (что обусловлено его математическим аппаратом). bzip2 применяют, если нет ограничений на время сжатия и на нагрузку на CPU, например, для разовой упаковки большого объёма данных.
В некоторых случаях bzip2 уступает по эффективности сжатия архиваторам 7-Zip (метод сжатия LZMA) и rar. Согласно данным автора программы от 2005 года, метод сжатия bzip2 уступает по эффективности сжатия на 10‑15 %[1] наилучшим методам, известным на тот момент (PPM)[2], но при этом в 2 раза быстрее при сжатии и в 6 раз быстрее при распаковке.
Описание алгоритма
Метод сжатия bzip2 работает следующим образом:
- несжатые данные делятся на блоки фиксированного размера;
- выполняется преобразование Барроуза — Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов;
- применяет преобразование MTF;
- используется кодирование Хаффмана.
Приблизительный размер блока можно выбрать при помощи аргументов командной строки («-1» для 100 килобайт, «-2» для 200 КБ, …, «-9» для 900 КБ). Каждый блок сжимается независимо, сжатые блоки записываются последовательно друг за другом, в начале каждого используется 48-битная последовательность — магическое число 0x314159265359 (в кодировке ASCII при выравнивании на границу байта отображается как «1AY&SY»), то есть запись первых десятичных цифр числа π в формате BCD[3]. Конец файла помечается 48-битной константой 0x177245385090, представляющей собой корень из числа Пи.
Предшественник bzip2, программа bzip, вместо кодирования Хаффмана использовала арифметическое кодирование. Из‑за патентных ограничений от этого алгоритма отказались.
- ↑ bzip2 and libbzip2, «It typically compresses files to within 10 % to 15 % of the best available techniques (the PPM family of statistical compressors)»
- ↑ На данный момент наиболее эффективно сжимают различные реализации метода PAQ. Однако, использование данного метода крайне затруднено по причине низкой производительности (сжатие требует больших временных затрат).
- ↑
