정렬된 빈도 입력으로 더 빠르게: O(n) 허프만 코딩 알고리즘 완벽 가이드

이전에 다룬 허프만 코드(Huffman Code) 문제에서는 문자의 빈도(frequency)가 정렬되어 있지 않은 상태였습니다. 하지만 만약 빈도 목록이 이미 정렬된 상태로 주어진다면, 각 문자에 코드를 할당하는 작업을 훨씬 더 효율적으로 수행할 수 있습니다.

이 문제에서는 두 개의 빈 큐(queue)를 활용합니다. 먼저 고유한 문자마다 하나의 리프 노드(leaf node)를 생성하고, 이를 빈도가 오름차순이 되도록 첫 번째 큐에 순서대로 삽입합니다.

이러한 접근 방식을 사용하면 알고리즘의 시간 복잡도를 O(n)까지 낮출 수 있으며, 우선순위 큐를 사용하는 일반적인 방식(O(n log n))보다 성능이 향상됩니다.

입력과 출력

입력:
정렬된 순서의 서로 다른 문자와 그 빈도
문자: {L, K, X, C, E, B, A, F}
빈도: {1, 1, 2, 2, 2, 2, 3, 4}

출력:
각 문자에 할당된 코드
L: 0000
K: 0001
X: 001
C: 010
E: 011
F: 10
B: 110
A: 111

알고리즘

1. huffmanCodes(dataList, freqList, n)

입력: 데이터 목록, 빈도 목록, 그리고 목록에 포함된 데이터의 개수 n

출력: 각 문자에 할당된 코드

Begin
    root := huffmanTree(dataList, freqList, n) // 허프만 트리의 루트 생성
    // 코드를 저장할 배열과 해당 배열의 top 포인터를 준비
    call getCodes(root, array, top) // 각 문자의 코드를 탐색
End

2. getCodes(root :node, array, top)

입력: 루트 노드, 코드를 저장할 배열, 배열의 top 위치

출력: 각 문자에 대한 코드

Begin
    if leftChild(root) ≠ φ then
        array[top] := 0
        getCodes(leftChild(root), array, top)
    if rightChild(root) ≠ φ then
        array[top] = 1
        getCode(rightChild(root), array, top)
    if leftChild(root) = φ AND rightChild(root) = φ then
        display the character ch of root
        for all entries of the array do
            display the code in array[i] for character ch
        done
End

3. huffmanTree(dataList, freqList, n)

입력: 데이터 목록, 빈도 목록, 데이터의 개수 n

출력: 생성된 허프만 트리

Begin
    for all different character ch do
        add node with ch and frequency of ch into queue q1
    done

    while q1 is not empty OR size of q2 ≠ 1 do
        find two minimum node using q1 and q2 and add them as left and
        right child of a new node.
        add new node in q2
    done

    delete node from q2 and return that node.
End

C++ 구현 예제

다음은 두 개의 큐를 이용해 허프만 트리를 구성하고 각 문자의 코드를 출력하는 C++ 프로그램입니다.

#include<iostream>
#include<queue>
using namespace std;

struct node {
    char data;
    int freq;
    node *child0, *child1;
};

node *getNode(char d, int f) {
    node *newNode = new node;
    newNode->data = d;
    newNode->freq = f;
    newNode->child0 = NULL;
    newNode->child1 = NULL;
    return newNode;
}

node *findMinNode(queue<node*>&q1, queue<node*>&q2) {
    node *minNode;
    if(q1.empty()) { // 첫 번째 큐가 비어 있으면 두 번째 큐에서 노드를 꺼내 반환
        minNode = q2.front();
        q2.pop();
        return minNode;
    }

    if(q2.empty()) { // 두 번째 큐가 비어 있으면 첫 번째 큐에서 노드를 꺼내 반환
        minNode = q1.front();
        q1.pop();
        return minNode;
    }

    if((q1.front()->freq) < (q2.front()->freq)) { // 두 큐의 front 중 더 작은 값 선택
        minNode = q1.front();
        q1.pop();
        return minNode;
    }else {
        minNode = q2.front();
        q2.pop();
        return minNode;
    }
}

node *huffmanTree(char data[], int frequency[], int n) {
    node *c0, *c1, *par;
    node *newNode;
    queue<node*> qu1, qu2;

    for(int i = 0; i<n; i++) { // 모든 노드를 큐 1에 삽입
        newNode = getNode(data[i], frequency[i]);
        qu1.push(newNode);
    }

    while(!(qu1.empty() && (qu2.size() == 1))) {
        c0 = findMinNode(qu1, qu2); // 최솟값 두 개를 찾아 자식으로 지정
        c1 = findMinNode(qu1, qu2);
        node *newNode = getNode('#', c0->freq+c1->freq);

        // 중간 노드는 특수 문자 '#'를 저장
        par = newNode;
        par->child0 = c0;
        par->child1 = c1;
        qu2.push(par); // 서브트리를 큐 2에 삽입
    }

    node *retNode = qu2.front();
    qu2.pop();
    return retNode;
}

void getCodes(node *rootNode, int array[], int n) { // 코드를 저장할 배열
    if(rootNode->child0 != NULL) {
        array[n] = 0;
        getCodes(rootNode->child0, array, n+1);
    }

    if(rootNode->child1 != NULL) {
        array[n] = 1;
        getCodes(rootNode->child1, array, n+1);
    }

    if(rootNode->child0 == NULL && rootNode->child1 == NULL) { // 루트가 리프 노드인 경우
        cout << rootNode->data << ": ";

        for(int i = 0; i<n; i++)
            cout << array[i];
        cout << endl;
    }
}

void huffmanCodes(char data[], int frequency[], int n) {
    node *rootNode = huffmanTree(data, frequency, n);
    int array[50], top = 0;
    getCodes(rootNode, array, top);
}

int main() {
    char data[] = {'L', 'K', 'X', 'C', 'E', 'B', 'A', 'F'};
    int frequency[] = {1, 1, 2, 2, 2, 2, 3, 4};
    int n = sizeof(data)/sizeof(data[0]);
    huffmanCodes(data, frequency, n);
}

실행 결과

L: 0000
K: 0001
X: 001
C: 010
E: 011
F: 10
B: 110
A: 111

핵심 정리

이 알고리즘의 핵심 아이디어는 다음과 같습니다.

• 두 개의 큐 활용: 첫 번째 큐에는 빈도 오름차순으로 정렬된 리프 노드를, 두 번째 큐에는 병합으로 생성된 내부 노드(subtree)를 관리합니다.
• 최소 노드 선택의 단순화: 두 큐 모두 빈도 기준으로 정렬된 상태를 유지하므로, 항상 두 큐의 front 요소만 비교하면 최솟값을 O(1)에 찾을 수 있습니다.
• 시간 복잡도 O(n): 우선순위 큐나 힙을 재구성하는 비용 없이 전체 트리를 선형 시간에 구축할 수 있습니다.

빈도 데이터가 미리 정렬되어 제공되는 경우, 이 방식은 허프만 코딩을 구현하는 가장 효율적인 방법 중 하나입니다.