압축 알고리즘 Run-Length Encoding (RLE)

압축 알고리즘 Run-Length Encoding (RLE)

1. 개요

Run-Length Encoding(RLE)은 데이터 압축 기법 중 하나로, 연속적으로 반복되는 데이터를 효율적으로 저장하는 방식입니다. 특히 이미지, 텍스트 및 신호 데이터와 같이 동일한 값이 연속적으로 나타나는 데이터에서 높은 압축 효율을 보입니다.

2. 원리 및 구조

RLE의 기본 원리는 동일한 문자가 연속적으로 나타날 경우, 해당 문자와 반복 횟수를 함께 저장하는 것입니다. 예를 들어, 다음과 같은 문자열이 있다고 가정합니다.

AAABBBCCDAA

이 문자열을 RLE 방식으로 인코딩하면 다음과 같이 표현할 수 있습니다.

A3B3C2D1A2

이러한 방식으로 데이터를 압축하면, 데이터의 크기를 줄일 수 있습니다. 그러나 모든 경우에서 압축 효율이 좋은 것은 아니며, 단일 문자 또는 서로 다른 문자가 많이 포함된 데이터에서는 오히려 원본보다 커질 수도 있습니다.

3. 이미지 데이터 압축 적용 예제

RLE는 1비트 흑백 이미지, 팔레트 기반 이미지 형식(BMP, PCX 등)에서 자주 사용됩니다. 예를 들어, 다음과 같은 4x4 픽셀의 흑백 이미지를 생각해 보겠습니다.

11110000
11110000
00001111
00001111

이 이미지를 RLE 방식으로 압축하면 다음과 같이 표현할 수 있습니다.

1 4, 0 4,
1 4, 0 4,
0 4, 1 4,
0 4, 1 4

이러한 방식은 동일한 값이 연속적으로 나오는 경우 데이터 저장 공간을 줄이는 데 유용합니다.

4. 구현 예제

RLE 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있습니다. 여기에서는 Java, C, Python을 이용한 예제를 살펴보겠습니다.

4.1 Java 구현 예제

public class RunLengthEncoding {
    public static String encode(String input) {
        StringBuilder encoded = new StringBuilder();
        int count;
        for (int i = 0; i < input.length(); i++) {
            count = 1;
            while (i + 1 < input.length() && input.charAt(i) == input.charAt(i + 1)) {
                count++;
                i++;
            }
            encoded.append(input.charAt(i)).append(count);
        }
        return encoded.toString();
    }

    public static void main(String[] args) {
        String input = "AAABBBCCDAA";
        System.out.println("Encoded: " + encode(input));
    }
}

4.2 C 구현 예제

#include <stdio.h>
#include <string.h>

void encode(char *input) {
    int length = strlen(input);
    for (int i = 0; i < length; i++) {
        int count = 1;
        while (i + 1 < length && input[i] == input[i + 1]) {
            count++;
            i++;
        }
        printf("%c%d", input[i], count);
    }
    printf("\n");
}

int main() {
    char input[] = "AAABBBCCDAA";
    printf("Encoded: ");
    encode(input);
    return 0;
}

5. 결론

Run-Length Encoding(RLE)은 간단한 알고리즘이지만, 반복되는 데이터에서 매우 효율적인 압축 효과를 발휘할 수 있습니다. 특히 이미지 및 신호 데이터와 같이 동일한 값이 연속적으로 반복되는 경우에 유용하게 적용할 수 있습니다. 하지만 다양한 데이터 패턴에 대해 항상 압축 효율이 높다고 할 수는 없으므로, 적용 전에 데이터 특성을 고려하는 것이 중요합니다.