[자료구조/JAVA] 허프만 코딩 (Huffman Coding)

허프만 코딩

데이터 문자의 등장 빈도에 따라 다른 길이의 부호를 사용하여 데이터를 압축하는 알고리즘이다.

자주 등장하는 문자는 짧은 부호로, 드물게 등장하는 문자는 긴 부호로 표현하여 데이터의 크기를 줄이는 데 효과적이다.

알고리즘에서 우선순위 큐가 사용되며, 이를 기반으로 빈도 기반의 허프만 부호화를 효율적으로 수행할 수 있다.

Unix 파일압축 명령어에 사용, JPEG, MP3 압축하기 위한 서브루틴으로서도 활용된다.

 

 

---

허프만 코딩 : 과정 

 

1. 입력

압축할 데이터에 대해서 입력받는다.

AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE

 

---

2. 문자 빈도 분석 

압출할 데이터에서 각 문자의 등장 빈도를 분석한다.

• A : 15
• B : 7
• C : 6
• D : 6
• E : 5

 

---

3. 허프만 트리 생성

우선 빈도 수를 우선순위로 하는 우선순위 큐(최소 힙)을 구성하게 된다.

해당 힙에서 빈도가 가장 낮은 두 문자를 선택하여 하나의 부모 노드를 가진 허프만 트리를 만든다.

부모 노드의 빈도는 자식 노드 빈도의 합으로 설정하고 모든 문자가 하나의 트리로 합쳐질 때까지 반복한다.

 

1. 빈도수로 최소 힙을 생성한다.

 

2. 빈도수가 가장 낮은 두 문자를 선택하여 트리로 묶는다.

(D와 E가 6, 5 이므로 부모 노드의 빈도는 11로 설정된다.)

 

 

3. 다시 빈도수가 가장 낮은 두 문자를 선택하여 트리로 묶는다.

(15(A), 7(B), 6(C), 11(D,E) 중 가장 낮은 빈도수인 B,C를 묶는다.)

 

 

4. 마찬가지로 15(A), 13(B,C), 11(D,E) 중 가장 낮은 빈도수인 (B,C), (D,E)를 묶는다.

 

 

 

5.  마지막으로  15(A), 24(B,C,D,E)를 묶어 허프만 트리의 생성을 완료한다.

 

 

 

 

 

---

4. 부호 할당

 

왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1로 표현한다.

트리의 루트 노드부터 각 리프 노드까지 경로를 따라 0과 1을 연결하여 문자의 부호를 생성한다. 허프만 코딩의 부호는 접두 부호라는 특징이 있다.

 

접두 부호: 어떤 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호이다. 아래의 부호 할당 결과에는 '10'이 존재하지 않는 것을 알 수 있는데, 이는 '100'의 접두어가 되므로 겹칠 수 있기 때문이다.

 

A : 0

B : 100

C : 101

D : 110

E : 111

 

 

---

5. 압축 결과

AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE

-> 0000000000000000100100100100100100100101101101101101101110110110110110110111111111111111

 

 

 

---

허프만 코딩 : 구현

 

 

1. 빈도수 계산

class HuffmanCoding {

    // 1. 빈도수 계산
    public Map<Character, Integer> calculateFrequency(String input) {
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : input.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        return frequencyMap;
    }
    
}

 

문자열의 빈도수를 계산해서 Map으로 반환하는 메서드를 작성하였다.

 

 

---

2. 허프만 트리 생성

class HuffmanNode {
    char data;
    int frequency;
    HuffmanNode left, right;

    public HuffmanNode(char data, int frequency) {
        this.data = data;
        this.frequency = frequency;
        left = right = null;
    }
}

class HuffmanCoding {

