허프만(Huffman) 알고리즘

📌 허프만 알고리즘이란?

 

압축 단위마다 문자의 출현 빈도를 조사하여 빈도가 높은 순서대로 비트 수가 적은 부호를 부여함으로써 데이터를 압축하는 방식

 

즉, 많이 사용된 문자는 더 적은 비트로 나타내고, 적게 사용된 문자는 더 많은 비트를 사용하여 효율적으로 문자열을 나타내는 방식을 말한다.

 

🧩 문자 압축 예제

 

AAAAAABBBBCDD => 'A' 6개, 'B' 4개, 'C' 1개, 'D' 2개

 

🏃‍♂️ 항 합치기

 

가장 적은 사용 빈도를 가진 두 항을 묶고 그 합을 적어준다.

 

 

이와 같이 한번 더 묶는다.

 

 

마지막 남은 A까지 묶어주면 다음과 같은 그림이 나온다.

 

 

🏃‍♂️ 비트 부여하기

 

루트 노드를 기준으로 왼쪽으로 한번 가면 0, 오른쪽으로 가면 1이라고 하겠다.

 

• A ➡ 0
• B ➡ 10
• C ➡ 110
• D ➡ 111

 

이를 사용하여 AAAAAABBBBCDD는 00000010101010110111111이 된다.

 

이처럼 문자의 사용 빈도를 이용하여 문자열을 압축하는 알고리즘이 허프만 알고리즘이다.

 

🔎 특징

 

✅ 모호성 제거

 

만약 다음과 같은 가변 길이 코드 변환 규칙이 있다고 하자.

 

{A, B, C, D} => {0, 01, 10, 1}

 

이때, AB와 AAD는 '001'로 동일하게 표현되기 때문에 모호성이 발생한다. 이를 해결하기 위해서는 어떠한 문자도 다른 문자의 prefix를 가지지 않으면 된다.

 

위에서 살펴봤던 허프만 코드는 이렇다.

 

{A, B, C, D} => {0, 10, 110, 111}

 

위와 같이 표기할 경우 어떠한 문자도 다른 문자의 prefix가 되는 경우가 없다. 따라서 허프만 코드는 모호성이 없다.

 

✅ 공간 절약

 

아래와 같은 빈도의 문자열이 있다고 하자.

 

문자	빈도	fixed-length	variable-length
A	60%	00	0
B	25%	01	10
C	10%	10	110
D	5%	11	111

 

fixed-length 코드를 사용하면 2비트만을 필요로 하기 때문에 공간적인 측면에서 절약이 가능하지만 모호성이 발생할 수 있다. 반면, variable-length 코드를 사용하면 1 ~ 3비트를 사용하므로 공간적인 절약을 항상 보장할 수 없지만 prefix-free 코드이므로 모호성이 발생하지 않는다.

 

하지만 variable-length 코드는 문자 출현 빈도에 따라 나타내는 비트 수가 다르기 때문에 평균적으로 1.55의 공간을 필요로 한다. 따라서 평균적으로는 fixed-length 코드의 평균 2보다 더 나은 효율성을 보인다.

 

🔨 구현

 

허프만 알고리즘은 Heap을 통해 구현된다. 그래서 힙으로 구현된 우선순위 큐를 이용하여 구현할 수 있다.

 

먼저 문자의 빈도 수에 따른 이진 트리를 생성하기 위해 아래와 같이 Node 클래스를 작성한다.

 

class Node {
    char word;
    int freq;
    Node left = null, right = null;
    
    Node(char word, int freq) {
        this.word = word;
        this.freq = freq;
    }
    
    Node(Node left, Node right) {
        this.freq = left.freq + right.freq; //항 합치기
        this.left = left;
        this.right = right;
    }
}

 

 

각 단어의 빈도를 집계하는 Map을 생성한다.

 

각 Node의 빈도 수가 적은 것부터 추출하기 위해 우선순위 큐를 이용하여 이진 트리를 생성한다.

 

poll()을 수행할 때마다 빈도 수가 적은 것부터 추출되고, 이를 다시 합쳐서 큐에 넣는 작업을 반복한다.

 

압축 결과를 출력하기 위해 optBits에 집계한 최적 비트를 통해 원본(txt)를 수정한다.

 

public void HuffmanCoding(String txt) {
    Map<Character, Integer> stat = new HashMap<>();
    for (char c : txt.toCharArray()) {
        stat.put(c, stat.getOrDefault(c, 0) + 1); //누적
    }
    
    //우선순위 큐를 통해 정렬
    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.freq));
    for (Map.Entry<Character, Integer> entry : stat.entrySet()) {
        pq.add(new Node(entry.getKey(), entry.getValue()));
    }
    
    //허프만 알고리즘에 따른 이진 트리 생성
    while (pq.size() > 1) {
        Node left = pq.poll();
        Node right = pq.poll();
        pq.add(new Node(left, right));
    }
    
    printCompression(pq.peek(), "");
    
    for (Map.Entry<String, String> entry : optBits.entrySet()) {
        txt = txt.replaceAll(entry.getKey(), entry.getValue());
    }

    System.out.println("압축 결과: " + txt);
}

 

이진 트리에서 왼쪽으로 이동할 때마다 '0'을 부여하고, 오른쪽으로 이동할 때마다 '1'을 부여했다.

 

노드의 좌우가 null이라는 것은 리프 노드에 도달했음을 의미하므로 출력을 수행한다. 이때, optBits 맵에 각 단어에 대한 variable-length 코드를 저장한다.

 

private static void printCompression(Node node, String comp) {
    if (node == null) return;
    
    //리프 노드에 도달한 경우 출력
    if (node.left = null && node.right == null) {
        optBits.put(node.word + "", comp); //압축 결과를 출력하기 위해 Map에 저장
        System.out.println(node.word + "-> " + comp);
    }
    
    //비트 압축
    printCompression(node.left, comp + "0");
    printCompression(node.right, comp + "1");
}

 

public class Huffman {

    static Map<String, String> optBits = new HashMap<>();

    ...

    public static void main(String[] args) {
        Huffman o = new Huffman();
        o.HuffmanCoding("AAAAAABBBBCDD");
    }
    
}

 

"AAAAAABBBBCDD"에 대해 부여된 최적 이진 코드

 

이 결과는 아래와 같은 이진 트리가 만들어진 케이스다.

 

 

그래서 최적 이진 코드는 하나의 케이스만 나오지 않는다.

 

이처럼 허프만 알고리즘은 그리디 알고리즘으로 그리디 선택 속성과 최적 부분 구조 조건을 만족하는 경우 최적화 문제를 효율적으로 해결할 수 있다.

 

References:

 

https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-13975%EB%B2%88-%ED%8C%8C%EC%9D%BC-%ED%95%A9%EC%B9%98%EA%B8%B0-3-java

백준 13975번 : 파일 합치기 3 java

 

https://yozm.wishket.com/magazine/detail/2478/

탐욕 알고리즘과 허프만 코딩 구현 방법 | 요즘IT

 

https://mirrorofcode.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Huffman-code-%ED%97%88%ED%94%84%EB%A7%8C%EC%BD%94%EB%93%9C

[알고리즘] Huffman code / 허프만코드