bpe_tokenizer.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "text is copied from https://www.theguardian.com/football/2024/oct/31/ruud-van-nistelrooy-manchester-united-future"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "text = \"Ruud van Nistelrooy is once again the focal point at Manchester United, almost two decades after ending a five-year spell leading the line. The boots were hung up long ago and he has swapped the famous red shirt for a tunic and long coat but it is like the old days as the Old Trafford fans elongate his first name. Ruuuuuuuud was the chant when he left the tunnel to take charge of his first match, leading United to a much-needed 5-2 Carabao Cup victory over Leicester. United laid down a marker but with Chelsea’s visit on Sunday and a first Europa League win of the season required against Paok four days later, the Dutchman knows this is not a busman’s holiday, even for someone who has maintained his hero status despite an acrimonious exit in 2006. I want to help, I want to do everything I can in my abilities, as many others do, to fight for this club,” said Van Nistelrooy, who returned in July as Erik ten Hag’s assistant. “The club is in a difficult situation and it is not where we all want it to be. The challenge is there. Everyone is looking at Man United and the situation it is in but it is up to us as people on the ground to do the utmost, supported by fans. It is a process and it is something to work for and do everything for. With Rúben Amorim waiting to join from Sporting in November’s international break, the caretaker manager knows his fate and timeframe, alleviating pressure. It is, on the other hand, a chance for Van Nistelrooy to prove his worth as a member of the backroom staff. Ole Gunnar Solskjær might have thought he had little chance of becoming the permanent manager when he stepped in after José Mourinho was dismissed. It helped the Norwegian that he was parachuted in from the outside as United looked to steady the ship with a legendary figure, whereas Van Nistelrooy has been on the touchline all season behind Ten Hag, watching the team fail. Van Nistelrooy has similar connections to Solskjær’s and spoke before his Old Trafford managerial debut to Sir Alex Ferguson, another figurehead who reminds supporters of better days. It was special to come back to the club and the city, Van Nistelrooy said. I enjoy being around Manchester, the players and staff – not many [staff from his playing days are] still around. I decided to come back here for a very important reason: that I am here as an assistant. I came here to help the club move forward and I am still very motivated to do so in any capacity, as an assistant and now an interim manager. After that I go back to my assistant contract that I have for this season and next. Van Nistelrooy followed a similar path to Ten Hag with his formation against Leicester. This is not the time for revolutionary thinking; that should come from Amorim. Pressure had been built up before Ten Hag’s tenure stumbled to its final demise at West Ham and the players looked more relaxed against Leicester, but they know Sunday poses a far more difficult equation. This is no audition for Van Nistelrooy and his popularity will not wane, regardless of the next three games, but he will want to stand aside as a legend, whether he moves back into the shadows or exits Old Trafford to make way for Amorim’s backroom staff. Unlike Lee Carsley during his time in charge of England, he will not have to deal with questions about a desire to take the job because everyone knows what comes next and when. Van Nistelrooy found out during a spell at PSV about the complexities of managing a big club that he knows well. Somehow he will have to balance the enjoyment of having his dream job with the knowledge of its brevity and the need to get results to leave United in a better place.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length of the text - 3663\n"
     ]
    }
   ],
   "source": [
    "print(f\"length of the text - {len(text)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using pythons Unicode text conversion functions to covert each char of this text to int"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3663"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text_ints = [ord(c) for c in text]\n",
    "len(text_ints)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using built-in  UTF-8 encodings to convert text to embeddings----------\n",
    "\n",
    "With utf-8 embeddings, we get int for each char in the text. As we are using 8-byte for encoding, max vocab size can be 255.\n",
    "So model has to deal to with long sequences of int even for short text.."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3687"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokens = list(text.encode(\"utf-8\"))\n",
    "tokens = list(map(int, tokens))\n",
    "len(tokens)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "introducing byte-pair encoding (BPE) to reduce sequence length -------\n",
    "\n",
    "This will helps us \"pack\" more information (more text) in smaller number of ints, i.e. we can then use model's context length effectively.\n",
    "\n",
    "Summary of BPE: find the bytes pairs (here bytes are converted to ints) that occur most often and replace them with a new id (here a new int).\n",
    "Repeat this process \"desired number of times\". Every time you replace a byte pair by a new id, your vocab size increases (so the size of model's embedding table) and your input sequence length reduces.\n",
    "\n",
    "Toy example of BPE: https://en.wikipedia.org/wiki/Byte_pair_encoding\n",
    "\n",
    "Programatically BPE has 2 main parts:\n",
    "- finding repeating byte-pairs \n",
    "- replacing the most frequently repeating byte-pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(82, 117): 2, (117, 117): 8, (117, 100): 3, (100, 32): 62, (32, 118): 5, (118, 97): 2, (97, 110): 67, (110, 32): 53, (32, 78): 11, (78, 105): 9, (105, 115): 47, (115, 116): 39, (116, 101): 40, (101, 108): 19, (108, 114): 9, (114, 111): 22, (111, 111): 15, (111, 121): 11, (121, 32): 29, (32, 105): 37, (115, 32): 86, (32, 111): 22, (111, 110): 28, (110, 99): 6, (99, 101): 9, (101, 32): 104, (32, 97): 82, (97, 103): 15, (103, 97): 7, (97, 105): 11, (105, 110): 49, (32, 116): 89, (116, 104): 63, (104, 101): 70, (32, 102): 35, (102, 111): 22, (111, 99): 2, (99, 97): 7, (97, 108): 12, (108, 32): 17, (32, 112): 14, (112, 111): 8, (111, 105): 2, (110, 116): 18, (116, 32): 70, (97, 116): 26, (32, 77): 4, (77, 97): 3, (99, 104): 14, (101, 115): 21, (101, 114): 45, (114, 32): 34, (32, 85): 7, (85, 110): 7, (110, 105): 8, (105, 116): 35, (101, 100): 27, (100, 44): 4, (44, 32): 24, (108, 109): 1, (109, 111): 12, (111, 115): 4, (116, 119): 1, (119, 111): 3, (111, 32): 45, (32, 100): 23, (100, 101): 12, (101, 99): 6, (97, 100): 8, (97, 102): 9, (102, 116): 4, (32, 101): 11, (101, 110): 20, (110, 100): 32, (100, 105): 7, (110, 103): 25, (103, 32): 23, (97, 32): 20, (102, 105): 10, (105, 118): 2, (118, 101): 18, (101, 45): 1, (45, 121): 1, (121, 101): 3, (101, 97): 17, (97, 114): 20, (32, 115): 33, (115, 112): 5, (112, 101): 8, (108, 108): 14, (32, 108): 16, (108, 101): 17, (108, 105): 7, (110, 101): 16, (101, 46): 6, (46, 32): 25, (32, 84): 10, (84, 104): 5, (32, 98): 30, (98, 111): 3, (111, 116): 11, (116, 115): 6, (32, 119): 37, (119, 101): 5, (114, 101): 35, (32, 104): 42, (104, 117): 2, (117, 110): 10, (32, 117): 5, (117, 112): 6, (112, 32): 6, (108, 111): 7, (103, 111): 2, (104, 97): 26, (97, 115): 27, (115, 119): 1, (119, 97): 14, (97, 112): 2, (112, 112): 4, (102, 97): 6, (97, 109): 10, (111, 117): 15, (117, 115): 7, (32, 114): 9, (115, 104): 4, (104, 105): 24, (105, 114): 7, (114, 116): 6, (111, 114): 32, (116, 117): 7, (105, 99): 7, (99, 32): 1, (32, 99): 24, (99, 111): 9, (111, 97): 1, (98, 117): 8, (117, 116): 14, (105, 107): 3, (107, 101): 10, (111, 108): 6, (108, 100): 5, (100, 97): 8, (97, 121): 11, (121, 115): 4, (32, 79): 4, (79, 108): 4, (84, 114): 3, (114, 97): 7, (102, 102): 9, (114, 100): 5, (110, 115): 7, (114, 115): 8, (32, 110): 13, (110, 97): 11, (109, 101): 16, (32, 82): 2, (119, 104): 10, (101, 102): 4, (110, 110): 3, (116, 111): 32, (116, 97): 15, (97, 107): 5, (114, 103): 3, (103, 101): 11, (111, 102): 10, (102, 32): 12, (32, 109): 21, (109, 97): 15, (116, 99): 3, (104, 44): 1, (109, 117): 1, (117, 99): 2, (104, 45): 1, (45, 110): 1, (101, 101): 6, (32, 53): 1, (53, 45): 1, (45, 50): 1, (50, 32): 1, (32, 67): 4, (67, 97): 2, (97, 98): 4, (98, 97): 8, (97, 111): 2, (67, 117): 1, (118, 105): 5, (99, 116): 3, (114, 121): 9, (111, 118): 5, (32, 76): 5, (76, 101): 5, (101, 105): 4, (114, 46): 4, (108, 97): 12, (105, 100): 7, (100, 111): 7, (111, 119): 11, (119, 110): 1, (114, 107): 2, (119, 105): 10, (104, 32): 8, (67, 104): 1, (108, 115): 3, (115, 101): 8, (97, 226): 1, (226, 128): 10, (128, 153): 7, (153, 115): 7, (115, 105): 12, (32, 83): 7, (83, 117): 2, (32, 69): 4, (69, 117): 1, (117, 114): 11, (111, 112): 3, (112, 97): 4, (103, 117): 4, (117, 101): 2, (115, 111): 8, (101, 113): 2, (113, 117): 3, (117, 105): 2, (32, 80): 3, (80, 97): 1, (111, 107): 5, (107, 32): 7, (114, 44): 3, (32, 68): 1, (68, 117): 1, (104, 109): 1, (32, 107): 6, (107, 110): 6, (110, 111): 15, (119, 115): 5, (115, 109): 2, (110, 226): 1, (104, 111): 8, (121, 44): 4, (101, 118): 7, (111, 109): 15, (101, 111): 2, (112, 105): 1, (97, 99): 11, (99, 114): 1, (114, 105): 11, (105, 109): 11, (105, 111): 10, (101, 120): 7, (120, 105): 3, (32, 50): 1, (50, 48): 1, (48, 48): 1, (48, 54): 1, (54, 46): 1, (32, 73): 14, (73, 32): 10, (108, 112): 3, (112, 44): 1, (121, 116): 2, (109, 121): 2, (98, 105): 2, (105, 108): 11, (116, 105): 20, (105, 101): 2, (115, 44): 3, (110, 121): 3, (111, 44): 1, (105, 103): 5, (103, 104): 3, (104, 116): 3, (99, 108): 5, (108, 117): 6, (117, 98): 5, (98, 44): 1, (44, 226): 1, (128, 157): 1, (157, 32): 1, (115, 97): 2, (32, 86): 8, (86, 97): 8, (101, 116): 7, (114, 110): 2, (32, 74): 2, (74, 117): 1, (117, 108): 6, (108, 121): 1, (69, 114): 1, (32, 72): 5, (72, 97): 5, (103, 226): 2, (115, 115): 9, (116, 46): 3, (32, 226): 2, (128, 156): 1, (156, 84): 1, (98, 32): 6, (105, 102): 2, (99, 117): 2, (108, 116): 4, (117, 97): 3, (98, 101): 14, (69, 118): 1, (121, 111): 2, (107, 105): 2, (112, 108): 6, (32, 103): 4, (103, 114): 1, (116, 109): 1, (116, 44): 1, (115, 117): 5, (98, 121): 1, (115, 46): 2, (73, 116): 4, (112, 114): 3, (32, 87): 2, (87, 105): 1, (82, 195): 1, (195, 186): 1, (186, 98): 1, (32, 65): 5, (65, 109): 3, (109, 32): 13, (32, 106): 3, (106, 111): 5, (102, 114): 5, (83, 112): 1, (78, 111): 2, (101, 109): 4, (109, 98): 3, (114, 226): 2, (98, 114): 2, (107, 44): 1, (101, 44): 3, (105, 97): 4, (99, 107): 6, (107, 114): 2, (102, 46): 2, (32, 71): 1, (71, 117): 1, (83, 111): 3, (115, 107): 2, (107, 106): 2, (106, 195): 2, (195, 166): 2, (166, 114): 2, (109, 105): 7, (97, 118): 6, (117, 103): 1, (116, 116): 3, (116, 108): 1, (114, 109): 2, (101, 112): 1, (74, 111): 1, (115, 195): 1, (195, 169): 1, (169, 32): 1, (77, 111): 1, (110, 104): 1, (100, 46): 3, (114, 119): 2, (101, 103): 4, (103, 105): 2, (100, 121): 1, (105, 112): 1, (104, 108): 1, (101, 104): 3, (84, 101): 3, (103, 44): 1, (108, 46): 2, (101, 98): 1, (83, 105): 1, (65, 108): 1, (120, 32): 1, (32, 70): 1, (70, 101): 1, (110, 44): 1, (100, 115): 1, (99, 105): 4, (116, 121): 4, (110, 106): 2, (128, 147): 1, (147, 32): 1, (32, 91): 1, (91, 115): 1, (121, 105): 1, (101, 93): 1, (93, 32): 1, (109, 112): 2, (110, 58): 1, (58, 32): 1, (119, 32): 3, (65, 102): 1, (116, 114): 1, (120, 116): 3, (118, 111): 1, (110, 107): 1, (103, 59): 1, (59, 32): 1, (109, 46): 1, (80, 114): 1, (110, 117): 1, (117, 109): 1, (98, 108): 1, (87, 101): 1, (97, 120): 1, (120, 101): 1, (101, 121): 2, (110, 46): 2, (97, 117): 2, (112, 117): 1, (100, 108): 1, (104, 114): 1, (109, 226): 1, (110, 108): 1, (115, 108): 1, (100, 117): 2, (69, 110): 1, (103, 108): 1, (32, 113): 1, (111, 98): 2, (80, 83): 1, (83, 86): 1, (86, 32): 1, (121, 109): 1, (100, 114): 1, (119, 108): 1, (100, 103): 1}\n"
     ]
    }
   ],
   "source": [
    "def find_bp_stats(text_list):\n",
    "  \"\"\"\n",
    "  finds repeating byte pair and their frequency\n",
    "  Args:\n",
    "      text_list (_type_): list containing int for each char in the text\n",
    "  \"\"\"\n",
    "  counts = {}\n",
    "  for idx in range(0, len(text_list)-1, 1):\n",
    "    bp = (text_list[idx], text_list[idx+1])\n",
    "    counts[bp] = counts.get(bp, 0) +1\n",
    "  # sort the bp wrt their frequency\n",
    "  # counts = sorted(((v, k) for k, v in counts.items()), reverse=True)\n",
    "  return counts\n",
    "\n",
    "stats = find_bp_stats(tokens)\n",
    "print(stats)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_bp(curr_txt, curr_bp, new_id):\n",
    "  \"\"\"\n",
    "  replaces given bp in curr_txt with new_id\n",
    "  Args:\n",
    "      curr_txt (_type_): text in the form ints\n",
    "      curr_bp (_type_): bp to be replaced by new id\n",
    "      new_id (_type_): id to be assigned when replacing bp\n",
    "  \"\"\"\n",
    "  new_text = []\n",
    "  i = 0\n",
    "  replacement_count = 0\n",
    "  while i < len(curr_txt):\n",
    "    if i < len(curr_txt) - 1 and curr_txt[i] == curr_bp[0] and curr_txt[i+1] == curr_bp[1]:\n",
    "      new_text.append(new_id)\n",
    "      i += 2\n",
    "      replacement_count += 1\n",
    "    else:\n",
    "      new_text.append(curr_txt[i])\n",
    "      i += 1\n",
    "  # print(f\"replacement counts - {replacement_count}\")\n",
    "  return new_text\n",
    "      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We know byte pair (101, 32) repeats 104 times, let's try to replace it.\n",
    "length of our text is 3687, if we replace (101, 32) -> we should have len(new_text) == 3687-104*2+104 = 3583"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3687\n",
      "3583\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(len(tokens))\n",
    "t2 = merge_bp(tokens, (101, 32), 3688)\n",
    "print(len(t2))\n",
    "3688 in t2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's perform BPE on whole text N times. \n",
    "To decide N, either we can treat vocab_size as y hyperparameter. As we are using utf-8 encoding, we have 256 unique bytes in ourvocab,\n",
    "so vocab_size = 256, lets expand vocab size by 25 by doing 25 merges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'tokens' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[1], line 3\u001b[0m\n\u001b[1;32m      1\u001b[0m vocab_size \u001b[38;5;241m=\u001b[39m \u001b[38;5;241m281\u001b[39m \u001b[38;5;66;03m# the desired final vocabulary size\u001b[39;00m\n\u001b[1;32m      2\u001b[0m num_merges \u001b[38;5;241m=\u001b[39m vocab_size \u001b[38;5;241m-\u001b[39m \u001b[38;5;241m256\u001b[39m\n\u001b[0;32m----> 3\u001b[0m ids \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mlist\u001b[39m(\u001b[43mtokens\u001b[49m) \u001b[38;5;66;03m# copy so we don't destroy the original list\u001b[39;00m\n\u001b[1;32m      5\u001b[0m merges \u001b[38;5;241m=\u001b[39m {} \u001b[38;5;66;03m# (int, int) -> int\u001b[39;00m\n\u001b[1;32m      6\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(num_merges):\n",
      "\u001b[0;31mNameError\u001b[0m: name 'tokens' is not defined"
     ]
    }
   ],
   "source": [
    "vocab_size = 281 # the desired final vocabulary size\n",
    "num_merges = vocab_size - 256\n",
    "ids = list(tokens) # copy so we don't destroy the original list\n",
    "\n",
    "merges = {} # (int, int) -> int\n",
    "for i in range(num_merges):\n",
    "  stats = find_bp_stats(ids)\n",
    "  pair = max(stats, key=stats.get)\n",
    "  idx = 256 + i\n",
    "  print(f\"merging {pair} into a new token {idx}\")\n",
    "  ids = merge_bp(ids, pair, idx)\n",
    "  merges[pair] = idx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "let's see how much text size reduction we could obtain\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tokens length: 3687\n",
      "ids length: 2688\n",
      "compression ratio: 1.37X\n"
     ]
    }
   ],
   "source": [
    "print(\"tokens length:\", len(tokens))\n",
    "print(\"ids length:\", len(ids))\n",
    "print(f\"compression ratio: {len(tokens) / len(ids):.2f}X\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This merging process is also called as \"training\" of the tokenizer. In this process we try to strike a sweet-spot between vocab_size and length of text after encoding using the tokenizer. \n",
    "\n",
    "Let's assume that we are happy after one round of training and see how can we use this tokenizer for encoding and decoding the text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's build vocab for our encode-decode experiment\n",
    "# why 256 -- we use utf-8 encoding, 8 bytes so 256 elements\n",
    "# and why bytes -- utf-8 has mapping of  bytes:chars, so we also need mapping of int:bytes\n",
    "\n",
    "vocab = {idx: bytes([idx]) for idx in range(256)}\n",
    "for (p0, p1), idx in merges.items():\n",
    "    vocab[idx] = vocab[p0] + vocab[p1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decode(ids):\n",
    "  \"\"\" given ids (list of integers), return Python string\n",
    "\n",
    "  Args:\n",
    "      ids: list of ints to be decoded\n",
    "\n",
    "  Returns:\n",
    "      text: decoded text i.e. int -> bytes -> chars mapping \n",
    "  \"\"\"\n",
    "  \n",
    "  # let's find bytes belonging to each id in ids and join them as a str\n",
    "  tokens = b\"\".join(vocab[idx] for idx in ids)\n",
    "  # lets decode this str of bytes using utf-8 format, remember utf-8 has mapping of bytes->chars\n",
    "  # also error handling with errors=\"replace\" as not every char will have a valid utf-x encoding/decoding, \"replace\" then catches\n",
    "  # the errors and replaces them with \"?\"\n",
    "  text = tokens.decode(\"utf-8\", errors=\"replace\")\n",
    "  return text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n"
     ]
    }
   ],
   "source": [
    "def encode(text):\n",
    "  \"\"\"given a string, return list of integers (the tokens)\n",
    "\n",
    "  Args:\n",
    "      text : list of str to be encoded\n",
    "\n",
    "  Returns:\n",
    "      _type_: int id for each char in str\n",
    "  \"\"\"\n",
    "  # convert the text into str of bytes\n",
    "  tokens = list(text.encode(\"utf-8\"))\n",
    "  while len(tokens) >= 2:\n",
    "    # let's find stats of repetative byte-pairs\n",
    "    stats = find_bp_stats(tokens)\n",
    "    # finding most eligible token for merging\n",
    "    \n",
    "    # Get the list of pairs that are in both stats and merges\n",
    "    available_pairs = [p for p in stats if p in merges]\n",
    "    # now merges is a dict of (int, int) -> priority_num. lower the priority_num -> earlier that (int, int) pairing was added to merges.\n",
    "    # in short we select pair for merging in the same order as comapred to merges\n",
    "    pair = min(available_pairs, key=lambda p: merges[p], default=None)\n",
    "    if pair not in merges:\n",
    "      break # nothing else can be merged\n",
    "    idx = merges[pair]\n",
    "    tokens = merge_bp(tokens, pair, idx)\n",
    "  return tokens\n",
    "\n",
    "print(encode(\"\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "let's test our encoding and decoding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "valtext = \"Many common characters, including numerals, punctuation, and other symbols, are unified within the standard and are not treated as specific to any given writing system. Unicode encodes thousands of emoji, with the continued development thereof conducted by the Consortium as a part of the standard.[4] Moreover, the widespread adoption of Unicode was in large part responsible for the initial popularization of emoji outside of Japan. Unicode is ultimately capable of encoding more than 1.1 million characters.\"\n",
    "valtext2 = decode(encode(valtext))\n",
    "print(valtext2 == valtext)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using regex to meaningfully split the text before tokenization, refer karpathy's video for [detailed explanation](https://www.youtube.com/watch?v=zduSFxRajkE&t=3456s)\n",
    "\n",
    "my understanding: Until now we have been spliting words almost without any logic. e.g. the most frequently occurring toeken (101, 32) was \"e. \".\n",
    "To split words meaningfully, a regex statement is used which --\n",
    "- splits words at spaces, \n",
    "- makes sequences of numbers \n",
    "- separates numbers from words\n",
    "- separates punctuations\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Why', \"'\", 'd', 'heck', 'we', 'need', 'tokenizer', '12', '?', '345', '?']\n"
     ]
    }
   ],
   "source": [
    "# for BPE a simpler regex should suffice, e.g.\n",
    "import regex as re\n",
    "bpe_pat = re.compile(r\"\\p{N}+|\\p{L}+|[^\\p{L}\\s]\")\n",
    "print(re.findall(bpe_pat, \"Why'd heck we need tokenizer12?345?\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Why', \"'d\", ' heck', ' we', ' need', ' tokenizer', '12', '?', '345', '?']\n"
     ]
    }
   ],
   "source": [
    "\n",
    "gpt2pat = re.compile(r\"\"\"'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)|\\s+\"\"\")\n",
    "# ##### this regex experession is much more like sentencepiece though.. Notice those spaces being included in the words?? \n",
    "# That's how sentencepiece pre-processes the input.\n",
    "print(re.findall(gpt2pat, \"Why'd heck we need tokenizer12?345?\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base_env",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}