    // 2. 허프만 트리 생성
    public HuffmanNode buildHuffmanTree(Map<Character, Integer> frequencyMap) {
        // 우선순위 큐(최소 힙)
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>((a, b) -> a.frequency - b.frequency);

        // 우선순위 큐에 문자와 빈도를 노드 형태로 삽입
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

       // 우선순위 큐에 하나의 루트 노드만 남을 때 까지 반복
        while (pq.size() > 1) {
            // 큐에서 두 개의 빈도가 작은 노드를 꺼냄
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();

            // 두 개의 노드를 한 개의 부모 노드를 통해서 묶음 + 부모 노드의 Frequency는 자식 노드의 합으로 설정
            HuffmanNode parent = new HuffmanNode('$', left.frequency + right.frequency);
            parent.left = left;
            parent.right = right;

            // 해당 부모 노드를 다시 큐로 집어넣음.
            pq.offer(parent);
        }
        return pq.poll();
    }

}

 

문자 빈도를 기반으로 허프만 트리를 생성해야 한다.

이에 따라 허프만 트리의 노드 클래스 HuffmanNode를 생성하고, 필드로는 문자(data)와 빈도수(frequency)가 있다. 최소 빈도수에 따라서 우선순위 큐에 정렬되도록 할 것이다.

 

이제 문자별로 얻어낸 빈도수들로 노드를 생성하여, 우선순위 큐에 모두 집어넣는다.

참고로 단어에 해당하는 노드들은 무조건 말단 노드(Leaf Node)가 될 것이라는 사실은 앞의 과정을 보면서 알 수 있을 것이다.

 

해당 우선순위 큐의 노드들이 루트 노드 1개에서 뻗어나가는 형태의 트리 형태가 될 때까지 아래의 루프를 반복할 것이다.

• 가장 빈도수가 낮은 노드 두 개를 우선순위 큐에서 꺼낸다.
• 해당 노드들을 한 개의 부모 노드를 생성하고, 그것의 자식 노드로 설정한다. 부모 노드의 빈도수는 자식 노드의 빈도수의 합으로 설정한다.
• 해당 부모 노드는 다시 우선순위 큐에 넣는다.

해당 과정을 통해 결국 1개의 루트 노드가 반환될 것이다.

 

 

 

---

3. 허프만 부호화

// 3. 허프만 부호화
public void generateHuffmanCodes(HuffmanNode root, String code, Map<Character, String> huffmanCodes) {
    if (root == null) return;
    if (root.left == null && root.right == null) {
        huffmanCodes.put(root.data, code);
    }
    generateHuffmanCodes(root.left, code + "0", huffmanCodes);
    generateHuffmanCodes(root.right, code + "1", huffmanCodes);
}

 

위에서 생성한 허프만 트리를 기반으로 각 단어들에 대해서 허프반 부호화를 수행한다.

루트로부터 왼쪽 자식 노드로 진행 시 0, 오른쪽 자식 노드로 진행 시 1의 접두어를 부여한다.

만약 말단 노드(Leaf Node)에 도달했다는 것은 해당 단어가 있는 노드에 도달했다는 뜻이며, 부호화가 완료되었다는 것이다. 따라서 이 때 Map에 해당 단어에 대한 부호화의 결과를 저장한다.

 

 

 

---

4. 문자열 압축 수행

public String compress(String input) {

    // 1. 빈도수 계산
    Map<Character, Integer> frequencyMap = calculateFrequency(input);
    System.out.println("1. 빈도수 계산");
    System.out.println(frequencyMap);

    // 2. 허프만 트리 생성
    HuffmanNode root = buildHuffmanTree(frequencyMap);
    System.out.println("2. 허프만 트리 생성");


    // 3. 허프만 부호화
    Map<Character, String> huffmanCodes = new HashMap<>();
    generateHuffmanCodes(root, "", huffmanCodes);
    System.out.println("3. 허프만 부호화");
    System.out.println(huffmanCodes);

    // 4. 문자열 압축
    StringBuilder compressedString = new StringBuilder();
    System.out.println("4. 문자열 압축");
    for (char c : input.toCharArray()) {
        compressedString.append(huffmanCodes.get(c));
    }
    return compressedString.toString();
}

 

