Byte-Pair Encoding

BPE(Byte-Pair Encoding) 는 GPT·Llama·Qwen 등 현대 언어 모델 대부분이 쓰는 하위 단어(subword) 토크나이저입니다. 원래 데이터 압축 알고리즘이었으나 Sennrich 등이 자연어 처리 어휘 구축에 도입하면서 NLP의 전환점이 되었습니다.Sennrich et al. (2016)

1BPE란 무엇인가¶

토크나이저는 텍스트를 모델이 다루는 정수 ID 열로 바꿉니다. 단위를 무엇으로 할지가 문제입니다.

단어 단위: 어휘가 폭발하고, 학습에 없던 단어(OOV)를 처리할 수 없습니다.
글자 단위: 어휘는 작지만 시퀀스가 너무 길어지고 의미 단위가 사라집니다.
하위 단어(subword): 둘의 절충. 자주 쓰는 덩어리(“ing”, “tion”)는 한 토큰으로, 드문 단어는 여러 조각으로 나눕니다. BPE가 대표적입니다.

BPE의 학습은 단순한 규칙의 반복입니다.

텍스트를 단어로 사전 분절(pre-tokenize) 한다.
모든 단어를 글자(또는 바이트) 로 쪼갠다.
말뭉치에서 가장 자주 인접하는 쌍 을 찾아 하나로 병합(merge) 한다.
목표 어휘 크기에 도달할 때까지 3을 반복한다. 병합 순서가 곧 토크나이저의 규칙(merges)이 된다.

21부 — BPE는 어떻게 학습되는가¶

작은 영어 말뭉치로 병합 알고리즘을 직접 돌려 봅니다. 라이브러리 없이 표준 라이브러리만 씁니다.

import re
from collections import defaultdict

corpus = [
    "This is the Deep Learning Language Models book.",
    "This chapter is about subword tokenization.",
    "This section builds a tokenizer from scratch.",
    "Hopefully, you will be able to understand how tokenizers are trained.",
]

2.1사전 분절 (pre-tokenization)¶

BPE는 단어 경계를 넘어 병합하지 않으므로, 먼저 텍스트를 단어로 나눕니다. GPT-2의 관례를 따라 단어 앞의 공백을 특수 기호 Ġ 로 표시 합니다(공백도 정보이므로 버리지 않습니다 — "is" 와 " is" 는 다른 토큰입니다). 2부에서 이 Ġ 가 어디서 오는지 정확히 설명합니다.

def 사전분절(text):
    # 선택적 선행 공백 + 비공백 덩어리 -> 단어 앞 공백을 Ġ 로
    return [매치.group().replace(" ", "\u0120") for 매치 in re.finditer(r" ?\S+", text)]

단어빈도 = defaultdict(int)
for text in corpus:
    for 단어 in 사전분절(text):
        단어빈도[단어] += 1

print(dict(list(단어빈도.items())[:6]))

{'This': 3, 'Ġis': 2, 'Ġthe': 1, 'ĠDeep': 1, 'ĠLearning': 1, 'ĠLanguage': 1}

2.2글자로 쪼개고, 인접 쌍의 빈도를 센다¶

각 단어를 글자 리스트로 분해한 뒤(분절), 말뭉치 전체에서 인접한 글자쌍이 몇 번 등장하는지 셉니다.

분절 = {단어: list(단어) for 단어 in 단어빈도}

def 쌍빈도(분절):
    빈도 = defaultdict(int)
    for 단어, 출현횟수 in 단어빈도.items():
        조각 = 분절[단어]
        for i in range(len(조각) - 1):
            빈도[(조각[i], 조각[i + 1])] += 출현횟수
    return 빈도

2.3최빈 쌍을 병합한다¶

가장 자주 나온 쌍을 모든 단어에서 하나의 토큰으로 합칩니다.

