bzip2

bzip2
"Bzip"은 여기서 리다이렉트 됩니다.단백질 도메인에 대해서는 bZIP 도메인을 참조하십시오.
bzip2
Bzip2-logo.svg
원저작자줄리언 시워드
개발자마크 비엘라드, 페데리코 메나, 마이카 스나이더
초기 릴리즈1996년 7월 18일; 26년 전 (1996-07-18)[1]
안정된 릴리스
1.0.8 / 2019년 7월 13일, 3년 전(2019-07-13)
저장소https://gitlab.com/bzip2/bzip2/
운영 체제크로스 플랫폼[어느 쪽?]
유형data 압축
면허증.BSD라이크 라이선스[2]
웹 사이트sourceware.org/bzip2/
bzip2
파일 이름 확장자
.bz2
인터넷 미디어 유형
application/x-bzip2
유형코드Bzp2
Uniform Type Identifier(UTI; 균일 유형 식별자)public.bzip2
매직 넘버BZh
개발자줄리언 시워드
포맷의 종류data 압축
오픈 포맷?네.

bzip2는 Burrows를 사용하는 무료 오픈 소스 파일 압축 프로그램입니다.휠러 알고리즘단일 파일만 압축하고 파일 아카이브는 아닙니다.그것은 줄리안 시워드에 의해 개발되었고 마크 위라드와 마이카 스나이더에 의해 유지되었다.

역사

Seward는 1996년 7월에 bzip2 버전 0.15를 처음으로 공개했습니다.이후 수년간 컴프레서의 안정성과 인기는 높아졌고 Seward는 2000년 [not verified in body]말에 버전 1.0을 출시했습니다.2010년 이후 9년간 프로젝트 갱신이 중단된 후 2019년 6월 4일 페데리코 메나는 bzip2 프로젝트의 [3]유지보수를 승인했다.2021년 6월부터 관리인은 마이카 스나이더입니다.[4]

실행

Bzip2는 여러 레이어의 압축 기술을 서로 겹쳐 사용합니다.압축 중에는 다음 순서로, 압축 해제 중에는 역순으로 발생합니다.

  1. 초기 데이터의 Run-Length Encoding(RLE; 실행 길이 부호화).
  2. 버로우즈휠러 변환(BWT) 또는 블록 정렬.
  3. MTF(Move-to-Front) 변환.
  4. MTF 결과의 Run-Length Encoding(RLE; 런렝스 부호화).
  5. 허프만 부호화
  6. 여러 Huffman 테이블 중 선택.
  7. Huffman 테이블 선택의 단항 base-1 부호화.
  8. 허프만 코드비트 길이의 Delta Encoding(δ; 델타 부호화).
  9. 사용되는 기호를 나타내는 스파스 비트 배열입니다.

4~255개의 연속된 중복 심볼의 시퀀스는 첫 번째 4개의 심볼과 0~251의 반복 길이로 대체됩니다.따라서 순서는AAAAAAABBBBCCCD로 대체되었습니다.AAAA\3BBBB\0CCCD,어디에\3그리고.\0는 각각 바이트 값 3과 0을 나타냅니다.실행 길이가 0으로 설정된 경우에도 기호 실행은 변환을 되돌릴 수 있도록 항상 연속 4개의 기호 후에 변환됩니다.

최악의 경우 1.25의 확장을 일으킬 수 있으며, 최선의 경우 0.02 미만으로 감소시킬 수 있습니다.이 사양에서는 이론적으로 256 ~259 의 길이의 실행을 부호화할 수 있습니다만, 레퍼런스 인코더에서는 그러한 출력이 생성되지 않습니다.

bzip2의 작성자는 RLE 스텝은 과거의 실수이며 병리학적 [5]케이스로부터 원래의 BWT 구현을 보호하기 위한 것일 뿐이라고 기술하고 있습니다.

버로우스 가족Wheeler 트랜스폼은 bzip2의 핵심인 리버서블블록 정렬입니다블록은 완전히 자기포함되어 같은 크기의 입력 버퍼와 출력 버퍼가 남아 있습니다.bzip2에서는 이 스테이지의 동작제한은 900kB입니다.블록 정렬은 i번째 기호에서 시작하도록 회전하는 (주제)행렬이 생성되며, 이 행 i는 버퍼 전체를 포함한다.회전 후에는 행렬의 행이 알파벳(숫자) 순서로 정렬됩니다.블록이 변환되지 않았을 때의 시작 위치를 나타내는 24비트 포인터가 기억된다.실제로는 완전한 매트릭스를 구성할 필요가 없습니다.대신 버퍼 내의 각 위치에 대한 포인터를 사용하여 정렬이 수행됩니다.출력 버퍼는 매트릭스의 마지막 열입니다.버퍼 전체는 포함되지만 동일한 기호의 대규모 실행이 포함되도록 순서를 변경합니다.

