반응형

허프만 트리


가장 빈도가 많이 나온순으로 정렬하고

그 값들을 트리에 모두 달아준다. 이때 0과 1로 된 트리에 달아줌으로써 문자열을 압축할 수 있다.

(Greedy Algorithm의 일종)


허프만 트리 설명 :: https://wooyaggo.tistory.com/95


입력이 

1110010001 이고

4개의 값(A,B,C,D)이 각각 00 01 11 10일 때

즉, 

1110010001

4 00 01 11 10 

로 인풋이 들어왔을 때

허프만 트리 알고리즘을 이용하면

답이 CDBAB가 된다.



추가 케이스 :


0001001100100111001

4 11 01 10 00 

답 DBDADCBAD






소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
#include <iostream>
 
typedef struct HuffmanTree {
public:
    HuffmanTree *left, *right;
    char ch;
 
    HuffmanTree() {
        left = right = nullptr;
        ch = '\0';
    }
};
 
int _strlen(char *str) {
    int len = 0;
    while (str[++len]);
    return len;
}
int main() {
    char str[52];
    scanf("%s", str);
 
    int n;
    scanf("%d"&n);
 
    HuffmanTree *root = new HuffmanTree();
 
    for (int i = 0; i < n; i++) {
        char tmp[52];
        scanf("%s", tmp);
 
        int len = _strlen(tmp);
        HuffmanTree *cur = root;
        for (int j = 0; j < len; j++) {
            if (tmp[j] == '0') {
                if (cur->left == nullptr) 
                    cur->left = new HuffmanTree();
 
                cur = cur->left;
            }
            else if(tmp[j] == '1') {
                if (cur->right == nullptr)
                    cur->right = new HuffmanTree();
 
                cur = cur->right;
            }
        }
        cur->ch = 'A' + i;
    }
 
    int len = _strlen(str);
    HuffmanTree *cur = root;
    for (int i = 0; i < len; i++) {
        if (str[i] == '0') {
            cur = cur->left;
            if (cur->left == nullptr) {
                printf("%c", cur->ch);
                cur = root;
            }
        }
        else if (str[i] == '1') {
            cur = cur->right;
            if (cur->right == nullptr) {
                printf("%c", cur->ch);
                cur = root;
            }
        }
    }
    return 0;
}
 
 
cs

반응형