Bzip2 압축 알고리즘

Bzip2 압축 알고리즘

1. 개요

Bzip2는 무손실 데이터 압축 알고리즘으로, Burrows-Wheeler 변환(BWT)과 무브 투 프론트 변환(MTF) 등의 기법을 활용하여 높은 압축률을 제공합니다. 이 알고리즘은 gzip보다 높은 압축률을 제공하며, 텍스트 파일과 같은 반복 패턴이 많은 데이터에서 특히 효과적입니다.

2. Bzip2의 동작 원리

Bzip2는 여러 단계의 변환을 거쳐 데이터를 압축합니다. 주요 단계는 다음과 같습니다.

2.1 Burrows-Wheeler 변환 (BWT)

Burrows-Wheeler 변환은 입력 문자열의 모든 회전(rotation)을 생성한 후 이를 사전 순으로 정렬하고 마지막 열을 추출하는 방식으로 동작합니다. 이 변환을 통해 데이터의 연속적인 패턴이 강조되어 후속 압축 단계에서 더 효율적으로 처리할 수 있습니다.

2.2 무브 투 프론트 변환 (MTF)

무브 투 프론트 변환은 반복되는 문자를 효율적으로 인코딩하기 위해 사용됩니다. 기존 문자 리스트에서 현재 문자의 위치를 찾아 해당 문자를 리스트의 맨 앞으로 이동시키는 방식으로 수행됩니다. 이렇게 하면 동일한 문자가 반복될 경우 낮은 숫자로 표현될 가능성이 높아집니다.

2.3 런렝스 인코딩 (RLE)

무브 투 프론트 변환을 거친 데이터는 연속된 같은 값이 많아지므로, 이를 런렝스 인코딩(RLE)을 적용하여 더 작은 크기로 줄일 수 있습니다.

2.4 허프만 코딩

허프만 코딩은 가변 길이 인코딩 방식으로, 자주 등장하는 문자에 짧은 비트 시퀀스를 할당하여 전체 데이터 크기를 줄이는 역할을 합니다. Bzip2는 보통 2차원 허프만 코딩을 적용하여 압축 효율을 더욱 높입니다.

3. Bzip2 구현 예제

Bzip2 알고리즘을 구현하는 방법을 Java와 C 언어를 사용하여 설명하겠습니다.

3.1 Java를 이용한 Bzip2 압축 및 해제 예제

Java에서는 Apache Commons Compress 라이브러리를 활용하여 Bzip2 압축을 쉽게 수행할 수 있습니다.

import java.io.*;
import org.apache.commons.compress.compressors.bzip2.BZip2CompressorOutputStream;
import org.apache.commons.compress.compressors.bzip2.BZip2CompressorInputStream;

public class Bzip2Example {
    public static void compressFile(String inputFile, String outputFile) throws IOException {
        try (FileInputStream fis = new FileInputStream(inputFile);
             FileOutputStream fos = new FileOutputStream(outputFile);
             BZip2CompressorOutputStream bzip2Out = new BZip2CompressorOutputStream(fos)) {
            byte[] buffer = new byte[1024];
            int bytesRead;
            while ((bytesRead = fis.read(buffer)) != -1) {
                bzip2Out.write(buffer, 0, bytesRead);
            }
        }
    }

    public static void decompressFile(String inputFile, String outputFile) throws IOException {
        try (FileInputStream fis = new FileInputStream(inputFile);
             BZip2CompressorInputStream bzip2In = new BZip2CompressorInputStream(fis);
             FileOutputStream fos = new FileOutputStream(outputFile)) {
            byte[] buffer = new byte[1024];
            int bytesRead;
            while ((bytesRead = bzip2In.read(buffer)) != -1) {
                fos.write(buffer, 0, bytesRead);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String originalFile = "example.txt";
        String compressedFile = "example.txt.bz2";
        String decompressedFile = "example_decompressed.txt";

        compressFile(originalFile, compressedFile);
        System.out.println("파일이 성공적으로 압축되었습니다.");

        decompressFile(compressedFile, decompressedFile);
        System.out.println("파일이 성공적으로 압축 해제되었습니다.");
    }
}

3.2 C 언어를 이용한 Bzip2 압축 및 해제 예제

C에서는 bzip2 라이브러리를 활용하여 파일을 압축하고 해제할 수 있습니다.

#include <stdio.h>
#include <stdlib.h>
#include <bzlib.h>

void compressFile(const char *inputFile, const char *outputFile) {
    FILE *in = fopen(inputFile, "rb");
    FILE *out = fopen(outputFile, "wb");
    if (!in || !out) {
        perror("파일을 열 수 없습니다");
        exit(EXIT_FAILURE);
    }

    BZFILE *bzOut = BZ2_bzWriteOpen(NULL, out, 9, 0, 0);
    if (!bzOut) {
        perror("BZ2 스트림을 열 수 없습니다");
        exit(EXIT_FAILURE);
    }

    char buffer[1024];
    int bytesRead;
    while ((bytesRead = fread(buffer, 1, sizeof(buffer), in)) > 0) {
        BZ2_bzWrite(NULL, bzOut, buffer, bytesRead);
    }

    BZ2_bzWriteClose(NULL, bzOut, 0, NULL, NULL);
    fclose(in);
    fclose(out);
}

void decompressFile(const char *inputFile, const char *outputFile) {
    FILE *in = fopen(inputFile, "rb");
    FILE *out = fopen(outputFile, "wb");
    if (!in || !out) {
        perror("파일을 열 수 없습니다");
        exit(EXIT_FAILURE);
    }

    BZFILE *bzIn = BZ2_bzReadOpen(NULL, in, 0, 0, NULL, 0);
    if (!bzIn) {
        perror("BZ2 스트림을 열 수 없습니다");
        exit(EXIT_FAILURE);
    }

    char buffer[1024];
    int bytesRead;
    while ((bytesRead = BZ2_bzRead(NULL, bzIn, buffer, sizeof(buffer))) > 0) {
        fwrite(buffer, 1, bytesRead, out);
    }

    BZ2_bzReadClose(NULL, bzIn);
    fclose(in);
    fclose(out);
}

int main() {
    compressFile("example.txt", "example.txt.bz2");
    printf("파일이 성공적으로 압축되었습니다.\n");

    decompressFile("example.txt.bz2", "example_decompressed.txt");
    printf("파일이 성공적으로 압축 해제되었습니다.\n");

    return 0;
}

4. 마무리

Bzip2는 높은 압축률을 제공하는 강력한 알고리즘으로, 여러 변환 기법을 결합하여 데이터를 효과적으로 줄입니다. Java와 C 언어를 활용하여 Bzip2 압축 및 해제 기능을 쉽게 구현할 수 있으며, 실제 응용에서는 다양한 파일 포맷을 처리하는 데 활용할 수 있습니다.