HPACK이 Huffman coding을 사용하는 이유

Huffman coding은 1952년 발표된 알고리즘으로, 2015년 발표한 HTTP/2.0은 60년이나 지난 알고리즘을 사용하는것이다.

HTTP Header를 압축하기 위해서 어떤 조건을 만족하는 알고리즘이 필요할까?

아마도 압축과정에서 손실이 없어야하며, 실시간으로 전송해야되므로 압축 속도 또한 매우 중요하고, 압축을 했으니 당연히 원래 크기보다는 작아야한다.

그럼 이제 압축 알고리즘을 분류해보자.

압축 알고리즘은 크게 2가지로 나눌 수 있다.

1. 무손실 압축

2. 손실 압축

HTTP Header 압축을 위해선 무손실 압축방법을 사용해야한다.

(이 부분에 대해서는 너무나 당연해서 왜 무손실 압축방법을 쓰는지는 설명하지 않겠다)

그리고 무손실 압축방법은 아래와 같이 3가지로 나눌 수 있다.

1. Repetitive Sequence Suppression

: 반복되는 심볼을 숫자로 표현해서 압축하는 방식이다.

대표적으로 Run Length Encoding (RLE)이 있으며,

 "AAABBB"라는 문자가 있으면 "3A3B"로 반복 횟수와 심볼을 적어주는 방식이다.

2. Statistical Encoding (= Entropy encoding)

: 자주 등장하는 심볼에는 짧은 코드를 할당해서 압축하는 방식이다.

대표적으로 Huffman coding이 있다.

3. Dictionary-based

: 사전을 이용해서 압축하는 방법.

대표적으로 LZ계열(LZ77,LZ78,LZW...)의 알고리즘이 있다.

Repetitive Sequence Suppression은 아이콘, 픽토그램같이 연속된 값이 많이 있는 데이터에 효과적이다.

HTTP Header와 같이 연속된 값이 거의 없는 데이터에는 비효율적이다.

Statistical Encoding은 압축 전 심볼의 분포를 알고 있어야 하는 단점이 있지만, HTTP Header같은 데이터(data가 크지않고 반복이 적은)를 압축할 경우 효율적이다.

Dictionary-based는 자주 등장하는 단어가 많으면 효율적이다. 하지만 그렇지 않을경우 사전 크기가 커져서 압축 전보다 압축 후가 더 size가 커지는 경우도 있다.

HTTP Header를 압축하는 방식으로는 무손실 압축 → Entropy encoding 방식을 사용하는게 좋다.

Entropy encoding의 대표적인 방식으로는

Huffman coding외에도 Arithmetic coding(산술 부호화), Range encoding(범위 부호화)이 있다.

(Range encoding은 Arithmetic coding과 매우 비슷하므로 생략하겠다)

Huffman coding에 대해서는 이 블로그에서 다룬적 있다. (Link: http://http2.tistory.com/1)

Arithmetic coding은 입력 신호의 발생 빈도로부터 입력 신호의 확률을 추정하는 방식이다.

하나의 입력심볼에 하나의 코드가 할당되는것이 아니고 여러 심볼을 묶은 심볼을 고정된 크기의 코드로 표현한다.

Arithmetic coding은 이진 데이터 소스처럼 적은 심볼을 갖고, 비대칭적인 확률분포를 갖는 소스를 압축하는데 유리하다.

Huffman보다 압축률이 좋다는 특징이 있으나(하지만, 단문의 메시지일 경우 압축률이 더 떨어질 수 있다)

복잡한 수학적 계산을 수행해야 하므로 연산량이 매우 크다 → 시간이 오래걸린다.

HTTP/2.0에서 압축을 하는 이유는 전송시 비용을 줄이기 위해서다.만약 압축하는데 시간이 오래 걸린다면 이 알고리즘은 더이상 고려 대상이 아니다. 

이러한 속도, 크기적으로 효율성이 좋은게 Huffman이라서 이걸 선택한게 아닌가 싶다.

물론 이 두 알고리즘 말고도 많은 알고리즘이 있을텐데 사실 글쓴이가 많은 압축알고리즘을 아는게 아니라서 자세한 부분까지 설명하기엔 무리가 있다.

reference

산술 부호화 https://ko.wikipedia.org/wiki/%EC%82%B0%EC%88%A0_%EB%B6%80%ED%98%B8%ED%99%94

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

http://thinkpiece.tistory.com/2

범위 부호화 https://en.wikipedia.org/wiki/Range_encoding