def 병합(앞, 뒤, 분절):
    for 단어 in 단어빈도:
        조각 = 분절[단어]; i = 0
        while i < len(조각) - 1:
            if 조각[i] == 앞 and 조각[i + 1] == 뒤:
                조각 = 조각[:i] + [앞 + 뒤] + 조각[i + 2:]
            else:
                i += 1
        분절[단어] = 조각
    return 분절

2.4학습 루프¶

목표 어휘 크기(여기서는 50)에 도달할 때까지 "최빈 쌍 찾기 $\to$ 병합"을 반복합니다. 병합되는 순서가 곧 규칙(merges)입니다.

어휘크기 = 50
알파벳 = sorted({글자 for 단어 in 단어빈도 for 글자 in 단어})
어휘 = ["<|endoftext|>"] + 알파벳     # 문장 종결 특수 토큰 + 글자들
merges = {}

while len(어휘) < 어휘크기:
    빈도 = 쌍빈도(분절)
    if not 빈도:
        break
    최빈 = max(빈도, key=빈도.get)
    분절 = 병합(*최빈, 분절)
    merges[최빈] = "".join(최빈)
    어휘.append(merges[최빈])

print("처음 8개 병합 규칙:", list(merges.items())[:8])
print("'This'의 최종 분절:", 분절["This"])

처음 8개 병합 규칙: [(('Ġ', 't'), 'Ġt'), (('i', 's'), 'is'), (('n', 'i'), 'ni'), (('o', 'k'), 'ok'), (('e', 'r'), 'er'), (('Ġ', 'a'), 'Ġa'), (('T', 'h'), 'Th'), (('Th', 'is'), 'This')]
'This'의 최종 분절: ['This']

빈도가 높은 Ġt, is, Th, This 등이 차례로 한 토큰으로 합쳐집니다. 이것이 BPE 학습의 전부입니다 — 자주 붙어 다니는 조각을 반복해서 합칠 뿐입니다.

32부 — 진짜 GPT-2 토크나이저 재현하기¶

1부는 원리를 보이기 위해 작은 말뭉치를 직접 학습 했습니다. 하지만 진짜 GPT-2 토크나이저는 5만 개의 병합을 새로 학습해 흉내 내는 게 아니라, OpenAI가 공개한 학습된 규칙 파일을 그대로 불러와 재현합니다. 그리고 글자가 아니라 바이트 단위로 동작합니다.

3.1왜 바이트 단위인가 (byte-level BPE)¶

글자 단위 BPE는 학습에서 못 본 문자(이모지, 희귀 한자 등)를 만나면 막힙니다. GPT-2는 텍스트를 UTF-8 바이트(0~255) 로 먼저 바꾼 뒤 그 바이트들을 병합합니다. 초기 어휘가 256개로 고정 되고, 세상의 모든 문자는 결국 바이트의 조합이므로 OOV가 원천적으로 사라집니다.

다만 일부 바이트(공백·제어문자)는 그대로 쓰면 다루기 불편합니다. 그래서 GPT-2는 256개 바이트를 눈에 보이는 유니코드 문자로 일대일 치환 하는 표를 씁니다. 여기서 공백(바이트 0x20)이 Ġ 로 바뀝니다 — 1부에서 본 Ġ 의 정체입니다.

def bytes_to_unicode():
    # 출력 가능한 바이트는 자기 자신으로, 나머지(공백·제어문자 등)는 256번부터의 문자로 매핑.
    # 비ASCII 경계는 \u 유니코드 이스케이프로 표기(키보드 입력 가능).
    출력가능_바이트 = (list(range(ord("!"), ord("~") + 1))             # U+0021..U+007E
                  + list(range(ord("\u00a1"), ord("\u00ac") + 1))   # U+00A1..U+00AC
                  + list(range(ord("\u00ae"), ord("\u00ff") + 1)))  # U+00AE..U+00FF
    바이트들 = 출력가능_바이트[:]            # 결과 딕셔너리의 키(바이트 값 0~255)
    문자코드들 = 출력가능_바이트[:]          # 각 바이트가 매핑될 유니코드 코드포인트
    다음_여유코드 = 256
    for 바이트 in range(256):
        if 바이트 not in 출력가능_바이트:           # 출력 불가 바이트는
            바이트들.append(바이트)                 # 그대로 키로 두되
            문자코드들.append(다음_여유코드)         # 256번부터의 빈 코드에 매핑
            다음_여유코드 += 1
    return {바이트: chr(코드) for 바이트, 코드 in zip(바이트들, 문자코드들)}