이제 위에서 작성한 알고리즘을 바탕으로 문자열 압축을 수행할 수 있게 되었다.

 

1. 문자열에 대한 빈도수를 계산하여 그 결과 Map을 얻어낸다.

2. 빈도수 Map을 바탕으로 허프만 트리를 생성한다.

3. <문자, 부호화된 문자>를 얻어낼 Map을 선언하고, 허프만 트리를 사용하여 해당 Map에 부호화된 문자 결과의 집합을 얻어낸다.

4. 부호화된 문자의 집합을 바탕으로 문자열을 부호화 문자열로 압축한다.

 

 

---

5. 전체 코드

 

class HuffmanNode {
    char data;
    int frequency;
    HuffmanNode left, right;

    public HuffmanNode(char data, int frequency) {
        this.data = data;
        this.frequency = frequency;
        left = right = null;
    }
}

class HuffmanCoding {

    // 1. 빈도수 계산
    public Map<Character, Integer> calculateFrequency(String input) {
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : input.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        return frequencyMap;
    }

    // 2. 허프만 트리 생성
    public HuffmanNode buildHuffmanTree(Map<Character, Integer> frequencyMap) {
        // 우선순위 큐(최소 힙)
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>((a, b) -> a.frequency - b.frequency);

        // 우선순위 큐에 문자와 빈도를 노드 형태로 삽입
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

       // 우선순위 큐에 하나의 루트 노드만 남을 때 까지 반복
        while (pq.size() > 1) {
            // 큐에서 두 개의 빈도가 작은 노드를 꺼냄
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();

            // 두 개의 노드를 한 개의 부모 노드를 통해서 묶음 + 부모 노드의 Frequency는 자식 노드의 합으로 설정
            HuffmanNode parent = new HuffmanNode('$', left.frequency + right.frequency);
            parent.left = left;
            parent.right = right;

            // 해당 부모 노드를 다시 큐로 집어넣음.
            pq.offer(parent);
        }
        return pq.poll();
    }

    // 3. 허프만 부호화
    public void generateHuffmanCodes(HuffmanNode root, String code, Map<Character, String> huffmanCodes) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            huffmanCodes.put(root.data, code);
        }
        generateHuffmanCodes(root.left, code + "0", huffmanCodes);
        generateHuffmanCodes(root.right, code + "1", huffmanCodes);
    }

    // 4. 문자열 압축
    public String compress(String input) {

        // 1. 빈도수 계산
        Map<Character, Integer> frequencyMap = calculateFrequency(input);
        System.out.println("1. 빈도수 계산");
        System.out.println(frequencyMap);

        // 2. 허프만 트리 생성
        HuffmanNode root = buildHuffmanTree(frequencyMap);
        System.out.println("2. 허프만 트리 생성");


        // 3. 허프만 부호화
        Map<Character, String> huffmanCodes = new HashMap<>();
        generateHuffmanCodes(root, "", huffmanCodes);
        System.out.println("3. 허프만 부호화");
        System.out.println(huffmanCodes);

        // 4. 문자열 압축
        StringBuilder compressedString = new StringBuilder();
        System.out.println("4. 문자열 압축");
        for (char c : input.toCharArray()) {
            compressedString.append(huffmanCodes.get(c));
        }
        return compressedString.toString();
    }
}

public class C01_Huffman{
    public static void main(String[] args) {
        HuffmanCoding hf = new HuffmanCoding();
        String input = "AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE";
        String compressedString = hf.compress(input);
        System.out.println("압축 전: " + input);
        System.out.println("압축 후: " + compressedString);
    }
}

1. 빈도수 계산
{A=15, B=7, C=6, D=6, E=5}
2. 허프만 트리 생성
3. 허프만 부호화
{A=0, B=111, C=110, D=101, E=100}
4. 문자열 압축
압축 전: AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE
압축 후: 000000000000000111111111111111111111110110110110110110101101101101101101100100100100100