bzip2 (한국어)

Bzip2는 압축 중에는 다음 순서로, 압축 해제 중에는 역순으로 서로 겹쳐진 여러 계층의 압축 기술을 사용합니다.

1. 초기 데이터의 실행 길이 인코딩 (RLE)
2. Burrows–Wheeler 변환 (BWT) 또는 블록 정렬
3. MTF (Move-to-front) 변환
4. MTF 결과의 실행 길이 인코딩 (RLE)
5. Huffman 코딩
6. 여러 Huffman 테이블 중에서 선택
7. 단항 base-1 인코딩 Huffman 테이블 선택의.
8. Huffman 코드 비트 길이의 델타 인코딩 (Δ)
9. 사용되는 기호를 보여주는 희소 비트 배열

초기 실행 길이 인코딩 편집

4에서 255 개의 연속 중복 기호 시퀀스는 처음 4 개의 기호와 0에서 251 사이의 반복 길이로 대체됩니다. 따라서 시퀀스는 AAAAAAABBBBCCCD는 AAAA\3BBBB\0CCCD로 대체됩니다. 여기서 \3 및 \0는 각각 바이트 값 3과 0을 나타냅니다. 연속 된 기호는 항상 4 개의 연속 기호 이후에 변환됩니다. 이는 실행 길이가 0으로 설정되어 있어도 변환을 되돌릴 수 있도록 유지합니다.

최악의 경우 1.25 확장이 발생할 수 있습니다. 가장 좋은 경우는 < 0.02로 줄이는 것입니다. 사양은 이론적으로 길이 256–259의 실행을 인코딩하도록 허용하지만 참조 인코더는 이러한 출력을 생성하지 않습니다.

bzip2의 작성자는 RLE 단계가 역사적 실수이며 의도 된 것일 뿐이라고 말했습니다. 원래 BWT 구현을 병리학 적 사례로부터 보호합니다.

Burrows–Wheeler transformEdit

이것은 가역적 블록 정렬입니다. bzip2의 핵심입니다. 블록은 완전히 독립적이며 입력 및 출력 버퍼가 동일한 크기로 남아 있습니다. bzip2에서이 단계의 작동 한계는 900kB입니다. 블록 정렬의 경우, 행 i가 버퍼 전체를 포함하는 (명목) 행렬이 생성되고 i 번째 기호에서 시작하도록 회전됩니다. 회전 후 행렬의 행은 알파벳 (숫자) 순서로 정렬됩니다. 블록이 변환되지 않을 때 시작 위치를 표시하는 24 비트 포인터가 저장됩니다. 실제로는 전체 행렬을 구성 할 필요가 없습니다. 오히려 버퍼의 각 위치에 대한 포인터를 사용하여 정렬이 수행됩니다. 출력 버퍼는 행렬의 마지막 열입니다. 여기에는 전체 버퍼가 포함되지만 동일한 기호가 대량으로 실행될 수 있도록 순서가 변경되었습니다.

Move-to-front transformEdit

다시 말하지만,이 변환은 처리 된 블록의 크기를 변경하지 않습니다. 문서에서 사용중인 각 기호는 배열에 배치됩니다. 심볼이 처리되면 배열의 위치 (인덱스)로 대체되고 해당 심볼은 배열의 앞쪽으로 섞입니다. 그 결과 즉시 반복되는 심볼은 0 심볼로 대체되고 (임의의 심볼이 길게 실행되면 0 심볼이 실행 됨) 다른 심볼은 로컬 주파수에 따라 다시 매핑됩니다.

많은 “자연스러운”데이터 제한된 범위 내에서 반복되는 동일한 기호를 포함합니다 (텍스트가 좋은 예입니다). MTF 변환은 자주 다시 나타나는 심볼에 낮은 값을 할당하기 때문에 낮은 정수 범위의 많은 심볼이 포함 된 데이터 스트림이 생성되며, 대부분은 동일합니다 (다른 반복 입력 심볼은 실제로 동일한 출력 심볼에 매핑 될 수 있음). 이러한 데이터는 기존 압축 방법을 사용하여 매우 효율적으로 인코딩 할 수 있습니다.

MTF resultEdit의 실행 길이 인코딩

앞으로 이동 변환의 출력에있는 긴 0 문자열 ( 이는 BWT 출력의 반복 된 기호에서 비롯됨) 실행 길이를 2 진수로 나타내는 두 개의 특수 코드 RUNA 및 RUNB 시퀀스로 대체됩니다. 실제 0은 출력에서 인코딩되지 않습니다. 고독한 제로는 RUNA가됩니다. (실제로이 단계는 MTF와 동시에 수행됩니다. MTF가 0을 생성 할 때마다 카운터를 증가시켜 RUNA 및 RUNB로 인코딩합니다.)