byte_encoder = bytes_to_unicode()
byte_decoder = {문자: 바이트 for 바이트, 문자 in byte_encoder.items()}
print("공백(0x20) ->", repr(byte_encoder[0x20]))   # 'Ġ'

공백(0x20) -> 'Ġ'

바이트가 어떤 문자로 매핑되는지 몇 가지 예입니다.

바이트	원래 의미	매핑된 문자	코드포인트	비고
`0x41`	`A`	`A`	U+0041	그대로
`0xFF`	`ÿ`	`ÿ`	U+00FF	그대로
`0x20`	공백	`Ġ`	U+0120	재매핑
`0x09`	탭	`ĉ`	U+0109	재매핑
`0x0A`	줄바꿈	`Ċ`	U+010A	재매핑
`0x00`	널(NUL)	`Ā`	U+0100	재매핑
`0xED`	`한`의 1번째 바이트	`í`	U+00ED	그대로
`0x95`	`한`의 2번째 바이트	`ķ`	U+0137	재매핑
`0x9C`	`한`의 3번째 바이트	`ľ`	U+013E	재매핑

출력 가능한 바이트(A, ÿ 등)는 자기 자신으로 두고, 공백·탭·줄바꿈 같은 제어문자만 U+0100 이후의 눈에 보이는 문자로 옮깁니다. 그래서 토큰 안에서 공백이 Ġ 로 나타나는 것입니다. 한글 한 글자 한 은 UTF-8에서 3바이트라, 각 바이트가 위 규칙대로 매핑되어 íķľ 세 문자가 됩니다. 이렇게 모든 문자가 결국 바이트 조합으로 환원되므로, 학습에 없던 글자도 처리할 수 있습니다(OOV 없음).

3.2GPT-2의 사전 분절 정규식¶

GPT-2는 정해진 정규식으로 사전 분절합니다(축약형 's·'t, 문자 덩어리, 숫자 덩어리, 기호, 공백을 구분). 유니코드 속성 \p{L}(문자)·\p{N}(숫자)을 쓰므로 표준 re 가 아닌 regex 모듈이 필요합니다.

import regex

PAT = regex.compile(
    r"""'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+""")

3.3학습된 규칙 불러오기¶

OpenAI가 공개한 어휘(vocab.json: 토큰 문자열 $\to$ ID)와 병합 규칙(merges.txt: 우선순위 순서로 나열된 쌍)을 내려받습니다. 정적 파일일 뿐이라 토크나이저 라이브러리는 필요 없습니다.

import json, os, urllib.request

BASE = "https://huggingface.co/openai-community/gpt2/resolve/main/"

def 내려받기(파일명):
    경로 = os.path.join("/tmp", 파일명)
    if not os.path.exists(경로):
        urllib.request.urlretrieve(BASE + 파일명, 경로)
    return 경로

encoder = json.load(open(내려받기("vocab.json")))           # 토큰 문자열 -> ID
decoder = {토큰문자열: 토큰id for 토큰id, 토큰문자열 in encoder.items()}
규칙목록 = [tuple(줄.split()) for 줄 in
          open(내려받기("merges.txt"), encoding="utf-8").read().split("\n")[1:-1]]
bpe_ranks = {쌍: 순위 for 순위, 쌍 in enumerate(규칙목록)}          # 쌍 -> 우선순위(낮을수록 먼저)
print("어휘 크기:", len(encoder), "| 병합 규칙 수:", len(bpe_ranks))

