Почему максимальный размер блока bzip2 составляет 900 КБ?

Question

bzip2 (то есть эта программа Джулиана Сьюарда) перечисляет доступные размеры блоков от 100 до 900 тысяч:

 $ bzip2 --help
 bzip2, a block-sorting file compressor.  Version 1.0.6, 6-Sept-2010.

 usage: bzip2 [flags and input files in any order]

   -1 .. -9            set block size to 100k .. 900k

Это число соответствует hundred_k_blocksize значение записывается в заголовок сжатого файла.

Из документации требования к памяти следующие:

Compression:   400k + ( 8 x block size )

Decompression: 100k + ( 4 x block size ), or
               100k + ( 2.5 x block size )

В то время, когда была написана оригинальная программа (1996), я думаю, что 7,6 МБ (400 КБ + 8 * 900 КБ) могли бы быть огромным объемом памяти на компьютере, но для современных машин это ничто.

Мой вопрос состоит из двух частей:

1) Будет ли достигнуто лучшее сжатие при больших размерах блока? (Наивно я бы предположил да). Есть ли причина не использовать большие блоки? Как время процессора для сжатия масштабируется с размером блока?

2) Практически, есть ли какие-либо вилки кода bzip2 (или альтернативные реализации), которые допускают больший размер блока? Требует ли это значительного пересмотра исходного кода?

Формат файла кажется достаточно гибким, чтобы справиться с этим. Например... так как hundred_k_blocksize содержит 8-битный символ, который указывает размер блока, можно расширить таблицу ASCII, чтобы указать больший размер блока (например, ':' знак равно x3A => 1000k, ';' знак равно x3B => 1100k, '<' знак равно x3C => 1200k...)

Answer 1

Ваша интуиция о том, что больший размер блока должен приводить к более высокой степени сжатия, подтверждается компиляцией программ Мэттом Махони из его большого теста сжатия текста. Например, BWT-программа с открытым исходным кодом, BBB ( http://mattmahoney.net/dc/text.html), имеет степень сжатия ~40%, увеличиваясь с размера блока от 10^6 до 10^9. Между этими двумя значениями время сжатия удваивается. Теперь, когда программа "xz", в которой используется вариант LZ (называемый LZMA2), первоначально описанный автором 7zip Игорем Павловым, начинает обгонять bzip2 в качестве стратегии по умолчанию для сжатия исходного кода, стоит изучить возможность использования bzip2. размер блока, чтобы увидеть, может ли это быть жизнеспособной альтернативой. Кроме того, bzip2 избежал арифметического кодирования из-за патентных ограничений, срок действия которых истек. В сочетании с возможностью использования быстрых асимметричных систем счисления для энтропийного кодирования, разработанных Яреком Дудой, модернизированный bzip2 вполне может быть конкурентоспособным как по степени сжатия, так и по скорости до xz.