GZIP의 압축 방식

GZIP

리눅스에서 주로 사용되는 압축 방식으로 HTTP 요청을 주고 받는과정에서도 gzip 알고리즘을 사용하여 그 size를 줄이기도 한다.

이러한 GZIP의 알고리즘에는 LZ77 알고리즘과 Huffman Coding 이 사용된다.

LZ77 알고리즘

문자열에서 반복되는 패턴을 찾아서 Back Reference 형태로 저장하여 중복을 제거하는 알고리즘이다.

 

LZ77은 원본 데이터를 offset, length, next char이라는 세 가지 요소로 구성된 형식의 토큰으로 변환한다.

 

변환 과정에서는 Sliding Window 기법을 사용하는데, 해당 기법을 사용하면서 동시에 과거의 문자열을 저장하는 Search Buffer와 현재 읽을 데이터를 저장하는 Lookahead Buffer를 사용한다.

 

ABABBCABABBA 라는 문자열이 있을 때 토큰의 변환 과정을 살펴보면 다음과 같다.

Search Buffer	Looakahead Buffer
	ABABBCABABBA

 

위 상황은 압축을 시작하기 직전의 상태로, 모든 문자열이 Lookahead Buffer에 포함되어있다.

 

 

압축을 시작하며 AB까지의 데이터가 Search Buffer로 이동된 상황을 살펴보면 아래와 같다.

Search Buffer	Looakahead Buffer
AB	ABBCABABBA

처음으로 등장한 문자들이기에 압축없이 그대로 출력되며, 토큰은 다음과 같다.

• Token: (0,0,'A')
• Token: (0,0,'B')

Search Buffer	Looakahead Buffer
ABAB	BCABABBA

이후 다음 AB를 Lookahead Buffer에서 꺼내는 과정에서 해당 문자열이 Search Buffer에 존재하는 것을 확인할 수 있으므로 다음과 같이 토큰을 설정한다.

• Token: (2,2,'B')
  위 토큰의 의미는 2칸전에서 2글자를 재사용하라는 의미이다.

Search Buffer	Looakahead Buffer
ABABBC	ABABBA

한 글자 C는 재사용할 부분이 없으므로 다음과 같은 토큰을 발급한다.

• Token: (0,0,C)

Search Buffer	Looakahead Buffer
ABABBCABABB	A

'ABABB'라는 이미 Search Buffer에 존재하는 패턴이 발견되었으므로 다음과 같은 토큰을 발급한다.

• Token: (6,5,'A')
  6칸 전의 5개의 길이를 재사용하며, 다음 문자는 'A'라는 의미를 가지는 토큰이다.

이로써 압축 과정은 종료되며, 최종 결과물은 아래와 같다.

(0,0,A) (0,0,B) (2,2,B), (0,0,C) (6,5,A)

Huffman coding

이제 위에서 LZ77 알고리즘을 이용해 1차 압축한 데이터를 Huffman coding으로 좀 더 사이즈를 줄이는 방법을 살펴보려고한다

Huffman coding이란 출현 빈도가 높은 기호에는 짧은 코드, 빈도가 낮은 기호에는 긴 코드를 부여하는 알고리즘이다.

LZ77의 결과로 얻은 token들을 개별 문자 단위로 분해하고, Huffman coding을 진행하면 된다.

문자	빈도수
0	8
2	1
6	1
5	1
A	2
B	3
C	1

진행 과정은 다음과 같다.

우선 가장 낮은 빈도수의 두 대상을 다음과 같이 병합한다.

      (2)          (2)      
     /   \        /   \      
   '2'   'C'    '5'   '6'    

위 그림에서 '2'와 'C'의 빈도수는 각각 1이므로, 두 노드를 합쳐서 트리를 생성하고 부모 노드를 두 자식 노드의 빈도수를 더한 2로 설정한 것을 확인할 수 있다. '5', '6'의 병합과정 또한 동일하다.

이후 다시 최소 빈도수를 비교하여 노드를 병합하며, 병합 결과는 다음과 같다.

        (4)               (5)
       /   \             /   \
     (2)   'A'         (2)   'B'
    /   \             /   \
  '2'   'C'         '5'   '6'

이러한 과정을 계속해서 반복하면 결과적으로 아래와 같은 트리가 완성된다.

            (17)
           /    \
        '0'(8)  (9)
              /    \
            (4)    (5)
           /   \   /   \
         (2)  'A' (2)  'B'
        /   \     /   \
      '2'   'C' '5'   '6'

이제 각 문자에 대해 좌측은 0, 우측은 1로 코드를 부여한다.

루트 노드에서부터 순차적으로 내려가면서 코드를 부여하는 방식이며
따라서 '0'은 0이라는 코드가 부여되며, 'A'에는 101이라는 코드가 부여된다.

기존문자	할당된 코드
0	0
A	101
2	1000
B	111
C	1001
5	1100
6	1101

따라서 LZ77 알고리즘과 허프만 코딩을 거친 최종 결과는 다음과 같다.

0010100111100010001110011100100111011100101