어휘 크기: 50257 | 병합 규칙 수: 50000

3.4인코딩 — 빈도가 아니라 '우선순위’로 병합¶

여기에 1부와의 핵심 차이 가 있습니다. 학습할 때는 가장 빈번한 쌍을 합쳤지만, 이미 학습된 규칙으로 새 단어를 인코딩할 때는 우선순위(merge rank)가 가장 높은(= bpe_ranks 값이 가장 작은) 쌍을 먼저 합칩니다. 더 합칠 규칙이 없을 때까지 반복합니다. 이 순서를 지키지 않으면 그럴듯해 보여도 GPT-2와 미묘하게 어긋납니다.

def 인접쌍(단어):
    return set(zip(단어[:-1], 단어[1:]))

def bpe(token):
    단어 = tuple(token)
    쌍 = 인접쌍(단어)
    while 쌍:
        후보 = min(쌍, key=lambda 한쌍: bpe_ranks.get(한쌍, float("inf")))  # 우선순위 최상
        if 후보 not in bpe_ranks:
            break
        앞, 뒤 = 후보; 새단어 = []; i = 0
        while i < len(단어):
            try:
                j = 단어.index(앞, i)
                새단어.extend(단어[i:j]); i = j
            except ValueError:
                새단어.extend(단어[i:]); break
            if 단어[i] == 앞 and i < len(단어) - 1 and 단어[i + 1] == 뒤:
                새단어.append(앞 + 뒤); i += 2
            else:
                새단어.append(단어[i]); i += 1
        단어 = tuple(새단어)
        if len(단어) == 1:
            break
        쌍 = 인접쌍(단어)
    return list(단어)

def encode(text):
    ids = []
    for piece in regex.findall(PAT, text):
        token = "".join(byte_encoder[바이트] for 바이트 in piece.encode("utf-8"))  # 바이트->유니코드
        ids.extend(encoder[바이트조각] for 바이트조각 in bpe(token))               # 병합 후 ID로
    return ids

def decode(ids):
    text = "".join(decoder[토큰id] for 토큰id in ids)
    return bytearray(byte_decoder[문자] for 문자 in text).decode("utf-8", errors="replace")

3.5멀티바이트 문자는 어떻게 쪼개지나¶

바이트 단위 BPE는 문자 경계가 아니라 바이트 흐름 을 토큰화합니다. 그래서 영어 단어는 보통 한 토큰이지만, 한글처럼 한 글자가 여러 바이트인 문자는 한 글자가 여러 토큰에 걸칠 수 있습니다. 각 토큰이 실제로 어떤 바이트로 이뤄지는지 들여다봅니다.

for text in ["Hello", "한", "한국어"]:
    ids = encode(text)
    print(f"{text!r} ({len(text.encode('utf-8'))} 바이트) -> {len(ids)} 토큰")
    for 토큰id in ids:
        조각 = decoder[토큰id]                              # 토큰의 바이트-문자 표현
        바이트 = bytes(byte_decoder[문자] for 문자 in 조각)   # 토큰이 담은 실제 바이트
        풀이 = 바이트.decode("utf-8", "replace")
        단독 = repr(풀이) if "\ufffd" not in 풀이 else "불완전"   # 한 토큰만으로는 못 푸는 바이트 조각
        print(f"   {토큰id:5d}: {조각!r:8} = {바이트.hex(' '):8} 단독={단독}")
    print("   전체 복원:", repr(decode(ids)))

'Hello' (5 바이트) -> 1 토큰
   15496: 'Hello'  = 48 65 6c 6c 6f 단독='Hello'
   전체 복원: 'Hello'
'한' (3 바이트) -> 2 토큰
   47991: 'íķ'     = ed 95    단독=불완전
     250: 'ľ'      = 9c       단독=불완전
   전체 복원: '한'
'한국어' (9 바이트) -> 8 토큰
   47991: 'íķ'     = ed 95    단독=불완전
     250: 'ľ'      = 9c       단독=불완전
     166: 'ê'      = ea       단독=불완전
     113: 'µ'      = b5       단독=불완전
     255: 'Ń'      = ad       단독=불완전
     168: 'ì'      = ec       단독=불완전
     244: 'ĸ'      = 96       단독=불완전
     112: '´'      = b4       단독=불완전
   전체 복원: '한국어'

'한'(3바이트)을 예로 들면 토큰 두 개로 쪼개집니다.

토큰 ID	바이트-문자	바이트	단독 디코딩
`47991`	`íķ`	`ed 95`	불완전
`250`	`ľ`	`9c`	불완전

'Hello'(5바이트)는 통째로 한 토큰(ID 15496)입니다 — 자주 등장해 하나로 병합됐기 때문입니다.
'한'은 2토큰, '한국어'는 8토큰 으로 쪼개집니다.
한글 토큰은 대부분 글자보다 작은 바이트 조각 이라, 토큰 하나만 떼어 디코딩하면 불완전한 UTF-8이라 온전한 글자가 되지 않습니다(파이썬은 대체 문자 U+FFFD로 표시). 바이트를 전부 모아 decode(ids) 로 한 번에 풀어야 '한국어' 가 복원됩니다.

GPT-2가 영어 위주로 학습돼 한글 병합 규칙이 적은 탓에, 같은 의미라도 한국어가 영어보다 토큰을 훨씬 많이 씁니다.

3.6토큰에서 온전한 음절로¶

앞 절에서 한글 토큰 하나는 대개 글자보다 작은 바이트 조각이라 단독으로는 디코딩되지 않았습니다. 그렇다면 토큰을 하나씩 받을 때(예: 모델이 생성하는 중) 언제 한 음절이 완성되는지 는 어떻게 알까요? 정답은 토큰 ID가 아니라 바이트 에 있습니다 — UTF-8은 바이트만 보고 글자 경계를 알 수 있게(자기 동기화) 설계돼 있기 때문입니다.

한글 음절(U+AC00~U+D7A3)은 모두 3바이트 입니다. 선두 바이트(0xEA~0xED)가 "이제부터 3바이트가 한 글자"임을 알리고, 이어지는 10xxxxxx 형태의 연속 바이트 2개가 채워지면 한 음절이 완성됩니다. 파이썬의 점진적(incremental) 디코더가 이 버퍼링을 대신 해 줍니다 — 바이트가 모자라면 빈 문자열을, 글자가 완성되면 그 글자를 돌려줍니다.

import codecs

음절디코더 = codecs.getincrementaldecoder("utf-8")()
for 토큰id in encode("한국어"):
    바이트 = bytes(byte_decoder[문자] for 문자 in decoder[토큰id])
    음절 = 음절디코더.decode(바이트)             # 불완전하면 "", 완성되면 그 글자
    상태 = repr(음절) if 음절 else "대기(바이트 더 필요)"
    print(f"   토큰 {토큰id:5d}  +{바이트.hex(' '):5}  ->  {상태}")

   토큰 47991  +ed 95  ->  대기(바이트 더 필요)
   토큰   250  +9c     ->  '한'
   토큰   166  +ea     ->  대기(바이트 더 필요)
   토큰   113  +b5     ->  대기(바이트 더 필요)
   토큰   255  +ad     ->  '국'
   토큰   168  +ec     ->  대기(바이트 더 필요)
   토큰   244  +96     ->  대기(바이트 더 필요)
   토큰   112  +b4     ->  '어'

'한국어'의 8개 토큰은 3바이트씩 모여 세 번 — 한, 국, 어 — 음절을 완성합니다. 즉 "어떤 토큰들이 한 음절을 이루는가"는, 선두 바이트가 요구하는 길이만큼 연속 바이트가 모일 때까지 토큰을 누적해 결정합니다. 모델이 토큰을 하나씩 생성하는 스트리밍 출력도 같은 원리입니다 — 바이트가 온전한 글자를 이루기 전에는 화면에 내보내지 않아야 깨진 글자가 보이지 않습니다.

3.7검증 — `tiktoken` 과 한 토큰도 다르지 않게¶

우리가 만든 인코더가 GPT 장에서 쓰는 바로 그 토크나이저(tiktoken 의 "gpt2")와 정확히 같은 결과를 내는지 확인합니다.

import tiktoken
gpt2 = tiktoken.get_encoding("gpt2")

샘플 = [
    "The quick brown fox jumps over the lazy dog.",
    "Hello, world! GPT-2 uses byte-level BPE.",
    "한국어도 UTF-8 바이트로 처리됩니다.",
    "numbers 12345 and emoji 🤖 and don't",
]
for t in 샘플:
    assert encode(t) == gpt2.encode(t)      # 토큰 ID 완전 일치
    assert decode(encode(t)) == t           # 왕복 복원
print("일치 — 직접 만든 BPE == tiktoken('gpt2')")

print("\n예) ", repr(샘플[0]))
print("토큰 ID :", encode(샘플[0]))
print("조각    :", [decode([i]) for i in encode(샘플[0])])

일치 — 직접 만든 BPE == tiktoken('gpt2')

예)  'The quick brown fox jumps over the lazy dog.'
토큰 ID : [464, 2068, 7586, 21831, 18045, 625, 262, 16931, 3290, 13]
조각    : ['The', ' quick', ' brown', ' fox', ' jumps', ' over', ' the', ' lazy', ' dog', '.']

영어·한국어·이모지·축약형·여러 공백까지 모두 tiktoken 과 한 토큰도 다르지 않게 일치합니다. 즉 우리는 GPT-2 토크나이저를 라이브러리 없이 완전히 재현했고, GPT 장의 tiktoken.get_encoding("gpt2") 가 내부에서 하는 일을 이제 정확히 압니다.

왜 ‘비슷한’ 토큰화가 아니라 ID까지 똑같아야 하나

사전훈련 모델을 쓰려면 토크나이저가 그 모델이 학습된 바로 그것 이어야 합니다. GPT 모델의 임베딩 표 wte 는 토큰 ID로 직접 색인 되기 때문입니다 — $i$ 번째 행이 토큰 ID $i$ 의 학습된 벡터입니다. 만약 우리 토크나이저가 "The" 에 GPT-2와 다른 ID를 매긴다면, 모델은 wte[엉뚱한 ID] 를 집어 전혀 다른 벡터를 받고 출력이 망가집니다. 출력단의 언어모델 헤드도 같은 50,257개 ID 위에 분포를 내므로, 토큰화 · 모델 · 역토큰화가 같은 어휘 ID 체계를 공유 해야만 동작합니다. 우리가 부분 단어 분절이 그럴듯한 데서 그치지 않고 토큰 ID까지 완전히 일치 시킨 이유가 바로 이것입니다.

4정리¶

BPE 학습은 최빈 인접 쌍을 반복 병합 하는 단순한 규칙입니다(1부). 병합 순서가 곧 토크나이저 규칙(merges)이 됩니다.
실제 GPT-2 토크나이저는 바이트 단위(byte-level) 로 동작해 OOV가 없고, 학습된 vocab.json·merges.txt 를 그대로 불러와 재현합니다(2부).
인코딩은 학습 때의 빈도 가 아니라 병합 우선순위(rank) 로 합치는 것이 핵심이며, bytes_to_unicode 표(공백 $\to$ Ġ)와 GPT-2 정규식까지 맞추면 tiktoken("gpt2") 과 완전히 일치 합니다.

References¶

Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 1715–1725. 10.18653/v1/P16-1162