LZ77, LZ78 및 LZW 알고리즘

LZ77, LZ78 및 LZW 알고리즘

데이터 압축은 데이터를 보다 효율적으로 저장하고 전송하기 위해 필수적인 기술입니다. 특히, 텍스트 데이터를 압축하는 기술은 파일 크기를 줄이고 네트워크 전송 속도를 향상시키는 데 중요한 역할을 합니다. 본 글에서는 대표적인 사전 기반 압축 알고리즘인 LZ77, LZ78 및 LZW에 대해 설명하고, 각 알고리즘의 차이점을 비교한 후, 실제 구현 예제를 살펴보겠습니다.

---

LZ77 알고리즘

LZ77 알고리즘은 1977년 Jacob Ziv와 Abraham Lempel이 제안한 무손실 데이터 압축 알고리즘입니다. LZ77은 슬라이딩 윈도우(sliding window) 기법을 사용하여 반복되는 문자열을 찾아 참조(reference)로 변환합니다.

동작 원리

1. 슬라이딩 윈도우: 데이터를 일정한 크기의 윈도우(lookahead buffer와 search buffer)로 나눕니다.
2. 반복 패턴 탐색: 검색 버퍼에서 lookahead 버퍼와 일치하는 가장 긴 문자열을 찾습니다.
3. 토큰 생성: (offset, length, next character) 형식의 토큰을 생성하여 데이터를 압축합니다.
4. 윈도우 이동: 압축된 데이터만큼 윈도우를 이동하고 반복합니다.

이 방식은 긴 문자열을 압축하는 데 효과적이며, ZIP 및 PNG 포맷과 같은 다양한 파일 형식에서 사용됩니다.

---

LZ78 알고리즘

LZ78은 1978년 Ziv와 Lempel이 발표한 알고리즘으로, LZ77과 다르게 사전(dictionary) 기반 압축 방식을 사용합니다. LZ78은 데이터를 처리하면서 새로운 문자열 패턴을 사전에 저장하고, 이후 반복되는 패턴을 참조하여 데이터를 압축합니다.

동작 원리

1. 사전 초기화: 처음에는 빈 사전에서 시작합니다.
2. 문자열 검색 및 추가: 입력 데이터에서 현재까지 발견되지 않은 문자열을 찾습니다.
3. 토큰 생성: (사전 인덱스, 새로운 문자) 형식의 토큰을 생성합니다.
4. 사전 업데이트: 새로운 문자열을 사전에 추가하고, 반복합니다.

LZ78은 LZ77보다 구현이 간단하며, GIF 및 TIFF와 같은 포맷에서 사용됩니다.

---

LZ77과 LZ78의 차이점

구분	LZ77	LZ78
압축 방식	슬라이딩 윈도우 사용	사전(dictionary) 사용
참조 방식	윈도우 내에서 과거 데이터를 참조	새로운 문자열을 사전에 저장하고 참조
메모리 사용량	상대적으로 큼	상대적으로 작음
압축 성능	중복 패턴이 많을 때 효과적	짧은 패턴의 반복이 많을 때 효과적

LZ77은 최근 데이터를 기반으로 압축을 수행하는 반면, LZ78은 발견된 패턴을 사전에 저장하고 참조하는 방식으로 차별화됩니다.

---

LZW 알고리즘

LZW(Lempel-Ziv-Welch) 알고리즘은 LZ78의 개선된 형태로, 1984년 Terry Welch가 개발하였습니다. LZW는 초기 사전을 알파벳 문자로 시작하고, 압축 과정에서 패턴을 추가하여 압축률을 향상시킵니다.

동작 원리

1. 초기화: 기본 알파벳 문자로 이루어진 사전 생성
2. 입력 데이터 검색: 가장 긴 문자열 패턴을 사전에서 찾음
3. 토큰 출력: 해당 패턴의 사전 인덱스를 출력
4. 사전 추가: 새로운 문자열 패턴을 사전에 추가
5. 반복 수행: 입력 데이터가 끝날 때까지 반복

LZW는 GIF, TIFF, PDF 등의 다양한 파일 포맷에서 사용되며, 하드웨어 구현에도 적합한 효율적인 알고리즘입니다.

---

텍스트 데이터 압축에 대한 적용

LZ77, LZ78 및 LZW는 텍스트 데이터 압축에서 매우 효과적입니다. 예를 들어, 중복이 많은 문서를 압축할 때 압축률이 높아지며, 사전 기반 압축을 사용하면 특정 문맥에서 반복되는 단어를 효율적으로 저장할 수 있습니다.

