[devel] rpm: rsyncable deflate vs LZMA

[Alexey Tourbin]

Я уже собирался включить LZMA сжатие для rpm payload (после некоторого
внутреннего тестирования), но Александр Боковой напомнил нам про
rsyncable патч для deflate сжатия (для gzip и zlib).

Поскольку deflate и LZMA алгоритмы по сути похожи (сжатие в два этапа --
замена подстрок по "словарю", точнее, поиск совпадающих подстрок в
пределах скользящего окна; и частотное кодирование "букв", когда
наиболее часто встречающиеся буквы кодируются ниболее короткими битовыми
последовательностями), то для LZMA в принципе возможен такой формат
"контейнера", в котором идут rsyncable сжатые блоки (как в zlib).

К сожалению, я убедился, что LZMA в текущем виде не может быть
использован (или ограниченно модифицирован) таким образом, чтобы
получить rsyncable сжатые данные.  "Старый" формат контейнера
LZMA_Alone вообще не предусматривание разбиение на блоки.  Спецификация
нового формата носит alpha status, разработчики пишут: "Do not trust
the files created by the alpha versions, unless you can uncompress
the files with the stable 4.32.x."  Кроме того, семантика "разбиения на
блоки" в новом LZMA формате отличается от семантики разбиения на блоки
в deflate.  В общем, если использовать новый формат LZMA контейнера
с целью добиться rsyncablity, то это плохо повлияет на сжатие.

Поэтому есть два варианта, как быть дальше.
1) Включить LZMA_Alone сжатие, забив на rsyncability.
2) Вернуться к идее rsyncable deflate.

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

Подробности про формат контейнера.  Чтобы эффективно реализовать
rsyncability для алгоритмов типа deflate/LZMA, должны быть выполнены
следующие условия: 1) небольшой размер окна; 2) продолжение/сохранение
прежнего словаря при записи сжатого блока (то есть "восстановление"
первого этапа кодирования при начале следующего сжатого блока);
3) повторная инициализация частотного кодирования "букв" (то есть
"ресет" второго этапа кодирования при начале следующего сжатого блока).

Семантика deflate блоков как раз состоит в том, что при переходе к
новому блоку словарь остаётся прежним (возможны backreferences в
предыдущие сжатые блоки в пределах окна), а частотное кодирование
инициализируется заново (в начале каждого сжатого блока идёт Huffman
tree).  Восстановление на первом этапе несколько ухудшает rsyncability,
то есть сжатые блоки могут различаться из-за несовпадающих backreferences;
но за счёт небольшого размера окна (см. требование №1) после
"провафленных" таким образом двух-трёх блоков backreferences будут
совпадать, и все последующие блоки будут rsyncable.  Зато восстановление
на первом этапе очень хорошо влияет на коэффициент сжатия.

А вот ресет частотного кодирования на втором этапе просто жизненно
неоходим для rsyncability, т.к. частотное кодирование определяет
бинарное представление сжатых данных (если частотная модель хоть
чуть-чуть отличается, то получается полностью несовпадающее побитовое
представление).

Более частый ресет частотного кодирования (из-за rsyncable patch)
отрицательно влияет на коэффициент сжатия, но это влияние огранчивается
где-то 1%.

В новом формате контейнера LZMA при начале нового блока ресетится
как словарь, так и частотное кодирование букв.  Из-за ресета словаря
коэффициент сжатия заметно падает.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 197 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20080529/0cf1efc9/attachment-0002.bin>