본문으로 이동

rzip

위키백과, 우리 모두의 백과사전.

rzip
원저자앤드루 트라젤(Andrew Tridgell)
안정화 버전
2.1 / 2006년 2월 14일(19년 전)(2006-02-14)
프로그래밍 언어C
운영 체제유닉스 계열
크기46K (source code tarball, gzipped)
웹사이트rzip.samba.org

rzip(알집)은 초기 LZ77 스타일 문자열 매칭(900 MB 사전 창에서), 이어서 bzip2 기반 버로우즈-휠러 변환 및 엔트로피 코딩(허프먼 부호화)을 900 kB 출력 청크에 적용하여 설계된 대규모 데이터 압축 컴퓨터 프로그램이다.

압축 알고리즘

[편집]

rzip은 두 단계로 작동한다. 첫 번째 단계는 입력 파일에서 잠재적으로 매우 긴 거리(900 MB)에 걸쳐 중복된 데이터의 큰 청크를 찾아 인코딩한다. 두 번째 단계는 표준 압축 알고리즘(bzip2)을 사용하여 첫 번째 단계의 출력을 압축한다.

요즘에는 장거리 중복을 포함하는 파일을 압축해야 하는 경우가 상당히 흔하다. 예를 들어, 홈 디렉터리 세트를 압축할 때 여러 사용자가 동일한 파일 또는 상당히 유사한 파일의 복사본을 가질 수 있다. 또한 동일한 이미지의 반복된 복사본을 포함하는 PDF 파일과 같이 장거리에서 큰 중복 청크를 포함하는 단일 파일도 흔하다. 대부분의 압축 프로그램은 이러한 중복을 활용할 수 없으므로 rzip이 달성할 수 있는 것보다 훨씬 낮은 압축률을 달성할 수 있다.

두 단계 간의 중간 인터페이스는 바이트 정렬된 데이터 스트림으로 구성되며, 여기에는 길이와 데이터가 있는 리터럴("추가") 명령 두 가지가 있다. 

 type:8       = 0 => 리터럴/추가 카운트 바이트 범위
 count:16     = 1..65535
 data:8..∞    = 삽입할 리터럴 데이터 (n개의 전체 바이트)

그리고 길이와 오프셋 매개변수가 있는 매치("복사") 명령이 있다. 

 type:8       = 1 => 매치/복사 카운트 바이트 범위
 count:16     = 31..65535
 offset:32    = 복사할 위치의 오프셋

65,535바이트보다 큰 리터럴 또는 매치/복사 길이는 여러 명령으로 분할된다. 스트림의 끝은 길이가 0인 리터럴/추가(type=0, count=0) 명령으로 표시되며 즉시 32비트 CRC 체크섬이 이어진다.

참조 구현

[편집]

rsync에 기반한 롤링-체크섬 알고리즘이 그렇게 큰 데이터세트에서 잠재적 매치를 찾는 데 사용된다. 해시 버킷이 채워지면 이전 해시("태그")는 두 번에 걸쳐 버려진다. 태그는 거리가 증가함에 따라 점진적으로 매치 세분화가 감소하면서 상당히 좋은 커버리지를 제공하는 방식으로 버려진다. 이 구현은 31바이트 미만의 연속적인 매치 길이를 검색하지 않는다.

장점

[편집]

rzip과 다른 잘 알려진 압축 알고리즘의 주요 차이점은 매우 장거리 중복을 활용할 수 있다는 점이다. gzip에 사용되는 잘 알려진 디플레이트 알고리즘은 최대 32 KiB의 기록 버퍼를 사용한다. bzip2에 사용되는 버로우즈-휠러 변환 블록 정렬 알고리즘은 900 KiB의 기록으로 제한된다. rzip의 기록 버퍼는 900 MiB 길이까지 가능하며, gzip이나 bzip2보다 몇 배나 더 크다. rzip은 백엔드로 bzip2 라이브러리를 사용함에도 불구하고 bzip2보다 훨씬 빠른 경우가 많다. 이는 rzip이 bzip2에 축소된 데이터를 공급하여 bzip2가 더 적은 작업을 수행하기 때문이다. 간단한 비교(권위 있는 벤치마크로는 너무 작지만)가 수행되었다.[1][2]

단점

[편집]

rzip은 모든 용도에 적합하지 않다. rzip의 두 가지 가장 큰 단점은 파이프라인 처리가 불가능하다는 점(따라서 표준 입력에서 읽거나 표준 출력에 쓸 수 없음)과 많은 양의 메모리를 사용한다는 점이다. 대용량 파일에서 일반적인 압축 실행은 수백 메가바이트의 RAM을 사용할 수 있다. 여유 RAM이 많고 매우 높은 압축률이 필요한 경우 rzip을 사용해야 하지만, 이러한 조건이 충족되지 않는 경우 메모리 사용량이 적은 gzip 및 bzip2와 같은 대체 압축 방법을 rzip 대신 사용해야 한다. 파이프라인 처리를 가능하게 하는 최소한 하나의 패치가 있다.[3]

역사

[편집]

rzip은 원래 앤드루 트리젤이 그의 박사 연구의 일부로 작성했다.

대체 구현

[편집]

lrzip

[편집]
lrzip
원저자콘 콜리바스, 피터 하이먼, 앤드루 트리젤
발표일2008년 1월(17년 전)(2008-01)
안정화 버전
0.651 / 2022년 3월 9일(3년 전)(2022-03-09)
프로그래밍 언어C, C++ (libzpaq)
운영 체제유닉스 계열
크기246K (source code tarball, gzipped)
웹사이트github.com/ckolivas/lrzip

