[Python] gzip 라이브러리

Python 내 압축 관련 라이브러리

파이썬에서 사용할 수 있는 라이브러리는 다양합니다.
brotli, lzma, zstd, bz2, lz4, zlib, gzip등이 있습니다.
이 중 zlib, bz2, lzma은 파이썬3에 내장모듈로 지원이 됩니다(lzma는 파이썬2에서 지원이 안됩니다).

압축 알고리즘 압축률 및 압축 시간 비교

위 그림을 보시면 zstd와 gzip이 시간도 빠르고 압축률도 높은 것으로 확인할 수 있습니다.
압축 알고리즘을 적용하는 ETL 파이프라인 프로젝트에서 저는 내장 모듈인 gzip을 사용하였습니다.

원리나 이해가 쉬운 자료를 찾기도 쉬웠고, 파이썬 공식문서에서도 자세히 설명되어 있어서 gzip으로 선택하였습니다.

오늘은 내장 모듈인 gzip 라이브러리에 대해서 배워보도록 하겠습니다.

gzip

gzip의 데이터 압축은 zlib 모듈에 의해 제공됩니다.
gzip 압축 알고리즘은 deflate와 같습니다.
스택오버플로우에 의하면 gzip이 deflate와 몇 개의 헤더, 그리고 체크섬이 있기 때문에 더 안정적이라고 합니다.
gzip = deflate + headers + checksums 인 셈입니다.

 

Deflate 알고리즘

해당 알고리즘은 허프만 코딩 알고리즘과 LZ77 알고리즘이 결합되어 있습니다.
LZ77의 결과인 LLD 블럭을 다시 허프만코딩으로 압축하면 deflate 알고리즘이 됩니다.

LZ77

입력 문자열을 순회하면서 이전에 등장했었던 반복되는 부분문자열을 압축하는 방식입니다.

• 압축 결과로 LLD(Literal, Length, Distance) 시퀀스를 생성합니다.
• 사전(Dictionary) 압축방식 : 이전에 등장한 단어를 찾는 방식입니다.

예를 들어 ababc라는 문자열을 압축하면 <0,0,a> <0,0,b> <2,2,c>의 형태로 LLD블록으로 출력됩니다.

 

허프만 코딩 알고리즘(Huffman Coding Algorithm)

허프만이라는 사람이 만든 알고리즘입니다.
가변길이 코딩을 만들기 위한 알고리즘이며, 가변길이 코딩이란 문자로 표현하는 비트를 최대한 짧게 사용해서 길이를 압축시키는 아이디어입니다.
가변길이 코딩의 반대는 고정길이 코딩입니다.
고정길이 코드의 예시로는 아스키 코드가 있으며 8비트로 표현됩니다.

 

고정길이 코드
NUL = 0000 0001 (NULL)
SOH = 0000 0010 (Start Of Header)
STX = 0000 0011 (Start Of Text)

 

가변길이 코드
NUL = 0
SOH = 1
STX = 01

 

허프만 코딩 알고리즘은 허프만 코드에 해당하는 이진트리를 구축하는 그리디 알고리즘입니다.

허프만 알고리즘에 의해 생성된 최적 이진코드이며, 최적 이진코드(Optimal Binary Code)는 주어진 파일에 있는 문자들을 이진코드로 표현할 때 필요한 비트의 수가 최소가 되는 이진트리를 구축하는 최적화 문제 중 하나입니다.

 

빈도 수가 가장 높은 심볼(단어 또는 문자)부터 정렬하여 이진트리를 생성하는 알고리즘입니다.

각 심볼의 등장빈도가 다음과 같다고 가정해보겠습니다.
code = 55
the = 94
tree = 32
a = 73

이 경우 허프만 코딩으로 문제를 풀어보겠습니다.

 

• the(94), a(73), code(55), tree(32)의 형태로 정렬합니다.
  

  

• code와 tree를 자식노드로 가지는 트리를 만듭니다.
  

  

• the(94), code-tree(87), a(73)의 형태로 정렬합니다.
• a와 code-tree를 자식노드로 가지는 트리를 만듭니다.
  

  

• codetree-a(160), the(94)의 형태로 정렬합니다.
• 최종트리를 완성합니다.
  

  

루트노드에서 각 단말노드로 가는 방향이 왼쪽이면 0, 오른쪽이면 1이라고 할 때,
code = 000
the = 1
tree = 001
a = 01
와 같이 표현할 수 있습니다.