Как способность сжимать поток влияет на алгоритм сжатия?

Question

Я недавно сделал резервную копию моего скоро истекающего домашнего каталога университета, отправив его в виде потока tar и сжав на моем конце: ssh user@host "tar cf - my_dir/" | bzip2 > uni_backup.tar.bz2.

Это заставило меня задуматься: я знаю только основы того, как работает сжатие, но я бы предположил, что эта способность сжимать поток данных приведет к ухудшению сжатия, поскольку алгоритм должен закончить обработку блока данных в одной точке. , запишите это в выходной поток и перейдите к следующему блоку.

Это так? Или эти программы просто читают много данных в память, сжимают это, записывают, а затем делают это снова? Или есть какие-нибудь хитрые уловки, используемые в этих «потоковых компрессорах»? Я вижу, что справочные страницы bzip2 и xz говорят об использовании памяти, а man bzip2 также намекает на тот факт, что при сортировке данных мало что теряется быть сжатым в блоки:

Большие размеры блоков дают быстро уменьшающиеся предельные прибыли. Большая часть сжатия происходит из первых двух или трех сотен тысяч блоков, что стоит учитывать при использовании bzip2 на небольших машинах. Также важно понимать, что требование к памяти для декомпрессии задается во время сжатия путем выбора размера блока.

Мне все равно хотелось бы услышать, если используются другие приемы, или о том, где я могу прочитать об этом подробнее.

Answer 1

Этот вопрос больше относится к обработке буфера, чем к алгоритму сжатия, хотя об этом тоже можно сказать немного.

Некоторые алгоритмы сжатия по своей сути основаны на блоках, что означает, что им абсолютно необходимо работать с блокамиконкретный размер.Это ситуация bzip2, размер блока которого выбирается благодаря переключателю уровня от 100 до 900 КБ.Таким образом, если вы передаете данные в него, он будет ждать заполнения блока и начнет сжимать этот блок, когда он заполнится (в качестве альтернативы, для последнего блока он будет работать с любым размером, который он получит).

Некоторые другие алгоритмы сжатия могут обрабатывать потоки, что означает, что они могут непрерывно сжимать новые данные, используя более старые данные, хранящиеся в буфере памяти.Это можно сделать с помощью алгоритмов, основанных на «скользящих окнах», и, как правило, zlib может этого добиться.

Теперь даже компрессоры с «скользящими окнами» могут, тем не менее, выбрать разделение входных данных на блоки либо для упрощения управления буфером,или для развития многопоточных возможностей, таких как pigz.