llm_tokenizer.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'안녕하세요 👋 (hello in Korean!)'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"안녕하세요 👋 (hello in Korean!)\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "len(unicode_code_point)=26\n",
      "[50504, 45397, 54616, 49464, 50836, 32, 128075, 32, 40, 104, 101, 108, 108, 111, 32, 105, 110, 32, 75, 111, 114, 101, 97, 110, 33, 41]\n"
     ]
    }
   ],
   "source": [
    "# 跟字符个数一样: unicode code point\n",
    "unicode_code_point = [ord(x) for x in \"안녕하세요 👋 (hello in Korean!)\"]\n",
    "print(f\"{len(unicode_code_point)=}\")\n",
    "print(unicode_code_point)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "len(utf8)=39\n",
      "utf8=[236, 149, 136, 235, 133, 149, 237, 149, 152, 236, 132, 184, 236, 154, 148, 32, 240, 159, 145, 139, 32, 40, 104, 101, 108, 108, 111, 32, 105, 110, 32, 75, 111, 114, 101, 97, 110, 33, 41]\n"
     ]
    }
   ],
   "source": [
    "# 使用 utf-8 编码\n",
    "utf8 = list(\"안녕하세요 👋 (hello in Korean!)\".encode(\"utf-8\"))\n",
    "print(f\"{len(utf8)=}\")\n",
    "print(f\"{utf8=}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---\n",
      "text='Ｕｎｉｃｏｄｅ! 🅤🅝🅘🅒🅞🅓🅔‽ 🇺\\u200c🇳\\u200c🇮\\u200c🇨\\u200c🇴\\u200c🇩\\u200c🇪! 😄 The very name strikes fear and awe into the hearts of programmers worldwide. We all know we ought to “support Unicode” in our software (whatever that means—like using wchar_t for all the strings, right?). But Unicode can be abstruse, and diving into the thousand-page Unicode Standard plus its dozens of supplementary annexes, reports, and notes can be more than a little intimidating. I don’t blame programmers for still finding the whole thing mysterious, even 30 years after Unicode’s inception.'\n",
      "len(text)=533\n",
      "---\n",
      "bytes_tokens=b'\\xef\\xbc\\xb5\\xef\\xbd\\x8e\\xef\\xbd\\x89\\xef\\xbd\\x83\\xef\\xbd\\x8f\\xef\\xbd\\x84\\xef\\xbd\\x85! \\xf0\\x9f\\x85\\xa4\\xf0\\x9f\\x85\\x9d\\xf0\\x9f\\x85\\x98\\xf0\\x9f\\x85\\x92\\xf0\\x9f\\x85\\x9e\\xf0\\x9f\\x85\\x93\\xf0\\x9f\\x85\\x94\\xe2\\x80\\xbd \\xf0\\x9f\\x87\\xba\\xe2\\x80\\x8c\\xf0\\x9f\\x87\\xb3\\xe2\\x80\\x8c\\xf0\\x9f\\x87\\xae\\xe2\\x80\\x8c\\xf0\\x9f\\x87\\xa8\\xe2\\x80\\x8c\\xf0\\x9f\\x87\\xb4\\xe2\\x80\\x8c\\xf0\\x9f\\x87\\xa9\\xe2\\x80\\x8c\\xf0\\x9f\\x87\\xaa! \\xf0\\x9f\\x98\\x84 The very name strikes fear and awe into the hearts of programmers worldwide. We all know we ought to \\xe2\\x80\\x9csupport Unicode\\xe2\\x80\\x9d in our software (whatever that means\\xe2\\x80\\x94like using wchar_t for all the strings, right?). But Unicode can be abstruse, and diving into the thousand-page Unicode Standard plus its dozens of supplementary annexes, reports, and notes can be more than a little intimidating. I don\\xe2\\x80\\x99t blame programmers for still finding the whole thing mysterious, even 30 years after Unicode\\xe2\\x80\\x99s inception.'\n",
      "len(bytes_tokens)=616\n",
      "---\n",
      "tokens=[239, 188, 181, 239, 189, 142, 239, 189, 137, 239, 189, 131, 239, 189, 143, 239, 189, 132, 239, 189, 133, 33, 32, 240, 159, 133, 164, 240, 159, 133, 157, 240, 159, 133, 152, 240, 159, 133, 146, 240, 159, 133, 158, 240, 159, 133, 147, 240, 159, 133, 148, 226, 128, 189, 32, 240, 159, 135, 186, 226, 128, 140, 240, 159, 135, 179, 226, 128, 140, 240, 159, 135, 174, 226, 128, 140, 240, 159, 135, 168, 226, 128, 140, 240, 159, 135, 180, 226, 128, 140, 240, 159, 135, 169, 226, 128, 140, 240, 159, 135, 170, 33, 32, 240, 159, 152, 132, 32, 84, 104, 101, 32, 118, 101, 114, 121, 32, 110, 97, 109, 101, 32, 115, 116, 114, 105, 107, 101, 115, 32, 102, 101, 97, 114, 32, 97, 110, 100, 32, 97, 119, 101, 32, 105, 110, 116, 111, 32, 116, 104, 101, 32, 104, 101, 97, 114, 116, 115, 32, 111, 102, 32, 112, 114, 111, 103, 114, 97, 109, 109, 101, 114, 115, 32, 119, 111, 114, 108, 100, 119, 105, 100, 101, 46, 32, 87, 101, 32, 97, 108, 108, 32, 107, 110, 111, 119, 32, 119, 101, 32, 111, 117, 103, 104, 116, 32, 116, 111, 32, 226, 128, 156, 115, 117, 112, 112, 111, 114, 116, 32, 85, 110, 105, 99, 111, 100, 101, 226, 128, 157, 32, 105, 110, 32, 111, 117, 114, 32, 115, 111, 102, 116, 119, 97, 114, 101, 32, 40, 119, 104, 97, 116, 101, 118, 101, 114, 32, 116, 104, 97, 116, 32, 109, 101, 97, 110, 115, 226, 128, 148, 108, 105, 107, 101, 32, 117, 115, 105, 110, 103, 32, 119, 99, 104, 97, 114, 95, 116, 32, 102, 111, 114, 32, 97, 108, 108, 32, 116, 104, 101, 32, 115, 116, 114, 105, 110, 103, 115, 44, 32, 114, 105, 103, 104, 116, 63, 41, 46, 32, 66, 117, 116, 32, 85, 110, 105, 99, 111, 100, 101, 32, 99, 97, 110, 32, 98, 101, 32, 97, 98, 115, 116, 114, 117, 115, 101, 44, 32, 97, 110, 100, 32, 100, 105, 118, 105, 110, 103, 32, 105, 110, 116, 111, 32, 116, 104, 101, 32, 116, 104, 111, 117, 115, 97, 110, 100, 45, 112, 97, 103, 101, 32, 85, 110, 105, 99, 111, 100, 101, 32, 83, 116, 97, 110, 100, 97, 114, 100, 32, 112, 108, 117, 115, 32, 105, 116, 115, 32, 100, 111, 122, 101, 110, 115, 32, 111, 102, 32, 115, 117, 112, 112, 108, 101, 109, 101, 110, 116, 97, 114, 121, 32, 97, 110, 110, 101, 120, 101, 115, 44, 32, 114, 101, 112, 111, 114, 116, 115, 44, 32, 97, 110, 100, 32, 110, 111, 116, 101, 115, 32, 99, 97, 110, 32, 98, 101, 32, 109, 111, 114, 101, 32, 116, 104, 97, 110, 32, 97, 32, 108, 105, 116, 116, 108, 101, 32, 105, 110, 116, 105, 109, 105, 100, 97, 116, 105, 110, 103, 46, 32, 73, 32, 100, 111, 110, 226, 128, 153, 116, 32, 98, 108, 97, 109, 101, 32, 112, 114, 111, 103, 114, 97, 109, 109, 101, 114, 115, 32, 102, 111, 114, 32, 115, 116, 105, 108, 108, 32, 102, 105, 110, 100, 105, 110, 103, 32, 116, 104, 101, 32, 119, 104, 111, 108, 101, 32, 116, 104, 105, 110, 103, 32, 109, 121, 115, 116, 101, 114, 105, 111, 117, 115, 44, 32, 101, 118, 101, 110, 32, 51, 48, 32, 121, 101, 97, 114, 115, 32, 97, 102, 116, 101, 114, 32, 85, 110, 105, 99, 111, 100, 101, 226, 128, 153, 115, 32, 105, 110, 99, 101, 112, 116, 105, 111, 110, 46]\n",
      "len(tokens)=616\n"
     ]
    }
   ],
   "source": [
    "text = \"Ｕｎｉｃｏｄｅ! 🅤🅝🅘🅒🅞🅓🅔‽ 🇺‌🇳‌🇮‌🇨‌🇴‌🇩‌🇪! 😄 The very name strikes fear and awe into the hearts of programmers worldwide. We all know we ought to “support Unicode” in our software (whatever that means—like using wchar_t for all the strings, right?). But Unicode can be abstruse, and diving into the thousand-page Unicode Standard plus its dozens of supplementary annexes, reports, and notes can be more than a little intimidating. I don’t blame programmers for still finding the whole thing mysterious, even 30 years after Unicode’s inception.\"\n",
    "bytes_tokens = text.encode('utf-8') # raw bytes: '\\xef\\xbc'\n",
    "# byte to int\n",
    "tokens = list(map(lambda x: int(x), bytes_tokens))\n",
    "print('---')\n",
    "print(f\"{text=}\\n{len(text)=}\")\n",
    "print('---')\n",
    "print(f\"{bytes_tokens=}\\n{len(bytes_tokens)=}\")\n",
    "print('---')\n",
    "print(f\"{tokens=}\\n{len(tokens)=}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "stats={(239, 188): 1, (188, 181): 1, (181, 239): 1, (239, 189): 6, (189, 142): 1, (142, 239): 1, (189, 137): 1, (137, 239): 1, (189, 131): 1, (131, 239): 1, (189, 143): 1, (143, 239): 1, (189, 132): 1, (132, 239): 1, (189, 133): 1, (133, 33): 1, (33, 32): 2, (32, 240): 3, (240, 159): 15, (159, 133): 7, (133, 164): 1, (164, 240): 1, (133, 157): 1, (157, 240): 1, (133, 152): 1, (152, 240): 1, (133, 146): 1, (146, 240): 1, (133, 158): 1, (158, 240): 1, (133, 147): 1, (147, 240): 1, (133, 148): 1, (148, 226): 1, (226, 128): 12, (128, 189): 1, (189, 32): 1, (159, 135): 7, (135, 186): 1, (186, 226): 1, (128, 140): 6, (140, 240): 6, (135, 179): 1, (179, 226): 1, (135, 174): 1, (174, 226): 1, (135, 168): 1, (168, 226): 1, (135, 180): 1, (180, 226): 1, (135, 169): 1, (169, 226): 1, (135, 170): 1, (170, 33): 1, (159, 152): 1, (152, 132): 1, (132, 32): 1, (32, 84): 1, (84, 104): 1, (104, 101): 6, (101, 32): 20, (32, 118): 1, (118, 101): 3, (101, 114): 6, (114, 121): 2, (121, 32): 2, (32, 110): 2, (110, 97): 1, (97, 109): 4, (109, 101): 6, (32, 115): 5, (115, 116): 5, (116, 114): 3, (114, 105): 4, (105, 107): 2, (107, 101): 2, (101, 115): 3, (115, 32): 10, (32, 102): 4, (102, 101): 1, (101, 97): 4, (97, 114): 7, (114, 32): 6, (32, 97): 10, (97, 110): 10, (110, 100): 6, (100, 32): 4, (97, 119): 1, (119, 101): 2, (32, 105): 6, (105, 110): 12, (110, 116): 4, (116, 111): 3, (111, 32): 3, (32, 116): 9, (116, 104): 8, (32, 104): 1, (114, 116): 3, (116, 115): 3, (32, 111): 4, (111, 102): 3, (102, 32): 2, (32, 112): 3, (112, 114): 2, (114, 111): 2, (111, 103): 2, (103, 114): 2, (114, 97): 2, (109, 109): 2, (114, 115): 3, (32, 119): 4, (119, 111): 1, (111, 114): 6, (114, 108): 1, (108, 100): 1, (100, 119): 1, (119, 105): 1, (105, 100): 2, (100, 101): 5, (101, 46): 1, (46, 32): 3, (32, 87): 1, (87, 101): 1, (97, 108): 2, (108, 108): 3, (108, 32): 3, (32, 107): 1, (107, 110): 1, (110, 111): 2, (111, 119): 1, (119, 32): 1, (111, 117): 4, (117, 103): 1, (103, 104): 2, (104, 116): 2, (116, 32): 6, (32, 226): 1, (128, 156): 1, (156, 115): 1, (115, 117): 2, (117, 112): 2, (112, 112): 2, (112, 111): 2, (32, 85): 4, (85, 110): 4, (110, 105): 4, (105, 99): 4, (99, 111): 4, (111, 100): 4, (101, 226): 2, (128, 157): 1, (157, 32): 1, (110, 32): 5, (117, 114): 1, (115, 111): 1, (102, 116): 2, (116, 119): 1, (119, 97): 1, (114, 101): 3, (32, 40): 1, (40, 119): 1, (119, 104): 2, (104, 97): 4, (97, 116): 3, (116, 101): 4, (101, 118): 2, (32, 109): 3, (110, 115): 2, (115, 226): 1, (128, 148): 1, (148, 108): 1, (108, 105): 2, (32, 117): 1, (117, 115): 5, (115, 105): 1, (110, 103): 6, (103, 32): 4, (119, 99): 1, (99, 104): 1, (114, 95): 1, (95, 116): 1, (102, 111): 2, (103, 115): 1, (115, 44): 4, (44, 32): 5, (32, 114): 2, (105, 103): 1, (116, 63): 1, (63, 41): 1, (41, 46): 1, (32, 66): 1, (66, 117): 1, (117, 116): 1, (32, 99): 2, (99, 97): 2, (32, 98): 3, (98, 101): 2, (97, 98): 1, (98, 115): 1, (114, 117): 1, (115, 101): 1, (101, 44): 1, (32, 100): 3, (100, 105): 2, (105, 118): 1, (118, 105): 1, (104, 111): 2, (115, 97): 1, (100, 45): 1, (45, 112): 1, (112, 97): 1, (97, 103): 1, (103, 101): 1, (32, 83): 1, (83, 116): 1, (116, 97): 2, (100, 97): 2, (114, 100): 1, (112, 108): 2, (108, 117): 1, (105, 116): 2, (100, 111): 2, (111, 122): 1, (122, 101): 1, (101, 110): 3, (108, 101): 3, (101, 109): 1, (110, 110): 1, (110, 101): 1, (101, 120): 1, (120, 101): 1, (101, 112): 2, (111, 116): 1, (109, 111): 1, (97, 32): 1, (32, 108): 1, (116, 116): 1, (116, 108): 1, (116, 105): 4, (105, 109): 1, (109, 105): 1, (103, 46): 1, (32, 73): 1, (73, 32): 1, (111, 110): 2, (110, 226): 1, (128, 153): 2, (153, 116): 1, (98, 108): 1, (108, 97): 1, (105, 108): 1, (102, 105): 1, (111, 108): 1, (104, 105): 1, (109, 121): 1, (121, 115): 1, (105, 111): 2, (32, 101): 1, (32, 51): 1, (51, 48): 1, (48, 32): 1, (32, 121): 1, (121, 101): 1, (97, 102): 1, (153, 115): 1, (110, 99): 1, (99, 101): 1, (112, 116): 1, (110, 46): 1}\n",
      "sorted(stats.items(), key=lambda x:x[1], reverse=True)=[((101, 32), 20), ((240, 159), 15), ((226, 128), 12), ((105, 110), 12), ((115, 32), 10), ((32, 97), 10), ((97, 110), 10), ((32, 116), 9), ((116, 104), 8), ((159, 133), 7), ((159, 135), 7), ((97, 114), 7), ((239, 189), 6), ((128, 140), 6), ((140, 240), 6), ((104, 101), 6), ((101, 114), 6), ((109, 101), 6), ((114, 32), 6), ((110, 100), 6), ((32, 105), 6), ((111, 114), 6), ((116, 32), 6), ((110, 103), 6), ((32, 115), 5), ((115, 116), 5), ((100, 101), 5), ((110, 32), 5), ((117, 115), 5), ((44, 32), 5), ((97, 109), 4), ((114, 105), 4), ((32, 102), 4), ((101, 97), 4), ((100, 32), 4), ((110, 116), 4), ((32, 111), 4), ((32, 119), 4), ((111, 117), 4), ((32, 85), 4), ((85, 110), 4), ((110, 105), 4), ((105, 99), 4), ((99, 111), 4), ((111, 100), 4), ((104, 97), 4), ((116, 101), 4), ((103, 32), 4), ((115, 44), 4), ((116, 105), 4), ((32, 240), 3), ((118, 101), 3), ((116, 114), 3), ((101, 115), 3), ((116, 111), 3), ((111, 32), 3), ((114, 116), 3), ((116, 115), 3), ((111, 102), 3), ((32, 112), 3), ((114, 115), 3), ((46, 32), 3), ((108, 108), 3), ((108, 32), 3), ((114, 101), 3), ((97, 116), 3), ((32, 109), 3), ((32, 98), 3), ((32, 100), 3), ((101, 110), 3), ((108, 101), 3), ((33, 32), 2), ((114, 121), 2), ((121, 32), 2), ((32, 110), 2), ((105, 107), 2), ((107, 101), 2), ((119, 101), 2), ((102, 32), 2), ((112, 114), 2), ((114, 111), 2), ((111, 103), 2), ((103, 114), 2), ((114, 97), 2), ((109, 109), 2), ((105, 100), 2), ((97, 108), 2), ((110, 111), 2), ((103, 104), 2), ((104, 116), 2), ((115, 117), 2), ((117, 112), 2), ((112, 112), 2), ((112, 111), 2), ((101, 226), 2), ((102, 116), 2), ((119, 104), 2), ((101, 118), 2), ((110, 115), 2), ((108, 105), 2), ((102, 111), 2), ((32, 114), 2), ((32, 99), 2), ((99, 97), 2), ((98, 101), 2), ((100, 105), 2), ((104, 111), 2), ((116, 97), 2), ((100, 97), 2), ((112, 108), 2), ((105, 116), 2), ((100, 111), 2), ((101, 112), 2), ((111, 110), 2), ((128, 153), 2), ((105, 111), 2), ((239, 188), 1), ((188, 181), 1), ((181, 239), 1), ((189, 142), 1), ((142, 239), 1), ((189, 137), 1), ((137, 239), 1), ((189, 131), 1), ((131, 239), 1), ((189, 143), 1), ((143, 239), 1), ((189, 132), 1), ((132, 239), 1), ((189, 133), 1), ((133, 33), 1), ((133, 164), 1), ((164, 240), 1), ((133, 157), 1), ((157, 240), 1), ((133, 152), 1), ((152, 240), 1), ((133, 146), 1), ((146, 240), 1), ((133, 158), 1), ((158, 240), 1), ((133, 147), 1), ((147, 240), 1), ((133, 148), 1), ((148, 226), 1), ((128, 189), 1), ((189, 32), 1), ((135, 186), 1), ((186, 226), 1), ((135, 179), 1), ((179, 226), 1), ((135, 174), 1), ((174, 226), 1), ((135, 168), 1), ((168, 226), 1), ((135, 180), 1), ((180, 226), 1), ((135, 169), 1), ((169, 226), 1), ((135, 170), 1), ((170, 33), 1), ((159, 152), 1), ((152, 132), 1), ((132, 32), 1), ((32, 84), 1), ((84, 104), 1), ((32, 118), 1), ((110, 97), 1), ((102, 101), 1), ((97, 119), 1), ((32, 104), 1), ((119, 111), 1), ((114, 108), 1), ((108, 100), 1), ((100, 119), 1), ((119, 105), 1), ((101, 46), 1), ((32, 87), 1), ((87, 101), 1), ((32, 107), 1), ((107, 110), 1), ((111, 119), 1), ((119, 32), 1), ((117, 103), 1), ((32, 226), 1), ((128, 156), 1), ((156, 115), 1), ((128, 157), 1), ((157, 32), 1), ((117, 114), 1), ((115, 111), 1), ((116, 119), 1), ((119, 97), 1), ((32, 40), 1), ((40, 119), 1), ((115, 226), 1), ((128, 148), 1), ((148, 108), 1), ((32, 117), 1), ((115, 105), 1), ((119, 99), 1), ((99, 104), 1), ((114, 95), 1), ((95, 116), 1), ((103, 115), 1), ((105, 103), 1), ((116, 63), 1), ((63, 41), 1), ((41, 46), 1), ((32, 66), 1), ((66, 117), 1), ((117, 116), 1), ((97, 98), 1), ((98, 115), 1), ((114, 117), 1), ((115, 101), 1), ((101, 44), 1), ((105, 118), 1), ((118, 105), 1), ((115, 97), 1), ((100, 45), 1), ((45, 112), 1), ((112, 97), 1), ((97, 103), 1), ((103, 101), 1), ((32, 83), 1), ((83, 116), 1), ((114, 100), 1), ((108, 117), 1), ((111, 122), 1), ((122, 101), 1), ((101, 109), 1), ((110, 110), 1), ((110, 101), 1), ((101, 120), 1), ((120, 101), 1), ((111, 116), 1), ((109, 111), 1), ((97, 32), 1), ((32, 108), 1), ((116, 116), 1), ((116, 108), 1), ((105, 109), 1), ((109, 105), 1), ((103, 46), 1), ((32, 73), 1), ((73, 32), 1), ((110, 226), 1), ((153, 116), 1), ((98, 108), 1), ((108, 97), 1), ((105, 108), 1), ((102, 105), 1), ((111, 108), 1), ((104, 105), 1), ((109, 121), 1), ((121, 115), 1), ((32, 101), 1), ((32, 51), 1), ((51, 48), 1), ((48, 32), 1), ((32, 121), 1), ((121, 101), 1), ((97, 102), 1), ((153, 115), 1), ((110, 99), 1), ((99, 101), 1), ((112, 116), 1), ((110, 46), 1)]\n"
     ]
    }
   ],
   "source": [
    "# 遍历 ids 里相邻的两个元素，统计两两元素出现的次数\n",
    "def get_stats(ids):\n",
    "    counts = {}\n",
    "    # pair 是一个元组，比如 (102, 32)\n",
    "    for pair in zip(ids, ids[1:]):\n",
    "        counts[pair] = counts.get(pair, 0) + 1 \n",
    "    return counts\n",
    "\n",
    "stats = get_stats(tokens)\n",
    "print(f\"{stats=}\")\n",
    "print(f\"{sorted(stats.items(), key=lambda x:x[1], reverse=True)=}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "top_pair=(32, 240)\n",
      "top_pair=(101, 32)\n",
      "merge(ids=[5,6,6,7,9,1], pair=(6,7), idx=99)=[5, 6, 99, 9, 1]\n",
      "len(merge(tokens, top_pair, 256))=596\n",
      "merge(tokens, top_pair, 256)=[239, 188, 181, 239, 189, 142, 239, 189, 137, 239, 189, 131, 239, 189, 143, 239, 189, 132, 239, 189, 133, 33, 32, 240, 159, 133, 164, 240, 159, 133, 157, 240, 159, 133, 152, 240, 159, 133, 146, 240, 159, 133, 158, 240, 159, 133, 147, 240, 159, 133, 148, 226, 128, 189, 32, 240, 159, 135, 186, 226, 128, 140, 240, 159, 135, 179, 226, 128, 140, 240, 159, 135, 174, 226, 128, 140, 240, 159, 135, 168, 226, 128, 140, 240, 159, 135, 180, 226, 128, 140, 240, 159, 135, 169, 226, 128, 140, 240, 159, 135, 170, 33, 32, 240, 159, 152, 132, 32, 84, 104, 256, 118, 101, 114, 121, 32, 110, 97, 109, 256, 115, 116, 114, 105, 107, 101, 115, 32, 102, 101, 97, 114, 32, 97, 110, 100, 32, 97, 119, 256, 105, 110, 116, 111, 32, 116, 104, 256, 104, 101, 97, 114, 116, 115, 32, 111, 102, 32, 112, 114, 111, 103, 114, 97, 109, 109, 101, 114, 115, 32, 119, 111, 114, 108, 100, 119, 105, 100, 101, 46, 32, 87, 256, 97, 108, 108, 32, 107, 110, 111, 119, 32, 119, 256, 111, 117, 103, 104, 116, 32, 116, 111, 32, 226, 128, 156, 115, 117, 112, 112, 111, 114, 116, 32, 85, 110, 105, 99, 111, 100, 101, 226, 128, 157, 32, 105, 110, 32, 111, 117, 114, 32, 115, 111, 102, 116, 119, 97, 114, 256, 40, 119, 104, 97, 116, 101, 118, 101, 114, 32, 116, 104, 97, 116, 32, 109, 101, 97, 110, 115, 226, 128, 148, 108, 105, 107, 256, 117, 115, 105, 110, 103, 32, 119, 99, 104, 97, 114, 95, 116, 32, 102, 111, 114, 32, 97, 108, 108, 32, 116, 104, 256, 115, 116, 114, 105, 110, 103, 115, 44, 32, 114, 105, 103, 104, 116, 63, 41, 46, 32, 66, 117, 116, 32, 85, 110, 105, 99, 111, 100, 256, 99, 97, 110, 32, 98, 256, 97, 98, 115, 116, 114, 117, 115, 101, 44, 32, 97, 110, 100, 32, 100, 105, 118, 105, 110, 103, 32, 105, 110, 116, 111, 32, 116, 104, 256, 116, 104, 111, 117, 115, 97, 110, 100, 45, 112, 97, 103, 256, 85, 110, 105, 99, 111, 100, 256, 83, 116, 97, 110, 100, 97, 114, 100, 32, 112, 108, 117, 115, 32, 105, 116, 115, 32, 100, 111, 122, 101, 110, 115, 32, 111, 102, 32, 115, 117, 112, 112, 108, 101, 109, 101, 110, 116, 97, 114, 121, 32, 97, 110, 110, 101, 120, 101, 115, 44, 32, 114, 101, 112, 111, 114, 116, 115, 44, 32, 97, 110, 100, 32, 110, 111, 116, 101, 115, 32, 99, 97, 110, 32, 98, 256, 109, 111, 114, 256, 116, 104, 97, 110, 32, 97, 32, 108, 105, 116, 116, 108, 256, 105, 110, 116, 105, 109, 105, 100, 97, 116, 105, 110, 103, 46, 32, 73, 32, 100, 111, 110, 226, 128, 153, 116, 32, 98, 108, 97, 109, 256, 112, 114, 111, 103, 114, 97, 109, 109, 101, 114, 115, 32, 102, 111, 114, 32, 115, 116, 105, 108, 108, 32, 102, 105, 110, 100, 105, 110, 103, 32, 116, 104, 256, 119, 104, 111, 108, 256, 116, 104, 105, 110, 103, 32, 109, 121, 115, 116, 101, 114, 105, 111, 117, 115, 44, 32, 101, 118, 101, 110, 32, 51, 48, 32, 121, 101, 97, 114, 115, 32, 97, 102, 116, 101, 114, 32, 85, 110, 105, 99, 111, 100, 101, 226, 128, 153, 115, 32, 105, 110, 99, 101, 112, 116, 105, 111, 110, 46]\n"
     ]
    }
   ],
   "source": [
    "top_pair = max(stats, key=lambda x:x[1])\n",
    "print(f\"{top_pair=}\")\n",
    "top_pair = max(stats, key=stats.get)\n",
    "print(f\"{top_pair=}\")\n",
    "# 把  ids 里 pair 这个连续的两个元素，合并为一个（用新的 idx）\n",
    "def merge(ids, pair, idx):\n",
    "    new_ids = []\n",
    "    i = 0\n",
    "    while i <= len(ids)-1:\n",
    "        if i < len(ids)-1 and ids[i] == pair[0] and ids[i+1] == pair[1]:\n",
    "            new_ids.append(idx)\n",
    "            i += 2\n",
    "        else:\n",
    "            new_ids.append(ids[i])\n",
    "            i += 1\n",
    "    \n",
    "    return new_ids\n",
    "\n",
    "print(f\"{merge(ids=[5,6,6,7,9,1], pair=(6,7), idx=99)=}\")\n",
    "\n",
    "print(f\"{len(merge(tokens, top_pair, 256))=}\")\n",
    "print(f\"{merge(tokens, top_pair, 256)=}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "merging (101, 32) into a new token 256\n",
      "merging (240, 159) into a new token 257\n",
      "merging (226, 128) into a new token 258\n",
      "merging (105, 110) into a new token 259\n",
      "merging (115, 32) into a new token 260\n",
      "merging (97, 110) into a new token 261\n",
      "merging (116, 104) into a new token 262\n",
      "merging (257, 133) into a new token 263\n",
      "merging (257, 135) into a new token 264\n",
      "merging (97, 114) into a new token 265\n",
      "merging (239, 189) into a new token 266\n",
      "merging (258, 140) into a new token 267\n",
      "merging (267, 264) into a new token 268\n",
      "merging (101, 114) into a new token 269\n",
      "merging (111, 114) into a new token 270\n",
      "merging (116, 32) into a new token 271\n",
      "merging (259, 103) into a new token 272\n",
      "merging (115, 116) into a new token 273\n",
      "merging (261, 100) into a new token 274\n",
      "merging (32, 262) into a new token 275\n"
     ]
    }
   ],
   "source": [
    "# ---\n",
    "vocab_size = 276 \n",
    "num_merges = vocab_size - 256 # unicode 里最大的\n",
    "ids = list(tokens) # copy\n",
    "merges = {} # (int, int) -> int\n",
    "for i in range(num_merges):\n",
    "    idx = 256+i\n",
    "    stats = get_stats(ids)\n",
    "    top_pair = max(stats, key=stats.get)\n",
    "    print(f\"merging {top_pair} into a new token {idx}\")\n",
    "    ids = merge(ids=ids, pair=top_pair, idx=idx)\n",
    "    merges[top_pair] = idx"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}