Move-to-Front 변환은 다시 처리되는 크기를 변경하지 않습니다.문서에서 사용 중인 각 기호는 배열에 배치됩니다.기호가 처리되면 해당 기호는 배열 내의 위치(색인)로 대체되고 해당 기호는 배열 앞으로 셰이핑됩니다.그 결과 즉시 반복되는 심볼은 제로 심볼로 대체되며(임의 심볼의 롱런은 제로 심볼이 됩니다), 다른 심볼은 로컬 주파수에 따라 재맵됩니다.

대부분의 "자연" 데이터에는 제한된 범위 내에서 반복되는 동일한 기호가 포함되어 있습니다(텍스트가 좋은 예입니다).MTF 변환은 자주 다시 나타나는 심볼에 낮은 값을 할당하므로 낮은 정수 범위의 많은 심볼을 포함하는 데이터 스트림이 생성됩니다(다른 반복 입력 심볼은 실제로 동일한 출력 심볼에 매핑할 수 있습니다).이러한 데이터는 모든 레거시 압축 방법으로 매우 효율적으로 인코딩할 수 있습니다.

Move-to-Front 변환 출력의 긴 0 문자열(BWT 출력의 반복 기호에서 비롯됨)은 2개의 특수 코드인 RUNA와 RUNB 시퀀스로 대체됩니다.RUNB는 이진수로 런 길이를 나타냅니다.실제 제로는 출력에 부호화되지 않습니다.론 제로는 RUNA가 됩니다(실제로 이 스텝은 MTF와 동시에 실행됩니다.MTF가 제로를 생성할 때마다 카운터를 증가시켜 RUNA 및 RUNB로 부호화합니다).

순서0, 0, 0, 0, 0, 1로 표현될 것이다RUNA, RUNB, 1;RUNA, RUNB는 다음에 설명하는 값 5를 나타냅니다.실행 길이 코드는 다른 일반 기호에 도달하여 종료됩니다.이 RLE 프로세스는 임의의 긴 정수를 부호화할 수 있기 때문에 초기 RLE 스텝보다 유연성이 높아집니다(실제로는 블록사이즈에 의해 제한되므로 이 스텝은 900,000바이트 이상의 실행을 부호화하지 않습니다).런렝스는 다음과 같이 부호화됩니다.시퀀스에서 1의 플레이스 값, 2의 플레이스 값, 4의 플레이스 값 등을 할당하고 RUNB 스팟 내의 각 플레이스 값에 2를 곱하여 결과적인 모든 플레이스 값(RUNA 값과 RUNB 값 모두)을 추가합니다.이것은 base-2 bijectionive numberation과 비슷합니다.따라서 순서는RUNA, RUNB결과 값은 (1 + 2 × 2) = 5. 보다 복잡한 예로서:

RUNA RUNB RUNA RUNB(ABAB) 1 2 4 8 16 1 4 4 8 32 = 49

이 프로세스는 0 ~ 258 범위의 고정 길이 기호를 사용 빈도에 따라 가변 길이 코드로 대체합니다.사용 빈도가 높은 코드는 더 짧아지고(2~3비트), 희귀 코드는 최대 20비트를 할당할 수 있습니다.비트의 시퀀스를 다른 코드로 혼동하지 않도록 코드를 신중하게 선택합니다.

스트림 종료 코드는 특히 흥미롭습니다.압축되지 않은 데이터에 사용되는 바이트(심볼)가 n개인 경우 허프만 코드는 2개의 RLE 코드(RUNA 및 RUNB), n - 1개의 기호 코드 및 1개의 스트림 종료 코드로 구성됩니다.앞의 2단계에서 MTF 및 RLE 인코딩의 조합 결과 때문에 MTF 테이블의 첫 번째 기호(일반 MTF에서는 0)를 명시적으로 참조할 필요가 없습니다.따라서 스트림 종료 마커의 1개의 기호(및 허프만 트리에 n - 1개의 기호만 코드화된 이유를 설명)를 저장할 수 있습니다.압축되지 않은 데이터에 하나의 기호만 사용되는 극단적인 경우 Huffman 트리에는 기호 코드가 전혀 없으며 전체 블록은 RUNA 및 RUNB(단일 바이트를 암시적으로 반복) 및 값이 2인 스트림 끝 마커로 구성됩니다.

0: RUNA,
1: RUNB,
2 ~ 257 : 0 ~255 바이트 값,
258: 스트림의 종료, 처리 종료(최소 2).

