Rzip

lrzip
Оригинальный автор(ы)	Кон Коливас, Питер Хайман, Эндрю Триджелл
Первоначальный выпуск	январь 2008 г .; 16 лет назад
Стабильная версия	0,651 / 9 марта 2022 г .; 2 года назад
Написано в	C, С++ (libzpaq)
Операционная система	Unix-подобный
Размер	246 КБ (архив исходного кода, сжатый gzip)
Веб-сайт	github .с /ckolivas /lrzip

Rzip
Оригинальный автор(ы)	Эндрю Триджелл
Стабильная версия	2.1 / 14 февраля 2006 г .; 18 лет назад
Написано в	С
Операционная система	Unix-подобный
Размер	46 КБ (архив исходного кода, сжатый gzip)
Веб-сайт	Rzip .самба .org

rzip — это крупномасштабная сжатия данных компьютерная программа , разработанная на основе первоначального сопоставления строк в стиле LZ77 в окне словаря размером 900 МБ с последующим bzip2 на основе преобразованием Берроуза-Уиллера и энтропийным кодированием ( Хаффман ) на выходных фрагментах размером 900 КБ.

Алгоритм сжатия

rzip работает в два этапа. Первый этап находит и кодирует во входном файле большие фрагменты дублированных данных на потенциально очень больших расстояниях (900 МБ). Второй этап использует стандартный алгоритм сжатия ( bzip2 ) для сжатия выходных данных первого этапа.

В наши дни довольно часто возникает необходимость сжимать файлы, содержащие избыточные данные на больших расстояниях. Например, при сжатии набора домашних каталогов несколько пользователей могут иметь копии одного и того же файла или очень похожих файлов. Также часто бывает один файл, содержащий большие дублированные фрагменты на больших расстояниях, например файлы PDF , содержащие повторяющиеся копии одного и того же изображения. Большинство программ сжатия не смогут воспользоваться этой избыточностью и, таким образом, могут достичь гораздо более низкой степени сжатия, чем может достичь rzip.

Промежуточный интерфейс между двумя этапами состоит из потока данных, выровненного по байтам, состоящего из двух команд: литерала («добавить») с длиной и данных:

 тип:8 = 0 => литерал/добавить диапазон счетчика байтов количество: 16 = 1..65535 data:8..∞ = вставляемые литеральные данные (n целых байтов)

и совпадение («копия») с параметрами длины и смещения:

 type:8 = 1 => совпадение/копирование диапазона счетчика байтов количество: 16 = 31..65535 offset:32 = смещение позиции для копирования

Литералы или совпадения/копии длиной более 65 535 байт разбиваются на несколько инструкций. Конец потока обозначается командой литерала/сложения нулевой длины (тип=0,счет=0), за которой сразу следует 32-битная контрольная сумма CRC.

Эталонная реализация

Алгоритм скользящей контрольной суммы, основанный на алгоритме rsync, используется для поиска потенциальных совпадений в таком большом наборе данных. По мере заполнения хеш-корзин предыдущие хэши («теги») отбрасываются дважды. ^{[ нужны разъяснения ]} Теги отбрасываются таким образом, чтобы обеспечить достаточно хорошее покрытие с постепенно уменьшающейся детализацией соответствия по мере увеличения расстояния. Эта реализация не ищет совпадения длиной менее 31 последовательного байта.

Преимущества

Ключевое отличие rzip от других известных алгоритмов сжатия заключается в его способности использовать преимущества избыточности на очень больших расстояниях. Хорошо известный алгоритм выкачивания, используемый в gzip, использует максимальный буфер истории размером 32 КиБ. Алгоритм сортировки блоков преобразования Берроуза-Уиллера , используемый в bzip2, ограничен 900 КиБ истории. Буфер истории в rzip может иметь длину до 900 МБ, что на несколько порядков больше, чем у gzip или bzip2. Rzip зачастую намного быстрее, чем bzip2, несмотря на использование библиотеки bzip2 в качестве серверной части. Это связано с тем, что rzip передает в bzip2 сжатые данные, поэтому bzip2 должен выполнять меньше работы. Были проведены простые сравнения (хотя они слишком малы, чтобы служить авторитетным ориентиром). ^[1]^[2]

Недостатки

rzip подходит не для всех целей. Двумя самыми большими недостатками rzip являются то, что он не может быть конвейерным (поэтому он не может читать со стандартного ввода или записывать на стандартный вывод) и что он использует большой объем памяти: типичное сжатие большого файла может занимать сотни мегабайт. оперативной памяти . Если имеется много свободной оперативной памяти и требуется очень высокая степень сжатия, следует использовать rzip, но если эти условия не выполняются, следует использовать альтернативные методы сжатия, такие как gzip и bzip2, которые менее требовательны к памяти. вместо рзипа.Существует как минимум один патч для включения конвейерной обработки. ^[3]

История

rzip изначально был написан Эндрю Триджеллом в рамках его докторской диссертации.

Альтернативные реализации

lrzip

lrzip (Long Range ZIP) — улучшенная версия rzip. Его формат файла ( .lrz) несовместим с rzip. Имеет следующие улучшения:

Выбор сжатия LZMA , LZO , DEFLATE , Bzip2 и ZPAQ (в отличие только от Bzip2)
Нет ограничений по словарю, даже не ограничено доступной оперативной памятью.
Возможность проверки данных на сжимаемость перед сжатием, что позволяет компьютеру не тратить время на попытки сжать несжимаемые данные.
Возможность конвейеризации со стандартного ввода/стандартного вывода (с потерей степени сжатия)
Возможность отключить сжатие последней стадии для использования с другим компрессором.
Дополнительное AES-128. шифрование ^[4]

