💬 NLP

Frequency-Ordered Tokenization for Better Text Compression

이 논문은 자연어 토큰의 빈도 분포를 활용하여 BPE 어휘를 빈도순으로 재배열하고 정수 인코딩을 적용하는 '빈도 순서 토큰화' 기법을 제안함으로써, 다양한 압축 알고리즘의 성능을 대폭 향상시키고 처리 속도를 가속화하는 방법을 제시합니다.

원저자: Maximilian Kalcher

게시일 2026-02-27

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Maximilian Kalcher

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 **"텍스트 압축을 더 잘하고, 더 빠르게 만드는 아주 간단한 비법"**을 소개합니다.

마치 책장을 정리할 때, 자주 나오는 단어를 책상 앞쪽 가장 손이 잘 닿는 곳에 두고, 드물게 나오는 단어는 뒤쪽 깊숙이 두는 것과 같은 원리입니다. 이 기술은 **'빈도순 토큰화 (Frequency-Ordered Tokenization)'**라고 불립니다.

이 복잡한 기술을 일상적인 비유로 쉽게 설명해 드릴게요.

1. 핵심 아이디어: "자주 쓰는 단어는 '짧은 이름'으로 부르기"

우리가 글을 쓸 때, 'the', 'a', 'is' 같은 단어는 정말 자주 나옵니다. 반면 'quintessential' 같은 어려운 단어는 거의 안 쓰이죠. (이걸 언어학에서는 지프의 법칙이라고 합니다.)

기존의 컴퓨터 압축 프로그램 (zlib, zstd 등) 은 이 글을 그대로 받아서 "이런 패턴이 반복되네?"라고 찾아서 압축합니다. 하지만 이 프로그램들은 글자 하나하나의 '빈도'를 아주 똑똑하게 분석하지는 못합니다.

이 논문은 다음과 같이 제안합니다:

단어를 쪼개기 (BPE): 글을 작은 조각 (토큰) 으로 나눕니다.
순위 매기기: 어떤 조각이 가장 자주 나오는지 세어봅니다.
이름 바꾸기: 자주 나오는 조각에는 **'1, 2, 3'**처럼 짧은 숫자 이름을 붙이고, 잘 안 나오는 조각에는 **'1000, 1001'**처럼 긴 숫자 이름을 붙입니다.
압축하기: 이제 컴퓨터는 "짧은 숫자 1, 2, 3"이 반복되는 글을 압축하게 됩니다. 짧은 숫자는 데이터 크기가 작기 때문에, 기존 압축 프로그램이 훨씬 더 잘 압축할 수 있게 됩니다.

💡 비유:
想象一下，你有一个巨大的仓库（原始文本），里面堆满了各种大小的箱子。

기존 방식: 자주 나오는 '물통' (자주 쓰는 단어) 과 드문 '진주' (드문 단어) 를 섞어서 무작위로 쌓아두고, 그걸 다 같이 묶으려다 보니 끈이 길어지고 무거워집니다.

이 논문의 방식: 자주 나오는 '물통'은 **작은 상자 (1 바이트)**에 담고, 드문 '진주'는 **큰 상자 (3 바이트)**에 담습니다. 그리고 자주 쓰는 물통만 모아서 압축하면, 전체 무게가 훨씬 가벼워집니다.

2. 왜 이것이 놀라운가요? (두 마리 토끼를 다 잡다)

보통 압축률을 높이려면 시간이 더 걸립니다. (더 똑똑하게 분석하니까요.) 하지만 이 방법은 압축률도 높이고, 속도도 더 빠르게 만들어줍니다.

압축률 향상: 100MB 짜리 위키백과 데이터를 압축했을 때, 가장 흔한 프로그램 (zlib) 은 7% 이상 더 작아졌습니다. (예: 36MB → 29MB)
속도 향상: 압축하는 데 걸리는 시간이 3 배나 빨라졌습니다.
- 이유: 압축 프로그램이 처리해야 할 데이터 양 자체가 줄었기 때문입니다. 100MB 의 원본 텍스트를 처리하는 대신, 40MB 정도의 '숫자 목록'만 처리하면 되니까 컴퓨터가 훨씬 편하게 일할 수 있습니다.

💡 비유:
택배 기사 (압축 프로그램) 가 100kg 의 무거운 짐을 나르려다 지쳐서 느리게 갑니다.
이 논문은 그 짐을 먼저 분류해서, 가장 무거운 것 (드문 단어) 은 버리고, 가벼운 것 (자주 쓰는 단어) 만 남긴 뒤 다시 포장합니다.
결과는? 짐도 더 작아지고 (압축률 UP), 기사도 더 빠르게 (속도 UP) 도착합니다.