여러 개의 동일한 크기의 Huffman 테이블을 사용함으로써 얻는 이득이 추가 테이블을 포함하는 비용보다 클 경우 블록과 함께 사용할 수 있습니다.최소 2 테이블에서 최대 6 테이블이 존재하며, 50개의 심볼이 처리되기 전에 가장 적합한 테이블을 다시 선택할 수 있습니다.이것은 DEFLATE에서 요구되는 것처럼 새로운 테이블을 지속적으로 공급할 필요 없이 매우 반응성이 뛰어난 Huffman 다이내믹스를 가질 수 있는 장점이 있습니다.이전 단계의 런렝스 부호화는 사용 중인 최단 코드 Huffman 코드보다 사용 확률이 높은 코드를 처리하도록 설계되었습니다.

여러 Huffman 테이블을 사용하는 경우 각 테이블(번호0 ~ 5)은 1~6비트 길이의 제로 종단 비트에 의해 리스트에서 선택됩니다.테이블 MTF 목록으로 선택됩니다.이 기능을 사용하면 약 1.015의 최대 확장을 얻을 수 있지만 일반적으로는 더 적게 확장됩니다.이러한 확장은 보다 적절한 Huffman 테이블을 선택할 수 있다는 장점으로 인해 크게 부각될 가능성이 높으며, 동일한 Huffman 테이블을 계속 사용하는 일반적인 경우가 단일 비트로 표현됩니다.이는 단항 부호화가 아니라 사실상 Huffman 트리의 극단적인 형태이며, 각 코드는 이전 코드보다 절반의 확률을 가집니다.

사용된 각 표준 Huffman 테이블을 재구성하려면 Huffman 코드 비트 길이가 필요합니다.각 비트 길이는 이전 코드 비트 길이에 대한 부호화된 차이로 저장됩니다.0비트(0)는 현재 코드에 대해 이전 비트 길이를 복제해야 함을 의미하며, 1비트(1)는 추가 비트를 읽고 해당 값에 따라 비트 길이를 증가 또는 감소시켜야 함을 의미합니다.일반적으로 테이블마다 기호별로 1비트가 사용되며 최악의 경우 길이1에서 길이20까지 약 37비트가 필요합니다.이전의 MTF 부호화 결과 코드 길이는 2~3비트 길이(매우 자주 사용되는 코드)에서 시작하여 점차 증가했습니다.즉, 델타 포맷은 매우 효율적이며 완전한 Huffman 테이블당 약 300비트(38바이트)가 필요합니다.

비트맵은 블록 내에서 사용되는 기호를 표시하기 위해 사용되며 Huffman 트리에 포함되어야 합니다.바이너리 데이터는 바이트로 나타낼 수 있는 256개의 기호를 모두 사용하는 반면 텍스트 데이터는 사용 가능한 값의 작은 부분 집합만 사용할 수 있으며, 아마도 32에서 126 사이의 ASCII 범위를 포함할 수 있습니다.256개의 제로 비트를 저장하는 것은 대부분 사용되지 않는 경우 비효율적입니다.스퍼스 방식이 사용됩니다.256개의 심볼은 16개의 범위로 분할되며, 이 블록 내에서 심볼이 사용되는 경우에만 16비트 배열이 포함됩니다.이들 각 16개 범위의 존재는 전면에 추가 16비트 배열로 나타납니다.총 비트맵은 32~272비트(4~34바이트)의 스토리지를 사용합니다.반면 DEFLATE 알고리즘은 실행 길이 부호화와 추가 Huffman 부호화를 포함한 제로 비트 길이를 갖는 기호로 부호화함으로써 기호 부재를 나타냅니다.

파일 형식

bzip2에 대한 공식 사양은 존재하지 않지만, 비공식 사양은 참조 [6]구현에서 리버스 엔지니어링되었습니다.

개요로서.bz2스트림은 4바이트 헤더와 0 이상의 압축 블록으로 구성되어 있으며, 그 직후에 처리된 평문 스트림 전체의 32비트 CRC를 포함하는 스트림 종료 마커로 구성됩니다.압축된 블록은 비트 정렬되며 패딩은 발생하지 않습니다. 

