상위 질문
타임라인
채팅
관점

Rzip

위키백과, 무료 백과사전

Remove ads

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 체크섬이 이어진다.

Remove ads

참조 구현

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 (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만 필요했다.

Remove ads

같이 보기

각주

외부 링크

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads