Build a Tokenizer by Hand

Goal

Build byte-level BPE yourself using only the standard library. Starting from UTF-8 bytes, count adjacent pairs, learn rules that merge the most common pair, apply those rules in the order they were learned to encode, and then restore the original text exactly. Finally, vary the vocabulary size and measure the curve along which the token count falls, and encode a Korean paragraph and an English paragraph of the same content with a single vocabulary and set the token counts side by side.

Why it matters

Both pricing and the context limit are in tokens, but a token is neither a character nor a word. Which pieces count as one is decided when the vocabulary is built, and the vocabulary differs from model to model. So the estimate "multiply the character count by something" falls apart the moment the language changes. A single Hangul syllable is 3 bytes in UTF-8, so with a small vocabulary one character becomes three tokens. This lab does not call the tokenizer of a real model. This Pod has no transformers, tokenizers or tiktoken, and the system Python has no numpy either. Instead you build the same algorithm by hand and use only numbers measured with the vocabulary you built. So statements like "model X counts this sentence as N tokens" are not made here. The algorithm itself is one sentence — merge the two items that most often appear together into one, and repeat until the vocabulary reaches the size you want. The difficulty is in the details. If it is not fixed how to count overlapping positions, how to break ties, and in what order to apply the rules when encoding, the vocabulary differs every time even for the same text. The grader does not trust the explanations you wrote down. It actually imports your module, pokes at the functions directly with different inputs every time, and checks them against values the grader computes separately. The inputs change on every run, so you cannot memorize values and plug them in.

Steps

1. In /root/work/tf-token/bpe.py, create the sample paragraphs SAMPLE_KO and SAMPLE_EN and to_ids(text) and from_ids(ids). Open the text into a list of UTF-8 bytes and turn it back into text.
2. Add count_pairs(ids) so that it counts how many times each pair of neighbors appears together. The key is a (앞, 뒤) pair (the placeholders are the first and second item of the pair), and overlapping positions are counted as they are.
3. Add merge(ids, pair, new_id) so that it replaces each place where that pair occurs with one new number. It goes from the left, without overlapping.
4. Create MIN_PAIR_COUNT = 2 and train(text, vocab_size) and have them collect the merge rules in the order they were learned. New numbers go up one at a time from 256.
5. Create encode(text, merges) so that it applies the merges in exactly the order they were learned.
6. Create decode(ids, merges) so that it expands the numbers all the way and restores the original text. Even if characters that were not in the vocabulary are mixed in, the result must not differ from the original by a single character.
7. Create vocab_curve(text, sizes) so that it measures how many tokens the same text becomes at each vocabulary size. It returns a list of (어휘크기, 토큰수) pairs (the placeholders are the vocabulary size and the token count).
8. Learn two vocabularies, measure the same two paragraphs, and record the results in /root/work/tf-token/token_report.json and /root/work/tf-token/token_report.md.

Notes