.backs:16 = 'BZ' 시그니처/캐릭터 번호:8 = 'h' ('H'uffman 코딩') = '0' (사용되지 않음) Bzip1.100_k_blocksize:8 = '1'..'9' 블록 크기 100kB-900KB (압축됨) = 03148x48있나 블록 .randomised:1=0=>, 1=> 정상적인;randomised(사용되지 않).origPtr:보세 창고 도거래에untransform .huffman_used_map 후에 16바이트 범위의 24)부터 포인터:16)비트 맵,present/not 현재 .huffman_used_bitmaps:기호 사용되는 0..256)비트 맵,present/not 선물(16배수)..huffman_groups:3 = 사용 중인 다른 허프만 테이블의 2 . 6 수.selectors _ used : 15 = 허프만 테이블이 스왑되는 횟수(각 50개 기호) *.selectors _ list : 1 . 6 = 제로 종단 비트 실행(0..62)의 MTF'ed Huffman 테이블(*selectors_used) .start_selectors_length: 5 = 0..허프만 델타의 20 시작 비트 길이 *.timeout_bit_length:1 . 40 = 0 = > 다음 기호, 1 = > 최소 길이 {1 = > 최소 길이 } (*(timeout+2) * 그룹) .timeout:2 .timeout = 블록의 종료까지 허프만 인코딩된 데이터 스트림(최대 7372800 비트) .timeout_:48.= 0x4402245385090 (BCD sqrt(pi)) .bc:32 = 전체 스트림에 대한 체크섬.bc:0..7 = 전체 바이트에 정렬

1단계 RLE 압축(상기 참조)을 위해 단일 900kB bzip2 블록에 포함할 수 있는 플레인텍스트의 최대 길이는 약 46MB(45,899,236바이트)입니다.이 문제는 전체 평문이 모두 반복된 값으로 구성되어 있는 경우 발생할 수 있습니다(결과)..bz2파일 길이는 46바이트입니다).전체 값 251(표관 압축비 1147480.9:1)을 포함하는 입력을 사용하면 40바이트의 더 작은 파일을 얻을 수 있습니다.

bzip2의 압축된 블록은 이전 블록을 처리할 필요 없이 독립적으로 압축 해제할 수 있습니다.즉, bzip2 파일을 병렬로 압축 해제할 수 있으므로 Hadoop 및 Apache [7]Spark와 같은 클러스터 컴퓨팅 프레임워크와 함께 빅데이터 애플리케이션에 사용하기에 적합한 포맷입니다.

효율성.

bzip2는 대부분의 파일을 오래된 LZW(.Z) 및 Deflate(.zip 및 .gz) 압축 알고리즘보다 더 효과적으로 압축하지만 상당히 느립니다.LZMA는 일반적으로 bzip2보다 공간 효율이 높지만 압축 속도는 더 느립니다.또한 압축 [8]해제 속도는 훨씬 빠릅니다.

bzip2는 100~900kB 크기의 블록으로 데이터를 압축하고 Burrows를 사용합니다.휠러 변환: 자주 반복되는 문자 시퀀스를 동일한 문자의 문자열로 변환합니다.그런 다음 Move-to-Front 변환과 Huffman 부호화를 적용합니다.bzip2의 조상 bzip은 Huffman 대신 산술 부호화를 사용했습니다.소프트웨어 특허 [9]제한으로 인해 변경이 이루어졌습니다.

압축 해제 속도가 비교적 빠르기 때문에 bzip2의 퍼포먼스는 비대칭입니다.압축에 필요한 CPU 시간이 길기 때문에 2003년에 멀티 스레딩을 지원하는 pbzip2라는 수정 버전이 개발되어 멀티 CPU [10]및 멀티 코어 컴퓨터의 속도가 거의 선형적으로 향상되었습니다.2010년 5월 현재 이 기능은 주요 프로젝트에 포함되지 않았습니다.

gzip과 마찬가지로 bzip2도 데이터 압축기에 불과합니다.tar나 ZIP과 같은 아카이브 서버는 아닙니다.프로그램 자체에는 여러 파일, 암호화 또는 아카이브 분할 기능이 없습니다.그러나 UNIX의 전통에서는 이러한 작업을 위해 tar나 GnuPG와 같은 별도의 외부 유틸리티에 의존합니다.

그grep베이스bzgrep도구를 사용하면 [11]먼저 내용을 압축 해제하지 않고도 압축된 텍스트를 직접 검색할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ bzip2/README, 1996년 7월 18일 (버전 0.15)
  2. ^ "bzip2 : Home". Julian Seward. Retrieved 21 July 2019. Why would I want to use it? [..] Because it's open-source (BSD-style license), and, as far as I know, patent-free.
  3. ^ "Articles with tag bzip2". viruta.org.
  4. ^ "Bzip2's experimental repository is changing maintainership - Federico's Blog". viruta.org. Retrieved 27 July 2022.
  5. ^ "bzip2 and libbzip2, version 1.0.8". sourceware.org.
  6. ^ "BZIP2 Format Specification" (PDF). GitHub. 17 March 2022.
  7. ^ "[HADOOP-4012] Providing splitting support for bzip2 compressed files". Apache Software Foundation. 2009. Retrieved 14 October 2015.
  8. ^ "7-zip vs bzip2 vs gzip". Archived from the original on 24 April 2016. Retrieved 12 February 2019.
  9. ^ "The bzip2 home page". Archived from the original on 4 July 1998. Retrieved 5 March 2009. - 섹션 "이전 서비스(bzip-0.21)와 어떻게 관련되어 있습니까?"
  10. ^ "compressionratings.com". ww1.compressionratings.com.
  11. ^ "bzgrep command in Linux with examples". die.net.

외부 링크