В дистрибутив lrzip входит пара программ для использования с tar : lrztar и lrzuntar.

rzip64

rzip64 — это расширение rzip для очень больших файлов, которые могут использовать несколько ядер процессора параллельно . Есть результаты тестов. ^[5] Однако наиболее важным является возможность прерывания работы rzip64 в любой момент. Таким образом, выполняемая задача сжатия (которая может легко занять несколько часов для больших файлов) сохраняется даже после перезагрузки системы при обслуживании без потери уже выполненной работы и может быть возобновлена позже. Формат файла rzip64 идентичен оригинальному rzip.

РЕП

REP — это альтернативная реализация алгоритма rzip Булата Зиганшина, используемая в его архиваторе FreeArc в качестве препроцессора для алгоритмов сжатия LZMA/Tornado. В FreeArc REP находит совпадения на большом расстоянии, а затем LZMA сжимает оставшиеся данные. Например, на компьютере с 2 ГБ ОЗУ REP находит совпадения длиной не менее 512 байт на расстоянии до 1 ГБ, а затем LZMA находит оставшиеся совпадения на расстоянии до 128 МБ. Таким образом, работая вместе, они обеспечивают максимально возможное сжатие при бюджете 2 ГБ ОЗУ.

Будучи оптимизированным для распаковки потока и совместной работы с LZMA, REP имеет некоторые отличия от исходной реализации RZIP. Во-первых, по умолчанию он находит только совпадения длиной более 512 байт, поскольку тестирование показало, что это оптимальная настройка для общего сжатия REP+LZMA. Во-вторых, он использует скользящий словарь длиной около половины ОЗУ, поэтому при распаковке не требуется повторное чтение данных из распакованного файла. Преимущество REP заключается в его мультипликативном скользящем хеше, который быстро вычисляется и имеет почти идеальное распределение.

Большая минимальная длина совпадения (512 байт по сравнению с 32 байтами в rzip) позволила провести дополнительную оптимизацию скорости, так что REP обеспечивает очень быстрое сжатие (около 200 МБ/с на Intel i3-2100).

СРЭП

SREP (SuperREP) — это реализация идеи Триджела о компрессоре LZ, который не хранит свой словарь в оперативной памяти, а вместо этого использует хэши SHA1 обработанных блоков для сравнения их содержимого. Это позволяет программе сжимать файлы, размер которых примерно в 10 раз больше, чем доступно в оперативной памяти. Распаковка выполняется либо путем чтения данных из распакованной части файла, либо путем сохранения в памяти будущих совпадений (алгоритм сжатия Future-LZ). Конечно, сжатие Future-LZ требует двух проходов по входному файлу, но для распаковки требуется небольшой объем памяти. ^{[ нужна ссылка ]} В одном эксперименте файл размером 22 ГБ, сжатый с минимальной длиной совпадения 512 байт и полным словарем размером 22 ГБ, потребовал для распаковки всего 2 ГБ ОЗУ. ^{[ нужна ссылка ]}

См. также

Ссылки

^ Выбор правильного почтового индекса ^{[узурпировал]}
^ "рзип" .
^ «Николас Рачинский: Ссылки» .
^ Коливас, Кон. "lrzip README" . Гитхаб . Проверено 27 января 2017 г.
^ «GHSi — Сравнительный анализ rzip64» .

Внешние ссылки

Rzip
lrzip — улучшение rzip, позволяющее bzip2 заменить сжатие на втором этапе на LZMA , LZO или отсутствие второго этапа (необработанное сжатие только по словарю). Автором является Кон Коливас, который утверждает, что «lrzip» означает «ZIP большого радиуса действия».
rzip64 — параллельное улучшение rzip с режимом остановки от Кея Горонци.
REP at the Wayback Machine (архивировано 19 ноября 2016 г.) — улучшенная реализация RZIP, оптимизированная для использования вместе с LZMA.
SREP в Wayback Machine (архивировано 23 декабря 2016 г.) — первый компрессор LZ, который использует меньше оперативной памяти, чем размер словаря.
DataCompression.info – LZ77/LZSS и производные

[1] Выбор правильного почтового индекса ^{[узурпировал]}

[2] "рзип" .

[3] «Николас Рачинский: Ссылки» .

[4] Коливас, Кон. "lrzip README" . Гитхаб . Проверено 27 января 2017 г.

[5] «GHSi — Сравнительный анализ rzip64» .

[1]

[2]

[3]

[4]

[5]

v т и Форматы архивов
Только архивирование	с cpio делиться берет ЛБР ВАД ВАРК
Только сжатие	Бротли bzip2 компресс gzip Цопфли ЛЗМА LZ4 lzip лзоп КВ. хз Zстандарт
Архивирование и сжатие	7з ТУЗ АРК АРЖ Б1 Кабинет cfs cpt но ГДГА .dmg .яйцо кгб ЛХА lrzip ЛЗХ MPQ МОЖЕТ БЫТЬ РАР Rzip сидеть ситх SQX БЕДРА Хар хороший Почтовый индекс ЗПАК
Упаковка и распространение программного обеспечения	апк Приложение ПРИЛОЖЕНИЕ что ХАП насилие БАНКА ВОЙНА Ява РАР УХО МСИ MSIX Пакет (macOS) об/мин XAP XBAP
Упаковка и распространение документов	Формат пакета OEB Формат контейнера OEBPS Соглашения об открытой упаковке УПАКОВКА
Сравнение Список Категория