Merging a pair

We know the most common pair is (32, 116) — " t". Now we merge it: invent a brand-new token to stand for that pair, and replace every occurrence in the sequence with it. Since bytes already use up ids 0–255, our first new token gets id 256. The next gets 257, and so on — that's how the vocabulary grows beyond bytes.

The merge function

merge walks the list and, wherever it sees the target pair back-to-back, writes the single new id instead of the two old ones. Everything else is copied through unchanged:

def merge(ids, pair, new_id):
  out = []
  i = 0
  while i < len(ids):
      # if the pair starts here, emit the new id and skip both elements
      if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
          out.append(new_id)
          i += 2
      else:
          out.append(ids[i])
          i += 1
  return out

The i += 2 is the key detail: after merging a pair we jump past both elements, so we never merge overlapping copies by mistake.

Watch it shrink

Merge the top pair into token 256 and the sequence gets shorter — every " t" is now one token instead of two:

stats = get_stats(ids)
top = max(stats, key=stats.get)          # (32, 116)
new_ids = merge(ids, top, 256)

print("before:", len(ids), "tokens")
print("after: ", len(new_ids), "tokens")

before: 247 tokens
after:  231 tokens

Sixteen " t" pairs collapsed into sixteen single tokens, so the length dropped by 16 (247 → 231). We've traded a bigger vocabulary (one new token) for a shorter sequence. Do that once and you've compressed the text a little. Do it in a loop — each time on whatever pair is now most common — and you've trained a tokenizer. That's the next chapter.