Rzip

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

## 압축 알고리즘
rzip은 두 단계로 작동한다. 첫 번째 단계는 입력 파일에서 잠재적으로 매우 긴 거리(900&nbsp;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&nbsp;KiB의 기록 버퍼를 사용한다. bzip2에 사용되는 버로우즈-휠러 변환 블록 정렬 알고리즘은 900&nbsp;KiB의 기록으로 제한된다. rzip의 기록 버퍼는 900&nbsp;MiB 길이까지 가능하며, gzip이나 bzip2보다 몇 배나 더 크다. rzip은 백엔드로 bzip2 라이브러리를 사용함에도 불구하고 bzip2보다 훨씬 빠른 경우가 많다. 이는 rzip이 bzip2에 축소된 데이터를 공급하여 bzip2가 더 적은 작업을 수행하기 때문이다. 간단한 비교(권위 있는 벤치마크로는 너무 작지만)가 수행되었다.

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

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

## 대체 구현

### lrzip

lrzip (Long Range ZIP)은 rzip의 개선된 버전이다. 파일 형식(`.lrz`)은 rzip과 호환되지 않는다. 다음과 같은 개선 사항이 있다.
* LZMA, LZO, DEFLATE, Bzip2, ZPAQ 압축 선택 (Bzip2만 가능했던 것과 대조적)
* 사전 제한 없음, 사용 가능한 RAM에도 제한되지 않음
* 압축 전에 데이터 압축 가능성을 테스트하여 컴퓨터가 압축 불가능한 데이터를 압축하려 시도하며 시간을 낭비하는 것을 방지
* 표준 입력/표준 출력에서 파이프라인 처리 가능 (압축률 손실 동반)
* 다른 압축기와 함께 사용하기 위해 최종 단계 압축 비활성화 가능
* 선택적 AES-128 암호화

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

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

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

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

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

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

## 같이 보기
* 아카이브 형식 목록, 아카이브 형식 비교
* 파일 아카이버 목록, 압축 소프트웨어의 비교

## 각주

## 외부 링크
* rzip
* lrzip — rzip의 개선판으로, 두 번째 단계 bzip2 축소를 LZMA, LZO 또는 두 번째 단계 없음(원시, 사전 전용 압축)으로 대체할 수 있다. 저자는 콘 콜리바스(Con Kolivas)이며 'lrzip'은 'Long Range ZIP'의 약자라고 명시한다.
* rzip64 — 카이 고론치(Kay Gorontzi)의 스톱 앤 고(stop-and-go) 모드를 포함한 'rzip'의 병렬 개선판.
*  — LZMA와 함께 사용하도록 최적화된 개선된 RZIP 구현
*  — 사전 크기보다 적은 RAM을 사용하는 최초의 LZ 압축기
* DataCompression.info – LZ77/LZSS 및 파생물

분류:자유 압축 소프트웨어