• Execution contract: the grader imports /root/work/tf-token/bpe.py as a Python module and uses SAMPLE_KO, SAMPLE_EN, to_ids, from_ids, count_pairs, merge, MIN_PAIR_COUNT, train, encode, decode and vocab_curve directly. It does not run it as a script, so if __name__ == "__main__" is not needed.
• Write the sample paragraphs with the same content in two languages. SAMPLE_KO must be at least 300 characters, mostly Hangul, and SAMPLE_EN at least 300 characters using only ASCII. Choose the content freely.
• to_ids(text) returns the bytes of text.encode("utf-8") as a list of integers. Not character numbers (ord).
• from_ids(ids) must not raise an exception even when fragmented bytes come in. Use the errors argument of decode.
• count_pairs([9, 9, 9]) is {(9, 9): 2}. Overlapping positions are counted as they are.
• merge([5, 5, 5], (5, 5), 300) is [300, 5]. After the first two are swallowed, the remaining 5 loses its partner. Do not modify the list you received in place; build a new list.
• One round of train: count adjacent pairs, pick the pair that appears most often, and merge that pair into a new number. In case of a tie, pick the pair whose (앞, 뒤) is smaller in dictionary order (the placeholders are the first and second item of the pair). Stop when the chosen pair appears fewer than MIN_PAIR_COUNT times. The return value is a list of ((앞, 뒤), 새번호) pairs (the placeholders are the pair of items and the new number), and the order is the order learned.
• train(text, 256) is an empty list. 0 to 255 are already used by bytes, so there is no room to make a new number.
• encode applies merges once each in the order received. Do not sort or repeat them.
• decode expands a new number into two, and if one of those two is again a new number, it expands that again. When nothing is left, it reads the result with from_ids.
• The step 8 report learns two vocabularies. Both have size 512. One is the shared vocabulary learned from SAMPLE_KO and SAMPLE_EN joined by a single newline, and the other is the English-only vocabulary learned from SAMPLE_EN alone. Encode the same two paragraphs with each of the two vocabularies and compare the token counts.
• vocab_size is only an upper bound. When the pairs worth merging run out, it stops at MIN_PAIR_COUNT, so the actual number of rules may be smaller than 512 minus 256. That is why you write the number of rules actually learned in shared_rules and en_only_rules.
• Measure the curve on the joined text at sizes 256, 320, 384 and 512.
• This Pod has no internet. pip install does not work and there are no transformers, tokenizers or tiktoken. numpy exists only inside /opt/onnx-lab/bin/python, so import numpy does not work in the system Python. The standard library is enough.
• Official documents: the original BPE paper · Hugging Face — Byte-Pair Encoding tokenization · Attention Is All You Need
• Common mistakes: using character numbers instead of bytes, counting pairs by skipping two positions at a time, advancing only one position at a time when merging and so swallowing overlaps, not fixing a tie-breaking rule, sorting the rules when encoding, and finishing decoding after expanding only one layer.

Open text into bytes

In /root/work/tf-token/bpe.py, create the sample paragraphs SAMPLE_KO (at least 300 characters, mostly Hangul) and SAMPLE_EN (at least 300 characters, ASCII only), and to_ids(text) and from_ids(ids). to_ids returns the UTF-8 bytes as a list of integers, and from_ids turns that back into text.

text.encode("utf-8") gives the byte string, and wrapping it in list() gives a list of integers from 0 to 255. To turn it back, gather it with bytes(ids) and decode it. It must not raise an exception even if a fragment cut in the middle of a character comes in, so pass the errors argument. The two samples must be written with the same content in two languages so that you can compare them later.

Count the neighbors

Add count_pairs(ids). It counts how many times each pair of neighbors appears together and returns {(앞, 뒤): 횟수} (the placeholders are the first item, the second item and the count). Overlapping positions are counted as they are, so count_pairs([9, 9, 9]) is {(9, 9): 2}.

zip(ids, ids[1:]) lets you sweep the neighboring pairs in one pass. If you count by skipping two positions at a time, you miss the overlapping positions, and then the judgment of what is worth merging goes off. If the list is empty or has only one element, the result is an empty dictionary.

Merge one pair into one

Add merge(ids, pair, new_id). It replaces each place where pair occurs with one new number. It goes from the left without overlapping, so merge([5, 5, 5], (5, 5), 300) is [300, 5]. Leave the list you received as it is and return a new list.

A while loop that moves the index by hand is the most accurate. When you find the pair, advance two positions; otherwise advance only one. If you advance only one at a time, you would see the new number you just made as the front of a pair again, swallowing overlaps. If you modify the list in place, the value the caller was holding changes silently.

Learn the merge rules

Create MIN_PAIR_COUNT = 2 and train(text, vocab_size). Repeat counting adjacent pairs, picking the pair that appears most often (in case of a tie, the pair whose (앞, 뒤) is smaller in dictionary order, where the placeholders are the first and second item of the pair), and merging that pair into a new number. New numbers go up one at a time from 256, and the return value is a list of ((앞, 뒤), 새번호) pairs (the placeholders are the pair of items and the new number).

