압축 알고리즘 — 허프만에서 gzip까지, HTTP 압축의 원리

문자열: "AABABCAAB"

빈도: A=5, B=3, C=1

고정 길이: A=00, B=01, C=10 → 9 × 2 = 18비트
허프만:     A=0,  B=10, C=11 → 5×1 + 3×2 + 1×2 = 13비트
                                          절약: 약 28%

public class HuffmanCoding {
    static class Node implements Comparable<Node> {
        char ch;
        int freq;
        Node left, right;

        Node(char ch, int freq) { this.ch = ch; this.freq = freq; }

        @Override
        public int compareTo(Node o) { return this.freq - o.freq; }
    }

    public Map<Character, String> buildCodes(String text) {
        // 1. 빈도 계산
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : text.toCharArray()) {
            freq.merge(c, 1, Integer::sum);
        }

        // 2. 우선순위 큐로 허프만 트리 구성
        PriorityQueue<Node> pq = new PriorityQueue<>();
        freq.forEach((ch, f) -> pq.offer(new Node(ch, f)));

        while (pq.size() > 1) {
            Node left = pq.poll();  // 빈도 가장 낮은 두 개를
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq);
            parent.left = left;     // 합쳐서 새 노드 생성
            parent.right = right;
            pq.offer(parent);
        }

        // 3. 트리를 순회하며 코드 생성
        Map<Character, String> codes = new HashMap<>();
        buildCodesRecursive(pq.poll(), "", codes);
        return codes;
    }

    private void buildCodesRecursive(Node node, String code, Map<Character, String> codes) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            codes.put(node.ch, code.isEmpty() ? "0" : code);
            return;
        }
        buildCodesRecursive(node.left, code + "0", codes);
        buildCodesRecursive(node.right, code + "1", codes);
    }
}

A=0, B=10, C=11

인코딩: 01010110 → 0|10|10|11|0 → ABBCA
모호함 없음!

텍스트: "ABCABCABC"

처리:
위치 0: A → (0, 0, 'A')  새 문자
위치 1: B → (0, 0, 'B')  새 문자
위치 2: C → (0, 0, 'C')  새 문자
위치 3: ABCABC → (3, 6, ?)  3글자 전에서 6글자 복사!

// LZ77 개념적 인코딩
public List<int[]> compress(String text) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    int windowSize = 4096; // 탐색 윈도우 크기

    while (i < text.length()) {
        int bestDist = 0, bestLen = 0;

        // 슬라이딩 윈도우에서 가장 긴 매칭 찾기
        int searchStart = Math.max(0, i - windowSize);
        for (int j = searchStart; j < i; j++) {
            int len = 0;
            while (i + len < text.length() &&
                   text.charAt(j + len) == text.charAt(i + len)) {
                len++;
            }
            if (len > bestLen) {
                bestLen = len;
                bestDist = i - j;
            }
        }

        if (bestLen > 2) { // 매칭이 충분히 길면 참조
            result.add(new int[]{bestDist, bestLen});
            i += bestLen;
        } else { // 리터럴(원래 문자 그대로)
            result.add(new int[]{0, text.charAt(i)});
            i++;
        }
    }
    return result;
}

1단계: LZ77으로 중복 문자열을 (거리, 길이) 쌍으로 치환
2단계: 허프만 코딩으로 결과를 최적 인코딩

원본 → [LZ77] → 중간 표현 → [허프만] → 압축 데이터

클라이언트 → 서버:
  Accept-Encoding: gzip, deflate, br

서버 → 클라이언트:
  Content-Encoding: gzip
  (압축된 응답 본문)

# application.yml
server:
  compression:
    enabled: true
    mime-types: application/json,application/xml,text/html,text/plain
    min-response-size: 1024   # 1KB 이상인 응답만 압축

// 프로그래밍 방식
@Bean
public WebServerFactoryCustomizer<ConfigurableServletWebServerFactory> customizer() {
    return factory -> {
        Compression compression = new Compression();
        compression.setEnabled(true);
        compression.setMimeTypes(new String[]{
            "application/json", "text/html", "text/plain"
        });
        compression.setMinResponseSize(DataSize.ofKilobytes(1));
        factory.setCompression(compression);
    };
}

✓ 압축해야 할 것: JSON, HTML, CSS, JS, XML, SVG
✗ 압축하면 안 되는 것: JPEG, PNG, MP4 (이미 압축됨 → 오히려 커질 수 있음)

// Java에서 GZip 압축
try (GZIPOutputStream gzip = new GZIPOutputStream(new FileOutputStream("app.log.gz"))) {
    gzip.write(logData.getBytes());
}