[압축 알고리즘] 허프만 부호화 (Huffman coding) + JAVA 구현

허프만 부호화 (Huffman coding)

허프만 부호화란 무손실 압축에 사용되는 엔트로피 코딩 중 하나이다.

이전 글에서 엔트로피 코딩의 목적은 데이터 심볼 당 평균 부호 길이가 엔트로피에 가까워지도록 부호를 할당하여 압축 효율을 높이는 것이라고 하였다.

 

허프만 부호화는 발생 빈도가 높은 (자주 나오는) 심볼에는 짧은 부호를 할당하고, 발생 빈도가 적은 심볼에는 비교적 긴 부호를 할당한다.

따라서 최대한으로 평균 부호길이가 압축되는 결과를 얻을 수 있다.

 

허프만 부호화 시 각각의 심볼에 접두 코드(Prefix code)를 할당한다.

접두 코드란 코드 집합에서 어떤 코드도 다른 코드의 접두사가 되지 않게 만들어진 코드이다.

예를 들어 {"0", "01"} 코드 집합의 경우 접두 코드가 아니다. "0"은 "01" 코드의 접두사이기 때문이다.

반대로 {"00", "010", "0111"}은 접두 코드이다. 이를 보면 어떤 코드도 다른 코드의 접두사에 포함되지 않는다는 것을 알 수 있다.

 

일반적으로 문자 하나의 크기는 1Byte이다. (유니코드와 인코딩 방식에 따라 다를 수도 있지만, 여기서는 ASCII code를 기준으로 설명한다. 나중에 기회가 되면 포스팅할 예정)

 

예를들어 ABCDABA라는 문자열의 크기는 7Byte 즉 56bit이다.

각각의 문자 심볼에 아래와 같이 접두 코드를 할당하면 아래와 같이 된다.

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

 

이를 이용하여 ABCDABA라는 문자열은 0101101110100라는 13bit 크기의 bitset으로 압축될 수 있다.

접두 코드가 할당되었기 때문에 앞에서부터 차례대로 복원하면 원래의 ABCDABA 문자열로 복구할 수 있다.

 

허프만 부호화는 이러한 원리를 이용한 압축 기법이다.

 

허프만 알고리즘 이해

ABCDEAAABDEEADAAEEEAAAD 문자열을 허프만 부호화를 이용하여 압축해보자.

 

1. 각 문자(character)의 출현 빈도수(frequency) 구하기

char	freq
A	10
B	2
C	1
D	4
E	6

 

2. 빈도 수로 오름차순 하여 문자 정렬

char	freq
C	1
B	2
D	4
E	6
A	10

 

3. 허프만 트리 생성

3-1. 각각의 문자를 leaf node로 만든다.

 

3-2. 가장 작은 freq를 가진 두 개의 node를 더하여 부모 node를 생성한다. (부모 node의 freq은 자식 node freq의 합)

 

3-3. 생성된 부모 node를 포함하여 3-2 단계 반복한다. (최종 root node 하나만 남을 때까지)

 

4. 접두 코드 (Prefix-code) 할당

4-1. 각각의 node 왼쪽 edge에는 '0'을, 오른쪽 edge에는 '1'을 할당한다.

 

4-2. root node에서부터 leaf node까지 할당된 bit를 연결하여 각각의 문자에 prefix code 할당한다.

(문자의 출현 빈도가 많을수록 prefix code가 짧고, 출현 빈도가 적을수록 비교적 긴 prefix code가 할당됨)

char	freq	prefix code
A	10	0
E	6	10
D	4	111
B	2	1101
C	1	1100

 

5. 최종 압축 문자열 확인

0110111001111000011011111010011100101010000111

184bit (23char * 8bit) 크기의 문자열이 46bit로 압축된 것을 확인할 수 있다.

 

6. 복구

prefix code table을 참고하여 앞에서부터 순차적으로 복구한다.

이를 통해 encoding 문자열의 bit가 조금만 손상되어도 전체 문자열의 복구가 불가능하다는 허프만 부호화의 단점을 알 수 있다.

 

---

 

JAVA 구현 (Encoding & Decoding)

JAVA로 허프만 부호화를 구현해보았다.

 

import java.nio.charset.StandardCharsets;
import java.util.*;
import java.util.stream.Stream;

public class Huffman {
    private static Scanner scan = new Scanner(System.in);
    private static Map<Character, String> prefixCodeTable = new HashMap<>();    // Binary PrefixCode by Character (HashMap)

    public static void main(String args[]){
        // Origin text data
        String data = scan.nextLine();
        System.out.println("Original data : " + data);

        // Huffman Encoding
        String encodeData = encode(data);
        System.out.println("Encoded data : " + encodeData);

        // Huffman Decoding
        String decodeData = decode(encodeData);
        System.out.println("Decoded data : " + decodeData);
        System.out.println();

        // Print Report
        int originDataByteSize = data.getBytes(StandardCharsets.UTF_8).length;
        System.out.println("Original data size : " + originDataByteSize * 8 + "Bit (" + originDataByteSize + "Byte)");
        int encodeDataByteSize = encodeData.length() % 8 == 0 ? encodeData.length() / 8 : encodeData.length() / 8 + 1;
        System.out.println("Encoded data size : " + encodeData.length() + "bit (" + encodeDataByteSize + "Byte)");
    }