You must count again on every round — because the neighbor relationships change after a merge. The key of max(counts.items(), key=...) can express the tie rule as well in one go. Stop when the chosen pair appears fewer than MIN_PAIR_COUNT times. Merging a pair that appears only once only enlarges the vocabulary and does not reduce the tokens at all. If vocab_size is 256, there is no room to make a new number, so the result is an empty list.

Encode in the learned order

Create encode(text, merges). After opening the text into bytes, apply merges once each in exactly the order received. Do not sort or repeat them.

A rule learned later uses the numbers made earlier as its material. That is why changing the order gives different results even from the same rule list. The function is done in three lines — open into bytes, call merge for each rule, and return the remaining list.

Restore it without a single character of difference

Create decode(ids, merges). Expand a new number into two, and if one of those two is again a new number, expand it again. When nothing is left, only bytes remain, and you read them as text. Even text that mixes in characters that were not in training must not differ from the original by a single character.

If you build a {새번호: (앞, 뒤)} table (the placeholders are the new number and the pair of items it stands for), expanding is just looking at that table. You must not finish after expanding only one layer — the expanded value may again be a new number. After everything is expanded, from_ids can be used as it is. Characters that were not in the vocabulary are always written as bytes, so in this structure it does not fail even when a character seen for the first time arrives.

A larger vocabulary means fewer tokens

Create vocab_curve(text, sizes). For each vocabulary size in sizes, learn the rules from scratch on that text, encode the same text, and measure the token count. The return value is a list of (어휘크기, 토큰수) pairs (the placeholders are the vocabulary size and the token count), in the same order as sizes.

You must measure each size with the rules of that size. If you learn once with the largest vocabulary and measure every point with those rules, the curve goes flat. If you use the train and encode you built earlier as they are, the function is five lines. Note that, because this algorithm chooses looking only forward, the result of train(글, 300) is the same as the front part of the result of train(글, 400) (the placeholder is the text) — raising the size means running longer, not choosing again. Look with your own eyes at how the amount of decrease changes.

Whose text was the vocabulary made from

Learn two vocabularies. One is a shared vocabulary of size 512 learned from SAMPLE_KO and SAMPLE_EN joined by a single newline, and the other is an English-only vocabulary of size 512 learned from SAMPLE_EN alone. After encoding the same two paragraphs with each of the two vocabularies, write vocab_size, ko_chars, ko_bytes, en_chars, en_bytes, shared_rules, en_only_rules, ko_tokens_shared, en_tokens_shared, ko_tokens_en_only, en_tokens_en_only, ko_bytes_per_token, en_bytes_per_token, curve and roundtrip_ok in /root/work/tf-token/token_report.json, and write /root/work/tf-token/token_report.md in the four sections ## 무엇을 쟀나 ## 어휘를 키우면 토큰이 어떻게 줄었나 ## 한국어가 손해를 보는 이유 ## 바이트 수준이라 안 깨지는 것 (the Korean headings mean "What was measured", "How tokens decreased as the vocabulary grew", "Why Korean loses out" and "What does not break because it is at the byte level").

Do not write the numbers by hand; fill them in with values obtained by actually running your own code. shared_rules and en_only_rules are the number of rules train() actually returned — even if you give size 512, it stops before that when the pairs to merge run out. ko_bytes_per_token and en_bytes_per_token are the byte count divided by the token count, based on the shared vocabulary. curve is [[크기, 토큰수], ...] measured on the joined text at sizes 256, 320, 384 and 512 (the placeholders are the size and the token count). roundtrip_ok is whether the two paragraphs come back exactly to the original with both vocabularies — that even Korean encoded with the English-only vocabulary comes back is the property of being at the byte level.