Арифметика потоковых архиваторов - 2
Jun. 6th, 2020 12:59 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dememaxИсходный пост 2008-го года: https://mpd.livejournal.com/5302.html или https://dememax.dreamwidth.org/4730.html
Отправная мысль проста (в исходном посте это выражено по-другому):
Производительность и эффективное использование ресурсов (память, процессор, использование всех ядер процессора, место на диске, и т.д., и т.п.) — нас не интересует вообще, исключительно факт сжатия очевидного повторения в исходном потоке.
Размер: в прошлый раз я брал файл 8'677'260 байт, в этот раз (всё ж таки 12 лет прошло!) - 94'883'920 байт (некий ELF 64-bit LSB shared object, x86-64, dynamically linked, stripped).
В результате: получилось определить первый пункт с новым файлом только с помощью zstd.
Теперь подробнее.
Объединение файлов: выполнено с помощью «tar (GNU tar) 1.32» командой:
Rar: установленный в системе «RAR 5.90 Copyright (c) 1993-2020 Alexander Roshal 26 Mar 2020» - хоть и выдаёт в хелпе опцию «md<n>[k,m,g] Dictionary size in KB, MB or GB», только не распознаёт её, пишет «ERROR: Unknown option: md10m». К автору не обращался, что за фигня — не хочу выяснять.
Остальные инструменты: «bzip2 version 1.0.6, 6-Sept-2010», «gzip 1.9», «zstd command line interface 64-bits v1.4.4».
rar: в зависимости от опции «m<0..5> Set compression level (0-store...3-default...5-maximal)»:
1: 43823050; 2: 40681104; 3: 40316157; 4: 40270861; 5: 40255324
bzip2: fast: 48144181; best: 44582638
gzip: fast: 51006034; best: 48020924
zstd: default: 44192751; long=31: 44132616
Промежуточный вывод: rar — лучший с 40'255'324, никто даже рядом не стоит.
Худший — gzip с 48'020'924.
rar: 80'438'911
bzip2: 89'178'197
gzip: 96'043'097
zstd: 44'139'807
Окончательный вывод: только один zstd смог обнаружить повторение файла, два файла он сжал лучше, чем bzip2 сжал один файл (на том этапе bzip2 был не самый худший!).
Разница между сжатым одним и сжатыми двумя файлами для zstd ничтожная при таких размерах: 44139807 - 44132616 = 7191 (меньше накладных расходов tar'а)!
Как заставить *zip* увидеть дублирование такого размера с таким расстоянием — не знаю, похоже, что никак.
Rar — как сказано выше, хоть и имеет соответствующую опцию, но не распознаёт её, и в результате суммарно сжал два файла по-отдельности.
Отправная мысль проста (в исходном посте это выражено по-другому):
- Архиватор должен найти повторяющиеся последовательности.
- А что, если они очень далеко?
- А что, если очень велики?
Производительность и эффективное использование ресурсов (память, процессор, использование всех ядер процессора, место на диске, и т.д., и т.п.) — нас не интересует вообще, исключительно факт сжатия очевидного повторения в исходном потоке.
Размер: в прошлый раз я брал файл 8'677'260 байт, в этот раз (всё ж таки 12 лет прошло!) - 94'883'920 байт (некий ELF 64-bit LSB shared object, x86-64, dynamically linked, stripped).
В результате: получилось определить первый пункт с новым файлом только с помощью zstd.
Теперь подробнее.
Объединение файлов: выполнено с помощью «tar (GNU tar) 1.32» командой:
> tar cf two.tar filename.ext the_same_file.extполученный размер - 189'777'920 байт, накладные расходы: 189777920 - 94883920*2 = 10080 байт, что не так уж и много, относительно исходного файла — чуть больше одной сотой процента, можно пренебречь.
Rar: установленный в системе «RAR 5.90 Copyright (c) 1993-2020 Alexander Roshal 26 Mar 2020» - хоть и выдаёт в хелпе опцию «md<n>[k,m,g] Dictionary size in KB, MB or GB», только не распознаёт её, пишет «ERROR: Unknown option: md10m». К автору не обращался, что за фигня — не хочу выяснять.
Остальные инструменты: «bzip2 version 1.0.6, 6-Sept-2010», «gzip 1.9», «zstd command line interface 64-bits v1.4.4».
Один файл
Если сжимать разными архиваторами один исходный файл, получаем:rar: в зависимости от опции «m<0..5> Set compression level (0-store...3-default...5-maximal)»:
1: 43823050; 2: 40681104; 3: 40316157; 4: 40270861; 5: 40255324
bzip2: fast: 48144181; best: 44582638
gzip: fast: 51006034; best: 48020924
zstd: default: 44192751; long=31: 44132616
Промежуточный вывод: rar — лучший с 40'255'324, никто даже рядом не стоит.
Худший — gzip с 48'020'924.
Два файла в одном
Даю только лучшие результаты. Для rar — опция «-m5», для bzip2 и gzip — опция «--best», для zstd — опция «--long=31».rar: 80'438'911
bzip2: 89'178'197
gzip: 96'043'097
zstd: 44'139'807
Окончательный вывод: только один zstd смог обнаружить повторение файла, два файла он сжал лучше, чем bzip2 сжал один файл (на том этапе bzip2 был не самый худший!).
Разница между сжатым одним и сжатыми двумя файлами для zstd ничтожная при таких размерах: 44139807 - 44132616 = 7191 (меньше накладных расходов tar'а)!
Как заставить *zip* увидеть дублирование такого размера с таким расстоянием — не знаю, похоже, что никак.
Rar — как сказано выше, хоть и имеет соответствующую опцию, но не распознаёт её, и в результате суммарно сжал два файла по-отдельности.
no subject
Date: 2020-06-06 02:47 am (UTC)Re: Интересный эксперимент.
Date: 2020-06-06 07:27 am (UTC)Вот, началось с того, что в далёком 2008-м, в Москве в гостях мне не поверили, что если два раза повторить на вход архиватору один и тот же файл - архиватор его не воспримет, будет каждый раз сжимать по-отдельности.
А такой сценарий - сплошь везде и рядом! Например, жмёте вы какой-то проект таром, потом - каким-то архиватором из перечисленных у меня. Проект, как правило, содержит одинаковые файлы (ну, или очень похожие), но в разных папках рядом. В результате не сожмёт дубликаты потоковый архив: слишком далеко или слишком большие повторения.
А чё! Места - как грязи! И технологии только ещё больше расслабляют! Пипл хавает! - как говорил один певец...
Re: Интересный эксперимент.
Date: 2020-06-11 10:35 am (UTC)tar само по себе не жмёт же.
Re: Интересный эксперимент.
Date: 2020-06-13 11:35 am (UTC)Что из исходного поста видно тоже.
Имелось в виду, не каким-нибудь архиватором, который сам может с многими файлами и папками работать, а сначала - таром, потом уже потоковым архиватором.
no subject
Date: 2020-06-07 03:09 pm (UTC)Re: never heard of zstd. Cool.
Date: 2020-06-07 04:48 pm (UTC)Well, completely agree, it's something new. In my previous post in 2008, I haven't mentioned this archiver, it appeared only in 2015 (my god, I was already in France) and presented in 2016, August.
I'm not a compression specialist or a compression algorithms historian, you can easily find all info on that product. I can say only that its good side of Facebook, and I personally hate Facebook as a social network for many reasons.
> How do they even do it? Is it literally a 50MB ring buffer?
Again, "я не настоящий сварщик". But it's common sense! If you are not a heptapod from Arrival film, you treat incoming data for lossless compression in the form of a sequence, a stream. Then you need to keep in mind what you already saw to use some well known algorithms like Run-length encoding, etc. All them operate with "windows" in input stream. That's all.
If you find the answer, please, tell us!
At the end, "for the knowledge of certain principles easily compensates the lack of knowledge of certain facts", I don't bother about data structures they use internally, but I do know that to find the duplicate of a long file in the sequence of two of them, the archiver should have enough distance and window size, and the man page of zstd gives me that possibility.