    // Encoding method
    public static String encode(String data){
        // Get Frequency by Character
        Map<Character, Integer> charFreq = new HashMap<>();
        for(char c : data.toCharArray()){
            if(!charFreq.containsKey(c)){
                charFreq.put(c, 1);
            }else{
                int no = charFreq.get(c);
                charFreq.put(c, ++no);
            }
        }
        System.out.println("Frequency by Character : " + charFreq);

        // Build Huffman Tree
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
        Set<Character> keySet = charFreq.keySet();
        for(char c : keySet){
            Node node = new Node(c, charFreq.get(c));
            priorityQueue.offer(node);      // Add priorityQueue by char's freq
        }
        Node rootNode = buildTree(priorityQueue);       // Recursive Call

        // Set Prefix Code by Character
        System.out.println("Prefix Code Table");
        setPrefixCode(rootNode, "");            // Recursive Call

        // Convert Origin data to Prefix code
        StringBuilder sb = new StringBuilder();
        for(char c : data.toCharArray()){
            sb.append(prefixCodeTable.get(c));
        }

        return sb.toString();
    }

    // Decoding method
    public static String decode(String encodeData){
        StringBuilder sb = new StringBuilder();
        String tmp = "";
        for(char c : encodeData.toCharArray()){
            tmp += c;

            if(prefixCodeTable.containsValue(tmp)){
                Stream<Character> keyStream = getKeysByValue(prefixCodeTable, tmp);
                char key = keyStream.findFirst().get();
                sb.append(key);
                tmp = "";
            }
        }
        return sb.toString();
    }

    // Build Huffman Tree Recursive method
    public static Node buildTree(PriorityQueue<Node> priorityQueue){
        if(priorityQueue.size() == 1){
            return priorityQueue.poll();
        }else{
            Node leftNode = priorityQueue.poll();
            Node rightNode = priorityQueue.poll();

            Node sumNode = new Node();
            sumNode.cData = '`';
            sumNode.frequency = leftNode.frequency + rightNode.frequency;
            sumNode.left = leftNode;
            sumNode.right = rightNode;

            priorityQueue.offer(sumNode);
            return buildTree(priorityQueue);
        }
    }

    // Set Prefix Code Recursive method
    public static void setPrefixCode(Node node, String code){
        if(node == null){
            return;
        }

        if(node.cData != '`' && node.left == null && node.right == null){
            prefixCodeTable.put(node.cData, code);
            System.out.println("- " + node.cData + "(" + node.frequency + ") = " + code);
        }else{
            setPrefixCode(node.left, code + '0');
            setPrefixCode(node.right, code + '1');
        }
    }

    public static <K, V> Stream<K> getKeysByValue(Map<K, V> map, V value) {
        return map
                .entrySet()
                .stream()
                .filter(entry -> value.equals(entry.getValue()))
                .map(Map.Entry::getKey);
    }
}

// Node of Huffman Tree
class Node implements Comparable<Node> {
    char cData;
    int frequency;
    Node left, right;

    Node(){}
    Node(char cData, int frequency){
        this.cData = cData;
        this.frequency = frequency;
    }

    // For Sorting priorityQueue
    @Override
    public int compareTo(Node node) {
        return frequency - node.frequency;
    }
}

결과

허프만 알고리즘 설명 시 예시로 진행했던 "ABCDEAAABDEEADAAEEEAAAD"

"hello! hola! hey!!!!"

 

설명

준비

우선 문자 별 접두 코드를 관리할 prefix code table을 HashMap 전역변수로 생성하였다.

Node 클래스에는 cData(문자 data)와 frequency(빈도수), 왼쪽과 오른쪽에 위치할 Node가 포함된다.

또한 나중에 등장할 Priority Queue에서 frequency로 Node를 정렬하기 위해 Comparable 인터페이스의 compareTo()를 재정의하였다.

 

Encoding

문자열 내에서 각 문자의 출현 빈도수를 구하고 HashMap에 저장한다.

각각의 문자로 leaf node를 만들고 이를 우선순위 큐(Priority Queue)에 저장한다.

 

buildTree() 메소드를 재귀 호출하며 priorityQueue에서 가장 적은 frequency를 가진 node 두 개로 부모 node를 만든다.

최종 root node가 만들어지면, setPrefixCode() 메소드를 재귀 호출하여 각각의 leaf node에 prefix code를 할당한다.

만들어진 prefix code는 맨 처음 전역변수로 생성했던 prefixCodeTable에 저장한다.

 

원본 문자열에 문자별로 prifix code를 적용하여 최종 압축 문자열을 return한다.

 

Decoding

이진수 prefix code로 이루어진 압축 문자열을 앞에서부터 읽으며, prefixCodeTable에 존재하는 경우 매핑된 문자로 치환한다.