Открыть список
Как стать автором
Обновить

Комментарии 24

Собственно, вспоминая дискуссию по поводу официального 7zip под Линукс.
Вот именно описанное в статье — одна из причин почему "комбайны" типа 7zip или RAR лучше чем .tar.*z — "комбайны" знают как лучше сортировать при конкатенации

Если они работают в один проход, то они очевидно попадут в ту же историю.

А кому сегодня нужен строго 1 проход? Вы всё ещё пользуетесь магнитными лентами?

Всем нужен один проход, потому что это означает не только скорость сжатия, но и возможность сжимать потоки. Все любят делать что-то вроде:


gzip < input1 > output.gz
gzip < input2 >> output.gz
zcat < output.gz > output # текст из обоих файликов 

Особенно это полезно в применении сжатия в браузерах, когда на лету распаковывается и отображается содержимое ресурсов веб-странички.

Для однофайловых архивов это верно. Но вопрос-то был в том, кому же так нужен один проход в многофайловых?

По моему опыту, если xz жмёт поток, то он не может делать это многопоточно (-T <n>), а если файл — то запросто. Жать в много потоков — быстрее пропорционально кол-ву потоков.

А "комбайны" точно этим заморачиваются?


Современный tar, кстати, тоже может сам отвечать за сжатие. Собственно, в примерах команд из статьи xz вызывается не отдельно, а самим tar — опция J; можно вызвать gzip опцией z, и, возможно, еще что-нибудь. Так что ничего не мешает и ему сортировать "по-умному".

Заморачиваются — заморачиваются.
7-Zip поддерживает два типа сортировки, по названию файла или по типу содержимого.
Если размер словаря меньше общего размера файлов, сортировка по типу может обеспечить лучший коэффициент сжатия в ряде случаев.


RAR тоже сортирует, и ещё умеет находить одинаковые файлы, и дубликат вообще не паковать заменяя ссылкой.

Хм, и правда, спасибо. Википедия называет сжатие нескольких файлов в одном стриме термином solid compression, и явно пишет о поддержке в rar и 7z.

Ну и обратная сторона метали, что приходится распаковывать гигабайты с начала архива, чтобы достать маленький файлик из конца.

Ну в статье tar, а с tar+компрессор получается тот же solid, только ещё хуже, т.к. распаковать весь архив до конца надо даже для того, чтобы достать файл из начала

Я как-то из-за необходимости произвольного доступа к файлам в архиве мастерил поделку, которая сохраняла отдельные файлы в виде gz архива в tar, а потом ещё и индекс смещений строил по этому tar, чтоб не надо было ревинд делать. Это было на удивление легко, хоть и весьма любопытно.

Сразу про солид подумалось.
Возьмите 206 войн-и-миров и сожмите тем же раром, но в двух вариантах, как непрерывный архив и НЕ непрерывный.
«Совершенно случайно» 206 войн-и-миров (в utf-8) — это гигабайт.

Результаты сжатия 206-войнмиров-utf8-10%инфвосст-НЕсолид:
~240мб
Результаты сжатия 206-войнмиров-utf8-10%инфвосст-солид:
~1.5мб

Тривиальней результатов даже и не придумаешь.

п.с.: А теперь с доступом к этому всему разберитесь) Он разный.
п.п.с.: В каждый экземпляр войны-и-мира в самый конец добавлена строка EOF xxx, где xxx — номер книжки. Т.е. эти книжки разные и что бы понять что они разные — нужно проверить на сравнение всю книжку до конца.
п.п.п.с.: жалось раром, конечно же (без вариантов)
tar + gzip — это нормально, и в той статье собственно в комментах это и обсуждалось.
tar + zip — это странно, потому что zip сам умеет каталогизировать.

Поэтому у меня больше вопрос зачем вообще в данном случае, если используют не tar+gzip а tar+что-то, вместо это использовать сразу zip или другой архиватор со сжатием.
В результате сортировки по имени рядом оказываются файлы, мало отличающиеся друг от друга. Судя по всему, это весьма благоприятно сказывается на эффективности сжатия.

Жалко, что статья упускает, возможно, самое интересное — исследование того, почему именно так происходит. Попытался поискать объяснение сам, буду рад, если кто-то поправит:


В xz используется LZMA, реализующий сжатие со словарем на основе скользящего окна. Грубо говоря, подстроки исходного файла могут быть заменены на пару чисел "(оффсет от текущего положения; длина подстроки)". Величина этих чисел ограничена, собственно, размером окна — чем больше, тем больше потенциальных кандидатов для замены (и больше степень сжатия), но больше время работы алгоритма сжатия и требуемая ему память. Соответственно, для наибольшего сжатия выгодно, чтобы схожие данные находились в пределах размера окна друг от друга.

Разве по сути статьи на эффективности сжатия благоприятно сказывается сортировка по имени?
Мне казалось, что именно сортировка по дате дает возможность экономить место при сжатии.

Там дата создания — часть имени.

Ну все же здесь в первую очередь речь не о tar и его методах сортировок, а о алгоритме XZ. Довольно очевидно, что предварительно сортированные по содержимому данные удобнее для сжатия любым алгоритмом, т.к. он в целом основан на поиске одинаковых частей во входящем потоке и при небольшом буфере и работе в один проход получаем то, что получаем.


То, что сортировка по содержимому и сортировка по дате в данном случае совпадает это частный случай, хотя и любопытный.


Кстати, кто-нибудь шарит в этих алгоритмах? Есть ли не поточные, а много проходные архиваторы? Или хотя бы архиваторы двух стадийные: на первом проходе составляем карту повторений, на втором уже архивируем с учетом статистики.

Странно, что нет хотя бы примерного разъяснения алгоритмов из семейства, к которому относится XZ.


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

Именно поэтому, в нагруженном вебе, возникает такая, казалось бы, идиотская задача как сортировка полей JSON по алфавиту. JSON значительно лучше жмутся таким образом, особенно потоковыми архиваторами транспортного уровня типа brotli, gzip, на низких настройках.

А чем помогает сортировка полей json по алфавиту, как это увеличивает шанс нахождения повторяющихся фрагментов?

Не шанс нахождения, а шанс и значимость самого повтора. Если у вас в одном месте { x: 1, y: 2, z: 3}, а в соседнем {x: 1, z: 3, y: 2}, и таких кусков много, то общего очень мало (часть типа "x: 1, " слишком короткая, чтобы вместо неё вставить признак повтора). А теперь экстраполируйте то же самое на порции в сотни и тысячи байт...


Разумеется, аналогично бы подошёл любой другой метод обеспечения порядка, но по алфавиту — самый надёжный.


Более простой вариант этого обеспечивается тем, что все актуальные реализации JavaScript дают итерировать ключи объектов в порядке добавления (а также Python на это перешёл начиная с ~3.6, PyPy делает это даже для 2.7, и вообще постепенно становится общим местом), но этот подход не защищён от изменения порядка, если ключ полностью удалён и затем добавлен.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Информация

Дата основания
Местоположение
Россия
Сайт
flant.ru
Численность
101–200 человек
Дата регистрации
Представитель
Дмитрий Шурупов

Блог на Хабре