bzip, 코드 압축에서 최고의 효율을 자랑하는 알고리즘!
bzip은 LZ77 기반의 다른 압축 알고리즘과 달리, BWT(Burrows-Wheeler Transform)를 사용하여 텍스트 데이터를 압축하여 코드 압축에 특화됨
bzip2는 327KB Lua 코드 파일을 63.7KB로 압축하여, zstd, xz, brotli 등 다른 압축 방식보다 뛰어난 성능을 보임
bzip은 런타임 성능(Runtime Performance)을 위해 단일 Huffman 테이블을 사용하며, 디코더 크기가 작아 임베디드 환경에 적합함
BWT 기반 압축은 텍스트 데이터의 반복 패턴을 효율적으로 처리하지만, 다양한 언어 혼합 시 성능 저하 가능성이 존재함
bzip의 BWT(Burrows-Wheeler Transform) 압축 방식
bzip은 LZ77 기반의 압축 방식과 달리 BWT(Burrows-Wheeler Transform)를 핵심 기술로 사용한다. BWT는 텍스트 내 문자를 문맥별로 재정렬하여 반복되는 패턴을 묶어 압축 효율을 높인다. 특히, 코드와 같이 텍스트 성격의 데이터에서 뛰어난 성능을 보이며, LZ77 방식보다 압축률(Compression Ratio)을 향상시킨다. BWT는 텍스트의 반복되는 부분을 효율적으로 처리하여, 런-렝스 인코딩(Run-Length Encoding)과 같은 간단한 기법으로 압축할 수 있도록 돕는다. 하지만, 서로 다른 언어의 텍스트가 혼합된 경우 성능 저하가 발생할 수 있다.
bzip2와 bzip3의 성능 비교
bzip2와 bzip3는 BWT를 기반으로 하지만, BWT 출력의 압축 방식에서 차이를 보인다. bzip2는 RLE(Run-Length Encoding)의 변형을 사용하고, bzip3는 더 지능적인 방식을 시도한다. 저자는 성능상의 이유로 bzip2를 선택했으며, bzip2는 다양한 압축 레벨을 지원하는 LZ77 방식과 달리, 결정적(Deterministic)이고 휴리스틱(Heuristics)이 적어 일관된 압축 결과를 제공한다. bzip2는 -9 옵션을 사용해도 큰 차이가 없으며, bzip3는 파라미터 없이도 bzip2와 유사한 압축률을 달성한다.
디코더 크기 및 성능 분석
bzip은 다른 압축 방식에 비해 작은 디코더 크기를 가진다. gzip, zstd, xz, brotli, lzip 등은 LZ77 기반으로, Huffman 코딩, FSE(Finite State Entropy) 등을 사용하며, 디코더 크기가 1.5KB에서 3KB에 이른다. 반면, bzip2는 MTF(Move-to-Front), RLE, Huffman 코딩을 사용하며, 단일 Huffman 테이블을 사용하면 디코더 크기를 1.5KB로 줄일 수 있다. bzip은 압축 속도가 느리다는 단점이 있지만, 코드 압축과 같이 압축률(Compression Ratio)이 중요한 경우, 디코딩 속도보다 압축 효율(Compression Efficiency)이 더 중요한 요소가 될 수 있다.
코드 압축에서의 bzip의 강점
bzip은 텍스트 및 코드 압축에 특화되어 있으며, LZ77 기반의 압축 방식보다 더 나은 압축률을 제공한다. 특히, 코드와 같이 구조화된 데이터에서 반복되는 패턴을 효율적으로 처리한다. 저자는 bzip을 사용하여 ComputerCraft의 Lua 코드 파일을 압축하고, 다른 압축 방식과의 비교를 통해 bzip의 우수성을 입증했다. SQLite 데이터베이스 파일 압축에서도 bzip이 zstd, deflate, LZMA2보다 우수한 성능을 보였다는 댓글이 이를 뒷받침한다.