시퀀스 0, 0, 0, 0, 0, 1는 RUNA, RUNB, 1로 표시됩니다. RUNA, RUNB는 아래 설명 된 값 5를 나타냅니다. 실행 길이 코드는 다른 일반 기호에 도달하여 종료됩니다. 이 RLE 프로세스는 임의의 긴 정수를 인코딩 할 수 있으므로 초기 RLE 단계보다 더 유연합니다 (실제로는 일반적으로 블록 크기에 의해 제한되므로이 단계는 900000 바이트 이상의 실행을 인코딩하지 않음). 실행 길이는 다음과 같은 방식으로 인코딩됩니다. 순서에서 1의 자리 값을 첫 번째 비트에, 2에 두 번째, 4에 세 번째 등을 할당하고 RUNB 지점의 각 자리 값에 2를 곱한 다음 모두 더합니다. 결과 자리 값 (RUNA 및 RUNB 값 모두에 대해) 함께. 이것은 base-2 bijective numeration과 유사합니다.따라서 시퀀스 RUNA, RUNB는 값 (1 + 2 × 2) = 5가됩니다. 더 복잡한 예 :

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

Huffman codingEdit

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

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

0 : RUNA, 1 : RUNB, 2–257 : 바이트 값 0–255, 258 : 스트림 끝, 처리 완료 (최소 2 일 수 있음).

다중 Huffman 테이블 편집

사용으로 인한 이득이 추가 테이블을 포함하는 비용보다 큰 경우 동일한 크기의 여러 Huffman 테이블을 블록과 함께 사용할 수 있습니다. 최소 2 개에서 최대 6 개의 테이블이있을 수 있으며, 50 개의 심볼이 처리 될 때마다 가장 적절한 테이블이 다시 선택됩니다. 이것은 DEFLATE에서 요구되는 것처럼 새로운 테이블을 지속적으로 제공 할 필요없이 매우 반응이 빠른 Huffman 역학을 갖는 장점이 있습니다. 이전 단계의 실행 길이 인코딩은 사용중인 가장 짧은 코드 Huffman 코드보다 사용 확률이 더 높은 코드를 처리하도록 설계되었습니다.

Huffman 테이블 선택의 단항 인코딩 편집

여러 Huffman 테이블이 사용중인 경우, 각 테이블 (0에서 5까지 번호가 매겨진)의 선택은 길이가 1 ~ 6 비트 인 0으로 끝나는 비트에 의해 목록에서 수행됩니다. 선택은 테이블의 MTF 목록에 있습니다. 이 기능을 사용하면 약 1.015의 최대 확장이 발생하지만 일반적으로 더 적습니다. 이 확장은 더 적절한 Huffman 테이블을 선택하는 이점으로 인해 크게 가려 질 수 있으며 동일한 Huffman 테이블을 계속 사용하는 일반적인 경우는 단일 비트로 표시됩니다. 단항 인코딩이 아니라 사실상 이것은 각 코드가 이전 코드의 절반 확률을 갖는 극단적 인 형태의 Huffman 트리입니다.

Delta encodingEdit

Huffman 코드 비트 길이는 다음과 같습니다. 사용 된 각 표준 Huffman 테이블을 재구성하는 데 필요합니다. 각 비트 길이는 이전 코드 비트 길이에 대한 인코딩 된 차이로 저장됩니다. 0 비트 (0)는 이전 비트 길이가 현재 코드에 대해 복제되어야 함을 의미하고, 1 비트 (1)는 추가 비트를 읽어야하며 해당 값에 따라 비트 길이를 증가 또는 감소시켜야 함을 의미합니다.

일반적인 경우 테이블 당 심볼 당 단일 비트가 사용되며 길이 1에서 길이 20까지의 최악의 경우 약 37 비트가 필요합니다. 이전 MTF 인코딩의 결과로 코드 길이는 2 ~ 3 비트 길이 (매우 자주 사용되는 코드)에서 시작하여 점차 증가합니다. 즉, 델타 형식이 상당히 효율적이며 전체 Huffman 테이블 당 약 300 비트 (38 바이트)가 필요합니다. .

Sparse bit arrayEdit

비트 맵은 블록 내에서 사용되는 기호를 표시하는 데 사용되며 Huffman 트리에 포함되어야합니다. 바이너리 데이터는 바이트로 표현할 수있는 256 개의 심볼을 모두 사용하는 반면, 텍스트 데이터는 32에서 126 사이의 ASCII 범위를 포함하는 사용 가능한 값의 작은 하위 집합 만 사용할 수 있습니다. 256 개의 0 비트를 저장하는 것은 대부분 사용되지 않는 경우 비효율적입니다. 희소 방법이 사용됩니다. 256 개의 심볼이 16 개의 범위로 나뉘며 해당 블록 내에서 심볼이 사용되는 경우에만 16 비트 배열이 포함됩니다. 이러한 16 개 범위 각각의 존재는 전면에 추가 16 비트 비트 배열로 표시됩니다.

총 비트 맵은 32 비트에서 272 비트 사이의 저장소 (4–34 바이트)를 사용합니다. 대조적으로, DEFLATE 알고리즘은 실행 길이 인코딩과 추가 Huffman 코딩을 사용하여 비트 길이가 0 인 심볼을 인코딩하여 심볼이 없음을 보여줍니다.