3. 어떤 경우에 효과가 있을까요?

효과가 큰 경우: 자연어 (영어, 한국어, 중국어 등) 텍스트. 사람이 쓰는 글은 규칙이 있어서 자주 쓰는 단어가 명확합니다.
효과가 없는 경우: 암호화된 데이터나 이진 파일 (이미지, 실행 파일). 이런 데이터는 '자주 나오는 패턴'이 없기 때문에 이 방법이 작동하지 않습니다.

4. 다른 방법들과 비교하면?

과거에도 비슷한 시도 (단어를 번호로 바꾸는 방법) 가 있었습니다. 하지만 이 논문은 '단어' 전체를 바꾸는 게 아니라, **단어의 조각 (Subword)**을 바꾸는 더 정교한 방법을 썼습니다.

장점: '사랑', '사랑해요', '사랑합니다'처럼 형태가 조금씩 다른 단어들을 잘 처리할 수 있어서, 더 적은 종류의 번호로 모든 글을 표현할 수 있습니다.

5. 결론: 왜 이 기술이 중요한가요?

이 기술은 복잡한 인공지능 (AI) 을 새로 만들 필요 없이, 기존에 쓰던 압축 프로그램 위에 얹기만 하면 됩니다. (코드 50 줄이면 구현 가능!)

우리가 매일 생성하는 데이터 (웹사이트, 채팅 기록, AI 학습 데이터) 는 기하급수적으로 늘어나고 있습니다. 이 작은 기술 하나만으로도 저장 공간을 크게 절약하고, 전송 속도를 높일 수 있다면, 전 세계의 데이터 센터와 인터넷 속도에 엄청난 도움이 될 것입니다.

한 줄 요약:

**"자주 나오는 글자에는 짧은 이름을 붙여서, 컴퓨터가 더 가볍고 빠르게 압축할 수 있게 도와주는 똑똑한 정리법"**입니다.

1. 문제 정의 (Problem)

현대 컴퓨팅에서 손실 없는 텍스트 압축은 필수적입니다. 그러나 기존 압축 알고리즘은 다음과 같은 한계가 있습니다.

통계적 모델링의 부재: LZ 계열 알고리즘 (zlib, zstd, LZMA 등) 은 반복되는 바이트 패턴을 슬라이딩 윈도우를 통해 참조하지만, 바이트의 빈도 분포를 명시적으로 모델링하지는 않습니다.
자연어 통계의 활용 미흡: 자연어는 '지프의 법칙 (Zipf's law)'을 따릅니다. 즉, 소수의 토큰이 전체 occurrences 의 대부분을 차지하는 멱법칙 (power-law) 분포를 보입니다. 기존 압축기는 이러한 빈도 편중을 최대한 활용하지 못해 압축 효율이 제한적입니다.
기존 방법의 한계: 단어 단위 변환 (Word Replacing Transform) 은 어휘 외 단어 (OOV) 처리나 형태소 변형에 취약하며, 언어별 규칙이 필요할 수 있습니다.

2. 방법론 (Methodology)

저자는 빈도 순서 토큰화 (Frequency-Ordered Tokenization) 라는 간단한 전처리 기법을 제안합니다. 이 방법은 신경망이나 학습된 파라미터 없이, 기존 압축기 앞에 배치할 수 있는 전처리 단계입니다.

핵심 단계:

BPE 토큰화 (Byte Pair Encoding): 텍스트를 서브워드 (subword) 단위로 토큰화합니다. 이는 형태소 변형, OOV, 비라틴 문자 (중국어, 아랍어 등) 를 언어별 규칙 없이 자연스럽게 처리합니다.
빈도 기반 ID 재배열 (Frequency-Ordered Reordering):
- 토큰 빈도를 계산합니다.
- 가장 빈번한 토큰에 작은 정수 ID(0, 1, 2...) 를 할당하고, 드문 토큰에는 큰 ID 를 할당합니다.
- 이는 지프의 법칙을 활용하여, 압축기에게 "작은 정수"가 압도적으로 많이 나타나는 데이터 스트림을 제공합니다.
가변 길이 정수 인코딩 (Varint Encoding): 재배열된 토큰 ID 를 LEB128 형식의 가변 길이 정수 (Varint) 로 인코딩합니다.
- ID 0~127: 1 바이트
- ID 128~16,383: 2 바이트
- 이 방식은 빈도가 높은 작은 ID 들을 1 바이트로 표현하여 데이터 크기를 획기적으로 줄입니다.
압축: 생성된 바이트 스트림을 일반적인 압축기 (zlib, zstd, LZMA 등) 에 입력합니다.

