Demos/19. BPE vs WordPiece：理解 Tokenizer 的工作原理与子词分割方法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2d293fb3-7b27-4c56-ad0e-1d681360265f",
   "metadata": {
    "collapsed": true,
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "source": [
    "# BPE vs WordPiece：理解 Tokenizer 的工作原理与子词分割方法\n",
    "\n",
    "> 引导文章：[21. BPE vs WordPiece：理解 Tokenizer 的工作原理与子词分割方法](https://github.com/Hoper-J/AI-Guide-and-Demos-zh_CN/blob/master/Guide/21.%20BPE%20vs%20WordPiece：理解%20Tokenizer%20的工作原理与子词分割方法.md)\n",
    ">\n",
    "> 当前代码文件完全镜像了文章的内容，可以仅阅读该文件。\n",
    "\n",
    "在线链接：[Kaggle](https://www.kaggle.com/code/aidemos/19-bpe-vs-wordpiece-tokenizer) | [Colab](https://colab.research.google.com/drive/1J6QN0QbuoWBDIIrBe-TJ6Hi5rnzTSovM?usp=sharing)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f0eb806-1599-4d18-9bf5-ed75c7220bd8",
   "metadata": {},
   "source": [
    "> 在应用的路上“蒙着头”走了一段，是时候回过头来理解其中的工作原理了。\n",
    ">\n",
    "> 文章将以文本处理为例，介绍数据预处理中的关键组件——**Tokenizer（分词器）**。需要注意的是，这里是偏概念性的讲解，不会深入具体函数的参数细节。\n",
    ">\n",
    "> 「构造词汇表」部分将介绍两种常见的子词分割方法：\n",
    ">\n",
    "> - **BPE（Byte-Pair Encoding）**：用于 GPT、GPT-2、RoBERTa、BART 和 DeBERTa 等模型。\n",
    "> - **WordPiece**：用于 DistilBERT、MobileBERT、Funnel Transformers 和 MPNET 等模型。\n",
    ">\n",
    "> 「拓展」部分将涉及两个重要概念：\n",
    ">\n",
    "> - **注意力掩码（Attention Mask）**\n",
    "> - **词元类型 ID （Token Type IDs）**\n",
    ">\n",
    "> 工具：[Tiktokenizer（推荐）](https://tiktokenizer.vercel.app) | [The Tokenizer Playground](https://huggingface.co/spaces/Xenova/the-tokenizer-playground)\n",
    "\n",
    "\n",
    "\n",
    "## 什么是 Tokenizer？\n",
    "\n",
    "**Tokenizer**（分词器）可以将原始文本（raw text）转换为模型能够理解的数字序列，在模型输入和输出的两个主要阶段中发挥重要作用：\n",
    "\n",
    "### 模型输入（编码 Encode）阶段\n",
    "\n",
    "1. **分词（Tokenize）**\n",
    "\n",
    "   将文本拆分为词元（Token），常见的分词方式包括字级、词级、子词级（如 BPE、WordPiece）、空格分词等。\n",
    "\n",
    "   ```sql\n",
    "   输入: \"你好\"\n",
    "   分词: [\"你\", \"好\"]\n",
    "   ```\n",
    "\n",
    "2. **映射（Mapping）**\n",
    "\n",
    "   将每个词元映射为词汇表中的唯一 ID，生成的数字序列即为模型的输入。\n",
    "\n",
    "   ```sql\n",
    "   分词: [\"你\", \"好\"]\n",
    "   映射: [1001, 1002]\n",
    "   ```\n",
    "\n",
    "### 模型输出（解码 Decode）阶段\n",
    "\n",
    "1. **反映射（De-mapping）**\n",
    "\n",
    "   模型输出的数字序列通过词汇表映射回对应的词元，二者是一一对应的关系。\n",
    "\n",
    "   ```sql\n",
    "   输出: [1001, 1002]\n",
    "   反映射: [\"你\", \"好\"]\n",
    "   ```\n",
    "\n",
    "2. **文本重组**\n",
    "\n",
    "   将解码后的词元以某种规则重新拼接为完整文本。\n",
    "\n",
    "   ```sql\n",
    "   反映射: [\"你\", \"好\"]\n",
    "   重组: \"你好\"\n",
    "   ```\n",
    "\n",
    "### 直观感受\n",
    "\n",
    "访问 [Tiktokenizer](https://tiktokenizer.vercel.app)，通过右上角选取不同的 Tokenizer 进行尝试：\n",
    "\n",
    "![image-20241022152315606](../Guide/assets/image-20241022152315606.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61b3a399-48ba-4f1f-aa7b-68e69a9b4e74",
   "metadata": {},
   "source": [
    "## 实际使用\n",
    "在进一步讲解之前，我们先通过 **Transformers** 库中的 `AutoTokenizer` 类来使用 Tokenizer。\n",
    "\n",
    "### 安装库\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "cf279482-ba17-48ef-9aaf-cd447e6249b9",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "!pip install transformers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "400d1a72-a07e-4394-a448-746e74b0e4b0",
   "metadata": {},
   "source": [
    "### BPE 分词器示例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b81d62a7-97cc-43a4-8df2-2827fa3cfc44",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens: ['Hello', ',', 'Ġworld', '!']\n",
      "Token IDs: [15496, 11, 995, 0]\n",
      "Tokens: ['Hello', ',', 'Ġworld', '!']\n",
      "Decoded Text: Hello, world!\n"
     ]
    }
   ],
   "source": [
    "from transformers import AutoTokenizer\n",
    "\n",
    "# 使用 GPT-2 的分词器（BPE）\n",
    "tokenizer = AutoTokenizer.from_pretrained(\"gpt2\")\n",
    "\n",
    "text = \"Hello, world!\"\n",
    "\n",
    "# 编码\n",
    "# 1. 将文本分词为 Tokens\n",
    "tokens = tokenizer.tokenize(text)\n",
    "print(\"Tokens:\", tokens)\n",
    "\n",
    "# 2. 将 Tokens 转换为 Token IDs\n",
    "token_ids = tokenizer.convert_tokens_to_ids(tokens)\n",
    "print(\"Token IDs:\", token_ids)\n",
    "\n",
    "# 解码\n",
    "# 1. Token IDs 转换为 Tokens\n",
    "tokens = tokenizer.convert_ids_to_tokens(token_ids)\n",
    "print(\"Tokens:\", tokens)\n",
    "\n",
    "# 2. Tokens 拼接为文本\n",
    "decoded_text = tokenizer.convert_tokens_to_string(tokens)\n",
    "print(\"Decoded Text:\", decoded_text)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c86bd1e-875c-4949-8a35-547e85b02951",
   "metadata": {},
   "source": [
    "### WordPiece 分词器示例\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "0cfaafd8-12e2-48b7-8a60-c3e53d4d48f8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens: ['hello', ',', 'world', '!']\n",
      "Token IDs: [7592, 1010, 2088, 999]\n",
      "Tokens: ['hello', ',', 'world', '!']\n",
      "Decoded Text: hello, world!\n"
     ]
    }
   ],
   "source": [
    "from transformers import AutoTokenizer\n",
    "\n",
    "# 使用 BERT 的分词器（WordPiece）\n",
    "tokenizer = AutoTokenizer.from_pretrained(\"bert-base-uncased\")\n",
    "\n",
    "text = \"Hello, world!\"\n",
    "\n",
    "# 编码\n",
    "# 1. 将文本分词为 Tokens\n",
    "tokens = tokenizer.tokenize(text)\n",
    "print(\"Tokens:\", tokens)\n",
    "\n",
    "# 2. 将 Tokens 转换为 Token IDs\n",
    "token_ids = tokenizer.convert_tokens_to_ids(tokens)\n",
    "print(\"Token IDs:\", token_ids)\n",
    "\n",
    "# 解码\n",
    "# 1. Token IDs 转换为 Tokens\n",
    "tokens = tokenizer.convert_ids_to_tokens(token_ids)\n",
    "print(\"Tokens:\", tokens)\n",
    "\n",
    "# 2. Tokens 拼接为文本\n",
    "decoded_text = tokenizer.convert_tokens_to_string(tokens)\n",
    "print(\"Decoded Text:\", decoded_text)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93d9ae48-58e4-4e96-b7b4-947f00ec146a",
   "metadata": {},
   "source": [
    "### 使用 `encode()` 和 `decode()` 方法\n",
    "\n",
    "更简洁且常见的使用方式是直接使用 `encode()` 和 `decode()` 方法：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "56cab755-c719-4742-a5d4-35e5dc4a7cc2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Token IDs: [15496, 11, 995, 0]\n",
      "Decoded Text: Hello, world!\n"
     ]
    }
   ],
   "source": [
    "from transformers import AutoTokenizer\n",
    "\n",
    "# 取消注释以对比两种分词器的输出差异\n",
    "tokenizer = AutoTokenizer.from_pretrained(\"gpt2\")\n",
    "# tokenizer = AutoTokenizer.from_pretrained(\"bert-base-uncased\")\n",
    "\n",
    "text = \"Hello, world!\"\n",
    "\n",
    "# 使用 encode() 将文本直接转换为 Token IDs\n",
    "token_ids = tokenizer.encode(text)\n",
    "print(\"Token IDs:\", token_ids)\n",
    "\n",
    "# 使用 decode() 将 Token IDs 转换回文本\n",
    "decoded_text = tokenizer.decode(token_ids)\n",
    "print(\"Decoded Text:\", decoded_text)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "112c9cd4-66cd-4601-b938-e48cc814d5f9",
   "metadata": {},
   "source": [
    "## 了解 Tokenizer 的基础属性\n",
    "\n",
    "导入分词器后，可以选择查看一些属性来获得直观的理解，例如查看词汇表、特殊标记等，以 GPT-2 为例。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a9345315-83db-484a-9945-360d26f8ae83",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vocabulary Size: 50257\n"
     ]
    }
   ],
   "source": [
    "# 获取词汇表大小\n",
    "vocab_size = tokenizer.vocab_size\n",
    "print(\"Vocabulary Size:\", vocab_size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "107665fe-51d3-4f65-8f5a-1aa3e4aeace5",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Ġban': 3958,\n",
       " 'Ġsorely': 50103,\n",
       " 'Ġspeaks': 9209,\n",
       " 'nih': 37373,\n",
       " 'Cong': 18649,\n",
       " 'usercontent': 43667,\n",
       " 'rax': 32040,\n",
       " 'ĠDPS': 25366,\n",
       " 'dies': 25990,\n",
       " 'ĠGovernment': 5070,\n",
       " 'Ang': 13450,\n",
       " 'annon': 8825,\n",
       " 'ĠNathan': 18106,\n",
       " 'ĠSlash': 26616,\n",
       " 'ophical': 49256,\n",
       " 'Ġ450': 18523,\n",
       " 'Ġdystopian': 49483,\n",
       " 'edes': 37507,\n",
       " 'Ġapi': 40391,\n",
       " 'Ġleans': 39416,\n",
       " 'Ġsituations': 7445,\n",
       " 'Ġcolorful': 20239,\n",
       " 'Ġupper': 6727,\n",
       " 'Ġvouchers': 41262,\n",
       " 'Ġwellbeing': 40013,\n",
       " 'ĠðŁĳ': 50169,\n",
       " 'action': 2673,\n",
       " 'udeb': 46092,\n",
       " 'ĠKak': 31250,\n",
       " 'Ġformations': 30648,\n",
       " 'Ġspecifies': 26052,\n",
       " 'ĠMeredith': 40378,\n",
       " 'through': 9579,\n",
       " 'ĠHousing': 16797,\n",
       " 'ĠMarathon': 24828,\n",
       " 'ĠRecent': 22926,\n",
       " 'ĠPlain': 28847,\n",
       " 'ĠProsecutor': 37478,\n",
       " 'ĠRomeo': 43989,\n",
       " 'ĠSte': 2441,\n",
       " 'Ġarbitrary': 14977,\n",
       " 'Ġstabilized': 44945,\n",
       " 'LINE': 24027,\n",
       " 'ĠÂ«': 21110,\n",
       " 'Ġreferral': 31413,\n",
       " 'ento': 50217,\n",
       " 'payer': 34987,\n",
       " 'af': 1878,\n",
       " 'ĠHector': 42621,\n",
       " 'ĠNUM': 36871,\n",
       " 'ĠSpo': 49331,\n",
       " 'Ġinstallment': 25168,\n",
       " 'Chuck': 44324,\n",
       " 'Hide': 38518,\n",
       " 'ying': 1112,\n",
       " '73': 4790,\n",
       " 'ĠLiber': 5261,\n",
       " 'Ġ414': 45900,\n",
       " 'Awesome': 49061,\n",
       " 'UN': 4944,\n",
       " 'ption': 1159,\n",
       " 'ĠRear': 30144,\n",
       " 'Ġgoats': 35199,\n",
       " 'ĠPremier': 9952,\n",
       " 'ĠNS': 10896,\n",
       " 'Ġobsessive': 36681,\n",
       " 'has': 10134,\n",
       " 'Ġstretched': 19110,\n",
       " 'Ġwaning': 50073,\n",
       " 'ĠMits': 22424,\n",
       " 'Ġ253': 32056,\n",
       " 'launch': 35681,\n",
       " 'phasis': 28432,\n",
       " 'ĠSamson': 47977,\n",
       " 'ban': 3820,\n",
       " 'Boy': 26554,\n",
       " 'MS': 5653,\n",
       " 'Nazis': 44527,\n",
       " 'ĠFn': 37481,\n",
       " 'TL': 14990,\n",
       " 'animous': 45873,\n",
       " 'istant': 10167,\n",
       " 'ERT': 17395,\n",
       " 'ĠDome': 31390,\n",
       " 'Ġbuses': 16893,\n",
       " '277': 27019,\n",
       " '=\"#': 25698,\n",
       " 'sche': 15952,\n",
       " 'ĠSaid': 23885,\n",
       " 'ĠGreece': 10315,\n",
       " 'Ġcommunities': 5348,\n",
       " 'Ġinfographic': 48033,\n",
       " 'ĠHorizons': 39519,\n",
       " 'Ġ51': 6885,\n",
       " 'fruit': 34711,\n",
       " 'Ġ------': 40103,\n",
       " 'ĠAge': 7129,\n",
       " 'ĠKyr': 42748,\n",
       " 'Ġgrass': 8701,\n",
       " 'Ġloaded': 9639,\n",
       " 'accept': 13635,\n",
       " 'WER': 45532,\n",
       " 'aching': 8103,\n",
       " 'olla': 33011,\n",
       " 'Ġmarking': 18730,\n",
       " 'Ġsane': 33241,\n",
       " 'Ġstacked': 24167,\n",
       " 'Ġ1984': 12844,\n",
       " 'ĠDuncan': 18625,\n",
       " 'ĠFemin': 25832,\n",
       " 'Ġauthorized': 10435,\n",
       " 'PLE': 16437,\n",
       " 'Ġcanon': 18061,\n",
       " 'Event': 9237,\n",
       " 'meter': 27231,\n",
       " 'alter': 47653,\n",
       " 'imaru': 49551,\n",
       " 'ä¸ī': 49011,\n",
       " 'ĠBring': 24347,\n",
       " 'Ġleakage': 47988,\n",
       " 'Enhanced': 49026,\n",
       " 'cludes': 13955,\n",
       " 'ĠApproximately': 40453,\n",
       " 'illy': 6548,\n",
       " 'hig': 25196,\n",
       " 'inoa': 40564,\n",
       " 'within': 33479,\n",
       " 'btn': 46118,\n",
       " 'xd': 24954,\n",
       " '385': 27203,\n",
       " 'ĠINFO': 24890,\n",
       " 'ĠEasy': 16789,\n",
       " 'ĠPlat': 32715,\n",
       " 'Ġmeet': 1826,\n",
       " 'Ġnoisy': 31210,\n",
       " 'Ġphone': 3072,\n",
       " 'abling': 11716,\n",
       " 'modified': 41771,\n",
       " 'ĠBMW': 19339,\n",
       " 'Ġ1926': 38525,\n",
       " 'ĠTue': 30030,\n",
       " 'Weak': 44898,\n",
       " 'ĠCheng': 27692,\n",
       " 'hen': 831,\n",
       " 'ĠEngine': 7117,\n",
       " 'ĠKurds': 23880,\n",
       " 'ĠMac': 4100,\n",
       " 'Ġbottom': 4220,\n",
       " 'Ġcoup': 12092,\n",
       " 'mitter': 37974,\n",
       " 'ä½': 19526,\n",
       " 'ĠEle': 15987,\n",
       " 'Ġjuxtap': 45273,\n",
       " 'Ġstrategist': 25651,\n",
       " 'Rock': 19665,\n",
       " 'Ġuterus': 41303,\n",
       " 'ĠEP': 14724,\n",
       " 'Ġomission': 35725,\n",
       " 'ĠClone': 30698,\n",
       " 'Ġalcohol': 5548,\n",
       " 'urion': 40956,\n",
       " 'Ġfailures': 15536,\n",
       " 'Ġturrets': 41104,\n",
       " 'Ġget': 651,\n",
       " 'for': 1640,\n",
       " 'Ġ320': 20959,\n",
       " 'Ġdisabilities': 19358,\n",
       " '025': 36629,\n",
       " 'otions': 36083,\n",
       " 'Count': 12332,\n",
       " 'GAME': 47109,\n",
       " 'interested': 34339,\n",
       " 'Ġinterestingly': 50226,\n",
       " 'Ġpatrols': 34141,\n",
       " 'Ġsubdued': 38759,\n",
       " 'ĠFlint': 21660,\n",
       " 'ĠThrough': 9561,\n",
       " 'Ġshaky': 35335,\n",
       " 'Ġswitches': 18225,\n",
       " 'ippy': 41214,\n",
       " 'Am': 5840,\n",
       " 'Ġconvictions': 19131,\n",
       " 'ĠCarolina': 5913,\n",
       " 'ĠFounding': 44593,\n",
       " 'ĠSerpent': 30177,\n",
       " 'ĠKel': 15150,\n",
       " 'ĠICC': 32300,\n",
       " '???': 28358,\n",
       " 'Ġinfamous': 16526,\n",
       " 'Ġroundup': 48390,\n",
       " '024': 40839,\n",
       " 'Ġboobs': 41050,\n",
       " 'ĠRex': 17853,\n",
       " 'ifully': 17049,\n",
       " 'ĠCaptain': 8599,\n",
       " 'Ġstopp': 43804,\n",
       " 'Fred': 30847,\n",
       " 'Ġquar': 36343,\n",
       " 'ĠSuzuki': 35807,\n",
       " 'iable': 3379,\n",
       " 'Ġnations': 7027,\n",
       " '...': 986,\n",
       " 'ĠOblivion': 34181,\n",
       " 'Ġconstructed': 12006,\n",
       " 'ĠVerge': 44499,\n",
       " 'Ġpurchaser': 39122,\n",
       " 'ĠBog': 21555,\n",
       " 'ĠRecap': 46585,\n",
       " 'athering': 25545,\n",
       " 'Admin': 46787,\n",
       " 'ĠCoal': 12896,\n",
       " 'Ġparental': 21694,\n",
       " 'Ġpirates': 27516,\n",
       " 'Studies': 45833,\n",
       " 'Ġsophisticated': 13767,\n",
       " 'event': 15596,\n",
       " 'rogram': 39529,\n",
       " 'Ġabl': 46624,\n",
       " 'Ġdisl': 19621,\n",
       " 'Ġubiquitous': 27888,\n",
       " 'Ľ': 249,\n",
       " 'ĠACLU': 24381,\n",
       " 'Und': 31319,\n",
       " 'avier': 19492,\n",
       " 'Ġsomething': 1223,\n",
       " 'Ni': 34153,\n",
       " 'context': 22866,\n",
       " 'ĠVirus': 40584,\n",
       " 'ĠLoading': 12320,\n",
       " 'ĠMarvin': 35105,\n",
       " 'Brend': 48015,\n",
       " 'Ġexploited': 21514,\n",
       " 'Ġcube': 23441,\n",
       " 'Ġmotivating': 46891,\n",
       " 'aturation': 36921,\n",
       " 'esm': 45798,\n",
       " 'ODUCT': 28644,\n",
       " 'ĠGren': 19674,\n",
       " 'itchie': 48423,\n",
       " 'ĠElections': 24473,\n",
       " 'ãģł': 46777,\n",
       " 'Ġathleticism': 35159,\n",
       " 'Ġbathing': 39153,\n",
       " 'Ġblocks': 7021,\n",
       " 'inguished': 46709,\n",
       " 'ĠHass': 20300,\n",
       " 'Ġcomplaint': 8224,\n",
       " 'Ġdisturbed': 24069,\n",
       " 'Ġimper': 11071,\n",
       " 'Ġsincere': 17082,\n",
       " 'ĠInteresting': 43580,\n",
       " 'Ġenabling': 15882,\n",
       " 'Ġyards': 5695,\n",
       " 'ĸļ': 31204,\n",
       " 'VE': 6089,\n",
       " 'ibaba': 37541,\n",
       " 'ĠHas': 7875,\n",
       " 'itions': 1756,\n",
       " 'oyer': 35301,\n",
       " 'ĠSah': 22982,\n",
       " 'Ġdedicated': 7256,\n",
       " 'Ġexpand': 4292,\n",
       " 'Ġpitchers': 25259,\n",
       " 'arantine': 37996,\n",
       " 'ador': 7079,\n",
       " 'utt': 15318,\n",
       " 'ĠDarling': 49825,\n",
       " 'ĠErie': 40911,\n",
       " 'ĠHispanic': 16949,\n",
       " 'ĠOx': 10736,\n",
       " 'neck': 27235,\n",
       " 'ĠVanessa': 42100,\n",
       " 'Ġwind': 2344,\n",
       " 'ĠWrestling': 29662,\n",
       " 'ether': 6750,\n",
       " 'ĠImam': 38386,\n",
       " 'ĠPhillip': 29470,\n",
       " 'ĠRide': 21640,\n",
       " 'Ġcorrelate': 39684,\n",
       " 'Ġtropical': 19690,\n",
       " 'trip': 39813,\n",
       " 'ĠArs': 24230,\n",
       " 'Ġspecialists': 22447,\n",
       " 'Ġunite': 24558,\n",
       " 'ĠBenef': 19899,\n",
       " 'Ġenacted': 17814,\n",
       " 'uded': 19289,\n",
       " 'Ġcoroner': 39723,\n",
       " 'Ġpractition': 17629,\n",
       " 'OST': 10892,\n",
       " 'independent': 34750,\n",
       " 'otic': 6210,\n",
       " 'ĠTopic': 47373,\n",
       " 'Ġcrammed': 48384,\n",
       " 'Ġpremature': 19905,\n",
       " 'ittees': 13263,\n",
       " 'ĠFerr': 19130,\n",
       " 'ĠSed': 22710,\n",
       " 'mot': 27926,\n",
       " 'ĠAutob': 41735,\n",
       " 'ĠCommentary': 45465,\n",
       " 'ĠPapa': 42328,\n",
       " 'Ġbalcony': 29780,\n",
       " 'ilee': 40626,\n",
       " 'ĠLearns': 30667,\n",
       " 'Ġdances': 38207,\n",
       " 'Ġdemonstrators': 25016,\n",
       " 'atan': 39036,\n",
       " 'Ġformerly': 15734,\n",
       " 'ĠCraft': 15745,\n",
       " 'otton': 11324,\n",
       " 'Ġprofessors': 20339,\n",
       " 'Ġraid': 9513,\n",
       " 'Ġthumbs': 32766,\n",
       " 'Ġunderwent': 25289,\n",
       " '(': 7,\n",
       " 'inges': 26792,\n",
       " 'erick': 41556,\n",
       " 'Ġtrooper': 41967,\n",
       " 'Sher': 28782,\n",
       " 'Ġrookie': 12302,\n",
       " 'Ġscheduled': 7530,\n",
       " 'ĠCalories': 45133,\n",
       " 'Ġpedest': 14238,\n",
       " 'backed': 17078,\n",
       " 'Ġintoxicated': 35344,\n",
       " 'Ġ284': 40654,\n",
       " 'Japanese': 25324,\n",
       " 'ĠCambridge': 14457,\n",
       " 'ĠNightmare': 23951,\n",
       " '********': 4557,\n",
       " 'ĠRated': 49949,\n",
       " 'Ġcontinue': 2555,\n",
       " 'ĠSerial': 23283,\n",
       " 'Ġhijacked': 41554,\n",
       " 'Ġhog': 40476,\n",
       " 'Ġorder': 1502,\n",
       " 'Ġurged': 11643,\n",
       " 'ulz': 37314,\n",
       " 'Ġall': 477,\n",
       " 'Ġfishing': 12478,\n",
       " 'ĠBapt': 18226,\n",
       " 'ĠCabin': 16804,\n",
       " 'aliation': 22885,\n",
       " 'creation': 38793,\n",
       " 'Fran': 38848,\n",
       " 'ĠEthnic': 48021,\n",
       " 'Ġfrying': 45366,\n",
       " 'Ġproblematic': 15833,\n",
       " 'ĠCastle': 11312,\n",
       " 'ĠNeil': 15929,\n",
       " 'onut': 16478,\n",
       " 'Ġwhopping': 27833,\n",
       " 'ompl': 6316,\n",
       " 'Ġmushrooms': 23452,\n",
       " 'yright': 4766,\n",
       " '\":-': 48219,\n",
       " 'effective': 16803,\n",
       " 'essler': 33730,\n",
       " 'Ġgeneral': 2276,\n",
       " 'ĠSexual': 19536,\n",
       " 'ĠZan': 47022,\n",
       " 'Ġrandom': 4738,\n",
       " 'Ġsegregated': 38135,\n",
       " 'Ãª': 25792,\n",
       " 'Education': 41183,\n",
       " 'Ġdormant': 41038,\n",
       " 'Ġpraying': 26002,\n",
       " 'Ġsignalling': 45829,\n",
       " 'Take': 12322,\n",
       " 'University': 21009,\n",
       " 'nsic': 19364,\n",
       " 'rupted': 31590,\n",
       " 'brates': 44835,\n",
       " 'ĠSheet': 21616,\n",
       " 'source': 10459,\n",
       " 'ĠUNHCR': 49558,\n",
       " 'Ġrevolution': 5854,\n",
       " 'Ġvacuum': 17076,\n",
       " 'ĠOptional': 32233,\n",
       " '205': 21261,\n",
       " 'Application': 23416,\n",
       " 'ĠSIGN': 36771,\n",
       " 'Ġdemocrat': 43268,\n",
       " 'ĠMastery': 37799,\n",
       " 'ĠMorris': 14433,\n",
       " 'Ġdiscriminatory': 27200,\n",
       " 'Ġoscill': 24969,\n",
       " 'Ġappreciate': 9144,\n",
       " 'ĠOffensive': 26855,\n",
       " 'HC': 16045,\n",
       " 'gin': 1655,\n",
       " 'ĠStrike': 12282,\n",
       " 'Ġhesitation': 29592,\n",
       " 'ĠHawaii': 13708,\n",
       " 'Cold': 34312,\n",
       " 'Ġchicken': 9015,\n",
       " 'ĠBritain': 5491,\n",
       " 'react': 45018,\n",
       " 'Ġfingerprint': 25338,\n",
       " 'ĠQU': 19604,\n",
       " 'ĠPatterns': 47020,\n",
       " 'Ġcapacity': 5339,\n",
       " 'Ġspeech': 4046,\n",
       " '!!\"': 37160,\n",
       " 'ĠTyp': 17134,\n",
       " 'ĠPizza': 20952,\n",
       " 'Ġcocktail': 24554,\n",
       " 'ĠOfficer': 10391,\n",
       " 'Ġconventions': 21396,\n",
       " 'illac': 40607,\n",
       " 'ATION': 6234,\n",
       " 'Cam': 21701,\n",
       " 'Ġringing': 32333,\n",
       " 'Ġfert': 11093,\n",
       " 'ĠYok': 45138,\n",
       " 'inter': 3849,\n",
       " 'Ġranges': 16069,\n",
       " 'deg': 13500,\n",
       " 'Ġsensed': 39243,\n",
       " 'assembled': 46826,\n",
       " 'industrial': 31130,\n",
       " 'Ġconsequences': 6948,\n",
       " 'ĠBAS': 29809,\n",
       " 'ĠWhile': 2893,\n",
       " 'Ġnumeric': 35575,\n",
       " 'Ġsocialist': 15889,\n",
       " 'Ġrule': 3896,\n",
       " 'Ġtournaments': 18130,\n",
       " '\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\': 34604,\n",
       " 'ricane': 11551,\n",
       " 'ĠKathryn': 48674,\n",
       " 'Ġmentioning': 20862,\n",
       " 'Ġrealms': 35423,\n",
       " 'today': 40838,\n",
       " 'Ķ': 242,\n",
       " 'Ġnation': 3277,\n",
       " 'Ġlivestream': 49683,\n",
       " 'ĠYelp': 44628,\n",
       " 'ced': 771,\n",
       " 'Ġcommuting': 45309,\n",
       " 'electric': 31067,\n",
       " 'aida': 30546,\n",
       " 'Ġattorneys': 14449,\n",
       " 'STER': 41809,\n",
       " '_{': 23330,\n",
       " 'ĠBuild': 10934,\n",
       " 'ĠMcCabe': 45395,\n",
       " 'Clar': 48035,\n",
       " 'ĠSach': 20678,\n",
       " 'iths': 47252,\n",
       " 'ĠWik': 11145,\n",
       " '×Ļ×': 33951,\n",
       " '999': 17032,\n",
       " 'ĠFlorida': 4744,\n",
       " 'ĠSpan': 49101,\n",
       " 'ĠWinchester': 40868,\n",
       " 'Ġauxiliary': 37419,\n",
       " 'Ġknot': 29654,\n",
       " 'ĠINS': 29194,\n",
       " 'Ġlush': 37408,\n",
       " 'Ġprinciples': 7811,\n",
       " 'eneg': 46495,\n",
       " 'Program': 15167,\n",
       " 'powers': 30132,\n",
       " 'ĠTracks': 42259,\n",
       " 'ldom': 23826,\n",
       " 'Ġtags': 15940,\n",
       " 'Tex': 17005,\n",
       " 'Ġesteem': 42213,\n",
       " 'Ġmobility': 15873,\n",
       " 'isl': 3044,\n",
       " 'olis': 8506,\n",
       " 'ruction': 2762,\n",
       " 'ĠFare': 35205,\n",
       " 'Les': 35882,\n",
       " 'Ġprevious': 2180,\n",
       " 'Ġsociop': 41221,\n",
       " 'billion': 24540,\n",
       " 'ĠPrior': 14481,\n",
       " 'Ġcontradiction': 25741,\n",
       " 'Ġdeviation': 28833,\n",
       " 'ĠPlayed': 33101,\n",
       " 'Ġtrauma': 14649,\n",
       " '558': 40486,\n",
       " 'Ġeditorial': 13684,\n",
       " 'Ġentirety': 21818,\n",
       " 'Â©': 16224,\n",
       " 'ĠGD': 27044,\n",
       " 'medi': 2379,\n",
       " 'ĠGarage': 45502,\n",
       " 'Lastly': 37511,\n",
       " 'inventory': 24807,\n",
       " 'Ġmediated': 36631,\n",
       " 'Ġreceives': 11583,\n",
       " 'Gear': 38141,\n",
       " 'ĠCla': 27166,\n",
       " 'Ġdiffered': 36337,\n",
       " 'itbart': 17868,\n",
       " 'onomy': 30565,\n",
       " 'ĠRegular': 23603,\n",
       " 'Ġbleach': 49024,\n",
       " 'Ġconcepts': 10838,\n",
       " 'Ġcourts': 8028,\n",
       " 'Ġforfeit': 46548,\n",
       " 'types': 19199,\n",
       " 'ĠPutting': 39956,\n",
       " 'Ġorganis': 13867,\n",
       " 'Shop': 29917,\n",
       " 'ĠHungarian': 27304,\n",
       " 'Ġscreamed': 25421,\n",
       " 'WASHINGTON': 21793,\n",
       " 'ĠLatino': 20496,\n",
       " 'Ġextensive': 7667,\n",
       " 'igning': 38944,\n",
       " 'Ġling': 18459,\n",
       " 'ublished': 33286,\n",
       " 'ĠElk': 40151,\n",
       " 'Ġunited': 16503,\n",
       " 'DK': 48510,\n",
       " 'raphic': 22262,\n",
       " 'Ġboycot': 46878,\n",
       " 'Ġdist': 1233,\n",
       " 'Ġinterruption': 41728,\n",
       " 'iability': 12455,\n",
       " 'urst': 24962,\n",
       " 'Ġsilhouette': 41834,\n",
       " 'OTT': 29089,\n",
       " 'ĠFOR': 7473,\n",
       " 'Ġresentment': 28888,\n",
       " 'Ġepisodes': 8640,\n",
       " 'variable': 45286,\n",
       " 'zhen': 46732,\n",
       " 'ĠGrey': 13980,\n",
       " 'Small': 18712,\n",
       " 'Nevertheless': 29011,\n",
       " 'uned': 40881,\n",
       " 'Ġitching': 48140,\n",
       " 'Disable': 48893,\n",
       " 'ĠNewspaper': 49598,\n",
       " 'elta': 12514,\n",
       " 'Ø§': 12919,\n",
       " 'ached': 2317,\n",
       " 'Ġmoderately': 32611,\n",
       " 'ĠUsage': 29566,\n",
       " 'Ġsued': 16334,\n",
       " 'ĠOrigin': 19349,\n",
       " 'mund': 20125,\n",
       " 'Ġadhere': 26325,\n",
       " 'ĠPosted': 12918,\n",
       " 'Ġorig': 1796,\n",
       " 'Found': 21077,\n",
       " 'Ġconducive': 45645,\n",
       " 'Peter': 19727,\n",
       " 'Ġecho': 9809,\n",
       " 'ĠFour': 6675,\n",
       " 'anything': 49459,\n",
       " 'enses': 4541,\n",
       " 'ĠGundam': 32467,\n",
       " 'ĠArizona': 7943,\n",
       " 'Ġresisted': 26643,\n",
       " 'ashtra': 38535,\n",
       " 'ynski': 40008,\n",
       " 'ĠAIR': 31600,\n",
       " 'Ġsponsored': 15901,\n",
       " 'igion': 17035,\n",
       " 'ĠIllum': 39256,\n",
       " 'Director': 28702,\n",
       " 'ĠLastly': 36778,\n",
       " 'ĠPra': 21127,\n",
       " 'Ġpartners': 4887,\n",
       " 'Ġinsomnia': 47104,\n",
       " 'ĠAzure': 22134,\n",
       " 'count': 9127,\n",
       " 'omics': 31994,\n",
       " 'lost': 33224,\n",
       " 'cles': 5427,\n",
       " 'rador': 40368,\n",
       " 'Ġannually': 13844,\n",
       " 'Ġuninstall': 43194,\n",
       " 'Ġfare': 14505,\n",
       " 'ĠKnife': 32287,\n",
       " 'Ġclues': 20195,\n",
       " 'Ġshone': 44193,\n",
       " 'Ġtrainers': 28514,\n",
       " 'ĠLabor': 7882,\n",
       " 'ael': 3010,\n",
       " 'ilateral': 14796,\n",
       " 'inside': 48787,\n",
       " 'lessness': 17587,\n",
       " 'neg': 12480,\n",
       " '/$': 32624,\n",
       " 'okingly': 48343,\n",
       " 'ĠBlue': 4518,\n",
       " 'UCK': 16696,\n",
       " 'Ġcollaborator': 50160,\n",
       " 'Ġcounties': 14683,\n",
       " 'Ġliqu': 14756,\n",
       " 'Ġmansion': 24141,\n",
       " 'Ġdraped': 38425,\n",
       " 'donald': 40915,\n",
       " 'Ġstrengthens': 49286,\n",
       " 'Going': 27404,\n",
       " 'Ġonlook': 47747,\n",
       " 'ĠLoan': 32314,\n",
       " 'Ġ188': 27778,\n",
       " 'Ġthorough': 9321,\n",
       " 'warm': 31975,\n",
       " 'apolis': 11174,\n",
       " 'ength': 3286,\n",
       " 'ĠTuls': 33219,\n",
       " 'Ġsten': 45219,\n",
       " 'aniel': 6321,\n",
       " 'essed': 6676,\n",
       " 'ĠVietnamese': 23618,\n",
       " 'ĠCame': 32653,\n",
       " 'Ġconceptions': 49849,\n",
       " 'Ġnumb': 35519,\n",
       " 'HTTP': 40717,\n",
       " 'ĠDuterte': 25763,\n",
       " 'ĠHick': 42441,\n",
       " 'ĠRM': 29820,\n",
       " 'Job': 33308,\n",
       " 'Ġpatched': 39378,\n",
       " 'Ġsocialism': 19803,\n",
       " 'o': 78,\n",
       " 'Ġ332': 41423,\n",
       " 'Ġstimulated': 40216,\n",
       " 'Ġkidney': 21919,\n",
       " '];': 11208,\n",
       " 'Ġopio': 18356,\n",
       " 'ĠTire': 45942,\n",
       " 'ĠCorpor': 8422,\n",
       " 'ĠIts': 6363,\n",
       " 'ĠWah': 35893,\n",
       " 'ĠTavern': 32693,\n",
       " 'RS': 6998,\n",
       " 'Ġmodesty': 48740,\n",
       " 'Ġactivated': 13906,\n",
       " 'Ġbecame': 2627,\n",
       " 'Ġâĸł': 34252,\n",
       " 'Ġparks': 14860,\n",
       " 'Ġsuggestive': 42789,\n",
       " '================': 4770,\n",
       " 'pose': 3455,\n",
       " 'ĠDiseases': 39988,\n",
       " 'Thu': 39902,\n",
       " 'sburgh': 11931,\n",
       " 'ĠDoc': 14432,\n",
       " 'Ġfarmland': 45723,\n",
       " 'city': 19205,\n",
       " 'Ġshelter': 11772,\n",
       " 'Ġmelanch': 40853,\n",
       " 'ĠMargaret': 19579,\n",
       " 'ĠVG': 34627,\n",
       " 'Ġfunction': 2163,\n",
       " 'igure': 7047,\n",
       " 'ĠCreat': 7921,\n",
       " 'bright': 29199,\n",
       " 'lar': 21681,\n",
       " 'roup': 3233,\n",
       " 'ĠInstead': 5455,\n",
       " '257': 28676,\n",
       " 'ĠTycoon': 28222,\n",
       " 'ĠZip': 38636,\n",
       " 'Ġcontagious': 43944,\n",
       " 'ĠMohammad': 29674,\n",
       " 'Ġdecipher': 42790,\n",
       " 'Ġplanned': 6027,\n",
       " 'ĠAnarch': 32229,\n",
       " 'han': 7637,\n",
       " 'ĠCarey': 31612,\n",
       " 'ĠMLA': 43265,\n",
       " 'Ġdemise': 25403,\n",
       " 'Ġpretext': 35097,\n",
       " 'Ġslice': 16416,\n",
       " 'Ġvaluable': 8119,\n",
       " 'reve': 36955,\n",
       " 'Ġ377': 42163,\n",
       " 'key': 2539,\n",
       " 'Ġinfluential': 14212,\n",
       " 'Ġshuff': 32299,\n",
       " 'Look': 8567,\n",
       " 'report': 13116,\n",
       " 'Ġarticulated': 36877,\n",
       " 'Ġgasped': 45236,\n",
       " 'Ġmoaning': 47644,\n",
       " 'onents': 3906,\n",
       " 'etically': 16877,\n",
       " 'ĠLucifer': 27084,\n",
       " 'Ġdog': 3290,\n",
       " 'Ġcounteract': 47578,\n",
       " 'card': 9517,\n",
       " 'ĠStrait': 41407,\n",
       " 'Ġhistorian': 18026,\n",
       " 'Ġmathemat': 11896,\n",
       " 'Ġchronic': 10726,\n",
       " 'Ġpack': 2353,\n",
       " 'ĠCoast': 8545,\n",
       " 'ĠRih': 44502,\n",
       " 'Ġhysteria': 38893,\n",
       " 'ĠSolidGoldMagikarp': 43453,\n",
       " 'Ġmembership': 9931,\n",
       " 'sim': 14323,\n",
       " 'Ġirrespective': 40611,\n",
       " 'Ġretired': 9880,\n",
       " 'oother': 31724,\n",
       " 'Ġexpenditures': 22895,\n",
       " 'Ġoptimizations': 41446,\n",
       " 'ĠPry': 32500,\n",
       " 'iasis': 48455,\n",
       " 'found': 9275,\n",
       " 'Ġfollowed': 3940,\n",
       " 'endra': 48286,\n",
       " 'Ġace': 31506,\n",
       " 'ĠAnn': 5506,\n",
       " 'ENDED': 49361,\n",
       " 'Ġaffairs': 9674,\n",
       " 'Ġdictatorship': 26457,\n",
       " 'margin': 36153,\n",
       " 'ASHINGTON': 19436,\n",
       " 'Disc': 15642,\n",
       " 'emn': 37705,\n",
       " 'Ëľ': 41185,\n",
       " 'ĠSic': 28799,\n",
       " 'Ġcommitted': 5364,\n",
       " 'Ġemployees': 4409,\n",
       " 'en': 268,\n",
       " 'ÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤÃĥÃĤ': 35496,\n",
       " 'Interest': 19302,\n",
       " 'uter': 11894,\n",
       " 'ĠGaz': 21347,\n",
       " 'Ġaccount': 1848,\n",
       " 'inois': 8981,\n",
       " 'Ġburned': 11544,\n",
       " 'aces': 2114,\n",
       " 'Ġexploding': 30990,\n",
       " 'Ġfo': 11511,\n",
       " 'Ġglut': 25276,\n",
       " 'YD': 35755,\n",
       " 'Ġinsofar': 44061,\n",
       " 'Moving': 33622,\n",
       " 'ĠAlliance': 10302,\n",
       " 'ĠWeekend': 30537,\n",
       " 'opt': 8738,\n",
       " 'Ġfumes': 47301,\n",
       " 'Ġlingu': 20280,\n",
       " 'Ġmail': 6920,\n",
       " 'Ġpolitic': 31723,\n",
       " 'Ġnoteworthy': 30902,\n",
       " 'ĠEverett': 36815,\n",
       " 'Ġstd': 14367,\n",
       " 'Ġintroduce': 10400,\n",
       " 'Ġheight': 6001,\n",
       " 'Ġdeclaration': 14305,\n",
       " 'Ł': 253,\n",
       " 'Ġjewels': 42701,\n",
       " 'Ġhockey': 12217,\n",
       " '#$': 29953,\n",
       " 'Ġwall': 3355,\n",
       " 'ĠErnst': 38129,\n",
       " 'Ġpot': 1787,\n",
       " 'ĠNevada': 12087,\n",
       " 'ĠNic': 8377,\n",
       " 'gh': 456,\n",
       " 'ĠOo': 45801,\n",
       " 'ĠPLEASE': 37795,\n",
       " 'ĠPTS': 20907,\n",
       " 'ĠVir': 16310,\n",
       " 'Ġplainly': 30723,\n",
       " \"'d\": 1549,\n",
       " 'GD': 45113,\n",
       " 'untary': 26468,\n",
       " 'ĠOperating': 24850,\n",
       " 'contract': 28484,\n",
       " 'ĠBarnes': 21335,\n",
       " 'ruly': 34715,\n",
       " '=#': 46249,\n",
       " 'Ġextraordinary': 11359,\n",
       " 'Solar': 38825,\n",
       " 'hu': 13415,\n",
       " 'Ġaesthetics': 35431,\n",
       " 'Ġslamming': 39603,\n",
       " 'odo': 24313,\n",
       " 'ĠFac': 13585,\n",
       " 'ĠKorean': 6983,\n",
       " 'compl': 23855,\n",
       " 'ĠChecks': 47719,\n",
       " 'ĠPentagon': 12651,\n",
       " 'ĠRecover': 49107,\n",
       " 'Ġclipping': 45013,\n",
       " 'angler': 49910,\n",
       " ':-': 21912,\n",
       " 'Ġrg': 48670,\n",
       " 'cycles': 32503,\n",
       " '464': 44578,\n",
       " 'Canada': 17940,\n",
       " 'Ġcoupons': 45972,\n",
       " 'hair': 27108,\n",
       " \"?'\": 8348,\n",
       " 'powered': 12293,\n",
       " 'ĠAvalon': 39600,\n",
       " 'iscovery': 40821,\n",
       " 'ĠInnovation': 27724,\n",
       " 'Users': 14490,\n",
       " 'ĠPerth': 29913,\n",
       " 'Ġeager': 11069,\n",
       " 'elman': 32370,\n",
       " 'ĠEarly': 12556,\n",
       " 'ochond': 22400,\n",
       " 'Ġfiltered': 29083,\n",
       " 'Ġjab': 33896,\n",
       " 'Ġlimb': 25035,\n",
       " 'Ġsal': 3664,\n",
       " 'Ġswap': 16075,\n",
       " 'ĠVentura': 43204,\n",
       " 'Ġrefund': 12929,\n",
       " 'Much': 20045,\n",
       " 'figured': 46296,\n",
       " 'sv': 21370,\n",
       " 'Ġchecked': 10667,\n",
       " 'Ġcloser': 5699,\n",
       " 'Ġevening': 6180,\n",
       " 'ĠBeer': 16971,\n",
       " 'ĠAssembly': 10006,\n",
       " 'Ġexplore': 7301,\n",
       " '?\".': 43634,\n",
       " 'ĠAristotle': 34067,\n",
       " 'Ġcommenting': 26387,\n",
       " 'ĠOT': 21676,\n",
       " 'Ġabilities': 7883,\n",
       " 'Han': 29919,\n",
       " 'ĠKT': 42293,\n",
       " 'ĠESC': 40251,\n",
       " 'pri': 3448,\n",
       " 'ĠApex': 49440,\n",
       " 'loe': 24617,\n",
       " 'ĠFaust': 47411,\n",
       " 'Ġdun': 12574,\n",
       " 'Ġfilling': 12591,\n",
       " 'Ġfragmented': 41630,\n",
       " 'illes': 21718,\n",
       " 'Ġhalt': 17369,\n",
       " 'abwe': 27050,\n",
       " 'Any': 7149,\n",
       " 'ãĥĺãĥ©': 34473,\n",
       " 'ĠBesides': 16238,\n",
       " 'ĠPassive': 31652,\n",
       " 'ĠRoh': 32694,\n",
       " 'Ġimg': 33705,\n",
       " 'Ġinvoke': 26342,\n",
       " 'Ġresonate': 41523,\n",
       " 'ĠXI': 30554,\n",
       " 'Ġrestore': 11169,\n",
       " 'Ġoptimal': 16586,\n",
       " 'Ġshareholders': 19195,\n",
       " 'Ġtal': 3305,\n",
       " 'Ġtriglycer': 47937,\n",
       " 'meal': 28208,\n",
       " '359': 30743,\n",
       " 'enei': 46009,\n",
       " 'ĠAshe': 36318,\n",
       " 'Ġpower': 1176,\n",
       " 'Ġshameless': 41564,\n",
       " 'zag': 50183,\n",
       " 'Ġaggrav': 20072,\n",
       " 'Ġdisg': 13757,\n",
       " 'Ġmore': 517,\n",
       " 'Ġrejects': 28317,\n",
       " 'snap': 45380,\n",
       " 'Ġjunction': 35037,\n",
       " 'Ġrooting': 40105,\n",
       " 'mic': 9383,\n",
       " 'chen': 6607,\n",
       " 'Ġguessing': 25260,\n",
       " 'Ġvideog': 36342,\n",
       " 'Ġvolunteers': 11661,\n",
       " 'known': 4002,\n",
       " 'Ġwhichever': 26204,\n",
       " 'ġ': 221,\n",
       " '806': 37988,\n",
       " 'Ġintrusion': 34396,\n",
       " 'ĠLegions': 48534,\n",
       " 'medical': 41693,\n",
       " 'ĠMozilla': 29258,\n",
       " 'Ġpreached': 38737,\n",
       " 'Ġpsych': 3795,\n",
       " 'Ġmaintains': 16047,\n",
       " 'oddy': 38553,\n",
       " 'Ġbir': 35122,\n",
       " 'shots': 20910,\n",
       " 'Ġrunway': 23443,\n",
       " 'Ġopioid': 23039,\n",
       " 'rill': 20190,\n",
       " 'ĠJoe': 5689,\n",
       " 'ĠCalcul': 27131,\n",
       " 'Ġstakes': 21147,\n",
       " 'Such': 16678,\n",
       " 'iance': 3610,\n",
       " 'Ġillegally': 15572,\n",
       " 'Ġwaits': 28364,\n",
       " 'guards': 33427,\n",
       " 'illegal': 47749,\n",
       " '->': 3784,\n",
       " 'livious': 35260,\n",
       " 'Ġworrisome': 48367,\n",
       " 'Ġtransports': 45245,\n",
       " 'ĠLondon': 3576,\n",
       " 'arus': 20272,\n",
       " 'arat': 34174,\n",
       " 'Ġwarships': 44304,\n",
       " 'TX': 29551,\n",
       " 'cms': 46406,\n",
       " 'ners': 2741,\n",
       " 'ĠCyrus': 34305,\n",
       " 'ĠOrleans': 12255,\n",
       " 'ojure': 32511,\n",
       " 'Ġinev': 9026,\n",
       " 'Ġscraps': 44496,\n",
       " 'Ń·': 48953,\n",
       " 'atile': 12610,\n",
       " 'Ġinflic': 30333,\n",
       " 'Ġkan': 43998,\n",
       " 'Ġincidentally': 42258,\n",
       " 'onto': 5957,\n",
       " 'Ġtyrant': 47167,\n",
       " 'ĠMalta': 35206,\n",
       " 'Ġautopsy': 30241,\n",
       " '005': 22544,\n",
       " 'opic': 16603,\n",
       " 'utterstock': 28819,\n",
       " 'ĠExamination': 50105,\n",
       " 'ĠGreenland': 30155,\n",
       " 'Ġincarcer': 18615,\n",
       " '////////////////': 27246,\n",
       " 'astery': 29310,\n",
       " 'itles': 30540,\n",
       " 'mbudsman': 47012,\n",
       " '1945': 41931,\n",
       " 'IRC': 49060,\n",
       " 'ĠDragonbound': 17900,\n",
       " 'ĠIsland': 5451,\n",
       " 'âĢĵ': 1906,\n",
       " 'ĠLC': 22228,\n",
       " 'node': 17440,\n",
       " 'ĠDimensions': 41265,\n",
       " 'Bob': 18861,\n",
       " 'ĠTra': 4759,\n",
       " 'ĠBaby': 14801,\n",
       " 'ĠBond': 12812,\n",
       " 'group': 8094,\n",
       " 'ĠPats': 47216,\n",
       " 'Ġchiefly': 36305,\n",
       " 'Ġcrane': 41175,\n",
       " 'Ġparade': 16134,\n",
       " 'fall': 7207,\n",
       " '273': 27367,\n",
       " 'parable': 37064,\n",
       " 'peed': 39492,\n",
       " 'Ġoutcome': 8055,\n",
       " 'Ġrepeats': 29819,\n",
       " 'Channel': 29239,\n",
       " 'rs': 3808,\n",
       " 'leck': 40667,\n",
       " 'ĠPis': 42021,\n",
       " 'ĠWA': 16400,\n",
       " 'ĠTrop': 25491,\n",
       " 'Ġneutron': 49810,\n",
       " 'Ġseeker': 45993,\n",
       " 'Ġargs': 26498,\n",
       " 'father': 11358,\n",
       " 'atar': 9459,\n",
       " 'Ġ3000': 20343,\n",
       " 'ĠKeyboard': 31973,\n",
       " 'ĠMississippi': 13797,\n",
       " '<<': 16791,\n",
       " 'Ġstainless': 25704,\n",
       " 'otle': 23556,\n",
       " 'Ġsubstantial': 8904,\n",
       " 'Ġtotaled': 39398,\n",
       " 'afia': 22214,\n",
       " 'clude': 9152,\n",
       " 'Ġfoam': 19828,\n",
       " 'ĠXu': 33591,\n",
       " 'ĠBhar': 33653,\n",
       " 'ãĤ¤ãĥĪ': 42396,\n",
       " 'Ġpledge': 13995,\n",
       " 'Ġcod': 14873,\n",
       " 'Ġcontinuity': 24216,\n",
       " 'ĠCato': 44509,\n",
       " 'Ġtuna': 38883,\n",
       " 'steen': 42580,\n",
       " 'Ġguided': 17455,\n",
       " 'ths': 9998,\n",
       " 'Ġstarve': 47141,\n",
       " 'hearted': 20122,\n",
       " 'ĠScriptures': 41622,\n",
       " 'Ġcomputing': 14492,\n",
       " 'Ġasteroid': 27460,\n",
       " 'Ġconspir': 29099,\n",
       " ...}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 查看词汇表\n",
    "tokenizer.vocab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d8be0bd1-c9c0-4cb2-92fa-0b8c5d230d0d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Token ID for 'world': 6894\n",
      "Token for ID 995: Ġworld\n"
     ]
    }
   ],
   "source": [
    "# 查看特定 Token 的 ID\n",
    "token_id = tokenizer.convert_tokens_to_ids('world')\n",
    "print(\"Token ID for 'world':\", token_id)\n",
    "\n",
    "# 查看特定 ID 对应的 Token\n",
    "token = tokenizer.convert_ids_to_tokens(995)\n",
    "print(\"Token for ID 995:\", token)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b2c3d36-3ac7-40ef-a8f7-48277b066825",
   "metadata": {},
   "source": [
    "> 这里的 `Ġ` 代表一个空格字符：\n",
    ">\n",
    "> ```python\n",
    "> print(tokenizer.tokenize(' '))\n",
    "> ```\n",
    ">\n",
    "> 输出为 `['Ġ']`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "26fc1035-abf5-46de-923a-e082863b55c4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All Special Tokens: ['<|endoftext|>']\n",
      "Special Token IDs: [50256]\n"
     ]
    }
   ],
   "source": [
    "# 查看所有特殊标记\n",
    "special_tokens = tokenizer.all_special_tokens\n",
    "print(\"All Special Tokens:\", special_tokens)\n",
    "\n",
    "# 查看特殊标记对应的 ID\n",
    "special_token_ids = tokenizer.all_special_ids\n",
    "print(\"Special Token IDs:\", special_token_ids)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c56c39bd-fd98-46c4-9da7-06f08f327125",
   "metadata": {},
   "source": [
    "**「接下来，我们将探讨 Tokenizer 的具体细节」**\n",
    "\n",
    "> 不需要深入接下来的所有代码细节，只需要查看输出与相应「步骤」的表述。\n",
    "\n",
    "## 分词（Tokenize）\n",
    "\n",
    "我们需要将语料库（corpus）的文本拆分为单词，假设当前语料库包含的单词和对应频次如下：\n",
    "\n",
    "```sql\n",
    "(\"low\", 5), (\"lower\", 2), (\"newest\", 6), (\"widest\", 3)\n",
    "```\n",
    "\n",
    "有些论文也用 `vocab` 来表述，知道后面是频次即可，命名不用纠结。\n",
    "\n",
    "### 构造词汇表\n",
    "\n",
    "#### Byte-Pair Encoding (BPE)\n",
    "\n",
    "> **参考文献：**\n",
    ">\n",
    "> - [A new algorithm for data compression. 1994](http://www.pennelynn.com/Documents/CUJ/HTML/94HTML/19940045.HTM)\n",
    "> - [Neural Machine Translation of Rare Words with Subword Units. 2015](https://arxiv.org/pdf/1508.07909v5)\n",
    ">\n",
    "> BPE 是一种基于数据压缩的技术，最早由 Gage 在 1994 年提出，后来被用于 GPT 等模型。它是一种子词分割算法，从字符级别开始，通过迭代合并频率最高的字符对（或字符序列）来构建新的 Token，从而可以处理部分 OOV（Out-Of-Vocabulary）情况。\n",
    ">\n",
    "> **Q: 什么是 OOV ？**\n",
    ">\n",
    "> 其实就是不在词汇表中的词，也称之为「未登录词」。\n",
    "\n",
    "BPE 每次的迭代目标是找到频率最高的相邻字符对，定义 Score 以与 WordPiece 作对比：\n",
    "\n",
    "$$\n",
    "\\text{Score}_{\\text{BPE}}(x, y) = \\text{freq}(x, y)\n",
    "$$\n",
    "其中，$\\text{freq}(x, y)$ 表示字符对 $(x, y)$ 在语料库中的出现频次。\n",
    "\n",
    "##### 步骤\n",
    "\n",
    "1. **初始化词汇表 $V$**：\n",
    "   - $V$ 包含语料库中的所有唯一字符，即单词字符的集合。\n",
    "2. **统计字符对的频次**：\n",
    "   - 对于每个单词的字符序列，统计相邻字符对的出现频次。\n",
    "3. **找到频次（Score）最高的字符对并合并**：\n",
    "   - 选择出现频率最高的字符对 $(x, y)$，将其合并为新符号 $xy$。\n",
    "4. **更新词汇表并重复步骤 2 到 4**：\n",
    "   - 将新符号添加到词汇表 $V = V \\cup \\{xy\\}$。\n",
    "   - 更新语料库中的单词表示，重复统计和合并过程，直到满足停止条件（例如，词汇表达到预定大小）。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccc09234-cef2-4898-8260-3ce47e0b2d50",
   "metadata": {},
   "source": [
    "##### 示例\n",
    "\n",
    "**步骤 1：初始化词汇表**\n",
    "\n",
    "- **将单词拆分为字符序列**：\n",
    "\n",
    "  ```plaintext\n",
    "  (\"l\", \"o\", \"w\"), 5  \n",
    "  (\"l\", \"o\", \"w\", \"e\", \"r\"), 2  \n",
    "  (\"n\", \"e\", \"w\", \"e\", \"s\", \"t\"), 6  \n",
    "  (\"w\", \"i\", \"d\", \"e\", \"s\", \"t\"), 3\n",
    "  ```\n",
    "\n",
    "- **词汇表 $V$**：\n",
    "\n",
    "  ```plaintext\n",
    "  {'l', 'o', 'w', 'e', 'r', 'n', 's', 't', 'i', 'd'}\n",
    "  ```\n",
    "\n",
    "**步骤 2：统计字符对的频次**\n",
    "\n",
    "编写一个函数，根据给定的单词和其频次，自动统计字符对的频次。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "39dfe4fe-c1fd-4c54-aa9b-3b21810b109b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "字符对频次统计结果:\n",
      "('l', 'o'): 7\n",
      "('o', 'w'): 7\n",
      "('w', 'e'): 8\n",
      "('e', 'r'): 2\n",
      "('n', 'e'): 6\n",
      "('e', 'w'): 6\n",
      "('e', 's'): 9\n",
      "('s', 't'): 9\n",
      "('w', 'i'): 3\n",
      "('i', 'd'): 3\n",
      "('d', 'e'): 3\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def count_char_pairs(word_freq):\n",
    "    \"\"\"\n",
    "    计算字符对的频次。\n",
    "    \n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词和其频次\n",
    "        \n",
    "    返回：\n",
    "        字符对频次的字典\n",
    "    \"\"\"\n",
    "    pair_freq = defaultdict(int)\n",
    "    for word, freq in word_freq:\n",
    "        chars = list(word)\n",
    "        for i in range(len(chars) - 1):\n",
    "            pair = (chars[i], chars[i + 1])\n",
    "            pair_freq[pair] += freq\n",
    "    return pair_freq\n",
    "\n",
    "# 示例词汇表和单词频次\n",
    "word_freq = [\n",
    "    (\"low\", 5),\n",
    "    (\"lower\", 2),\n",
    "    (\"newest\", 6),\n",
    "    (\"widest\", 3)\n",
    "]\n",
    "\n",
    "pair_freq = count_char_pairs(word_freq)\n",
    "print(\"字符对频次统计结果:\")\n",
    "for pair, freq in pair_freq.items():\n",
    "    print(f\"{pair}: {freq}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c237d666-d360-44b3-95d8-54b56884cb5d",
   "metadata": {},
   "source": [
    "**步骤 3：找到频次最高的字符对并合并**\n",
    "\n",
    "- **选择频次最高的字符对**：\n",
    "\n",
    "  - `(\"e\", \"s\")` 和 `(\"s\", \"t\")`，频次均为 9。可以任选其一进行合并，假设选择排序第一的： `(\"e\", \"s\")`。\n",
    "\n",
    "- **合并 `(\"e\", \"s\")` 为新符号 `es`**。\n",
    "\n",
    "- **记录合并操作**：\n",
    "\n",
    "  ```plaintext\n",
    "  Merge 1: (\"e\", \"s\") -> \"es\"\n",
    "  ```\n",
    "\n",
    "**步骤 4：更新词汇表并重复**\n",
    "\n",
    "- **更新单词序列**：\n",
    "\n",
    "  ```plaintext\n",
    "  (\"l\", \"o\", \"w\"), 5  \n",
    "  (\"l\", \"o\", \"w\", \"e\", \"r\"), 2  \n",
    "  (\"n\", \"e\", \"w\", \"es\", \"t\"), 6  \n",
    "  (\"w\", \"i\", \"d\", \"es\", \"t\"), 3\n",
    "  ```\n",
    "\n",
    "- **更新词汇表 $V$**：\n",
    "\n",
    "  ```plaintext\n",
    "  {'l', 'o', 'w', 'e', 'r', 'n', 's', 't', 'i', 'd', 'es'}\n",
    "  ```\n",
    "\n",
    "- **重复步骤 2 到 4，直到达到预定的词汇表大小**。\n",
    "\n",
    "> ##### 📝 练习题\n",
    ">\n",
    "> 停下来思考一下，答案和代码位于当前模块末尾。\n",
    ">\n",
    "> **Q1.** 最初的词汇表大小为 10，假设预定大小为 13，那么当前的词汇表 $V$ 为多少？合并记录是什么？\n",
    ">\n",
    "> **Q2.** 如果以 `</w>`（表示单词结尾）作为每个语料库中单词的结尾，最初的词汇表会受到什么影响，后续的过程会如何变化？假设预定大小为 14，当前的合并记录是什么？"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fe352af-0f8f-4848-a8dd-b10136fbe205",
   "metadata": {},
   "source": [
    "#### WordPiece\n",
    "\n",
    "> **参考文献：**\n",
    ">\n",
    "> - [Japanese and Korean voice search. 2012](https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/37842.pdf)\n",
    "> - [Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation. 2016](https://arxiv.org/pdf/1609.08144v2)\n",
    ">\n",
    "> WordPiece 是一种子词分割算法，最初用于处理日语和韩语的语音搜索，后来在 Google 的神经机器翻译系统中得到应用。\n",
    "\n",
    "与 BPE 不同，WordPiece 的 Score 由字符对频次与其组成部分频次的比值决定，定义 Score：\n",
    "\n",
    "$$\n",
    "\\text{Score}_{\\text{WordPiece}}(x, y) = \\frac{\\text{freq}(xy)}{\\text{freq}(x) \\times \\text{freq}(y)}\n",
    "$$\n",
    "\n",
    "其中，$\\text{freq}(x)$、$\\text{freq}(y)$ 和 $\\text{freq}(xy)$ 分别表示符号 $x$、$y$ 和它们合并后的符号 $xy$ 的频次。\n",
    "\n",
    "##### 步骤\n",
    "\n",
    "1. **初始化词汇表 $V$**：\n",
    "   - 与 BPE 相同，$V$ 包含语料库中的所有唯一字符，但处理方式略有不同：对于每个单词，除了首个字符外，其他字符前都加上 `##` 前缀。\n",
    "2. **统计字符对的频次及 Score**：\n",
    "   - 对于每个可能的字符对 $(x, y)$，计算 $\\text{freq}(x)$、$\\text{freq}(y)$、$\\text{freq}(xy)$，并计算 Score。\n",
    "3. **找到 Score 最高的字符对并合并**：\n",
    "   - 选择 Score 最高的字符对 $(x, y)$，将其合并为新符号 $xy$，注意：\n",
    "     - 如果第二个符号以 `##` 开头，合并时去掉 `##` 前缀再进行连接。\n",
    "     - 新符号是否以 `##` 开头，取决于第一个符号是否以 `##` 开头。\n",
    "4. **更新词汇表并重复步骤 2 到 4**：\n",
    "   - 将新符号添加到词汇表 $V = V \\cup \\{xy\\}$。\n",
    "   - 更新语料库中的单词表示，重复统计和合并过程，直到满足停止条件。\n",
    "\n",
    "##### 示例\n",
    "\n",
    "使用与 BPE 示例相同的语料库。\n",
    "\n",
    "**步骤 1：初始化词汇表**\n",
    "\n",
    "- **将单词拆分为字符序列**：\n",
    "\n",
    "  ```plaintext\n",
    "  ('l', '##o', '##w'), 5                       # \"low\"\n",
    "  ('l', '##o', '##w', '##e', '##r'), 2         # \"lower\"\n",
    "  ('n', '##e', '##w', '##e', '##s', '##t'), 6  # \"newest\"\n",
    "  ('w', '##i', '##d', '##e', '##s', '##t'), 3  # \"widest\"\n",
    "  ```\n",
    "\n",
    "- **词汇表 $V$**：\n",
    "\n",
    "  ```plaintext\n",
    "  {'l', '##o', '##w', '##e', '##r', 'n', '##s', '##t', 'w', '##i', '##d'}\n",
    "  ```\n",
    "\n",
    "**步骤 2：统计字符和字符对的频次，计算 Score**\n",
    "\n",
    "可以设计一个函数完成这个步骤（直接运行查看输出）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "5910b8ee-7091-4cd6-803a-73802b7e5d85",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "字符对频次统计结果:\n",
      "('l', '##o'): 7\n",
      "('##o', '##w'): 7\n",
      "('##w', '##e'): 8\n",
      "('##e', '##r'): 2\n",
      "('n', '##e'): 6\n",
      "('##e', '##w'): 6\n",
      "('##e', '##s'): 9\n",
      "('##s', '##t'): 9\n",
      "('w', '##i'): 3\n",
      "('##i', '##d'): 3\n",
      "('##d', '##e'): 3\n",
      "\n",
      "单个字符频次统计结果:\n",
      "l: 7\n",
      "##o: 7\n",
      "##w: 13\n",
      "##e: 17\n",
      "##r: 2\n",
      "n: 6\n",
      "##s: 9\n",
      "##t: 9\n",
      "w: 3\n",
      "##i: 3\n",
      "##d: 3\n",
      "\n",
      "字符对 Score 计算结果:\n",
      "('l', '##o'): 0.1429\n",
      "('##o', '##w'): 0.0769\n",
      "('##w', '##e'): 0.0362\n",
      "('##e', '##r'): 0.0588\n",
      "('n', '##e'): 0.0588\n",
      "('##e', '##w'): 0.0271\n",
      "('##e', '##s'): 0.0588\n",
      "('##s', '##t'): 0.1111\n",
      "('w', '##i'): 0.3333\n",
      "('##i', '##d'): 0.3333\n",
      "('##d', '##e'): 0.0588\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def count_char_pairs_wordpiece(word_freq):\n",
    "    \"\"\"\n",
    "    计算字符对的频次和单个字符的频次。\n",
    "    \n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词（列表形式）和其频次\n",
    "        \n",
    "    返回：\n",
    "        两个字典，分别为字符对频次和单个字符频次\n",
    "    \"\"\"\n",
    "    pair_freq = defaultdict(int)\n",
    "    char_freq = defaultdict(int)\n",
    "    for word, freq in word_freq:\n",
    "        for i in range(len(word)):\n",
    "            char_freq[word[i]] += freq\n",
    "            if i < len(word) - 1:\n",
    "                pair = (word[i], word[i + 1])\n",
    "                pair_freq[pair] += freq\n",
    "    return pair_freq, char_freq\n",
    "\n",
    "def compute_wordpiece_score(freq_xy, freq_x, freq_y):\n",
    "    \"\"\"\n",
    "    根据 WordPiece 的定义计算 Score。\n",
    "    \n",
    "    参数：\n",
    "        freq_xy: 符号对的频次\n",
    "        freq_x: 符号 x 的频次\n",
    "        freq_y: 符号 y 的频次\n",
    "        \n",
    "    返回：\n",
    "        计算得到的 Score\n",
    "    \"\"\"\n",
    "    if freq_x == 0 or freq_y == 0:\n",
    "        return 0\n",
    "    return freq_xy / (freq_x * freq_y)\n",
    "\n",
    "# 示例词汇表和单词频次\n",
    "word_freq = [\n",
    "    (['l', '##o', '##w'], 5),\n",
    "    (['l', '##o', '##w', '##e', '##r'], 2),\n",
    "    (['n', '##e', '##w', '##e', '##s', '##t'], 6),\n",
    "    (['w', '##i', '##d', '##e', '##s', '##t'], 3)\n",
    "]\n",
    "\n",
    "# 统计字符对频次和单个字符频次\n",
    "pair_freq, char_freq = count_char_pairs_wordpiece(word_freq)\n",
    "\n",
    "# 计算每对字符的 Score\n",
    "scores = {}\n",
    "for pair in pair_freq:\n",
    "    freq_xy = pair_freq[pair]\n",
    "    freq_x = char_freq[pair[0]]\n",
    "    freq_y = char_freq[pair[1]]\n",
    "    score = compute_wordpiece_score(freq_xy, freq_x, freq_y)\n",
    "    scores[pair] = score\n",
    "\n",
    "# 输出结果\n",
    "print(\"字符对频次统计结果:\")\n",
    "for pair, freq in pair_freq.items():\n",
    "    print(f\"{pair}: {freq}\")\n",
    "\n",
    "print(\"\\n单个字符频次统计结果:\")\n",
    "for char, freq in char_freq.items():\n",
    "    print(f\"{char}: {freq}\")\n",
    "\n",
    "print(\"\\n字符对 Score 计算结果:\")\n",
    "for pair, score in scores.items():\n",
    "    print(f\"{pair}: {score:.4f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8204f92b-08d1-42b5-a3b1-1b38a2fa2a3f",
   "metadata": {},
   "source": [
    "- **选择频次最高的字符对**：\n",
    "\n",
    "  -  `('w', '##i')` 和 `('##i', '##d')`，Score 都为 0.3333。可以任选其一进行合并，假设选择排序第一的： `(\"w\", \"##i\")`。\n",
    "\n",
    "- **合并 `('w', '##i')` 为新符号 `wi`**\n",
    "\n",
    "  - 注意：合并时，若第二个符号以 `##` 开头，合并后的新符号为第一个符号加上第二个符号去掉 `##` 前缀的部分。\n",
    "\n",
    "- **记录合并操作：**\n",
    "\n",
    "  ```plaintext\n",
    "  Merge 1: ('w', '##i') -> 'wi'\n",
    "  ```\n",
    "\n",
    "**步骤 4：更新词汇表并重复**\n",
    "\n",
    "- **更新词汇表 $V$**：\n",
    "\n",
    "  ```plaintext\n",
    "  {'l', '##o', '##w', '##e', '##r', 'n', '##s', '##t', 'w', '##i', '##d', 'wi'}\n",
    "  ```\n",
    "\n",
    "- **更新单词序列**：\n",
    "\n",
    "  ```plaintext\n",
    "  ('l', '##o', '##w'), 5                       # \"low\"\n",
    "  ('l', '##o', '##w', '##e', '##r'), 2         # \"lower\"\n",
    "  ('n', '##e', '##w', '##e', '##s', '##t'), 6  # \"newest\"\n",
    "  ('wi', '##d', '##e', '##s', '##t'), 3        # \"widest\"\n",
    "  ```\n",
    "\n",
    "- **重复步骤 2 到 4，直到达到预定的词汇表大小**。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c125f661-a493-405f-8c2e-cee84129afbe",
   "metadata": {},
   "source": [
    "##### 使用函数实现简单的 WordPiece\n",
    "\n",
    "BPE 的实现在「练习题答案」中。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "90b5a44a-72b1-46f5-997e-b497940186fe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Merge: ('w', '##i') -> wi, Score: 0.3333, 词汇表大小: 12\n",
      "Merge: ('wi', '##d') -> wid, Score: 0.3333, 词汇表大小: 13\n",
      "Merge: ('l', '##o') -> lo, Score: 0.1429, 词汇表大小: 14\n",
      "Merge: ('##s', '##t') -> ##st, Score: 0.1111, 词汇表大小: 15\n",
      "\n",
      "最终词汇表 V:\n",
      "{'n', '##w', '##s', '##e', '##t', 'lo', 'wid', '##r', '##i', 'wi', 'w', '##o', '##d', 'l', '##st'}\n",
      "\n",
      "合并记录:\n",
      "Merge 1: ('w', '##i') -> wi\n",
      "Merge 2: ('wi', '##d') -> wid\n",
      "Merge 3: ('l', '##o') -> lo\n",
      "Merge 4: ('##s', '##t') -> ##st\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def create_new_symbol(x, y):\n",
    "    \"\"\"\n",
    "    根据 WordPiece 的规则创建新符号。\n",
    "\n",
    "    - 如果 y 以 '##' 开头，合并时需要去掉 y 的 '##' 前缀。\n",
    "    - 新符号是否以 '##' 开头，取决于 x 是否以 '##' 开头。\n",
    "    \"\"\"\n",
    "    x_starts_hash = x.startswith('##')\n",
    "    x_without_hash = x[2:] if x_starts_hash else x\n",
    "    y_without_hash = y[2:] if y.startswith('##') else y\n",
    "    new_symbol = x_without_hash + y_without_hash\n",
    "    if x_starts_hash:\n",
    "        new_symbol = '##' + new_symbol\n",
    "    return new_symbol\n",
    "\n",
    "def count_char_pairs_wordpiece(word_freq):\n",
    "    \"\"\"\n",
    "    计算字符对的频次和单个字符的频次。\n",
    "    \n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词（列表形式）和其频次\n",
    "        \n",
    "    返回：\n",
    "        两个字典，分别为字符对频次和单个字符频次\n",
    "    \"\"\"\n",
    "    pair_freq = defaultdict(int)\n",
    "    char_freq = defaultdict(int)\n",
    "    for word, freq in word_freq:\n",
    "        for i in range(len(word)):\n",
    "            char_freq[word[i]] += freq\n",
    "            if i < len(word) - 1:\n",
    "                pair = (word[i], word[i + 1])\n",
    "                pair_freq[pair] += freq\n",
    "    return pair_freq, char_freq\n",
    "\n",
    "def compute_wordpiece_score(freq_xy, freq_x, freq_y):\n",
    "    \"\"\"\n",
    "    根据 WordPiece 的定义计算 Score。\n",
    "    \n",
    "    参数：\n",
    "        freq_xy: 符号对的频次\n",
    "        freq_x: 符号 x 的频次\n",
    "        freq_y: 符号 y 的频次\n",
    "        \n",
    "    返回：\n",
    "        计算得到的 Score\n",
    "    \"\"\"\n",
    "    if freq_x == 0 or freq_y == 0:\n",
    "        return 0\n",
    "    return freq_xy / (freq_x * freq_y)\n",
    "\n",
    "def find_best_pair_wordpiece(pair_freq, char_freq):\n",
    "    \"\"\"\n",
    "    找到具有最高 Score 的字符对。\n",
    "\n",
    "    参数：\n",
    "        pair_freq: 字符对频次的字典\n",
    "        char_freq: 单个字符频次的字典\n",
    "        \n",
    "    返回：\n",
    "        具有最高 Score 的字符对及其 Score\n",
    "    \"\"\"\n",
    "    scores = {}\n",
    "    for pair, freq_xy in pair_freq.items():\n",
    "        x, y = pair\n",
    "        freq_x = char_freq.get(x, 0)\n",
    "        freq_y = char_freq.get(y, 0)\n",
    "        score = compute_wordpiece_score(freq_xy, freq_x, freq_y)\n",
    "        scores[pair] = score\n",
    "    if not scores:\n",
    "        return None, 0\n",
    "    best_pair = max(scores, key=scores.get)\n",
    "    return best_pair, scores[best_pair]\n",
    "\n",
    "def merge_pair_wordpiece(word_freq, pair_to_merge):\n",
    "    \"\"\"\n",
    "    合并指定的字符对到新符号。\n",
    "\n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词（列表形式）和其频次\n",
    "        pair_to_merge: 要合并的字符对\n",
    "    返回：\n",
    "        更新后的单词频次列表\n",
    "    \"\"\"\n",
    "    merged_word_freq = []\n",
    "    new_symbol = create_new_symbol(pair_to_merge[0], pair_to_merge[1])\n",
    "    for word, freq in word_freq:\n",
    "        new_word = []\n",
    "        i = 0\n",
    "        while i < len(word):\n",
    "            # 检查当前字符和下一个字符是否是要合并的字符对\n",
    "            if (\n",
    "                i < len(word) - 1\n",
    "                and word[i] == pair_to_merge[0]\n",
    "                and word[i + 1] == pair_to_merge[1]\n",
    "            ):\n",
    "                new_word.append(new_symbol)\n",
    "                i += 2  # 跳过下一个字符，因为已合并\n",
    "            else:\n",
    "                new_word.append(word[i])\n",
    "                i += 1\n",
    "        merged_word_freq.append((new_word, freq))\n",
    "    return merged_word_freq\n",
    "\n",
    "def wordpiece_merge(word_freq, vocab_size):\n",
    "    \"\"\"\n",
    "    执行 WordPiece 合并操作，直到词汇表达到预定大小。\n",
    "\n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词（列表形式）和其频次\n",
    "        vocab_size: 预定的词汇表大小\n",
    "        \n",
    "    返回：\n",
    "        最终词汇表和合并记录\n",
    "    \"\"\"\n",
    "    # 初始化词汇表\n",
    "    vocab = set()\n",
    "    for word, _ in word_freq:\n",
    "        vocab.update(word)\n",
    "    merges = []\n",
    "\n",
    "    while len(vocab) < vocab_size:\n",
    "        pair_freq, char_freq = count_char_pairs_wordpiece(word_freq)\n",
    "        best_pair, best_score = find_best_pair_wordpiece(pair_freq, char_freq)\n",
    "        if not best_pair:\n",
    "            break\n",
    "        # 合并最佳字符对\n",
    "        new_symbol = create_new_symbol(best_pair[0], best_pair[1])\n",
    "        word_freq = merge_pair_wordpiece(word_freq, best_pair)\n",
    "        vocab.add(new_symbol)\n",
    "        merges.append((best_pair, new_symbol))\n",
    "        print(\n",
    "            f\"Merge: {best_pair} -> {new_symbol}, Score: {best_score:.4f}, 词汇表大小: {len(vocab)}\"\n",
    "        )\n",
    "\n",
    "    return vocab, merges\n",
    "\n",
    "# 示例\n",
    "word_freq = [\n",
    "    (['l', '##o', '##w'], 5),\n",
    "    (['l', '##o', '##w', '##e', '##r'], 2),\n",
    "    (['n', '##e', '##w', '##e', '##s', '##t'], 6),\n",
    "    (['w', '##i', '##d', '##e', '##s', '##t'], 3)\n",
    "]\n",
    "\n",
    "# 预定词汇表大小为15\n",
    "final_vocab_wp, merge_records_wp = wordpiece_merge(word_freq, 15)\n",
    "\n",
    "print(\"\\n最终词汇表 V:\")\n",
    "print(final_vocab_wp)\n",
    "\n",
    "print(\"\\n合并记录:\")\n",
    "for idx, (pair, new_sym) in enumerate(merge_records_wp, 1):\n",
    "    print(f\"Merge {idx}: {pair} -> {new_sym}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee4a4da0-76fa-49b3-a327-525a47240d17",
   "metadata": {},
   "source": [
    "#### 📝 练习题答案\n",
    "\n",
    "**Q1. 最初的词汇表大小为 10，假设预定大小为 13，那么当前的词汇表 $V$ 为多少？合并记录呢？**\n",
    "\n",
    "- **初始词汇表 $V$**：\n",
    "\n",
    "  ```plaintext\n",
    "  {'l', 'o', 'w', 'e', 'r', 'n', 's', 't', 'i', 'd'}\n",
    "  ```\n",
    "\n",
    "  大小为 10。\n",
    "\n",
    "- **合并记录**：\n",
    "\n",
    "  1. 合并 `(\"e\", \"s\")` -> `es`，词汇表大小增加到 11。\n",
    "  2. 合并 `(\"es\", \"t\")` -> `est`，词汇表大小增加到 12。\n",
    "  3. 合并 `(\"l\", \"o\")` -> `lo`，词汇表大小增加到 13。\n",
    "\n",
    "- **最终词汇表 $V$**：\n",
    "\n",
    "  ```plaintext\n",
    "  {'l', 'o', 'w', 'e', 'r', 'n', 's', 't', 'i', 'd', 'es', 'est', 'lo'}\n",
    "  ```\n",
    "\n",
    "运行代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b4b1dd5a-2c25-467b-ba37-92ceed36df98",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Merge: ('e', 's') -> es, 词汇表大小: 11\n",
      "Merge: ('es', 't') -> est, 词汇表大小: 12\n",
      "Merge: ('l', 'o') -> lo, 词汇表大小: 13\n",
      "\n",
      "最终词汇表 V:\n",
      "{'n', 'es', 'i', 'est', 'lo', 't', 's', 'w', 'e', 'r', 'd', 'o', 'l'}\n",
      "\n",
      "合并记录:\n",
      "Merge 1: ('e', 's') -> es\n",
      "Merge 2: ('es', 't') -> est\n",
      "Merge 3: ('l', 'o') -> lo\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def count_char_pairs(word_freq):\n",
    "    \"\"\"\n",
    "    计算字符对的频次。\n",
    "    \n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词（列表形式）和其频次\n",
    "    \n",
    "    返回：\n",
    "        字符对频次的字典\n",
    "    \"\"\"\n",
    "    pair_freq = defaultdict(int)\n",
    "    for word, freq in word_freq:\n",
    "        for i in range(len(word) - 1):\n",
    "            pair = (word[i], word[i + 1])\n",
    "            pair_freq[pair] += freq\n",
    "    return pair_freq\n",
    "\n",
    "def find_best_pair(freq):\n",
    "    \"\"\"\n",
    "    找到频次最高的字符对。\n",
    "    \n",
    "    参数：\n",
    "        freq: 字符对频次的字典\n",
    "        \n",
    "    返回：\n",
    "        频次最高的字符对及其频次\n",
    "    \"\"\"\n",
    "    if not freq:\n",
    "        return None, 0\n",
    "    best_pair = max(freq, key=freq.get)\n",
    "    return best_pair, freq[best_pair]\n",
    "\n",
    "def merge_pair(word_freq, pair_to_merge):\n",
    "    \"\"\"\n",
    "    合并指定的字符对到新符号。\n",
    "    \n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词（列表形式）和其频次\n",
    "        pair_to_merge: 要合并的字符对\n",
    "    \n",
    "    返回：\n",
    "        更新后的单词频次列表\n",
    "    \"\"\"\n",
    "    merged_word_freq = []\n",
    "    pair_str = ''.join(pair_to_merge)\n",
    "    for word, freq in word_freq:\n",
    "        new_word = []\n",
    "        i = 0\n",
    "        while i < len(word):\n",
    "            # 检查当前字符和下一个字符是否是要合并的字符对\n",
    "            if i < len(word) - 1 and word[i] == pair_to_merge[0] and word[i + 1] == pair_to_merge[1]:\n",
    "                new_word.append(pair_str)\n",
    "                i += 2  # 跳过下一个字符，因为已合并\n",
    "            else:\n",
    "                new_word.append(word[i])\n",
    "                i += 1\n",
    "        merged_word_freq.append((new_word, freq))\n",
    "    return merged_word_freq\n",
    "\n",
    "def bpe_merge(word_freq, vocab_size):\n",
    "    \"\"\"\n",
    "    执行 BPE 合并操作，直到词汇表达到预定大小。\n",
    "    \n",
    "    参数：\n",
    "        word_freq: List of tuples, 每个元组包含单词（列表形式）和其频次\n",
    "        vocab_size: 预定的词汇表大小\n",
    "    \n",
    "    返回：\n",
    "        最终词汇表和合并记录\n",
    "    \"\"\"\n",
    "    # 初始化词汇表\n",
    "    vocab = set()\n",
    "    for word, _ in word_freq:\n",
    "        vocab.update(word)\n",
    "    merges = []\n",
    "    \n",
    "    while len(vocab) < vocab_size:\n",
    "        pair_freq = count_char_pairs(word_freq)\n",
    "        best_pair, best_freq = find_best_pair(pair_freq)\n",
    "        if not best_pair:\n",
    "            break\n",
    "        # 合并最佳字符对\n",
    "        word_freq = merge_pair(word_freq, best_pair)\n",
    "        new_symbol = ''.join(best_pair)\n",
    "        vocab.add(new_symbol)\n",
    "        merges.append((best_pair, new_symbol))\n",
    "        print(f\"Merge: {best_pair} -> {new_symbol}, 词汇表大小: {len(vocab)}\")\n",
    "            \n",
    "    return vocab, merges\n",
    "\n",
    "# 示例\n",
    "word_freq = [\n",
    "    (['l', 'o', 'w'], 5),\n",
    "    (['l', 'o', 'w', 'e', 'r'], 2),\n",
    "    (['n', 'e', 'w', 'e', 's', 't'], 6),\n",
    "    (['w', 'i', 'd', 'e', 's', 't'], 3)\n",
    "]\n",
    "\n",
    "# 预定词汇表大小为13\n",
    "final_vocab, merge_records = bpe_merge(word_freq, 13)\n",
    "\n",
    "print(\"\\n最终词汇表 V:\")\n",
    "print(final_vocab)\n",
    "\n",
    "print(\"\\n合并记录:\")\n",
    "for idx, (pair, new_sym) in enumerate(merge_records, 1):\n",
    "    print(f\"Merge {idx}: {pair} -> {new_sym}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7e876d7-d9de-4c89-9727-d0330309edec",
   "metadata": {},
   "source": [
    "**Q2. 如果以`</w>`（end-of-word）作为每个语料库中单词的结尾，最初的词汇表会受到什么影响，后续的过程呢？假设预定大小为 14，当前的合并记录是什么？**\n",
    "\n",
    "- **初始词汇表 $V$**：\n",
    "\n",
    "  添加 `</w>` 后，词汇表变为：\n",
    "\n",
    "  ```plaintext\n",
    "  {'l', 'o', 'w', 'e', 'r', 'n', 's', 't', 'i', 'd', '</w>'}\n",
    "  ```\n",
    "\n",
    "  大小为 11。\n",
    "\n",
    "- **影响**：\n",
    "\n",
    "  合并过程和合并记录将会发生变化，因为 `</w>` 的存在会影响字符对的频次统计和合并顺序。\n",
    "\n",
    "- **合并记录**：\n",
    "\n",
    "  1. 合并 `(\"e\", \"s\")` -> `es`，词汇表大小增加到 12。\n",
    "  2. 合并 `(\"es\", \"t\")` -> `est`，词汇表大小增加到 13。\n",
    "  3. 合并 `(\"est\", \"<\\w>\")` -> `est<\\w>`，词汇表大小增加到 14。\n",
    "\n",
    "运行代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "cc46f02a-2533-423b-aa70-68d4f668a39f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Merge: ('e', 's') -> es, 词汇表大小: 12\n",
      "Merge: ('es', 't') -> est, 词汇表大小: 13\n",
      "Merge: ('est', '</w>') -> est</w>, 词汇表大小: 14\n",
      "\n",
      "最终词汇表 V:\n",
      "{'n', 'es', '</w>', 'i', 'est', 'est</w>', 't', 's', 'w', 'e', 'r', 'd', 'o', 'l'}\n",
      "\n",
      "合并记录:\n",
      "Merge 1: ('e', 's') -> es\n",
      "Merge 2: ('es', 't') -> est\n",
      "Merge 3: ('est', '</w>') -> est</w>\n"
     ]
    }
   ],
   "source": [
    "# 示例\n",
    "word_freq = [\n",
    "    (['l', 'o', 'w', '</w>'], 5),\n",
    "    (['l', 'o', 'w', 'e', 'r', '</w>'], 2),\n",
    "    (['n', 'e', 'w', 'e', 's', 't', '</w>'], 6),\n",
    "    (['w', 'i', 'd', 'e', 's', 't', '</w>'], 3)\n",
    "]\n",
    "\n",
    "# 预定词汇表大小为14\n",
    "final_vocab, merge_records = bpe_merge(word_freq, 14)\n",
    "\n",
    "print(\"\\n最终词汇表 V:\")\n",
    "print(final_vocab)\n",
    "\n",
    "print(\"\\n合并记录:\")\n",
    "for idx, (pair, new_sym) in enumerate(merge_records, 1):\n",
    "    print(f\"Merge {idx}: {pair} -> {new_sym}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d33a88f0-86c3-4625-9b7d-c9f5e7c10909",
   "metadata": {},
   "source": [
    "### 标记文本\n",
    "\n",
    "你可能已经注意到，每次合并时我们都会记录对应的 **merge** 规则，但并未详细说明其作用，下面将以 BPE 为例进行解释。\n",
    "\n",
    "#### BPE\n",
    "\n",
    "在之前的示例中，三轮合并后将得到以下合并规则（按合并顺序排列）：  \n",
    "\n",
    "1. 合并字符对 `'e'` 和 `'s'`，得到 `'es'`。\n",
    "2. 合并字符对 `'es'` 和 `'t'`，得到 `'est'`。\n",
    "3. 合并字符对 `'l'` 和 `'o'`，得到 `'lo'`。\n",
    "\n",
    "假设当前词汇表包含所有单个字符，修改[官方文档](https://huggingface.co/learn/nlp-course/en/chapter6/5)最后提供的 tokenize() 示例代码进行演示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d9511ff0-6d34-442e-80cd-b1119b896eba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "初始预分词结果:\n",
      "['estimate', ',', 'Ġlocal']\n",
      "\n",
      "初始拆分结果:\n",
      "[['e', 's', 't', 'i', 'm', 'a', 't', 'e'], [','], ['Ġ', 'l', 'o', 'c', 'a', 'l']]\n",
      "\n",
      "应用合并规则: ('e', 's') -> es\n",
      "  合并前第 1 个单词: ['e', 's', 't', 'i', 'm', 'a', 't', 'e']\n",
      "    在位置 0 处合并: ['es', 't', 'i', 'm', 'a', 't', 'e']\n",
      "  合并前第 2 个单词: [',']\n",
      "  合并前第 3 个单词: ['Ġ', 'l', 'o', 'c', 'a', 'l']\n",
      "\n",
      "应用合并规则: ('es', 't') -> est\n",
      "  合并前第 1 个单词: ['es', 't', 'i', 'm', 'a', 't', 'e']\n",
      "    在位置 0 处合并: ['est', 'i', 'm', 'a', 't', 'e']\n",
      "  合并前第 2 个单词: [',']\n",
      "  合并前第 3 个单词: ['Ġ', 'l', 'o', 'c', 'a', 'l']\n",
      "\n",
      "应用合并规则: ('l', 'o') -> lo\n",
      "  合并前第 1 个单词: ['est', 'i', 'm', 'a', 't', 'e']\n",
      "  合并前第 2 个单词: [',']\n",
      "  合并前第 3 个单词: ['Ġ', 'l', 'o', 'c', 'a', 'l']\n",
      "    在位置 1 处合并: ['Ġ', 'lo', 'c', 'a', 'l']\n",
      "\n",
      "最终拆分结果:\n",
      "[['est', 'i', 'm', 'a', 't', 'e'], [','], ['Ġ', 'lo', 'c', 'a', 'l']]\n",
      "\n",
      "最终生成的 Tokens:\n",
      "['est', 'i', 'm', 'a', 't', 'e', ',', 'Ġ', 'lo', 'c', 'a', 'l']\n"
     ]
    }
   ],
   "source": [
    "def tokenize(text):\n",
    "    # 预分词处理：将文本拆分为初步的单词列表\n",
    "    pre_tokenize_result = tokenizer._tokenizer.pre_tokenizer.pre_tokenize_str(text)\n",
    "    pre_tokenized_text = [word for word, offset in pre_tokenize_result]\n",
    "\n",
    "    print(\"初始预分词结果:\")\n",
    "    print(pre_tokenized_text)\n",
    "\n",
    "    # 将每个单词拆分为字符列表\n",
    "    splits = [[l for l in word] for word in pre_tokenized_text]\n",
    "    print(\"\\n初始拆分结果:\")\n",
    "    print(splits)\n",
    "\n",
    "    # 遍历所有合并规则（merges），逐步应用到拆分后的结果中\n",
    "    for pair, merge in merges.items():\n",
    "        print(f\"\\n应用合并规则: {pair} -> {merge}\")\n",
    "\n",
    "        # 遍历每个已拆分的单词\n",
    "        for idx, split in enumerate(splits):\n",
    "            print(f\"  合并前第 {idx+1} 个单词: {split}\")\n",
    "            i = 0\n",
    "            # 在当前拆分的字符中查找匹配的字符对\n",
    "            while i < len(split) - 1:\n",
    "                if split[i] == pair[0] and split[i + 1] == pair[1]:\n",
    "                    # 合并字符对\n",
    "                    split = split[:i] + [merge] + split[i + 2 :]\n",
    "                    print(f\"    在位置 {i} 处合并: {split}\")\n",
    "                else:\n",
    "                    i += 1\n",
    "            # 更新拆分后的结果\n",
    "            splits[idx] = split\n",
    "\n",
    "    print(\"\\n最终拆分结果:\")\n",
    "    print(splits)\n",
    "\n",
    "    # 将所有拆分后的结果合并为一个 Token 列表并返回\n",
    "    return sum(splits, [])\n",
    "\n",
    "# 示例 merges 字典\n",
    "merges = {\n",
    "    ('e', 's'): 'es',\n",
    "    ('es', 't'): 'est',\n",
    "    ('l', 'o'): 'lo'\n",
    "}\n",
    "\n",
    "# 示例文本\n",
    "text = \"estimate, local\"\n",
    "\n",
    "# 调用 tokenize 函数，并打印中间过程\n",
    "tokens = tokenize(text)\n",
    "print(\"\\n最终生成的 Tokens:\")\n",
    "print(tokens)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3951e873-4468-4a40-b959-f8ee645a4ec9",
   "metadata": {},
   "source": [
    "不过，在之前的过程中生成的最终词汇表 $V$ 并未包含所有单个字符，而是：  \n",
    "\n",
    "```\n",
    "{'e', 'r', 's', 'est', 'w', 'l', 'o', 'lo', 'es', 'i', 'n', 't', 'd'}\n",
    "```\n",
    "\n",
    "因此，对于输入 `\"estimate, local\"`，其标记结果为：  \n",
    "\n",
    "```\n",
    "['est', 'i', '[UNK]', 'a', 't', 'e', '[UNK]', 'lo', '[UNK]', '[UNK]', l]\n",
    "```\n",
    "\n",
    "这里的 `'[UNK]'`（UNKNOWN）表示该子词不在词汇表中，即属于 **OOV（Out-of-Vocabulary）** 的情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b85de72-6c72-414e-a2ef-574f3f745350",
   "metadata": {},
   "source": [
    "#### WordPiece\n",
    "\n",
    "和 BPE 不同，WordPiece 对 OOV 采取的是「宁杀错不放过」策略，即只要有一个字符没见过，整个单词都标记为 `'[UNK]'`。\n",
    "\n",
    "修改[官方文档](https://huggingface.co/learn/nlp-course/en/chapter6/6)最后提供的 tokenize() 示例代码进行演示："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "59dd5189-0e5c-430b-90bf-8794cdcd8410",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "初始预分词结果:\n",
      "['estimate', ',', 'local', ',', 'lows']\n",
      "\n",
      "正在标记单词: estimate\n",
      "  [UNK] 标记: estimate\n",
      "  标记结果: ['[UNK]']\n",
      "\n",
      "正在标记单词: ,\n",
      "  [UNK] 标记: ,\n",
      "  标记结果: ['[UNK]']\n",
      "\n",
      "正在标记单词: local\n",
      "  匹配到 Token: lo\n",
      "  剩余部分添加前缀: ##cal\n",
      "  [UNK] 标记: ##cal\n",
      "  标记结果: ['[UNK]']\n",
      "\n",
      "正在标记单词: ,\n",
      "  [UNK] 标记: ,\n",
      "  标记结果: ['[UNK]']\n",
      "\n",
      "正在标记单词: lows\n",
      "  匹配到 Token: lo\n",
      "  剩余部分添加前缀: ##ws\n",
      "  匹配到 Token: ##w\n",
      "  剩余部分添加前缀: ##s\n",
      "  匹配到 Token: ##s\n",
      "  标记结果: ['lo', '##w', '##s']\n",
      "\n",
      "最终标记结果:\n",
      "['[UNK]', '[UNK]', '[UNK]', '[UNK]', 'lo', '##w', '##s']\n"
     ]
    }
   ],
   "source": [
    "from transformers import AutoTokenizer\n",
    "\n",
    "def tokenize(text):\n",
    "    # 预分词处理：将文本拆分为初步的单词列表\n",
    "    pre_tokenize_result = tokenizer._tokenizer.pre_tokenizer.pre_tokenize_str(text)\n",
    "    pre_tokenized_text = [word for word, offset in pre_tokenize_result]\n",
    "\n",
    "    print(\"\\n初始预分词结果:\")\n",
    "    print(pre_tokenized_text)\n",
    "\n",
    "    # 对每个单词进行标记\n",
    "    tokenized_words = []\n",
    "    for word in pre_tokenized_text:\n",
    "        tokens = []\n",
    "        print(f\"\\n正在标记单词: {word}\")\n",
    "        \n",
    "        while len(word) > 0:\n",
    "            i = len(word)\n",
    "            # 尝试匹配词汇表中的最长子词\n",
    "            while i > 0 and word[:i] not in vocab:\n",
    "                i -= 1\n",
    "            if i == 0:\n",
    "                print(f\"  [UNK] 标记: {word}\")\n",
    "                tokens = [\"[UNK]\"]  # 没有匹配到则返回 [UNK]\n",
    "                break  # 跳出循环，不再继续处理该单词\n",
    "\n",
    "            # 匹配到子词，添加到 tokens 列表中\n",
    "            matched_token = word[:i]\n",
    "            tokens.append(matched_token)\n",
    "            print(f\"  匹配到 Token: {matched_token}\")\n",
    "\n",
    "            # 更新剩余部分，并添加“##”作为前缀\n",
    "            word = word[i:]\n",
    "            if len(word) > 0:\n",
    "                word = f\"##{word}\"\n",
    "                print(f\"  剩余部分添加前缀: {word}\")\n",
    "\n",
    "        print(f\"  标记结果: {tokens}\")\n",
    "        tokenized_words.append(tokens)\n",
    "\n",
    "    print(\"\\n最终标记结果:\")\n",
    "    flattened_tokens = sum(tokenized_words, [])  # 展平成单层列表\n",
    "    print(flattened_tokens)\n",
    "\n",
    "    return flattened_tokens\n",
    "\n",
    "# 示例词汇表\n",
    "vocab = {'##st', 'n', '##i', '##s', 'wid', '##d', 'wi', '##r', '##o', \n",
    "         'lo', 'w', '##e', '##w', '##t', 'l'}\n",
    "\n",
    "# 示例文本\n",
    "text = \"estimate, local, lows\"\n",
    "\n",
    "# 使用 BERT 的分词器（WordPiece）\n",
    "tokenizer = AutoTokenizer.from_pretrained('bert-base-uncased')\n",
    "\n",
    "# 调用 tokenize 函数，并打印中间过程\n",
    "tokens = tokenize(text)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad32bb25-8169-4237-9216-05df067be214",
   "metadata": {},
   "source": [
    "## 映射（Mapping）\n",
    "\n",
    "以 BPE 为例，最终词汇表 $V$ 中的 Token 和对应的频次分别为：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "28723d53-2500-4986-a363-70688c16ac36",
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab = {\n",
    "    'lo': 7,\n",
    "    'w': 16,\n",
    "    'e': 8,\n",
    "    'r': 2,\n",
    "    'n': 6,\n",
    "    'est': 9,\n",
    "    'i': 3,\n",
    "    'd': 3\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e716182-86fc-47d7-b9cc-6d06ff85d9aa",
   "metadata": {},
   "source": [
    "简单实现 Token 和 ID 之间的映射关系的代码：\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ff684d26-c327-4d87-8aad-a31ecf11f8dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Token to ID: {'lo': 0, 'w': 1, 'e': 2, 'r': 3, 'n': 4, 'est': 5, 'i': 6, 'd': 7}\n",
      "ID to Token: {0: 'lo', 1: 'w', 2: 'e', 3: 'r', 4: 'n', 5: 'est', 6: 'i', 7: 'd'}\n"
     ]
    }
   ],
   "source": [
    "# 创建 token 到 ID 的映射\n",
    "token_to_id = {token: idx for idx, token in enumerate(vocab)}\n",
    "\n",
    "# 创建 ID 到 token 的映射\n",
    "id_to_token = {idx: token for token, idx in token_to_id.items()}\n",
    "\n",
    "# 打印映射关系\n",
    "print(\"Token to ID:\", token_to_id)\n",
    "print(\"ID to Token:\", id_to_token)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b903c7c9-c792-4520-ab64-6fe7dfd456c8",
   "metadata": {},
   "source": [
    "当然，也可以根据频次或者其他规则进行特殊处理。\n",
    "\n",
    "\n",
    "以上是编码部分的概述，实际上在文本预处理的时候还会增加特殊标记，但这些以及后续的解码部分大多是一些文本处理的规则，这里就不过多赘述了，Tokenizer 之间的核心差异在于使用的分割方法和词汇表的构建策略。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c5f0d6b-fccd-45ed-92c2-127512850764",
   "metadata": {},
   "source": [
    "## 拓展（Transformers）\n",
    "\n",
    "在 Transformers 中，**分词（tokenization）** 实际上包含以下几个步骤：  \n",
    "\n",
    "1. **标准化（Normalization）**：对文本进行必要的清理操作，例如删除多余空格或重音符号、进行 Unicode 标准化等。\n",
    "2. **预分词（Pre-tokenization）**：将输入拆分为单词。\n",
    "3. **通过模型处理输入（Running the input through the model）**：使用预分词后的单词生成一系列词元（tokens）。\n",
    "4. **后处理（Post-processing）**：添加分词器的特殊标记，生成注意力掩码（attention mask）和词元类型 ID（token type IDs）。\n",
    "\n",
    "[官方文档](https://huggingface.co/learn/nlp-course/en/chapter6/8)给出了一张整体流程图：\n",
    "\n",
    "![en_chapter6_tokenization_pipeline](../Guide/assets/en_chapter6_tokenization_pipeline.svg)\n",
    "\n",
    "运行代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "0385adda-9eea-456e-99b3-a8cca01ad27c",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始文本: Hello how are U tday\n",
      "标准化后的文本: hello how are u tday\n",
      "预分词结果: [('hello', (0, 5)), ('how', (6, 9)), ('are', (10, 13)), ('u', (14, 15)), ('tday', (16, 20))]\n",
      "词元（Tokens）: ['hello', 'how', 'are', 'u', 'td', '##ay']\n",
      "词元 ID（Token IDs）: [7592, 2129, 2024, 1057, 14595, 4710]\n",
      "编码结果: {'input_ids': tensor([[  101,  7592,  2129,  2024,  1057, 14595,  4710,   102]]), 'token_type_ids': tensor([[0, 0, 0, 0, 0, 0, 0, 0]]), 'attention_mask': tensor([[1, 1, 1, 1, 1, 1, 1, 1]])}\n",
      "注意力掩码（Attention Mask）: tensor([[1, 1, 1, 1, 1, 1, 1, 1]])\n",
      "词元类型 ID（Token Type IDs）: tensor([[0, 0, 0, 0, 0, 0, 0, 0]])\n",
      "解码后的文本: hello how are u tday\n"
     ]
    }
   ],
   "source": [
    "from transformers import AutoTokenizer\n",
    "\n",
    "# 加载 BERT 的分词器\n",
    "tokenizer = AutoTokenizer.from_pretrained(\"bert-base-uncased\")\n",
    "\n",
    "# 原始文本\n",
    "text = \"Hello how are U tday\"\n",
    "print(\"原始文本:\", text)\n",
    "\n",
    "# 1. 标准化：转换为小写\n",
    "normalized_text = text.lower()\n",
    "print(\"标准化后的文本:\", normalized_text)\n",
    "\n",
    "# 2. 预分词（Pre-tokenization）：将输入拆分为单词\n",
    "pre_tokenized = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(normalized_text)\n",
    "print(\"预分词结果:\", pre_tokenized)\n",
    "\n",
    "# 3. 分词：将预分词后的结果转换为子词级词元\n",
    "tokens = tokenizer.tokenize(normalized_text)\n",
    "print(\"词元（Tokens）:\", tokens)\n",
    "\n",
    "# 4. 将 tokens 转换为 token IDs\n",
    "token_ids = tokenizer.convert_tokens_to_ids(tokens)\n",
    "print(\"词元 ID（Token IDs）:\", token_ids)\n",
    "\n",
    "# 5. 编码（包含特殊标记和后处理）\n",
    "encoded = tokenizer(normalized_text, return_tensors=\"pt\")\n",
    "print(\"编码结果:\", encoded)\n",
    "\n",
    "# 6. 打印注意力掩码和词元类型 ID（后处理部分）\n",
    "print(\"注意力掩码（Attention Mask）:\", encoded[\"attention_mask\"])\n",
    "print(\"词元类型 ID（Token Type IDs）:\", encoded[\"token_type_ids\"])\n",
    "\n",
    "# 7. 解码：将 token IDs 转换回文本\n",
    "decoded_text = tokenizer.decode(token_ids)\n",
    "print(\"解码后的文本:\", decoded_text)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9eb6a2ed-cec9-4b68-8957-c89adf62bd0f",
   "metadata": {},
   "source": [
    "### Q：注意力掩码（Attention Mask）和词元类型 ID （Token Type IDs）是什么？\n",
    "\n",
    "**注意力掩码**确保模型只关注实际的词元，忽略填充部分，从而避免无效的计算：\n",
    "\n",
    "- **1**：表示模型应关注的词元（Tokens）\n",
    "- **0**：表示模型应忽略的词元（通常是填充 `padding` 的部分）。\n",
    "\n",
    "在之前的[文章](https://github.com/Hoper-J/AI-Guide-and-Demos-zh_CN/blob/master/Guide/16.%20用%20LoRA%20微调%20Stable%20Diffusion：拆开炼丹炉，动手实现你的第一次%20AI%20绘画.md#怎么让模型理解文本)中曾展示过注意力掩码在 `padding=\"max_length\"` 下的表现。\n",
    "\n",
    "**词元类型 ID** 用于区分输入中的不同句子或段落：\n",
    "\n",
    "- **0**：表示第一个句子的词元。\n",
    "- **1**：表示第二个句子的词元。\n",
    "\n",
    "运行代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "9398d22e-7fa6-465d-a187-d3f664d2085b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "词元类型 ID（Token Type IDs）: tensor([[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]])\n",
      "解码后的文本: [CLS] hello how are you [SEP] i am fine thank you [SEP]\n"
     ]
    }
   ],
   "source": [
    "from transformers import AutoTokenizer\n",
    "\n",
    "# 加载 BERT 的分词器\n",
    "tokenizer = AutoTokenizer.from_pretrained(\"bert-base-uncased\")\n",
    "\n",
    "# 两个句子\n",
    "text_a = \"Hello how are you\"\n",
    "text_b = \"I am fine thank you\"\n",
    "\n",
    "# 编码两个句子\n",
    "encoded = tokenizer(text_a, text_b, return_tensors=\"pt\", padding=True, truncation=True)\n",
    "\n",
    "# 打印词元类型 ID\n",
    "print(\"词元类型 ID（Token Type IDs）:\", encoded[\"token_type_ids\"])\n",
    "\n",
    "# 解码\n",
    "decoded_text = tokenizer.decode(encoded[\"input_ids\"][0])\n",
    "print(\"解码后的文本:\", decoded_text)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f7b802a-34a8-4251-a76e-144ed3c49daa",
   "metadata": {},
   "source": [
    "## 参考链接\n",
    "\n",
    "- [Byte-Pair Encoding tokenization](https://huggingface.co/learn/nlp-course/en/chapter6/5)\n",
    "- [WordPiece tokenization](https://huggingface.co/learn/nlp-course/en/chapter6/6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "acebfbb6-fa74-4449-9acc-da34b7ef9f2c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}