허프먼 부호화 트리 구현과 복호화

컴퓨터에서 텍스트를 표현하는 데 쓰이는 ASCII 코드는 각 문자를 7개의 고정된 비트열을 이용하여 부호화한다.

일곱개의 비트로는 총 128(2⁷)개의 서로 다른 문자를 표현할 수 있다. 이처럼 고정된 비트로 각 기호를 표현하는 부호를 가리켜 고정 길이 부호(fixed-length code)라고 한다.

한편, 각 기호를 서로 다른 개수의 비트로 표현하는 가변 길이 부호(varaible-length code)를 사용하는 것이 나을 때도 있다. 사용되는 빈도수가 높은 글자일수록 적은 수의 비트를 배정하면 데이터를 적게 사용하도록 부호화 할 수 있을 것이다.

알파벳, 숫자 모스부호

모스 부호도 가변 길이 부호의 한 예시이다. 사용 빈도수가 높은 E, T, A, I 등의 문자에는 적은수의 비트를 배정하고, 사용 빈도수가 낮은 Q, X, Y, Z 등에는 많은 수의 비트를 배정해서 사용한다.

 

가변 길이 부호를 사용할 때 어려운 점 중 하나는 각 기호의 끝을 어떻게 인식할 것인가인데, 모스 부호에서는 각 글자의 전송 사이에 신호 전송을 잠시 쉬는 것으로 이문제를 해결한다.

또 다른 해결책은 한 기호의 완전한 부호가 다른 기호의 완전한 부호의 prefix와 겹치는 일이 없도록 기호들에 부호를 배정하는것이다. 그런 부호체계를 앞자리 부호(prefix code)라고 부른다.

이를 이용하여 만들어진 부호 체계가 허프먼 부호(Huffman code)이다.

허프먼 부호

허프먼 부호는 부호화할 메시지를 구성하는 기호들의 상대도수를 가중치로 활용하여 가변 길이 앞자리 부호 체계로 만든 것이다.

이 허프먼 부호체계를 구현하기 위해서는 허프먼 부호화 트리를 구축해야 한다.

허프먼 부호화 트리

허프먼 부호화 트리는 앞자리 부호체계와 가중치(기호의 상대도수) 따라 각 기호에 비트를 배정하고 부호화된 데이터를 복호화하는데 쓰이는 이진트리다.

부호화할 기호들을 leaf 노드(말단 노드)들에 담고 중간노드는 그 노드 아래에 있는 모든 leaf 노드의 가중치를 합한 가중치가 배정된다.

만일 A~H 의 기호가 A:8, B:3, C~H:1 의 가중치를 가졌다면 이를 위한 허프만 부호화 트리는 다음과 같이 구축할 수 있다.

허프만 부호화 트리 예시

허프만 부호화 트리에서 각 기호가 leaf node에만 배정되어 prefix code 체계를 만족하게 된다는 점을 확인하자.

(즉, 한 부호가 다른 부호의 prefix가 되는 경우가 생기지 않는다)

 

임의의 기호를 부호화하는 과정은 다음과 같다.

1️⃣ 트리의 root -> leaf 노드까지 찾아 내려간다.

2️⃣ 왼쪽가지로 내려가면 비트0, 오른쪽 가지로 내려가면 비트1을 추가한다.

 

예를 들어 D의 부호를 찾는다고 하면 root를 기준으로 오-왼-오-오 이므로 1011이 된다.

 

복호화 하는 방법도 비슷하다.

1️⃣ root에서 출발하여 주어진 비트열의 첫 비트가 0이면 왼쪽, 1이면 오른쪽 가지를 선택한다.

2️⃣ 가지를 선택하면서 leaf 노드까지 도달할때까지 다음 비트를 확인한다.

3️⃣ leaf 노드에 도달하면 leaf에 해당하는 기호로 복호화한다.

4️⃣ 비트열의 모든 비트가 소진될때까지 1-3을 반복한다.

 

