Python 과 zstd - LZ77 과 허프만 코딩
25년 10월 7일, 추석 연휴가 한창일때, Python 3.14 정식 버전 (3.14.0) 이 배포되었습니다. 많은 Python 사용자들이 Free-Threaded 에 대해 이야기했습니다. 하지만 저는 Python Native zstd 압축이 지원된다는 사실에 더 관심이 갔습니다. 최근 I/O Bounded API Server 의 응답속도 개선에 관심을 기울이고 있었기 때문입니다.
이번 글에서는 본격적으로 zstd 압축 알고리즘을 알아보고 활용법을 탐구하기 전에 대표적인 무손실 압축 알고리즘인 LZ77과 허프만 코딩을 알아보겠습니다.
대표적인 무손실 압축 알고리즘
zstd 압축에 대해서 이야기하기에 앞서 현대 컴퓨터 시스템에서 압축 알고리즘의 근간이 되는 두 알고리즘을 살펴보겠습니다. 앞으로 설명할 gzip, brotli 그리고 zstd 까지 모두 이 두 알고리즘을 적절히 적용한 사례입니다.
LZ77
대표적인 사전기반 (dictionary based) 압축 기법의 한 종류로 데이터 스트림(인풋 데이터)에서 반복적인 시퀀스를 처리하는 알고리즘입니다.
데이터 스트림내에서 반복적으로 나타는 바이트 시퀀스를 찾아내어 사전(dictionary)을 만들고 두 번째 등장부터는 해당 시퀀스가 처음 나타났던 위치에 대한 참조(reference)로 바이트 시퀀스를 교체하는 식으로 동작합니다. 즉, 반복적으로 등장하는 원본데이터를 작은 크기의 포인터로 표현하는 것이죠.
슬라이딩 윈도우
LZ77 알고리즘은 일정한 크기의 데이터 스트림을 읽는데 이를 슬라이딩 윈도우라고 합니다. 이 슬라이딩 윈도우는 다시 2개로 나뉘는데요, 이미 인코딩된 데이터로 구성되며, 이후에 읽어들일 데이터에 사전 역할을 하는 서치 버퍼(Search Buffer)와 이제 읽어들여서 인코딩될 대상인 룩어헤드 버퍼(Look ahead Bugger) 입니다.
(Distance, Length) 쌍으로 인코딩
룩어헤드 버퍼의 시작 부분과 일치하는 가장 긴 시퀀스를 서치버퍼에서 발견하면, 알고리즘은 이 반복되는 시퀀스를 (Distance, Length) 쌍으로 인코딩합니다.
- Distance: 슬라이딩 윈도우의 시퀀스와 룩어헤드 버퍼의 시퀀스가 일치하는 시작점까지의 거리
- Length: 일치하는 시퀀스가 몇 바이트로 구성되어 있는지
위의 예시에서 룩어헤드 버퍼 부분이 인코딩 된 결과를 보자면 아래와 같습니다.
- Step1: 처음 데이터를 읽었을때 서치버퍼의 시작부분과 룩어헤드 버퍼와 매치되는 시퀀스가 없습니다. 그래서 슬라이딩 윈도우가 한칸 이동했습니다.
- Step2: 이제 서치버퍼와 룩어헤드 버퍼가 일치하는 시퀀스를 찾았습니다. 두 시퀀스의 시작점간의 거리(DIstance)가 7칸, 그리고 일치되는 시퀀스의 길이(Length)가 4칸, 그리고 다음 문자가 r 이어서 (7,4,'r') 로 데이터가 인코딩 됩니다.
첫번째 데이터와 c 와 같이 인코딩 되지 않은 데이터를 리터럴이라고 합니다.
LZ77 은 LZ78 그리고 LZW 등 다양한 변형 알고리즘이 존재하지만 기본적인 프레임워크는 동일합니다.
허프만 코딩
데이터의 통계적인 중복성을 제거하는 알고리즘입니다.
더 자주 나타나는 심볼에는 더 짧은 길이의 이진 코드를 할당하고, 드물게 나타나는 심볼에는 더 긴 길이의 이진 코드를 할당하여 전체 데이터 비트수를 줄이는 방식입니다.
허프만 트리
정말 직관적인 설명이죠? 위의 설명은 Spec 으로 본다면 이제는 구현 세부사항을 알아볼 차례입니다. 빈도 기반 이진코드를 만들기 위해 허프만 트리라는 이진트리를 활용합니다.
이진트리는 이런 순서로 만들 수 있는데요.
- 데이터에서 각 심볼이 나타나는 빈도를 계산하고 각 빈도를 가중치(weight)로 갖는 리프 노드(leaf node)를 생성합니다.
- 생성된 모든 리프 노드를 우선순위 큐(priority queue)에 넣습니다. 큐의 head 부분에는 가중치가 낮은 노드가 위치합니다.
- 큐에 노드가 하나 남을때까지 두 노드를 꺼내고 이 두 노드를 자식으로 하는 부모 노드를 생성합니다. 이때 부모 노드의 가중치는 두 자식 도으 가중치의 합으로 합니다. 새로 생성된 부모 노드를 다시 우선순위 큐에 넣습니다.
- 마지막으로 하나 남은 노드가 바로 허프만 트리의 루트 노드(root node)가 됩니다.
"this is an example of a huffman tree". 라는 데이터를 대상으로 허프만 트리를 만들면 아래와 같이 구성됩니다.
이진코드 부여
이렇게 만들어진 허프만 트리를 기반으로 드디어 심볼에 대한 이진코드를 부여합니다. 이진 코드는 루트 노드에서 해당 심볼의 리프 노드까지의 경로로 결정되는데요. 일반적으로 왼쪽 가지로 이동하는 것을 '0'으로 오른쪽 가지로 이동하는 것을 '1'로 표현합니다.
이 과정을 통해 빈도가 높은 심볼은 루트에 가까운, 즉 경로가 짧은 위치에 배치되어 짧은 코드를 할당받고, 빈도가 낮은 심볼은 루트에서 멀리 떨어진, 즉 경로가 긴 위치에 배치되어 긴 코드를 할당받게 됩니다. 그리고 이런 과정을 통해 이진코드를 부여하면 놀랍게도 어떤 심볼의 코드도 다른 심볼 코드의 접두사(prefix)가 되지 않는다는 특징을 갖게됩니다. 예를 들어, 'A'의 코드가 01이라면, 다른 어떤 심볼의 코드도 01로 시작할 수 없습니다.
이러한 접두사 없는 코드(Prefix-Free Code)라는 특징은 압축 해제 과정에서 해당 심볼이 무엇을 의미하는지 모호함이 없도록 만들고 결국 더 효율적이고 정확한 데이터 복원을 가능하게 만듭니다.
참고
Python 3.14 신기능: https://docs.python.org/3.14/whatsnew/3.14.html
Python Free-Threded: https://docs.python.org/3.14/whatsnew/3.14.html#whatsnew314-free-threaded-cpython
Python zstd: https://docs.python.org/3/library/compression.zstd.html
LZ77 알고리즘 예시: https://www.youtube.com/watch?v=yTQIONTE3Y8