적용 사례

1. 파일 압축: ZIP, GZIP, 7z 등의 파일 포맷
2. 이미지 압축: GIF, PNG
3. 네트워크 데이터 전송: HTTP/2 헤더 압축 (HPACK)
4. 데이터베이스 저장 최적화

이러한 압축 기술은 텍스트 데이터의 크기를 줄이고, 저장 공간과 전송 시간을 절약하는 데 기여합니다.

---

구현 예제

아래는 LZW 알고리즘의 Java 및 C 언어 구현 예제입니다.

Java 구현

import java.util.*;

public class LZWCompression {
    public static List<Integer> compress(String input) {
        Map<String, Integer> dictionary = new HashMap<>();
        for (int i = 0; i < 256; i++) {
            dictionary.put("" + (char) i, i);
        }

        List<Integer> output = new ArrayList<>();
        String current = "";
        int dictSize = 256;

        for (char c : input.toCharArray()) {
            String newStr = current + c;
            if (dictionary.containsKey(newStr)) {
                current = newStr;
            } else {
                output.add(dictionary.get(current));
                dictionary.put(newStr, dictSize++);
                current = "" + c;
            }
        }
        if (!current.equals("")) {
            output.add(dictionary.get(current));
        }
        return output;
    }

    public static void main(String[] args) {
        String input = "ABABABABA";
        System.out.println(compress(input));
    }
}

C 구현

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

#define MAX_DICT_SIZE 4096 // 최대 사전 크기
#define MAX_INPUT_SIZE 1024

typedef struct {
    char *key;
    int code;
} DictionaryEntry;

DictionaryEntry dictionary[MAX_DICT_SIZE];
int dict_size = 256; // 기본 ASCII 문자만 초기 사전으로 사용

// 사전 초기화
void initializeDictionary() {
    for (int i = 0; i < 256; i++) {
        dictionary[i].key = (char *)malloc(2);
        dictionary[i].key[0] = (char)i;
        dictionary[i].key[1] = '\0';
        dictionary[i].code = i;
    }
}

// 사전에 문자열 추가
int addToDictionary(const char *key) {
    if (dict_size >= MAX_DICT_SIZE) return -1; // 사전이 가득 찼으면 추가 불가
    dictionary[dict_size].key = strdup(key);
    dictionary[dict_size].code = dict_size;
    return dict_size++;
}

// 사전에서 문자열 검색 (있으면 코드 반환, 없으면 -1)
int findInDictionary(const char *key) {
    for (int i = 0; i < dict_size; i++) {
        if (strcmp(dictionary[i].key, key) == 0) {
            return dictionary[i].code;
        }
    }
    return -1;
}

// LZW 압축 함수
void lzwCompress(const char *input) {
    char current[MAX_INPUT_SIZE] = "";
    char next[2] = "";
    int index = 0;

    printf("압축 결과: ");
    while (input[index] != '\0') {
        next[0] = input[index];
        next[1] = '\0';

        char temp[MAX_INPUT_SIZE];
        strcpy(temp, current);
        strcat(temp, next);

        if (findInDictionary(temp) != -1) {
            strcpy(current, temp);
        } else {
            printf("%d ", findInDictionary(current));
            addToDictionary(temp);
            strcpy(current, next);
        }
        index++;
    }
    printf("%d\n", findInDictionary(current));
}

// 메모리 해제
void freeDictionary() {
    for (int i = 0; i < dict_size; i++) {
        free(dictionary[i].key);
    }
}

int main() {
    char input[] = "ABABABABA";
    printf("LZW 압축 예제 (C)\n");
    printf("입력 데이터: %s\n", input);

    initializeDictionary();
    lzwCompress(input);
    freeDictionary();

    return 0;
}

---

결론

LZ77, LZ78 및 LZW 알고리즘은 텍스트 압축에서 중요한 역할을 합니다. 각각의 알고리즘은 특정한 상황에서 더 효과적일 수 있으며, GIF, ZIP, HTTP/2 헤더 압축과 같은 다양한 응용에서 활용되고 있습니다. 본 글에서는 각 알고리즘의 원리를 설명하고, Java 및 C 언어 구현 예제를 제공하였습니다. 이러한 기술을 활용하면 텍스트 데이터를 보다 효율적으로 저장하고 전송할 수 있습니다.