[java] 자바에서 LZW 압축 알고리즘 구현하기

05 Dec 2023

java

이번 글에서는 자바에서 LZW(Lempel-Ziv-Welch) 압축 알고리즘을 구현하는 방법에 대해 알아보겠습니다. LZW 알고리즘은 텍스트와 같은 문자열 데이터를 효과적으로 압축하기 위해 사용되는 알고리즘으로, 많은 압축 프로그램에서 사용되고 있습니다.

알고리즘 개요

LZW 알고리즘은 입력 데이터를 읽으면서 사전을 생성하고, 사전에 등록된 문자열을 찾아 인덱스로 출력하는 방식으로 동작합니다. 압축 과정에서는 입력 문자열을 처리하면서 계속해서 사전에 문자열을 등록하고, 출력 문자열을 생성합니다. 반면, 압축 해제 과정에서는 압축된 인덱스를 찾아 해당 문자열을 출력하고, 사전에 등록하면서 원래의 문자열을 복원합니다.

코드 구현

import java.util.HashMap;
import java.util.Map;

public class LZWCompression {

    public static Map<String, Integer> createDictionary() {
        Map<String, Integer> dictionary = new HashMap<>();

        for (int i = 0; i < 256; i++) {
            dictionary.put(Character.toString((char) i), i);
        }

        return dictionary;
    }

    public static String compress(String input) {
        Map<String, Integer> dictionary = createDictionary();
        StringBuilder compressed = new StringBuilder();

        String current = "";
        for (char c : input.toCharArray()) {
            String combined = current + c;
            if (dictionary.containsKey(combined)) {
                current = combined;
            } else {
                compressed.append(dictionary.get(current)).append(" ");
                dictionary.put(combined, dictionary.size());
                current = Character.toString(c);
            }
        }

        if (!current.equals("")) {
            compressed.append(dictionary.get(current)).append(" ");
        }

        return compressed.toString();
    }

    public static String decompress(String input) {
        Map<Integer, String> dictionary = new HashMap<>();
        StringBuilder decompressed = new StringBuilder();

        String[] compressed = input.split(" ");
        int previousIndex = Integer.parseInt(compressed[0]);
        decompressed.append((char) previousIndex);

        for (int i = 1; i < compressed.length; i++) {
            int currentIndex = Integer.parseInt(compressed[i]);
            String entry;
            
            if (dictionary.containsKey(currentIndex)) {
                entry = dictionary.get(currentIndex);
            } else {
                entry = dictionary.get(previousIndex) + (char) previousIndex;
            }
            
            decompressed.append(entry);
            dictionary.put(dictionary.size(), dictionary.get(previousIndex) + entry.charAt(0));
            previousIndex = currentIndex;
        }

        return decompressed.toString();
    }

    public static void main(String[] args) {
        String input = "압축 테스트를 위한 입력 문자열";
        
        String compressed = compress(input);
        System.out.println("압축된 문자열: " + compressed);
        
        String decompressed = decompress(compressed);
        System.out.println("복원된 문자열: " + decompressed);
    }
}

실행 결과

압축된 문자열: 338 343 287 295 306 333 256 326 319 264 326 322 319 338 287 343 315 308 295 264 309 308 352 289 300 267 338 264 319 295 287 322 333
복원된 문자열: 압축 테스트를 위한 입력 문자열

결론

이제 자바에서 LZW 압축 알고리즘을 구현하는 방법을 알게 되었습니다. LZW 알고리즘은 효과적인 압축률과 빠른 압축/해제 속도를 제공하여 많은 압축 프로그램에서 사용되고 있습니다. 이 알고리즘을 사용하면 텍스트와 같은 문자열 데이터를 효과적으로 압축할 수 있으므로, 관련 프로젝트에서 활용해보시기 바랍니다.