lrzip (Long Range ZIP)은 rzip의 개선된 버전이다. 파일 형식(.lrz)은 rzip과 호환되지 않는다. 다음과 같은 개선 사항이 있다.

  • LZMA, LZO, DEFLATE, Bzip2, ZPAQ 압축 선택 (Bzip2만 가능했던 것과 대조적)
  • 사전 제한 없음, 사용 가능한 RAM에도 제한되지 않음
  • 압축 전에 데이터 압축 가능성을 테스트하여 컴퓨터가 압축 불가능한 데이터를 압축하려 시도하며 시간을 낭비하는 것을 방지
  • 표준 입력/표준 출력에서 파이프라인 처리 가능 (압축률 손실 동반)
  • 다른 압축기와 함께 사용하기 위해 최종 단계 압축 비활성화 가능
  • 선택적 AES-128 암호화[4]

lrzip 배포판에는 tar와 함께 사용할 수 있는 lrztar 및 lrzuntar 프로그램 쌍이 포함되어 있다.

rzip64

[편집]

rzip64는 여러 CPU 코어를 병렬로 활용할 수 있는 매우 큰 파일을 위한 rzip의 확장이다. 벤치마크 결과가 있다.[5] 그러나 가장 중요한 것은 rzip64가 언제든지 중단될 수 있다는 점이다. 따라서 실행 중인 압축 작업(대용량 파일의 경우 몇 시간이 걸릴 수 있음)은 시스템 유지보수 재부팅에도 이미 완료된 작업을 잃지 않고 생존하며 나중에 재개할 수 있다. rzip64의 파일 형식은 원래 rzip과 동일하다.

REP

[편집]

REP는 불라트 지간신(Bulat Ziganshin)이 FreeArc 아카이버에서 LZMA/Tornado 압축 알고리즘의 전처리기(preprocessor)로 사용하는 rzip 알고리즘의 대체 구현이다. FreeArc에서 REP는 장거리 매치를 찾은 다음 LZMA가 나머지 데이터를 압축한다. 예를 들어, 2 GB RAM을 사용하는 컴퓨터에서 REP는 최대 1 GB 거리에서 최소 512바이트 길이의 매치를 찾은 다음 LZMA는 최대 128 MB 거리에서 남아 있는 매치를 찾는다. 따라서 함께 작동하여 2 GB RAM 예산에서 가능한 최고의 압축을 제공한다.

스트림 압축 해제 및 LZMA와의 협업에 최적화된 REP는 원래 RZIP 구현과 몇 가지 차이점이 있다. 첫째, 기본적으로 512+ 바이트 길이의 매치만 찾는데, 이는 벤치마크를 통해 이것이 전체 REP+LZMA 압축에 최적의 설정임이 입증되었기 때문이다. 둘째, RAM 길이의 약 1/2인 슬라이딩 사전을 사용하므로 압축 해제 시 압축 해제된 파일에서 데이터를 다시 읽을 필요가 없다. REP의 장점은 계산이 빠르고 거의 이상적인 분포를 갖는 곱셈 롤링 해시이다.

더 큰 최소 매치 길이(rzip의 32바이트에 비해 512바이트)는 추가적인 속도 최적화를 가능하게 하여 REP가 매우 빠른 압축(Intel i3-2100에서 약 200 MB/s)을 제공한다.

SREP

[편집]

SREP (SuperREP)은 사전을 RAM에 저장하지 않고 처리된 블록의 SHA1 해시를 사용하여 내용을 비교하는 트리젤의 LZ 압축기 아이디어의 구현이다. 이 프로그램은 사용 가능한 RAM보다 약 10배 큰 파일을 압축할 수 있다. 압축 해제는 파일의 압축 해제된 부분에서 데이터를 읽거나, 메모리에 미래 매치를 저장하여 수행된다(미래-LZ 압축 알고리즘). 물론, 미래-LZ 압축은 입력 파일에 대해 두 번의 통과를 필요로 하지만 압축 해제에는 아주 적은 메모리가 필요하다. 한 실험에서 최소 매치 길이가 512바이트이고 전체 22 GB 사전을 가진 22 GB 파일은 압축 해제에 2 GB의 RAM만 필요했다.

같이 보기

[편집]

각주

[편집]
  1. ↑ Choosing the Right Zip Code
  2. ↑ “rzip”. 
  3. ↑ “Nicolas Rachinsky: Links”. 
  4. ↑ Kolivas, Kon. “lrzip README”. 《GitHub》. 2017년 1월 27일에 확인함. 
  5. ↑ “GHSi - Benchmarking rzip64”. 

외부 링크

[편집]
  • rzip
  • lrzip — rzip의 개선판으로, 두 번째 단계 bzip2 축소를 LZMA, LZO 또는 두 번째 단계 없음(원시, 사전 전용 압축)으로 대체할 수 있다. 저자는 콘 콜리바스(Con Kolivas)이며 'lrzip'은 'Long Range ZIP'의 약자라고 명시한다.
  • rzip64 — 카이 고론치(Kay Gorontzi)의 스톱 앤 고(stop-and-go) 모드를 포함한 'rzip'의 병렬 개선판.
  • REP - 웨이백 머신 (보관됨 2016-11-19) — LZMA와 함께 사용하도록 최적화된 개선된 RZIP 구현
  • SREP - 웨이백 머신 (보관됨 2016-12-23) — 사전 크기보다 적은 RAM을 사용하는 최초의 LZ 압축기
  • DataCompression.info – LZ77/LZSS 및 파생물
원본 주소 "https://ko.wikipedia.org/w/index.php?title=Rzip&oldid=40234526"