bzip, 코드 압축에서 최고의 효율을 자랑하는 알고리즘!
by DD
2개월 전
조회수 8
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와 유사한 압축률을 달성한다.
