Building a BPE Tokeniser From Scratch

Goal

You implement a BPE tokenizer in pure Python with no libraries and complete one full cycle from training to encoding and decoding.

Why it matters

The tokenizer is the component that runs first and is understood least in an LLM pipeline. Yet a lot is decided here. Prompt cost is charged by token count, not character count, and the context length limit is also in tokens. The reason a model is especially weak on questions about the spelling of a word is also that token boundaries differ from character boundaries.

When you build one yourself, you find out that these properties are not abstract stories but natural consequences of the implementation. In particular, when you measure the compression ratio in the last step, you can confirm in numbers why Korean uses more tokens than English.

This lab does not download a model. You need neither the internet nor a GPU. The corpus is 30 Korean documents in the docs table of the lab database.

Steps

The working directory is /root/llm. You are graded only if you follow the rules exactly.

1. Save the body of the docs table, ordered by id ascending, one per line in /root/llm/corpus.txt. It is 30 lines.
2. Save the frequency of each character in the corpus to /root/llm/char_freq.tsv. The format is 문자<탭>빈도 (character, tab, frequency), and whitespace characters are not counted. Sort by frequency descending, and by character ascending when equal.
3. Save the base vocabulary to /root/llm/vocab_base.txt, one per line. Take the set of characters in the corpus (excluding whitespace) plus the end-of-word marker character _, sorted by code point ascending.
4. Save 120 BPE merge rules to /root/llm/merges.txt. On each line, write 앞토큰 뒤토큰 (first token, second token) separated by a space. The training rules are these.
   • Split each line on spaces to make words, and start each word as the list 문자들 + ['_'] (the word's characters plus the end marker).
   • At each step, count the frequency of adjacent pairs across all words and merge the pair with the highest frequency.
   • If frequencies are equal, choose the pair that is smaller in alphabetical order as the tuple (앞토큰, 뒤토큰) (first token, second token).
   • Apply the merge in each word from the left without overlap.
5. Save the final vocabulary to /root/llm/vocab.tsv in the format 토큰<탭>id (token, tab, id). Put the base characters from step 3 in order starting at 0, then append the tokens produced by merges in merge order.
6. Convert each document into a sequence of token ids and save it to /root/llm/encoded.tsv. The format is docs.id<탭>id id id ... on each line (docs.id, tab, then the ids), and it is 30 lines. Encoding applies the learned merge rules in the recorded order.
7. Restore the original text from vocab.tsv and encoded.tsv alone and save it to /root/llm/decoded.txt. After you concatenate the tokens, turn _ into a space and strip trailing whitespace at the end of the line, the result must equal the original.
8. Save one line to /root/llm/stats.tsv as 문자수<탭>토큰수<탭>압축비 (character count, tab, token count, tab, compression ratio). The character count is the sum of the lengths of the corpus lines (spaces included), the token count is the total number of tokens, and the compression ratio is the character count divided by the token count, rounded to three decimal places.

Notes

• Extracting the corpus: PGPASSWORD=lab psql -tA -h 127.0.0.1 -U lab -d labdb -c "select body from docs order by id"
• Use only Python. collections.Counter is convenient but not required.
• Common mistake 1: if you leave out the tie handling in merges, the rule order changes and every later step goes off.
• Common mistake 2: if you leave out the end-of-word marker, you cannot restore spaces when decoding.

Download the corpus

Save the body of the docs table, ordered by id ascending, one per line in /root/llm/corpus.txt. It is 30 lines.

Write the body of the docs table to the file one per line, in id order. It is convenient to use the psql option that prints only the result.

Count character frequencies

Save the frequency of each character in the corpus to /root/llm/char_freq.tsv. The format is 문자<탭>빈도 (character, tab, frequency), and whitespace characters are not counted. Sort by frequency descending, and by character ascending when equal.

Do not count whitespace. Note that there are two sort keys.

Build the base character vocabulary

Save the base vocabulary to /root/llm/vocab_base.txt, one per line. Take the set of characters in the corpus (excluding whitespace) plus the end-of-word marker character _, sorted by code point ascending.

In addition to the characters that appear in the corpus, the marker character that indicates the end of a word also goes in the vocabulary.

Learn 120 merge rules

Save 120 BPE merge rules to /root/llm/merges.txt. On each line, write 앞토큰 뒤토큰 (first token, second token) separated by a space. The training rules are these.

• Split each line on spaces to make words, and start each word as the list 문자들 + ['_'] (the word's characters plus the end marker).
• At each step, count the frequency of adjacent pairs across all words and merge the pair with the highest frequency.
• If frequencies are equal, choose the pair that is smaller in alphabetical order as the tuple (앞토큰, 뒤토큰) (first token, second token).
• Apply the merge in each word from the left without overlap.

You have to recount the frequency of adjacent pairs at every step. Follow the tie-handling rule exactly.

Build the final vocabulary

Save the final vocabulary to /root/llm/vocab.tsv in the format 토큰<탭>id (token, tab, id). Put the base characters from step 3 in order starting at 0, then append the tokens produced by merges in merge order.

Put the base characters in first, then append in the order in which the merges happened. The ids are consecutive from 0.

Convert documents to token id sequences

Convert each document into a sequence of token ids and save it to /root/llm/encoded.tsv. The format is docs.id<탭>id id id ... on each line (docs.id, tab, then the ids), and it is 30 lines. Encoding applies the learned merge rules in the recorded order.

You must apply the merge rules in the same order as in training to get the same result.

Restore the original from the id sequence alone

Restore the original text from vocab.tsv and encoded.tsv alone and save it to /root/llm/decoded.txt. After you concatenate the tokens, turn _ into a space and strip trailing whitespace at the end of the line, the result must equal the original.

After concatenating the tokens, turn the end-of-word marker back into a space. Remove the extra trailing whitespace at the end of the line.

Calculate the compression ratio

Save one line to /root/llm/stats.tsv as 문자수<탭>토큰수<탭>압축비 (character count, tab, token count, tab, compression ratio). The character count is the sum of the lengths of the corpus lines (spaces included), the token count is the total number of tokens, and the compression ratio is the character count divided by the token count, rounded to three decimal places.

Divide the character count by the token count. The character count includes spaces.