예를 들어 10001010을 위의 허프만 트리로 복호화한다면

오-왼-왼(B)

왼(A)

오-왼-오-왼(C)

이므로 전체 메시지는 BAC가 된다.

허프먼 트리 구현

허프먼 트리를 구현하는 알고리즘은 다음과 같다.

1️⃣ 부호화를 적용할 기호와 상대도수를 담은 leaf로 구성된 노드 집합을 만든다.

2️⃣ 가중치(상대도수)가 가장 낮은 두 leaf노드를 선택해서 그 두 노드가 왼쪽, 오른쪽 자식 노드인 중간 노드를 만든다. 이 때 새 중간 노드의 가중치는 두 자식 노드 가중치의 합이다.

3️⃣ 노드 집합에서 두 노드를 제거하고 새로 만든 중간 노드를 노드 집합에 추가한다.

4️⃣ 남은 노드들에 대해서도 이러한 노드 병합 과정을 반복한다. 집합에 노드가 하나만 남으면 반복을 멈춘다.

{ (A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1) }
{ (A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1) }
{ (A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1) }
{ (A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2) }
{ (A 8) (B 3) ({C D} 2) ({E F G H} 4) }
{ (A 8) ({B C D} 5) ({E F G H} 4) }
{ (A 8) ({B C D E F G H} 9) }
{ ({A B C D E F G H} 17) }

 

leaf노드의 생성자 및 선택자, leaf노드를 판별하는 함수는 다음과 같이 정의할 수 있다.

(list, head, tail 함수는 https://sayyeah.tistory.com/12 의 쌍객체 부분을 참고)

const make_leaf = (symbol, weight) => list("leaf", symbol, weight);

const is_leaf = object => head(object) === "leaf";

const symbol_leaf = x => head(tail(x));

const weight_leaf = x => head(tail(tail(x)));

 

일반적인 트리는 "code_tree"라는 문자열과 left_branch, right_branch, 기호들의 집합, 가중치로 구성된 목록으로 표현한다.

이러한 일반적인 트리의 생성자 및 선택자들은 다음과 같이 정의할 수 있다.

const left_branch = tree => head(tail(tree));

const right_branch = tree => head(tail(tail(tree)));

function symbols(tree) {
    return is_leaf(tree)
           ? list(symbol_leaf(tree))
           : head(tail(tail(tail(tree))));
}

function weight(tree) {
    return is_leaf(tree)
           ? weight_leaf(tree)
           : head(tail(tail(tail(tail(tree)))));
}

function make_code_tree(left, right) {
    return list("code_tree", left, right,
                append(symbols(left), symbols(right)),
                weight(left) + weight(right));
}

 

symbols와 weight는 주어진 인수가 leaf노드인지 code_tree(일반적인 트리)인지에 따라 다르게 작동한다는 것에 주의하자.

허프먼 트리 복호화 알고리즘

비트열(0, 1의 목록)과 허프만 트리 객체를 받아 복호화하는 알고리즘은 다음과 같이 구현할 수 있다.

function decode(bits, tree) {
  function decode_1(bits, current_branch) {
  	if (is_null(bits)) {
      return null;
	} else {
      const next_branch = choose_branch(head(bits), current_branch);
      return is_leaf(next_branch)
      	? pair(symbol_leaf(next_branch), decode_1(tail(bits), tree)) // root tree로 돌아가서 다음 기호 탐색
        : decode_1(tail(bits), next_branch);
    }
  }
  return decode_1(bits, tree);
}

function choose_branch(bit, branch) {
  return bit === 0
  	? left_branch(branch)
    : bit === 1
    ? right_branch(branch)
    : error(bit, "bad bit -- choose_branch");
}

// 허프먼 트리 구성
const my_leaf_1 = make_leaf("A", 8);
const my_leaf_2 = make_leaf("B", 3);
const my_tree = make_code_tree(my_leaf_1, my_leaf_2);

// 복호화
decode(list(0, 1, 1, 0), my_tree); // ABBA