{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-1 fw=all -->\n",
    "\n",
    "# From Text to Tokens\n",
    "\n",
    "The sequence models of this chapter will spend most of their time reading\n",
    "and writing text. Text poses a problem that the synthetic series of\n",
    "that section did not: neural networks consume vectors of numbers,\n",
    "while text arrives as a string of characters. Before we can model language,\n",
    "we must decide how to carve a string into *tokens*, the atomic units that\n",
    "our models will treat as observations $x_t$, and how to map each token to a\n",
    "numerical index. This choice looks like bookkeeping but turns out to shape\n",
    "everything downstream: the size of the model's output layer, the effective\n",
    "length of every document it reads, and even which arithmetic problems it\n",
    "can solve. Every modern language model ships with a tokenizer, and the\n",
    "tokenizer is best thought of as part of the model.\n",
    "\n",
    "This section builds tokenization up from first principles. We start with\n",
    "the two obvious schemes, characters and words, and see that they sit at\n",
    "opposite ends of a trade-off. We then rebuild text from raw bytes and learn\n",
    "a vocabulary *from data* with byte pair encoding (BPE), the algorithm\n",
    "behind essentially every production tokenizer today\n",
    "[@Sennrich.Haddow.Birch.2015; @Radford.Wu.Child.ea.2019]. Our\n",
    "implementation is small enough to read in one sitting, yet exact: at the\n",
    "end of the section we load the published merge table of GPT-2 into it and\n",
    "reproduce the output of OpenAI's `tiktoken` library token for token.\n",
    "\n",
    "## Reading the Dataset\n",
    "\n",
    "Throughout the chapter we work with H. G. Wells'\n",
    "[The Time Machine](http://www.gutenberg.org/ebooks/35), a novella of just\n",
    "over 30,000 words. Real corpora are measured in trillions of tokens, but\n",
    "this one is large enough to exhibit the statistics that matter and small\n",
    "enough to tokenize in seconds. The `_download` method reads the raw text\n",
    "into a single string."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-converting-raw-text-into-sequence-data"
   },
   "source": [
    "import collections\n",
    "import re\n",
    "import tiktoken\n",
    "from d2l import jax as d2l\n",
    "import jax"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-reading-the-dataset-1"
   },
   "source": [
    "class TimeMachine(d2l.DataModule):\n",
    "    \"\"\"The Time Machine dataset.\"\"\"\n",
    "    def _download(self):\n",
    "        fname = d2l.download(d2l.DATA_URL + 'timemachine.txt', self.root,\n",
    "                             '090b5e7e70c295757f55df93cb0a180b9691891a')\n",
    "        with open(fname) as f:\n",
    "            return f.read()\n",
    "\n",
    "data = TimeMachine()\n",
    "raw_text = data._download()\n",
    "raw_text[:60]"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "'The Time Machine, by H. G. Wells [1898]\\n\\n\\n\\n\\nI\\n\\n\\nThe Time Tra'"
     },
     "metadata": {},
     "execution_count": 2
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-2 fw=all -->\n",
    "\n",
    "Classical preprocessing pipelines aggressively normalized text of this\n",
    "kind: they stripped punctuation, folded everything to lowercase, and only\n",
    "then split it into units. We keep such a step around, both because it\n",
    "simplifies the character- and word-level experiments below and because\n",
    "several later sections reuse it, but note its cost. Normalization throws\n",
    "away information (capitalization distinguishes \"Bill\" from \"bill\") and it\n",
    "already commits us to decisions about what a token may look like. The\n",
    "byte-level tokenizer we build later in this section needs no normalization\n",
    "at all."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-reading-the-dataset-2"
   },
   "source": [
    "@d2l.add_to_class(TimeMachine)\n",
    "def _preprocess(self, text):\n",
    "    return re.sub('[^A-Za-z]+', ' ', text).lower()\n",
    "\n",
    "text = data._preprocess(raw_text)\n",
    "text[:60]"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "'the time machine by h g wells i the time traveller for so it'"
     },
     "metadata": {},
     "execution_count": 3
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-3 fw=all -->\n",
    "\n",
    "## Characters, Words, and Bytes\n",
    "\n",
    "### Two Ends of a Spectrum\n",
    "\n",
    "*Tokens* are the indivisible units that a sequence model reads, one per\n",
    "time step. The two schemes that suggest themselves immediately are\n",
    "characters and words, and it is instructive to try both."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-tokenization"
   },
   "source": [
    "@d2l.add_to_class(TimeMachine)\n",
    "def _tokenize(self, text):\n",
    "    return list(text)\n",
    "\n",
    "tokens = data._tokenize(text)\n",
    "','.join(tokens[:30])"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "'t,h,e, ,t,i,m,e, ,m,a,c,h,i,n,e, ,b,y, ,h, ,g, ,w,e,l,l,s, '"
     },
     "metadata": {},
     "execution_count": 4
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-4 fw=all -->\n",
    "\n",
    "Splitting on whitespace instead yields word tokens. Comparing the two\n",
    "schemes on our corpus makes the trade-off concrete: we count the number of\n",
    "*distinct* token values (the vocabulary a model must handle) and the total\n",
    "number of tokens (the length of the sequence a model must process)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-two-ends-of-a-spectrum-1"
   },
   "source": [
    "words = text.split()\n",
    "print(f'characters: {len(set(tokens)):>6} distinct, '\n",
    "      f'{len(tokens):>7} tokens in the corpus')\n",
    "print(f'words:      {len(set(words)):>6} distinct, '\n",
    "      f'{len(words):>7} tokens in the corpus')"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "characters:     27 distinct,  173428 tokens in the corpus\nwords:        4579 distinct,   32775 tokens in the corpus\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-5 fw=all -->\n",
    "\n",
    "Character tokenization needs a vocabulary of a few dozen symbols and can\n",
    "represent any input, but it stretches the corpus to some 170,000 time\n",
    "steps, and every long-range relationship (say, between a subject and its\n",
    "verb) must be carried across dozens of steps. Word tokenization compresses\n",
    "the same text into a fifth as many tokens, each far more meaningful, but\n",
    "already on this small corpus it produces thousands of distinct types, and\n",
    "the vocabulary keeps growing with the corpus: every name, typo, and\n",
    "inflection (\"traveller\", \"travellers\", \"travelled\") claims its own slot.\n",
    "Worse, any word not seen during training is simply *out of vocabulary*\n",
    "(OOV) at test time. the figure places the two\n",
    "schemes on a common axis: vocabulary size buys shorter sequences, and the\n",
    "interesting question is where between the extremes to sit. Subword\n",
    "tokenizers, to which we now turn, let us choose that operating point\n",
    "freely.\n",
    "\n",
    "![Tokenization granularities on one trade-off curve: a larger vocabulary encodes the same text in fewer tokens. Characters and bytes never fall out of vocabulary; a fixed word list does. Byte pair encoding interpolates between the extremes.](../img/mdl-rnn-granularity-spectrum.svg)\n",
    "\n",
    "### Text as Bytes\n",
    "\n",
    "Before we can interpolate between characters and words we need a base\n",
    "alphabet that is truly universal. \"Characters\" are shakier ground than they\n",
    "appear: Unicode defines around 150,000 of them, covering scripts, accents,\n",
    "and emoji, so a character-level vocabulary is not small at all once we\n",
    "leave English. The fix used by modern tokenizers is to go one level lower.\n",
    "Every string your computer stores is ultimately a sequence of *bytes*\n",
    "under some encoding, almost always UTF-8. A byte holds one of $2^8 = 256$\n",
    "values, so a byte-level model needs a base vocabulary of exactly 256\n",
    "symbols, and *no input can ever be out of vocabulary*: any string, in any\n",
    "language, with any typo, is some sequence of bytes.\n",
    "\n",
    "UTF-8 is a variable-length code: it spends one byte on ASCII characters\n",
    "and up to four on rarer ones."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-text-as-bytes"
   },
   "source": [
    "s = 'Hello, naïve café: 你好 🚀'\n",
    "print(len(s), 'characters,', len(s.encode('utf-8')), 'bytes')\n",
    "for ch in 'a é 你 🚀'.split():\n",
    "    print(repr(ch), '->', list(ch.encode('utf-8')))"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "23 characters, 32 bytes\n'a' -> [97]\n'é' -> [195, 169]\n'你' -> [228, 189, 160]\n'🚀' -> [240, 159, 154, 128]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-6 fw=all -->\n",
    "\n",
    "The price of universality is length. English text costs about one byte per\n",
    "character, but the accented \"é\" costs two, the Chinese character three,\n",
    "and the emoji four: raw bytes stretch non-English text even further than\n",
    "they stretch English. How many tokens a tokenizer spends per word of a\n",
    "language is called its *fertility*, and we will measure it at the end of\n",
    "this section. Keep this cost in mind: everything that follows is an\n",
    "attempt to keep the universality of bytes while clawing back the length.\n",
    "\n",
    "## Byte Pair Encoding\n",
    "\n",
    "### The Merge Rule\n",
    "\n",
    "Byte pair encoding starts from the 256 byte symbols and grows the\n",
    "vocabulary greedily: count how often each *pair* of adjacent tokens occurs\n",
    "in the training corpus, merge the most frequent pair into a single new\n",
    "token, and repeat until the vocabulary reaches a target size\n",
    "[@Sennrich.Haddow.Birch.2015]. Each merge shortens the corpus by the\n",
    "number of occurrences it collapses, so BPE is a greedy compression\n",
    "algorithm, and its vocabulary is a learned dictionary of the corpus's most\n",
    "common fragments.\n",
    "\n",
    "The algorithm is best seen once in slow motion. Take the toy corpus below,\n",
    "five distinct words in eight occurrences:\n",
    "\n",
    "```\n",
    "hug pug pun bun hugs hug hug pug\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-7 fw=all -->\n",
    "\n",
    "The corpus is 32 bytes long. The most frequent adjacent pair is\n",
    "(`u`, `g`), which occurs six times (in \"hug\", \"pug\", and \"hugs\"), so the\n",
    "first merge creates the token `ug`. After replacing every occurrence, the\n",
    "most frequent pair is (`h`, `ug`), and so on:\n",
    "\n",
    "| step | most frequent pair | count | new token | corpus length |\n",
    "|:----:|:------------------:|:-----:|:---------:|:-------------:|\n",
    "| 0    | (start from bytes) |       |           | 32            |\n",
    "| 1    | `u`, `g`           | 6     | `ug`      | 26            |\n",
    "| 2    | `h`, `ug`          | 4     | `hug`     | 22            |\n",
    "| 3    | `hug`, `' '`       | 3     | `'hug '`  | 19            |\n",
    "\n",
    "Two things are worth noticing. First, merges compose: the token `hug` is\n",
    "built on top of `ug`, so the learned vocabulary forms a *merge tree* over\n",
    "the byte alphabet (the figure), and any new text can be\n",
    "retokenized by replaying the same merges. The word \"hugs\", for instance,\n",
    "becomes the two tokens `hug` and `s`; the rare word \"bun\" stays as three\n",
    "raw bytes. Nothing is ever out of vocabulary, because unmergeable input\n",
    "simply falls back to bytes. Second, the third merge already glued a word\n",
    "to the *space that follows it*: nothing stops BPE from merging across word\n",
    "boundaries. Hold that thought; it becomes a real problem on a real corpus.\n",
    "\n",
    "![The first three merges learned on the toy corpus form a tree over the byte alphabet. New text reuses the tree: \"hugs\" becomes two tokens, while unseen fragments fall back to bytes.](../img/mdl-rnn-merge-tree.svg)\n",
    "\n",
    "### Implementation\n",
    "\n",
    "The trainer below implements exactly the loop we just traced. Token ids 0\n",
    "through 255 denote raw bytes; each learned merge gets the next free id, so\n",
    "ids double as merge *ranks*: a smaller id means the merge was learned\n",
    "earlier. The optional `pattern` and `specials` arguments will be explained\n",
    "shortly; both defaults are harmless for now. Note that we import `regex`,\n",
    "a drop-in extension of Python's `re` whose Unicode character classes\n",
    "(such as `\\p{L}` for \"any letter\") we will need for pre-tokenization."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-implementation-1"
   },
   "source": [
    "\n",
    "import regex\n",
    "\n",
    "class BPETokenizer:\n",
    "    \"\"\"Byte-level BPE tokenizer trained by iterated most-frequent-pair\n",
    "    merges.\n",
    "\n",
    "    Token ids 0..255 are raw bytes; learned merges get ids\n",
    "    256..vocab_size-1; special tokens sit above those and are never\n",
    "    produced by BPE itself. `pattern` is an optional pre-tokenization\n",
    "    regex: text is split into chunks and merges never cross chunk\n",
    "    boundaries.\n",
    "    \"\"\"\n",
    "\n",
    "    GPT2_PATTERN = (r\"'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+\"\n",
    "                    r\"| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)|\\s+\")\n",
    "\n",
    "    def __init__(self, vocab_size=1024, pattern=None,\n",
    "                 specials=('<pad>', '<bos>', '<eos>')):\n",
    "        self.vocab_size, self.pattern = vocab_size, pattern\n",
    "        self.merges = {}                                  # (id, id) -> new id\n",
    "        self.vocab = {i: bytes([i]) for i in range(256)}  # id -> bytes\n",
    "        self.byte_ids = list(range(256))                  # byte value -> id\n",
    "        self.specials = {s: vocab_size + i for i, s in enumerate(specials)}\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.vocab_size + len(self.specials)\n",
    "\n",
    "    @property\n",
    "    def pad(self):\n",
    "        return self.specials['<pad>']\n",
    "\n",
    "    @property\n",
    "    def bos(self):\n",
    "        return self.specials['<bos>']\n",
    "\n",
    "    @property\n",
    "    def eos(self):\n",
    "        return self.specials['<eos>']\n",
    "\n",
    "    def _chunks(self, text):\n",
    "        return [text] if self.pattern is None else regex.findall(\n",
    "            self.pattern, text)\n",
    "\n",
    "    def _merge(self, ids, pair, new_id):\n",
    "        \"\"\"Replace every occurrence of pair in ids by new_id.\"\"\"\n",
    "        out, i = [], 0\n",
    "        while i < len(ids):\n",
    "            try:  # list.index scans for the next candidate at C speed\n",
    "                j = ids.index(pair[0], i)\n",
    "            except ValueError:\n",
    "                j = len(ids)\n",
    "            out.extend(ids[i:j])\n",
    "            if j < len(ids) - 1 and ids[j + 1] == pair[1]:\n",
    "                out.append(new_id)\n",
    "                i = j + 2\n",
    "            elif j < len(ids):\n",
    "                out.append(ids[j])\n",
    "                i = j + 1\n",
    "            else:\n",
    "                i = j\n",
    "        return out\n",
    "\n",
    "    def train(self, text):\n",
    "        \"\"\"Learn vocab_size - 256 merges, most frequent pair first.\"\"\"\n",
    "        chunk_freq = collections.Counter(self._chunks(text))\n",
    "        seqs = [list(chunk.encode('utf-8')) for chunk in chunk_freq]\n",
    "        for new_id in range(256, self.vocab_size):\n",
    "            pairs = collections.Counter()\n",
    "            for seq, w in zip(seqs, chunk_freq.values()):\n",
    "                if w == 1:  # Counter.update counts at C speed\n",
    "                    pairs.update(zip(seq, seq[1:]))\n",
    "                else:  # weight pair counts by chunk frequency\n",
    "                    for pair in zip(seq, seq[1:]):\n",
    "                        pairs[pair] += w\n",
    "            if not pairs:\n",
    "                break  # nothing left to merge\n",
    "            pair = max(pairs, key=pairs.get)\n",
    "            self.merges[pair] = new_id\n",
    "            self.vocab[new_id] = self.vocab[pair[0]] + self.vocab[pair[1]]\n",
    "            seqs = [self._merge(seq, pair, new_id) for seq in seqs]"
   ],
   "execution_count": 7,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-8 fw=all -->\n",
    "\n",
    "A few implementation notes. Training deduplicates identical chunks and\n",
    "weights their pair counts by frequency; without a pre-tokenization pattern\n",
    "there is a single chunk (the whole corpus), so this costs nothing, and\n",
    "with one it makes training roughly tenfold faster. Production trainers\n",
    "further update pair counts incrementally around each merge site rather\n",
    "than recounting; we recount for clarity. Training on our toy corpus\n",
    "reproduces the hand trace:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-implementation-2"
   },
   "source": [
    "toy_tok = BPETokenizer(vocab_size=256 + 3)\n",
    "toy_tok.train('hug pug pun bun hugs hug hug pug')\n",
    "for (a, b), new_id in toy_tok.merges.items():\n",
    "    print(f'{toy_tok.vocab[a]} + {toy_tok.vocab[b]} -> '\n",
    "          f'{toy_tok.vocab[new_id]}')"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "b'u' + b'g' -> b'ug'\nb'h' + b'ug' -> b'hug'\nb'hug' + b' ' -> b'hug '\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-9 fw=all -->\n",
    "\n",
    "### Encoding and Decoding\n",
    "\n",
    "Training produced a merge table. To *encode* new text we replay merges on\n",
    "its bytes: repeatedly find the adjacent pair with the lowest merge rank\n",
    "and merge it, until no adjacent pair is in the table. Because ranks are\n",
    "consulted rather than corpus statistics, encoding is a pure function of\n",
    "the merge table: **the tokenizer is defined by its merge ranks**, and\n",
    "training time and inference time agree by construction. Decoding is\n",
    "trivial, since every token id maps to a byte string; we concatenate and\n",
    "decode as UTF-8. (A generation model can emit ids whose bytes do not align\n",
    "with character boundaries, so we ask Python to replace, rather than reject,\n",
    "malformed fragments.)"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-encoding-and-decoding-1"
   },
   "source": [
    "@d2l.add_to_class(BPETokenizer)\n",
    "def _encode_chunk(self, text_bytes):\n",
    "    ids = [self.byte_ids[b] for b in text_bytes]\n",
    "    while len(ids) > 1:\n",
    "        # The lowest-rank merge applicable anywhere in this chunk\n",
    "        pair = min(zip(ids, ids[1:]),\n",
    "                   key=lambda p: self.merges.get(p, float('inf')))\n",
    "        if pair not in self.merges:\n",
    "            break\n",
    "        ids = self._merge(ids, pair, self.merges[pair])\n",
    "    return ids\n",
    "\n",
    "@d2l.add_to_class(BPETokenizer)\n",
    "def encode(self, text, allow_special=False):\n",
    "    if allow_special and self.specials:\n",
    "        pat = '(' + '|'.join(regex.escape(s) for s in self.specials) + ')'\n",
    "        ids = []\n",
    "        for part in regex.split(pat, text):\n",
    "            if part in self.specials:\n",
    "                ids.append(self.specials[part])\n",
    "            elif part:\n",
    "                ids.extend(self.encode(part))\n",
    "        return ids\n",
    "    return [i for chunk in self._chunks(text)\n",
    "            for i in self._encode_chunk(chunk.encode('utf-8'))]\n",
    "\n",
    "@d2l.add_to_class(BPETokenizer)\n",
    "def decode(self, ids):\n",
    "    specials = {i: s.encode('utf-8') for s, i in self.specials.items()}\n",
    "    data = b''.join(self.vocab[i] if i in self.vocab else specials[i]\n",
    "                    for i in ids)\n",
    "    return data.decode('utf-8', errors='replace')"
   ],
   "execution_count": 9,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-10 fw=all -->\n",
    "\n",
    "On the toy tokenizer, encoding behaves as promised: frequent fragments\n",
    "become single tokens, rare ones fall back toward bytes, and decoding\n",
    "inverts encoding exactly."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-encoding-and-decoding-2"
   },
   "source": [
    "print([toy_tok.vocab[i] for i in toy_tok.encode('hugs')])\n",
    "print([toy_tok.vocab[i] for i in toy_tok.encode('bun')])\n",
    "toy_tok.decode(toy_tok.encode('hug pug hugs'))"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[b'hug', b's']\n[b'b', b'u', b'n']\n"
     ]
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "'hug pug hugs'"
     },
     "metadata": {},
     "execution_count": 10
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-11 fw=all -->\n",
    "\n",
    "### Training on The Time Machine\n",
    "\n",
    "Now the real thing: we train a 1,024-token vocabulary on the raw,\n",
    "unnormalized novella. The first merges are humble letter pairs; by the end\n",
    "of training the tokenizer has discovered whole words of Wells' prose. Look\n",
    "closely at the encoded sample, though: one of its \"tokens\" is the two-word\n",
    "composite \"Time Traveller \", spaces included. We will return to that."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-training-on-the-time-machine-1"
   },
   "source": [
    "tok = BPETokenizer(vocab_size=1024)\n",
    "tok.train(raw_text)\n",
    "merged_ids = list(tok.merges.values())\n",
    "print('first:', [tok.vocab[i] for i in merged_ids[:8]])\n",
    "print('last: ', [tok.vocab[i] for i in merged_ids[-8:]])\n",
    "ids = tok.encode('The Time Traveller smiled. Are you sure?')\n",
    "print(len(ids), 'tokens:', [tok.vocab[i] for i in ids])"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "first: [b'e ', b'th', b'd ', b'in', b't ', b's ', b'an', b'er']\nlast:  [b'appe', b'vo', b'ering ', b'too ', b'door', b'acro', b'clo', b'after ']\n13 tokens: [b'The ', b'Time Traveller ', b's', b'mi', b'le', b'd', b'. A', b'r', b'e ', b'you ', b'su', b're', b'?']\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-12 fw=all -->\n",
    "\n",
    "How much does a bigger vocabulary buy? Because ids are assigned in rank\n",
    "order, a BPE tokenizer with a smaller vocabulary is literally a *prefix*\n",
    "of a larger one trained on the same corpus: keeping only the merges with\n",
    "id below $v$ recovers exactly the tokenizer we would have gotten by\n",
    "stopping training at vocabulary size $v$. We exploit this to sweep the\n",
    "vocabulary size from 256 to 4,096 with a single training run, measuring\n",
    "compression in bytes per token on an excerpt."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-training-on-the-time-machine-2"
   },
   "source": [
    "big = BPETokenizer(vocab_size=4096)\n",
    "big.train(raw_text)\n",
    "excerpt = raw_text[:10000]\n",
    "sizes = [256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096]\n",
    "ratios = []\n",
    "for v in sizes:\n",
    "    sub = BPETokenizer(vocab_size=v)  # the first v - 256 merges of big\n",
    "    sub.merges = {p: i for p, i in big.merges.items() if i < v}\n",
    "    sub.vocab = {i: b for i, b in big.vocab.items() if i < v}\n",
    "    ratios.append(len(excerpt.encode('utf-8')) / len(sub.encode(excerpt)))\n",
    "d2l.plot(sizes, [ratios], 'vocabulary size', 'bytes per token',\n",
    "         xscale='log')"
   ],
   "execution_count": 12,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"236.740625pt\" height=\"183.35625pt\" viewBox=\"0 0 236.740625 183.35625\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:59:00.533156</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 183.35625 \nL 236.740625 183.35625 \nL 236.740625 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 34.240625 145.8 \nL 229.540625 145.8 \nL 229.540625 7.2 \nL 34.240625 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 130.371914 145.8 \nL 130.371914 7.2 \n\" clip-path=\"url(#p580e9a2068)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"mbb3e790dda\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mbb3e790dda\" x=\"130.371914\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{3}}$ -->\n      <g transform=\"translate(121.571914 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <defs>\n       <path id=\"mbbf9d91779\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"53.274327\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"71.696333\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"85.98555\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"97.660691\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"107.531882\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"116.082696\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"123.625049\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"174.758277\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_10\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"200.722636\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_11\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#mbbf9d91779\" x=\"219.144641\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_2\">\n     <!-- vocabulary size -->\n     <g transform=\"translate(92.964062 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-76\" d=\"M 191 3500 \nL 800 3500 \nL 1894 563 \nL 2988 3500 \nL 3597 3500 \nL 2284 0 \nL 1503 0 \nL 191 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-62\" d=\"M 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\nM 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2969 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-79\" d=\"M 2059 -325 \nQ 1816 -950 1584 -1140 \nQ 1353 -1331 966 -1331 \nL 506 -1331 \nL 506 -850 \nL 844 -850 \nQ 1081 -850 1212 -737 \nQ 1344 -625 1503 -206 \nL 1606 56 \nL 191 3500 \nL 800 3500 \nL 1894 763 \nL 2988 3500 \nL 3597 3500 \nL 2059 -325 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-7a\" d=\"M 353 3500 \nL 3084 3500 \nL 3084 2975 \nL 922 459 \nL 3084 459 \nL 3084 0 \nL 275 0 \nL 275 525 \nL 2438 3041 \nL 353 3041 \nL 353 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-76\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(59.179688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(120.361328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(175.341797 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(236.621094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(300.097656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(363.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(391.259766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(452.539062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(493.652344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(552.832031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(584.619141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(636.71875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-7a\" transform=\"translate(664.501953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(716.992188 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_13\">\n      <path d=\"M 34.240625 139.5 \nL 229.540625 139.5 \n\" clip-path=\"url(#p580e9a2068)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <defs>\n       <path id=\"m60fceb8857\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m60fceb8857\" x=\"34.240625\" y=\"139.5\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 1 -->\n      <g transform=\"translate(20.878125 143.299219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_15\">\n      <path d=\"M 34.240625 104.498211 \nL 229.540625 104.498211 \n\" clip-path=\"url(#p580e9a2068)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m60fceb8857\" x=\"34.240625\" y=\"104.498211\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 2 -->\n      <g transform=\"translate(20.878125 108.29743) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_17\">\n      <path d=\"M 34.240625 69.496422 \nL 229.540625 69.496422 \n\" clip-path=\"url(#p580e9a2068)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m60fceb8857\" x=\"34.240625\" y=\"69.496422\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 3 -->\n      <g transform=\"translate(20.878125 73.295641) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-33\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_19\">\n      <path d=\"M 34.240625 34.494633 \nL 229.540625 34.494633 \n\" clip-path=\"url(#p580e9a2068)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m60fceb8857\" x=\"34.240625\" y=\"34.494633\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 4 -->\n      <g transform=\"translate(20.878125 38.293852) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_7\">\n     <!-- bytes per token -->\n     <g transform=\"translate(14.798438 115.738281) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6b\" d=\"M 581 4863 \nL 1159 4863 \nL 1159 1991 \nL 2875 3500 \nL 3609 3500 \nL 1753 1863 \nL 3688 0 \nL 2938 0 \nL 1159 1709 \nL 1159 0 \nL 581 0 \nL 581 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-62\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(122.65625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(161.865234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(223.388672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(275.488281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(307.275391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(370.751953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(432.275391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(473.388672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(505.175781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(544.384766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(605.566406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(659.851562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(721.375 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_21\">\n    <path d=\"M 43.117898 139.5 \nL 69.082256 112.496848 \nL 87.504261 101.793461 \nL 113.46862 88.396527 \nL 131.890625 78.316604 \nL 157.854983 64.606062 \nL 176.276989 52.203435 \nL 202.241347 35.550662 \nL 220.663352 13.5 \n\" clip-path=\"url(#p580e9a2068)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 34.240625 145.8 \nL 34.240625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 229.540625 145.8 \nL 229.540625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 34.240625 145.8 \nL 229.540625 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 34.240625 7.2 \nL 229.540625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p580e9a2068\">\n   <rect x=\"34.240625\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-13 fw=all -->\n",
    "\n",
    "Each doubling of the vocabulary buys a roughly constant increment of\n",
    "compression: bytes per token grows only logarithmically in vocabulary\n",
    "size. That is the greedy dynamic at work. Early merges (\"e \", \"th\", \"d \")\n",
    "each save thousands of occurrences, while the 4,000th merge saves a\n",
    "handful, so returns per merge fall off relentlessly. This also explains\n",
    "why production vocabularies of 50,000 to 200,000 tokens are not\n",
    "dramatically deeper into the curve: on English prose they land around\n",
    "four to five bytes per token, roughly one token per word, as we will\n",
    "measure below. Their extra slots mostly buy compression of *other*\n",
    "languages, to which we also return.\n",
    "\n",
    "### Pre-Tokenization: Telling BPE Where Words End\n",
    "\n",
    "Look at what our unconstrained tokenizer actually learned, though.\n",
    "Alongside sensible word fragments, its vocabulary is peppered with tokens\n",
    "that straddle word boundaries:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-pre-tokenization-telling-bpe-where-words-end-1"
   },
   "source": [
    "crossers = [v.decode('utf-8', 'replace') for i, v in tok.vocab.items()\n",
    "            if i >= 256 and b' ' in v.strip(b' ')]\n",
    "print(len(crossers), 'tokens cross a word boundary, e.g.', crossers[:8])"
   ],
   "execution_count": 13,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "78 tokens cross a word boundary, e.g. [', and ', 'of the ', '. I ', '. Th', '. A', '. I', 'in the ', 'ed to ']\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-14 fw=all -->\n",
    "\n",
    "Merges like \"of the \" compress the training corpus, but they are brittle\n",
    "composites: they burn vocabulary slots on specific phrase spellings,\n",
    "fragment the counts of the words they contain (\"of\" now appears in many\n",
    "disguises), and generalize poorly to new text. Every production tokenizer\n",
    "therefore adds one ingredient we have so far omitted: *pre-tokenization*.\n",
    "The text is first split into chunks with a regular expression, and BPE is\n",
    "trained, and applied, strictly *within* chunks, so no merge can cross a\n",
    "chunk boundary. The pattern used by GPT-2\n",
    "[@Radford.Wu.Child.ea.2019], kept as `BPETokenizer.GPT2_PATTERN`, is\n",
    "worth reading once:\n",
    "\n",
    "```\n",
    "'s|'t|'re|'ve|'m|'ll|'d        common English contractions, split off\n",
    "| ?\\p{L}+                      a run of letters, with its leading space\n",
    "| ?\\p{N}+                      a run of digits, with its leading space\n",
    "| ?[^\\s\\p{L}\\p{N}]+            a run of punctuation or other symbols\n",
    "|\\s+(?!\\S)|\\s+                 remaining whitespace\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-15 fw=all -->\n",
    "\n",
    "Note the design decisions embedded here. A word's *leading space* is kept\n",
    "attached to it (\" the\" rather than \"the \"), so a word carries its own\n",
    "separation from the previous one; letters, digits, and punctuation are\n",
    "segregated, so numbers and symbols never fuse with words; contractions\n",
    "split into meaningful units. Later OpenAI tokenizers refine the digit\n",
    "rule further, capping digit runs at three, a detail whose surprising\n",
    "consequences we examine shortly."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-pre-tokenization-telling-bpe-where-words-end-2"
   },
   "source": [
    "regex.findall(BPETokenizer.GPT2_PATTERN,\n",
    "              \"The traveller's clock struck 12,345 times.\")"
   ],
   "execution_count": 14,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "['The',\n ' traveller',\n \"'s\",\n ' clock',\n ' struck',\n ' 12',\n ',',\n '345',\n ' times',\n '.']"
     },
     "metadata": {},
     "execution_count": 14
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-16 fw=all -->\n",
    "\n",
    "Training with the pattern is a one-argument change\n",
    "(the figure shows the resulting pipeline end to end),\n",
    "and comparing the learned vocabulary against the unconstrained run shows\n",
    "exactly the repair we hoped for: boundary-crossing composites disappear\n",
    "and their slots are spent on genuine words instead."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-pre-tokenization-telling-bpe-where-words-end-3"
   },
   "source": [
    "bpe = BPETokenizer(vocab_size=1024, pattern=BPETokenizer.GPT2_PATTERN)\n",
    "bpe.train(raw_text)\n",
    "crossers = [v for i, v in bpe.vocab.items()\n",
    "            if i >= 256 and b' ' in v.strip(b' ')]\n",
    "print('boundary-crossing tokens now:', len(crossers))\n",
    "gained = sorted(set(bpe.vocab.values()) - set(tok.vocab.values()),\n",
    "                key=lambda v: (-len(v), v))\n",
    "print('longest tokens gained instead:',\n",
    "      [v.decode('utf-8', 'replace') for v in gained[:6]])"
   ],
   "execution_count": 15,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "boundary-crossing tokens now: 0\nlongest tokens gained instead: [' Psychologist', 'sychologist', ' Traveller', ' Morlocks', ' darkness', ' Machine']\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-17 fw=all -->\n",
    "\n",
    "![Pre-tokenization in action on a real sentence. The regex first cuts the text into chunks: words with their leading spaces, digit runs, and punctuation. BPE merges are then applied within each chunk, and can never cross a chunk boundary.](../img/mdl-rnn-pretokenization-pipeline.svg)\n",
    "\n",
    "## Vocabularies and Special Tokens\n",
    "\n",
    "### From Tokens to Indices\n",
    "\n",
    "For the character- and word-level pipelines that some later sections still\n",
    "use, we need the classical piece of machinery that BPE gave us for free: a\n",
    "*vocabulary* object that assigns each distinct token string an index and\n",
    "maps unknown tokens to a reserved `<unk>` slot. Rare tokens (below\n",
    "`min_freq` occurrences) can be dropped to keep the table small; that this\n",
    "is even necessary is precisely the OOV problem that byte-level BPE\n",
    "eliminates."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-vocabulary-1"
   },
   "source": [
    "class Vocab:\n",
    "    \"\"\"Vocabulary for text.\"\"\"\n",
    "    def __init__(self, tokens=[], min_freq=0, reserved_tokens=[]):\n",
    "        # Flatten a 2D list if needed\n",
    "        if tokens and isinstance(tokens[0], list):\n",
    "            tokens = [token for line in tokens for token in line]\n",
    "        # Count token frequencies\n",
    "        counter = collections.Counter(tokens)\n",
    "        self.token_freqs = sorted(counter.items(), key=lambda x: x[1],\n",
    "                                  reverse=True)\n",
    "        # The list of unique tokens, ordered by descending frequency.\n",
    "        # Reserve <unk> at index 0 so vocab[0] is the unknown token.\n",
    "        self.idx_to_token = ['<unk>'] + reserved_tokens + [\n",
    "            token for token, freq in self.token_freqs\n",
    "            if freq >= min_freq and token not in reserved_tokens]\n",
    "        self.token_to_idx = {token: idx\n",
    "                             for idx, token in enumerate(self.idx_to_token)}\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.idx_to_token)\n",
    "\n",
    "    def __getitem__(self, tokens):\n",
    "        if not isinstance(tokens, (list, tuple)):\n",
    "            return self.token_to_idx.get(tokens, self.unk)\n",
    "        return [self.__getitem__(token) for token in tokens]\n",
    "\n",
    "    def to_tokens(self, indices):\n",
    "        if hasattr(indices, '__len__') and len(indices) > 1:\n",
    "            return [self.idx_to_token[int(index)] for index in indices]\n",
    "        return self.idx_to_token[indices]\n",
    "\n",
    "    @property\n",
    "    def unk(self):  # Index for the unknown token\n",
    "        return self.token_to_idx['<unk>']"
   ],
   "execution_count": 16,
   "outputs": []
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-vocabulary-2"
   },
   "source": [
    "vocab = Vocab(tokens)\n",
    "indices = vocab[tokens[:10]]\n",
    "print('indices:', indices)\n",
    "print('tokens:', vocab.to_tokens(indices))"
   ],
   "execution_count": 17,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "indices: [3, 9, 2, 1, 3, 5, 13, 2, 1, 13]\ntokens: ['t', 'h', 'e', ' ', 't', 'i', 'm', 'e', ' ', 'm']\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-18 fw=all -->\n",
    "\n",
    "The `build` convenience method packages the whole classical pipeline,\n",
    "preprocess, tokenize, and index, returning a corpus of ids and its\n",
    "vocabulary; several later sections call it."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-putting-it-all-together"
   },
   "source": [
    "@d2l.add_to_class(TimeMachine)\n",
    "def build(self, raw_text, vocab=None):\n",
    "    tokens = self._tokenize(self._preprocess(raw_text))\n",
    "    if vocab is None: vocab = Vocab(tokens)\n",
    "    corpus = [vocab[token] for token in tokens]\n",
    "    return corpus, vocab\n",
    "\n",
    "corpus, vocab = data.build(raw_text)\n",
    "len(corpus), len(vocab)"
   ],
   "execution_count": 18,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(173428, 28)"
     },
     "metadata": {},
     "execution_count": 18
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-19 fw=all -->\n",
    "\n",
    "### Special Tokens\n",
    "\n",
    "Training pipelines need a handful of tokens that mean something to the\n",
    "*infrastructure* rather than to the text: `<pad>` fills the unused tail of\n",
    "short sequences in a batch, `<bos>` marks the beginning of a sequence, and\n",
    "`<eos>` lets a model declare that generation is finished. (The\n",
    "encoder-decoder models of that section will use all\n",
    "three.) Our `BPETokenizer` assigns these ids *above* the BPE range, and\n",
    "this is a deliberate safety property, not a convenience: a special token\n",
    "must never be producible by encoding ordinary text. If it were, any\n",
    "document that happened to contain the string \"&lt;eos&gt;\" could inject a\n",
    "control signal into the model's input, a cousin of the prompt-injection\n",
    "attacks that plague deployed LLM systems. Our `encode` therefore treats\n",
    "special strings in ordinary text as plain bytes unless the caller\n",
    "explicitly opts in with `allow_special=True`; `tiktoken` implements the\n",
    "same guard with its `allowed_special` argument and raises an error by\n",
    "default."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-special-tokens"
   },
   "source": [
    "print('as plain text:  ', bpe.encode('<bos>the time machine'))\n",
    "print('as control code:', bpe.encode('<bos>the time machine',\n",
    "                                     allow_special=True))\n",
    "print('pad/bos/eos ids:', bpe.pad, bpe.bos, bpe.eos, '| len:', len(bpe))"
   ],
   "execution_count": 19,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "as plain text:   [60, 98, 111, 115, 62, 341, 513, 680]\nas control code: [1025, 341, 513, 680]\npad/bos/eos ids: 1024 1025 1026 | len: 1027\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-20 fw=all -->\n",
    "\n",
    "## Tokenizers in the Wild\n",
    "\n",
    "### What a Production Tokenizer Stores\n",
    "\n",
    "Everything a deployed tokenizer knows fits in one table. OpenAI's\n",
    "open-source `tiktoken` library ships, for each model family, a mapping\n",
    "from byte strings to integer *ranks* plus a pre-tokenization pattern, and\n",
    "that is the entire artifact: no neural network, no language-specific\n",
    "rules. Peeking at the GPT-2 table around the byte boundary is instructive."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-what-a-production-tokenizer-stores"
   },
   "source": [
    "enc = tiktoken.get_encoding('gpt2')\n",
    "print(list(enc._mergeable_ranks.items())[254:260])\n",
    "print(enc._special_tokens)"
   ],
   "execution_count": 20,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[(b'\\xa0', 254), (b'\\xad', 255), (b' t', 256), (b' a', 257), (b'he', 258), (b'in', 259)]\n{'<|endoftext|>': 50256}\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-21 fw=all -->\n",
    "\n",
    "The first 256 ranks are the single bytes (in a permuted order: GPT-2 lists\n",
    "printable characters first), and rank 256 onward are learned merges in\n",
    "rank order, exactly the structure our `BPETokenizer` uses. Amusingly,\n",
    "GPT-2's first two merges, \" t\" and \" a\", learned from 40 gigabytes of web\n",
    "text, are among the very first our tokenizer learned from one Victorian\n",
    "novella: the head of the English fragment distribution is that stable.\n",
    "\n",
    "### Verifying Our Implementation\n",
    "\n",
    "Since the artifact is just a rank table, we can load GPT-2's published\n",
    "table into *our* encoder: ranks become our token ids, the 256 single-byte\n",
    "entries give the byte permutation, and each multi-byte token's parents are\n",
    "recovered by re-running BPE on its own bytes with all strictly\n",
    "lower-ranked merges (a token's two parents are whatever its bytes merge\n",
    "into just before its own rank applies)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-verifying-our-implementation-1"
   },
   "source": [
    "@d2l.add_to_class(BPETokenizer)\n",
    "@classmethod\n",
    "def from_tiktoken(cls, name):\n",
    "    \"\"\"Load a published bytes->rank table (e.g. 'gpt2') into our encoder.\"\"\"\n",
    "    import tiktoken  # lazy: d2l itself does not require tiktoken\n",
    "    enc = tiktoken.get_encoding(name)\n",
    "    ranks = enc._mergeable_ranks\n",
    "    tok = cls(vocab_size=len(ranks), pattern=enc._pat_str, specials=())\n",
    "    tok.specials = dict(enc._special_tokens)\n",
    "    tok.vocab = {rank: b for b, rank in ranks.items()}\n",
    "    tok.byte_ids = [ranks[bytes([b])] for b in range(256)]\n",
    "    for token, rank in ranks.items():\n",
    "        if len(token) > 1:  # recover which pair merged into this token\n",
    "            parts = [bytes([b]) for b in token]\n",
    "            while len(parts) > 2:\n",
    "                a, b = min(zip(parts, parts[1:]),\n",
    "                           key=lambda p: ranks.get(p[0] + p[1],\n",
    "                                                   float('inf')))\n",
    "                i = list(zip(parts, parts[1:])).index((a, b))\n",
    "                parts[i:i + 2] = [a + b]\n",
    "            tok.merges[ranks[parts[0]], ranks[parts[1]]] = rank\n",
    "    return tok"
   ],
   "execution_count": 21,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-22 fw=all -->\n",
    "\n",
    "The moment of truth: on a paragraph mixing prose, numbers, accents, and an\n",
    "emoji, our from-scratch encoder must reproduce `tiktoken`'s output token\n",
    "for token. It does; the `assert` below runs, and passes, every time this\n",
    "book is built."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-verifying-our-implementation-2"
   },
   "source": [
    "ours = BPETokenizer.from_tiktoken('gpt2')\n",
    "para = ('The Time Traveller (for so it will be convenient to speak of '\n",
    "        'him) was expounding a recondite matter to us; his pale grey '\n",
    "        'eyes shone and twinkled. Prices rose 3.5% in 1895, and naïve '\n",
    "        'café patrons paid £12,345 more! 🚀')\n",
    "assert ours.encode(para) == enc.encode(para)\n",
    "print(len(ours.encode(para)), 'tokens, identical to tiktoken')\n",
    "print([ours.vocab[i].decode('utf-8', 'replace')\n",
    "       for i in ours.encode(para)[:8]])"
   ],
   "execution_count": 22,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "60 tokens, identical to tiktoken\n['The', ' Time', ' Trave', 'ller', ' (', 'for', ' so', ' it']\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-23 fw=all -->\n",
    "\n",
    "How do vocabularies across the generations compare on our corpus? We pit\n",
    "our 1,024-token Time Machine tokenizer against GPT-2's 50,257 and\n",
    "`o200k_base` (the roughly 200,000-token vocabulary used by GPT-4o-era\n",
    "models)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-verifying-our-implementation-3"
   },
   "source": [
    "n_bytes = len(raw_text.encode('utf-8'))\n",
    "rows = [('ours (1k, in-domain)', len(bpe.encode(raw_text)))]\n",
    "for name in ('gpt2', 'o200k_base'):\n",
    "    e = tiktoken.get_encoding(name)\n",
    "    rows.append((f'{name} ({len(e._mergeable_ranks) // 1000}k)',\n",
    "                 len(e.encode(raw_text))))\n",
    "for name, n in rows:\n",
    "    print(f'{name:>22}: {n:>6} tokens, {n_bytes / n:.2f} bytes/token')"
   ],
   "execution_count": 23,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "  ours (1k, in-domain):  65741 tokens, 2.72 bytes/token\n            gpt2 (50k):  44073 tokens, 4.06 bytes/token\n     o200k_base (199k):  42624 tokens, 4.20 bytes/token\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-24 fw=all -->\n",
    "\n",
    "Token counts fall as vocabularies grow, but note how well our tiny\n",
    "tokenizer holds up: trained on exactly this distribution, it achieves two\n",
    "thirds the compression of tokenizers fifty and two hundred times its size. A\n",
    "tokenizer is a compression model of its training corpus, and like any\n",
    "model it performs best in domain. The flip side is that *mismatch costs\n",
    "context budget*: text that is cheap for one tokenizer can be expensive for\n",
    "another, which brings us to the pathologies.\n",
    "\n",
    "### Fertility, Digits, and Glitch Tokens\n",
    "\n",
    "*Fertility*, the average number of tokens per word, measures that mismatch\n",
    "across languages. GPT-2's tokenizer was trained on overwhelmingly English\n",
    "text; the same short sentence, translated, costs dramatically different\n",
    "amounts of context:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-fertility-digits-and-glitch-tokens-1"
   },
   "source": [
    "sentences = {\n",
    "    'English': 'The time traveller returned after many years.',\n",
    "    'German': 'Der Zeitreisende kehrte nach vielen Jahren zurück.',\n",
    "    'Greek': 'Ο ταξιδιώτης του χρόνου επέστρεψε μετά από πολλά χρόνια.'}\n",
    "fert = {lang: [len(tiktoken.get_encoding(e).encode(s)) / len(s.split())\n",
    "               for e in ('gpt2', 'o200k_base')]\n",
    "        for lang, s in sentences.items()}\n",
    "d2l.set_figsize((5, 3))\n",
    "xs = range(len(fert))\n",
    "d2l.plt.bar([x - 0.2 for x in xs], [v[0] for v in fert.values()],\n",
    "            0.4, label='gpt2 (50k)')\n",
    "d2l.plt.bar([x + 0.2 for x in xs], [v[1] for v in fert.values()],\n",
    "            0.4, label='o200k_base (200k)')\n",
    "d2l.plt.xticks(list(xs), list(fert))\n",
    "d2l.plt.ylabel('tokens per word')\n",
    "d2l.plt.legend();"
   ],
   "execution_count": 24,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"320.440625pt\" height=\"197.398125pt\" viewBox=\"0 0 320.440625 197.398125\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:59:27.912167</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 197.398125 \nL 320.440625 197.398125 \nL 320.440625 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 34.240625 173.52 \nL 313.240625 173.52 \nL 313.240625 7.2 \nL 34.240625 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 46.922443 173.52 \nL 83.156209 173.52 \nL 83.156209 148.834286 \nL 46.922443 148.834286 \nz\n\" clip-path=\"url(#p1de6e00283)\" style=\"fill: #1f77b4\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 137.506859 173.52 \nL 173.740625 173.52 \nL 173.740625 111.805714 \nL 137.506859 111.805714 \nz\n\" clip-path=\"url(#p1de6e00283)\" style=\"fill: #1f77b4\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 228.091274 173.52 \nL 264.325041 173.52 \nL 264.325041 15.12 \nL 228.091274 15.12 \nz\n\" clip-path=\"url(#p1de6e00283)\" style=\"fill: #1f77b4\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 83.156209 173.52 \nL 119.389976 173.52 \nL 119.389976 148.834286 \nL 83.156209 148.834286 \nz\n\" clip-path=\"url(#p1de6e00283)\" style=\"fill: #ff7f0e\"/>\n   </g>\n   <g id=\"patch_7\">\n    <path d=\"M 173.740625 173.52 \nL 209.974391 173.52 \nL 209.974391 139.577143 \nL 173.740625 139.577143 \nz\n\" clip-path=\"url(#p1de6e00283)\" style=\"fill: #ff7f0e\"/>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 264.325041 173.52 \nL 300.558807 173.52 \nL 300.558807 132.72 \nL 264.325041 132.72 \nz\n\" clip-path=\"url(#p1de6e00283)\" style=\"fill: #ff7f0e\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"m595e4fae18\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m595e4fae18\" x=\"83.156209\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- English -->\n      <g transform=\"translate(65.102303 188.118438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-45\" d=\"M 628 4666 \nL 3578 4666 \nL 3578 4134 \nL 1259 4134 \nL 1259 2753 \nL 3481 2753 \nL 3481 2222 \nL 1259 2222 \nL 1259 531 \nL 3634 531 \nL 3634 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-45\"/>\n       <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(63.183594 0)\"/>\n       <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(126.5625 0)\"/>\n       <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(190.039062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(217.822266 0)\"/>\n       <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(245.605469 0)\"/>\n       <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(297.705078 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#m595e4fae18\" x=\"173.740625\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- German -->\n      <g transform=\"translate(153.71875 188.118438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-47\" d=\"M 3809 666 \nL 3809 1919 \nL 2778 1919 \nL 2778 2438 \nL 4434 2438 \nL 4434 434 \nQ 4069 175 3628 42 \nQ 3188 -91 2688 -91 \nQ 1594 -91 976 548 \nQ 359 1188 359 2328 \nQ 359 3472 976 4111 \nQ 1594 4750 2688 4750 \nQ 3144 4750 3555 4637 \nQ 3966 4525 4313 4306 \nL 4313 3634 \nQ 3963 3931 3569 4081 \nQ 3175 4231 2741 4231 \nQ 1884 4231 1454 3753 \nQ 1025 3275 1025 2328 \nQ 1025 1384 1454 906 \nQ 1884 428 2741 428 \nQ 3075 428 3337 486 \nQ 3600 544 3809 666 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-47\"/>\n       <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(77.490234 0)\"/>\n       <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(139.013672 0)\"/>\n       <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(178.376953 0)\"/>\n       <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(275.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(337.068359 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#m595e4fae18\" x=\"264.325041\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- Greek -->\n      <g transform=\"translate(249.459416 188.118438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-6b\" d=\"M 581 4863 \nL 1159 4863 \nL 1159 1991 \nL 2875 3500 \nL 3609 3500 \nL 1753 1863 \nL 3688 0 \nL 2938 0 \nL 1159 1709 \nL 1159 0 \nL 581 0 \nL 581 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-47\"/>\n       <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(77.490234 0)\"/>\n       <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(116.353516 0)\"/>\n       <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(177.876953 0)\"/>\n       <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(239.400391 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_4\">\n      <defs>\n       <path id=\"m791f16fd15\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 0 -->\n      <g transform=\"translate(20.878125 177.319219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"151.92\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 1 -->\n      <g transform=\"translate(20.878125 155.719219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"130.32\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 2 -->\n      <g transform=\"translate(20.878125 134.119219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"108.72\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 3 -->\n      <g transform=\"translate(20.878125 112.519219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-33\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"87.12\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 4 -->\n      <g transform=\"translate(20.878125 90.919219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"65.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 5 -->\n      <g transform=\"translate(20.878125 69.319219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-35\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"43.92\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 6 -->\n      <g transform=\"translate(20.878125 47.719219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#m791f16fd15\" x=\"34.240625\" y=\"22.32\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- 7 -->\n      <g transform=\"translate(20.878125 26.119219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-37\" d=\"M 525 4666 \nL 3525 4666 \nL 3525 4397 \nL 1831 0 \nL 1172 0 \nL 2766 4134 \nL 525 4134 \nL 525 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-37\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_12\">\n     <!-- tokens per word -->\n     <g transform=\"translate(14.798438 130.718594) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-77\" d=\"M 269 3500 \nL 844 3500 \nL 1563 769 \nL 2278 3500 \nL 2956 3500 \nL 3675 769 \nL 4391 3500 \nL 4966 3500 \nL 4050 0 \nL 3372 0 \nL 2619 2869 \nL 1863 0 \nL 1184 0 \nL 269 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(100.390625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(154.675781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(216.199219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(279.578125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(331.677734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(363.464844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(426.941406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(488.464844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(529.578125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-77\" transform=\"translate(561.365234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(643.152344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(704.333984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(743.697266 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_9\">\n    <path d=\"M 34.240625 173.52 \nL 34.240625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_10\">\n    <path d=\"M 313.240625 173.52 \nL 313.240625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_11\">\n    <path d=\"M 34.240625 173.52 \nL 313.240625 173.52 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_12\">\n    <path d=\"M 34.240625 7.2 \nL 313.240625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_13\">\n     <path d=\"M 41.240625 44.834375 \nL 168.935938 44.834375 \nQ 170.935938 44.834375 170.935938 42.834375 \nL 170.935938 14.2 \nQ 170.935938 12.2 168.935938 12.2 \nL 41.240625 12.2 \nQ 39.240625 12.2 39.240625 14.2 \nL 39.240625 42.834375 \nQ 39.240625 44.834375 41.240625 44.834375 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"patch_14\">\n     <path d=\"M 43.240625 23.798438 \nL 63.240625 23.798438 \nL 63.240625 16.798438 \nL 43.240625 16.798438 \nz\n\" style=\"fill: #1f77b4\"/>\n    </g>\n    <g id=\"text_13\">\n     <!-- gpt2 (50k) -->\n     <g transform=\"translate(71.240625 23.798438) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-28\" d=\"M 1984 4856 \nQ 1566 4138 1362 3434 \nQ 1159 2731 1159 2009 \nQ 1159 1288 1364 580 \nQ 1569 -128 1984 -844 \nL 1484 -844 \nQ 1016 -109 783 600 \nQ 550 1309 550 2009 \nQ 550 2706 781 3412 \nQ 1013 4119 1484 4856 \nL 1984 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-29\" d=\"M 513 4856 \nL 1013 4856 \nQ 1481 4119 1714 3412 \nQ 1947 2706 1947 2009 \nQ 1947 1309 1714 600 \nQ 1481 -109 1013 -844 \nL 513 -844 \nQ 928 -128 1133 580 \nQ 1338 1288 1338 2009 \nQ 1338 2731 1133 3434 \nQ 928 4138 513 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-67\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(126.953125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(166.162109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(229.785156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-28\" transform=\"translate(261.572266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(300.585938 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(364.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(427.832031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-29\" transform=\"translate(485.742188 0)\"/>\n     </g>\n    </g>\n    <g id=\"patch_15\">\n     <path d=\"M 43.240625 38.476563 \nL 63.240625 38.476563 \nL 63.240625 31.476563 \nL 43.240625 31.476563 \nz\n\" style=\"fill: #ff7f0e\"/>\n    </g>\n    <g id=\"text_14\">\n     <!-- o200k_base (200k) -->\n     <g transform=\"translate(71.240625 38.476563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-5f\" d=\"M 3263 -1063 \nL 3263 -1509 \nL -63 -1509 \nL -63 -1063 \nL 3263 -1063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-62\" d=\"M 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\nM 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2969 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6f\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(61.181641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(124.804688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(188.427734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(252.050781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-5f\" transform=\"translate(309.960938 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(359.960938 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(423.4375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(484.716797 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(536.816406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(598.339844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-28\" transform=\"translate(630.126953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(669.140625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(732.763672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(796.386719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(860.009766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-29\" transform=\"translate(917.919922 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p1de6e00283\">\n   <rect x=\"34.240625\" y=\"7.2\" width=\"279\" height=\"166.32\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-25 fw=all -->\n",
    "\n",
    "Under GPT-2's tokenizer a Greek word costs about seven tokens (Greek\n",
    "letters are two UTF-8 bytes each, and almost no Greek merges were\n",
    "learned), while an English word costs about one: the same context window\n",
    "holds seven times less Greek than English, and every Greek word must be\n",
    "\"spelled out\" byte by byte. The multilingually trained `o200k_base`\n",
    "narrows the gap to about two.\n",
    "\n",
    "Digits show how sensitive model behavior is to tokenization minutiae.\n",
    "GPT-2 lets BPE carve numbers by corpus frequency, so digit strings split\n",
    "into irregular, frequency-dependent pieces; modern tokenizers cap digit\n",
    "runs at three in pre-tokenization, making token boundaries at least\n",
    "predictable:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-fertility-digits-and-glitch-tokens-2"
   },
   "source": [
    "for name in ('gpt2', 'o200k_base'):\n",
    "    e = tiktoken.get_encoding(name)\n",
    "    print(f'{name}: 12345678 ->',\n",
    "          [e.decode([t]) for t in e.encode('12345678')])"
   ],
   "execution_count": 25,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "gpt2: 12345678 -> ['123', '45', '678']\no200k_base: 12345678 -> ['123', '456', '78']\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-26 fw=all -->\n",
    "\n",
    "Neither scheme aligns token boundaries with the *columns* of arithmetic:\n",
    "grade-school addition works right to left in ones, tens, and hundreds,\n",
    "while \"12345678\" tokenizes left to right into \"123 456 78\". A model must\n",
    "learn arithmetic over these misaligned chunks, one reason why LLM\n",
    "arithmetic is brittle and why asking a model to insert separators\n",
    "(\"12,345,678\") often helps. The exercises pursue this.\n",
    "\n",
    "Finally, a cautionary tale about trusting the tokenizer's training data.\n",
    "Early GPT-2/GPT-3 vocabularies contained tokens such as\n",
    "\" SolidGoldMagikarp\", single tokens for strings (here, a Reddit username)\n",
    "that were frequent in the *tokenizer's* training corpus but were later\n",
    "filtered out of the *language model's* training corpus. The result is a\n",
    "so-called glitch token: it occupies a vocabulary slot, so a prompt can\n",
    "contain it, yet the model has essentially never seen it during training\n",
    "and its embedding is close to its random initialization. Models asked to\n",
    "repeat such tokens have produced evasions, insults, and unrelated words\n",
    "instead. The lesson generalizes: the tokenizer is part of the model, and a\n",
    "vocabulary entry is only as meaningful as the model's training exposure to\n",
    "it."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "text-sequence-fertility-digits-and-glitch-tokens-3"
   },
   "source": [
    "enc.encode(' SolidGoldMagikarp')  # one token for an 18-character string"
   ],
   "execution_count": 26,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[43453]"
     },
     "metadata": {},
     "execution_count": 26
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-27 fw=all -->\n",
    "\n",
    "## Summary\n",
    "\n",
    "Tokenization converts raw text into the integer sequences that sequence\n",
    "models consume, and it embodies a trade-off: larger vocabularies encode\n",
    "the same text in fewer tokens but cost more parameters, more data to\n",
    "estimate them, and, for word-level schemes, an out-of-vocabulary failure\n",
    "mode. Byte-level BPE resolves the tension by starting from the 256 bytes\n",
    "(so no input is ever out of vocabulary) and greedily merging the most\n",
    "frequent adjacent pair to build a learned vocabulary of frequent\n",
    "fragments; encoding replays merges by rank, so the merge table *is* the\n",
    "tokenizer. Pre-tokenization regexes confine merges to within words, and\n",
    "special tokens live outside the BPE range so that untrusted text can never\n",
    "forge them. Production tokenizers such as `tiktoken`'s are exactly this\n",
    "construction at scale, as we verified by reproducing GPT-2's tokenization\n",
    "token for token, and their fingerprints (fertility differences across\n",
    "languages, digit chunking, glitch tokens) are visible in the behavior of\n",
    "every deployed language model. The statistics of the token sequences we\n",
    "have just produced, and what it takes to model them, are the subject of\n",
    "that section.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Train `BPETokenizer` on a different text you like (another public\n",
    "   domain book, your own notes, source code). Inspect the first 20 and\n",
    "   last 20 merges. How many of the late merges would you expect to\n",
    "   transfer to a different corpus? Measure compression (bytes per token)\n",
    "   of your tokenizer on *The Time Machine* and of `bpe` on your corpus,\n",
    "   and compare both to the in-domain numbers.\n",
    "1. Retrain the tokenizer with vocabulary sizes 512, 2,048, and 4,096 and\n",
    "   keep the resulting corpora of token ids. After you have trained the\n",
    "   language model of that section, compare the models\n",
    "   trained on each corpus. Why is per-token perplexity the wrong metric\n",
    "   for this comparison, and what should you report instead?\n",
    "1. Ablate pre-tokenization: retrain the 4,096 vocabulary without the\n",
    "   GPT-2 pattern and list the 20 longest learned tokens of both runs.\n",
    "   Which tokens are compression wins on the training corpus but liabilities\n",
    "   on new text, and why? Check whether the unconstrained run compresses\n",
    "   the training corpus better, and explain why it must.\n",
    "1. Explain how a glitch token such as \" SolidGoldMagikarp\" comes to\n",
    "   exist. Concretely: what property must the tokenizer's training corpus\n",
    "   have relative to the model's, and why does BPE's frequency-based merge\n",
    "   rule turn that mismatch into a single token rather than several? Why is\n",
    "   the embedding of such a token approximately random after training?\n",
    "1. Digit chunking. Tokenize the addition prompts \"123+456=\" and\n",
    "   \"1234+5678=\" with `gpt2` and `o200k_base`, writing out the token\n",
    "   boundaries of each number. For three-digit capping, which digit\n",
    "   positions of the two summands end up in the same token, and how does\n",
    "   that mislead column-wise addition? Propose a pre-tokenization rule that\n",
    "   aligns tokens with place value, and state one drawback of your rule."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=text-sequence-md-28 fw=jax -->\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/18011)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-jax",
   "display_name": "d2l (JAX)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