복호화: 압축 해제 시 역순으로 수행하며, 빈도 매핑 (Vocabulary mapping) 은 압축 데이터와 함께 저장됩니다.

3. 주요 기여 (Key Contributions)

성능 향상 제안: enwik8(100MB) 및 enwik9(1GB) 기준 LZ 계열 압축기에서 1~7%p의 압축률 개선을 달성했습니다. 이는 기존 Word Replacing Transform (WRT) 보다 우수한 성능입니다.
속도 - 압축률 파레토 개선 (Pareto Improvement): 계산 비용이 큰 압축기 (zstd-22, LZMA) 의 경우, 전처리 오버헤드에도 불구하고 압축률 향상과 동시에 압축 속도가 빨라지는 효과를 입증했습니다. (전체 처리 시간 단축)
이론적 분석 및 검증: 지프의 법칙 ( $\alpha \approx 1.04$ ) 과 가변 길이 인코딩의 정보 이론적 분석을 통해 이론적 기대값과 실험 결과를 일치시켰으며, 중국어 및 아랍어 등 다양한 언어와 데이터셋에서 일반화 가능성을 검증했습니다.

4. 실험 결과 (Results)

A. 압축률 (enwik8 기준, 100MB)

zlib-9: 36.48% $\rightarrow$ 29.40% (개선 7.08%p)
LZMA: 26.38% $\rightarrow$ 24.69% (개선 1.69%p)
zstd-22: 25.27% $\rightarrow$ 24.51% (개선 0.76%p)
bz2, PPMd: 오히려 성능이 약간 저하됨 (기존 알고리즘이 이미 빈도/맥락 정보를 잘 활용하기 때문).

B. 속도 향상 (압축 시간)

zstd-22: 95.5초 $\rightarrow$ 30.5초 (약 3.1 배 가속)
LZMA: 89.8초 $\rightarrow$ 37.6초 (약 2.4 배 가속)
이유: 원본 텍스트 (100MB) 가 전처리 후 약 41.6MB 의 간결한 바이트 스트림으로 변환되어, 압축기가 처리해야 할 데이터 양이 줄어들고 패턴 매칭이 단순해지기 때문입니다.

C. 일반화 및 비교

다국어 지원: 중국어, 아랍어 텍스트에서도 일관된 개선을 보임.
파일 크기: 파일이 작을수록 (100KB 등) 개선 폭이 더 큼 (10.5%p).
WRT 대비 우위: BPE 기반 서브워드 처리 덕분에 어휘 크기가 더 작고 (71k vs 354k), 희귀 단어나 형태소 변형을 더 효율적으로 처리하여 WRT 보다 우월한 성능을 보임.

5. 의의 및 결론 (Significance & Conclusion)

실용성: 복잡한 신경망 기반 압축 (cmix 등) 과 달리, 기존 압축기 (LZ 계열) 를 수정하지 않고도 50 줄 미만의 코드로 구현 가능한 간단한 전처리 단계입니다.
비용 효율성: 웹 규모 코퍼스, 대화형 AI 시스템, LLM 데이터 파이프라인 등 방대한 텍스트 데이터가 생성되는 시대에, 소폭의 압축률 개선만으로도 막대한 저장 공간 및 전송 비용 절감 효과를 기대할 수 있습니다.
한계점:
- 전처리 시 전체 데이터를 한 번 읽어야 하므로 단일 패스 스트리밍에는 부적합합니다.
- 이진 데이터나 암호화된 데이터에는 적용되지 않습니다.
- 압축 해제 시 전처리 오버헤드 (바이트 디코딩 등) 로 인해 압축 속도보다 느릴 수 있으나, 아카이빙 (write-heavy) 작업에는 적합합니다.

결론적으로, 이 논문은 자연어의 통계적 특성 (지프의 법칙) 을 BPE 토큰화와 가변 길이 인코딩을 통해 결합함으로써, 기존 LZ 계열 압축기의 성능 한계를 돌파하고 속도 - 효율성 트레이드오프를 개선하는 혁신적인 전처리 기법을 제시했습니다.