HPACK에서 사용하는 Huffman coding

HTTP/2.0에는 핵심적인 기능 3가지가 있다.

1. HPACK : Header Compression

2. Multiplexing

3. Server push

HPACK에서 Header압축을 하는 알고리즘으로

Huffman coding(혹은 Huffman code)을 활용한다

(HPACK에 대한 자세한 정보는 RFC7541 참고)

이 글에선 Huffman coding에 대해서 다룬다.

Huffman coding이란

무손실 압축 알고리즘으로, 심볼의 출현횟수(출현빈도)를 기준으로 코드를 부여하는데

자주 출현하는 심볼에는 짧은 코드를 부여하고, 상대적으로 적게 출현하는 심볼에는 더 긴 코드를 부여한다.

if "dessert"라는 문자가 있다면 심볼(문자)의 출현 횟수는

d = 1

e = 2

s = 2

r = 1

t = 1이다.

여기서 e,s가 각각 2번씩 출현했으므로(자주 등장하므로) 적은 수의 코드로 표현하고,

1번씩 출현한 d,r,t는 2번씩 출현한 e,s와 비교했을때 많은 수의 코드로 표현된다.

Huffman coding processing

Huffman coding을 이해하는데 중요한 키워드는 내림차순 정렬, 이진트리 정도이다.

"dessert"에 대해서 심볼, 출현 횟수를 "(심볼,횟수)"로 표현하면

(d,1) (e,2) (s,2) (r,1) (t,1)로 표현 할 수 있고, 각각을 이진트리의 node로 다시 표현하면 아래와 같다.

위 그림을 먼저 출현 횟수를 기준으로 내림차순 정렬한다.

이렇게 정렬된 상태에서 우측 2개의 node(출현 횟수가 낮은 node)에 parent node를 만들어준다. parent node는 child node 출현 횟수를 합산한 값만을 가지고 있다.

출현 빈도를 보면 e,s가 2번으로 같고, d,r,t는 1번씩으로 같다. Huffman coding을 이해하는데 있어서 같은 출현빈도를 가진 node들의 순서를 어떤 기준으로 정하는지는 크게 중요하지 않다.

parent node의 숫자를 기준으로 또 다시 내림차순 정렬을 한다.

또 다시 우측 2개의 node에 parent node를 만들어준다.

(정확한 표현은 우측 2개의 tree를 하나의 tree로 합치는거지만 편의상 노드라고 표현)

역시 parent node는 하위 심볼의 빈출횟수를 합산한 값을 가진다.

이렇게 정렬하고 parent node를 만들어 주는 과정을 계속해서 반복한다. (1개의 Tree로 만들어질때까지 혹은 parent node의 값이 모든 심볼의 출현횟수를 더한 값과 같은 parent node가 출현할때까지)

내림차순 정렬

우측 2개 노드에 parent node 삽입

내림차순 정렬

우측 2개 node에 parent node삽입

이 과정이 끝나서 하나의 이진트리가 완성되면 node 좌측에는 "0", 우측에는 "1"의 값을 적용해서 해당하는 심볼의 Huffman coding의 결과 값을 알 수 있다.

심볼	출현 횟수	코드
e	2	00
s	2	01
r	1	100
t	1	101
d	1	11

위 결과로 "dessert"를 Huffman coding으로 encoding하면1100010100100101로 결과가 나온다.

dessert

1100010100100101

decoding은 앞에서부터 bit를 하나씩 비교하면서 위 테이블과 일치하는 코드가 있으면 해당 심볼로 변환해주면된다.

(그러므로 decoding과정에서 위 테이블은 없어서는 안된다, 혹은 마지막 그림인 완성된? 이진트리가 있으면 된다)

Reference

- http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf

- http://www.ktword.co.kr/abbr_view.php?m_temp1=1443