bzip2, 코드 압축에서 xz, zstd를 뛰어넘다!

bzip2는 LZ77 방식 대신 BWT(Burrows-Wheeler Transform)를 사용하여 텍스트 데이터를 압축한다. BWT는 텍스트 내 문자를 재정렬하여 유사한 문자를 인접하게 배치한다. LZ77 방식은 반복되는 문자열을 참조하지만, BWT는 문맥을 기반으로 압축하므로, 코드와 같은 텍스트 데이터에 효과적이다. 특히, BWT는 런-렝스 인코딩(Run-Length Encoding)을 통해 간단하게 압축할 수 있어, 압축률과 디코딩 속도를 모두 잡을 수 있다.

저자는 bzip2를 gzip, zstd, xz, brotli, lzip 등과 비교하여 bzip2의 장점을 강조한다. 특히, 코드 압축 시 bzip2가 다른 알고리즘보다 높은 압축률을 보이며, 디코더 크기도 작다는 점을 강조한다. gzip은 속도가 빠르지만, 압축률이 낮고, zstd, brotli는 압축률이 높지만, 디코더 크기가 크고, 디코딩 속도가 느리다. bzip2는 이러한 단점을 보완하여, 코드 압축에 최적화된 알고리즘으로 평가받는다.

저자는 bzip2 디코더의 크기가 다른 알고리즘에 비해 작다는 점을 강조한다. LZ77 기반 알고리즘은 토큰 인코딩에 많은 공간을 사용하지만, bzip2는 BWT와 MTF, RLE, Huffman 코딩을 결합하여 디코더 크기를 줄인다. 특히, 단일 Huffman 테이블을 사용하면 디코더 크기를 1.5KB까지 줄일 수 있다. 이는 xz, lzip보다 작고, 디코딩 속도도 빠르다. 고수준 언어에서 bzip2의 디코딩 속도는 더욱 향상된다.

bzip3는 bzip2보다 압축률이 높지만, 디코딩 속도가 느리고, bit-by-bit 코딩으로 인해 복잡도가 높다. bzip3는 bzip2와 달리 다양한 압축 레벨을 지원하지 않는다. 저자는 bzip3의 bit-by-bit 코딩 방식이 디코딩 속도를 저하시킨다고 분석하며, bzip2의 성능을 선호한다. bzip2는 성능과 압축률의 균형을 이루는 반면, bzip3는 압축률에 더 중점을 둔 것으로 평가된다.