HTTP/2 Spec에서 Header Compression 기술인 HPACK의 핵심인 Huffman coding에 대해 알아보자.
1.이론
+ 자주 쓰이는 문자에 가장 작은 bit를 할당하고 한두번 쓰이는 문자에 큰 bit 를 할당한다.
+ AABBAC라는 문자열의 경우 총 6byte인데
+ A는 3번, B는 2번 C는 1번
+ A에게 0이라는 1bit 부여, B는 10, C는 11 부여
+ A(0)A(0)B(10)B(10)A(0)C(11)
+ 001010011 9bit = 1byte+1bit로 압축
+ 원래 문자열이 6byte = 48bit를 차지하였는데 9/48 = 0.19 로 약 20%로 압축됨, 압축률은 80%
+ 큰 파일이고, 텍스트 기반일수록 자주쓰이는 문자가 많을 수록 압축률은 높아지게 되어 있다.
2.이진트리
+ 실제 적용 방법 을 순서대로 한번 살펴보자
대상 문자열 : CDDCACBCBCCCBBCDA
1) 각 문자열별로 빈도수를 검사한다
2) 빈도수 순서대로 정렬한다 (repeat 1/2)
3) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 바꾼다 (repeat 2/2)
4) 빈도수 순서대로 정렬한다 ( repeat 1/2 )
5) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. ( repeat 2/2 )
6) 빈도수 순서대로 정렬한다. ( repeat 1/2 )
7) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다 ( repeat 2/2 ) 트리 완성
8) 완성된 트리에서 윗 트리에서부터 빈도가 큰 트리에 0을 작은 트리에 1을 부여한다.
9) 위 트리를 기준으로 각 문자열의 비트를 참조한다
부모노드에서 출발하여 문자열에 다다를때까지 비트를 더하여 참조한다
A는 001이 된다.
이와 같은 방법으로 B는 01 C는 1, D-000 로 비트를 할당 할 수 있게 된다.
1000000100110110111101011000001
총 17문자, 17byte였던 문자열이 31bit, 즉, 4byte로 압축이 되었다.
3.디코딩
+ 호프만 알고리즘을 이용하여 압축을 하면 어떤 문자가 어떤 bit로 치환되었는지 판단해야되기 때문에 호프만 테이블이라고 불리는 테이블을 추가해야한다.
+ 호프만 테이블은 위에 설명된 이진트리를 말한다
+ 트리를 사용해 복호화한다
한 bit 단위로 읽어서 테이블대로 문자가 나올때까지 트리를 타고 가면서 치환한다.
00101이라는 데이터는 AB를 나타낸다
00100 복호화
1) 첫 비트 0은 17로 표시되어 있는 트리에서 왼쪽, 즉 9로 표시된 트리로 내려간다.
2) 다음 0 역시 왼쪽, 5로 내려간다
3) 다음 1비트는 오르녹 2로 표시된 A를 나타낸다
4) 다음 0은 17트리에서 9트리로
5) 다음 1은 오른쪽 4트리로 즉 4를 나타낸다
