Comments 24
Собственно, вспоминая дискуссию по поводу официального 7zip под Линукс.
Вот именно описанное в статье — одна из причин почему "комбайны" типа 7zip или RAR лучше чем .tar.*z — "комбайны" знают как лучше сортировать при конкатенации
Если они работают в один проход, то они очевидно попадут в ту же историю.
Всем нужен один проход, потому что это означает не только скорость сжатия, но и возможность сжимать потоки. Все любят делать что-то вроде:
gzip < input1 > output.gz
gzip < input2 >> output.gz
zcat < output.gz > output # текст из обоих файликов Особенно это полезно в применении сжатия в браузерах, когда на лету распаковывается и отображается содержимое ресурсов веб-странички.
А "комбайны" точно этим заморачиваются?
Современный tar, кстати, тоже может сам отвечать за сжатие. Собственно, в примерах команд из статьи xz вызывается не отдельно, а самим tar — опция J; можно вызвать gzip опцией z, и, возможно, еще что-нибудь. Так что ничего не мешает и ему сортировать "по-умному".
Заморачиваются — заморачиваются.
7-Zip поддерживает два типа сортировки, по названию файла или по типу содержимого.
Если размер словаря меньше общего размера файлов, сортировка по типу может обеспечить лучший коэффициент сжатия в ряде случаев.
RAR тоже сортирует, и ещё умеет находить одинаковые файлы, и дубликат вообще не паковать заменяя ссылкой.
Хм, и правда, спасибо. Википедия называет сжатие нескольких файлов в одном стриме термином solid compression, и явно пишет о поддержке в rar и 7z.
Возьмите 206 войн-и-миров и сожмите тем же раром, но в двух вариантах, как непрерывный архив и НЕ непрерывный.
«Совершенно случайно» 206 войн-и-миров (в utf-8) — это гигабайт.
Результаты сжатия 206-войнмиров-utf8-10%инфвосст-НЕсолид:
~240мб
Результаты сжатия 206-войнмиров-utf8-10%инфвосст-солид:
~1.5мб
Тривиальней результатов даже и не придумаешь.
п.с.: А теперь с доступом к этому всему разберитесь) Он разный.
п.п.с.: В каждый экземпляр войны-и-мира в самый конец добавлена строка EOF xxx, где xxx — номер книжки. Т.е. эти книжки разные и что бы понять что они разные — нужно проверить на сравнение всю книжку до конца.
п.п.п.с.: жалось раром, конечно же (без вариантов)
tar + zip — это странно, потому что zip сам умеет каталогизировать.
Поэтому у меня больше вопрос зачем вообще в данном случае, если используют не tar+gzip а tar+что-то, вместо это использовать сразу zip или другой архиватор со сжатием.
В результате сортировки по имени рядом оказываются файлы, мало отличающиеся друг от друга. Судя по всему, это весьма благоприятно сказывается на эффективности сжатия.
Жалко, что статья упускает, возможно, самое интересное — исследование того, почему именно так происходит. Попытался поискать объяснение сам, буду рад, если кто-то поправит:
В xz используется LZMA, реализующий сжатие со словарем на основе скользящего окна. Грубо говоря, подстроки исходного файла могут быть заменены на пару чисел "(оффсет от текущего положения; длина подстроки)". Величина этих чисел ограничена, собственно, размером окна — чем больше, тем больше потенциальных кандидатов для замены (и больше степень сжатия), но больше время работы алгоритма сжатия и требуемая ему память. Соответственно, для наибольшего сжатия выгодно, чтобы схожие данные находились в пределах размера окна друг от друга.
Ну все же здесь в первую очередь речь не о tar и его методах сортировок, а о алгоритме XZ. Довольно очевидно, что предварительно сортированные по содержимому данные удобнее для сжатия любым алгоритмом, т.к. он в целом основан на поиске одинаковых частей во входящем потоке и при небольшом буфере и работе в один проход получаем то, что получаем.
То, что сортировка по содержимому и сортировка по дате в данном случае совпадает это частный случай, хотя и любопытный.
Кстати, кто-нибудь шарит в этих алгоритмах? Есть ли не поточные, а много проходные архиваторы? Или хотя бы архиваторы двух стадийные: на первом проходе составляем карту повторений, на втором уже архивируем с учетом статистики.
Странно, что нет хотя бы примерного разъяснения алгоритмов из семейства, к которому относится XZ.
Секрет в том, что это сжатие со скользящим окном. То есть если в примере похожие файлы неотсортированы перед сжатием, или если файлы слишком большие, то алгоритм может и не заметить одинаковые битовые последовательности.
А чем помогает сортировка полей json по алфавиту, как это увеличивает шанс нахождения повторяющихся фрагментов?
Да, имено это.
Не шанс нахождения, а шанс и значимость самого повтора. Если у вас в одном месте { x: 1, y: 2, z: 3}, а в соседнем {x: 1, z: 3, y: 2}, и таких кусков много, то общего очень мало (часть типа "x: 1, " слишком короткая, чтобы вместо неё вставить признак повтора). А теперь экстраполируйте то же самое на порции в сотни и тысячи байт...
Разумеется, аналогично бы подошёл любой другой метод обеспечения порядка, но по алфавиту — самый надёжный.
Более простой вариант этого обеспечивается тем, что все актуальные реализации JavaScript дают итерировать ключи объектов в порядке добавления (а также Python на это перешёл начиная с ~3.6, PyPy делает это даже для 2.7, и вообще постепенно становится общим местом), но этот подход не защищён от изменения порядка, если ключ полностью удалён и затем добавлен.
Почему tar.xz-файлы, созданные с Python tar, оказались в 15 раз меньше, чем у macOS tar