# BPE 分词器的训练与编码 ## 题目描述 **BPE（Byte-Pair Encoding，字节对编码）** 是现代大语言模型分词器（如 GPT 系列、 Llama 系列的 SentencePiece / tiktoken）最常用的子词切分算法。它从「每个字符一个 token」出发，反复把**语料中频次最高的相邻符号对**合并成一个新符号，从而把常见词压成整块、把生僻词拆成子词。本题要求你实现 BPE 的两个核心环节： | 入口 | 签名 | 作用 | |------|------|------| | 训练 | `train(corpus, vocab_size, min_frequency=1) -> list[list[str]]` | 从语料学出**合并规则**列表（按学习顺序） | | 编码 | `encode(text, merges) -> list[str]` | 用给定规则把文本切成 **token 序列** | 平台通过 Solution 容器调用模块级入口 `solve(input_str)`；`solve` 需要按输入中的 `task` 字段把请求分派给 `train` / `encode`，并返回结果 JSON 文本。 > 本题不涉及字节级 BPE、不考虑特殊 token（`` / `` 等）， > 也**不做正则预分词**：切分规则完全由下文给出，请严格按照题面实现。 ## 输入格式一行 JSON 对象（`input_str` 即该 JSON 文本）。公共字段： | 字段 | 类型 | 说明 | |------|------|------| | `task` | 字符串 | `"train"` 或 `"encode"`（只会是这两个值之一） | `task == "train"` 时另有： | 字段 | 类型 | 说明 | |------|------|------| | `corpus` | 字符串数组 | 语料，每个元素是一段文本；**可以为空数组** | | `vocab_size` | 整数 | 目标词表大小；**可以为 0 或负数** | | `min_frequency` | 整数 | 可选，缺省为 `1`；最低频次阈值 | `task == "encode"` 时另有： | 字段 | 类型 | 说明 | |------|------|------| | `text` | 字符串 | 待编码文本；**可以为空串** | | `merges` | 二维字符串数组 | 合并规则，顺序即优先级；**可以为空数组** | ## 输出格式一行 JSON 对象。`task == "train"` 时输出： ```json {"merges": [["l", "o"], ["lo", "w"], ["e", "s"]]} ``` `task == "encode"` 时输出： ```json {"tokens": ["low", "est"]} ``` | 字段 | 说明 | |------|------| | `merges` | 学到的合并规则，**顺序必须与学习顺序一致**；每条规则是 `[左符号, 右符号]` 两个字符串 | | `tokens` | token 字符串数组，顺序与文本从左到右一致 | 允许在结果行之前打印任意调试信息（评测时只取**最后一行非空内容**作为结果）。 ## 通用约定以下约定同时适用于 `train` 与 `encode`，是本题**唯一**的切分口径： 1. **词切分**：把一段文本按**空白字符**切分成词，空白字符指 `str.isspace()` 为真的字符（空格、`\t`、`\n`、`\r`、`\v`、`\f`、不换行空格 U+00A0、全角空格 U+3000、行分隔符 U+2028 等）。这等价于 Python 中 `text.split()` 无参调用的语义。切分产生的**空串被丢弃**。 2. **空白不产生 token**：空白只作分隔符，任何空白都不会出现在 `tokens` 里，也不参与语料的符号序列。 3. **字符 = Unicode 码点**：一个「字符」就是 Python 字符串的一个元素（一个码点）。 **不**按字素簇（grapheme cluster）聚合，因此组合 emoji 会被拆成多个码点，例如 `"👨‍👩‍👧"` 含 5 个码点（👨 / U+200D / 👩 / U+200D / 👧）。 4. **零宽空格 U+200B 不是空白**（它的 `isspace()` 为 `False`），因此它留在词内部，是一个普通字符。 ## 训练规则（`train`）记语料切出的全部词为 $w_1, \dots, w_m$（重复出现的词**按出现次数重复计入**，即保留重数）。初始时每个词表示成它的**单字符符号序列**。初始词表为语料中出现过的**全部不同字符**（去重后的大小记为 $C$；空语料时 $C=0$）。 **合并次数上限**： $$ \text{max\_merges} = \max(0,\ \text{vocab\_size} - C) $$ 即最终词表大小为 $\max(C,\ \min(\text{vocab\_size},\ C + \text{实际可合并次数}))$；若 `vocab_size <= C`，则一条规则也学不到，直接输出 `{"merges": []}`。 **迭代过程**：在 `len(merges) < max_merges` 时重复： 1. **统计**：对当前每个词的符号序列，统计所有**相邻符号对** `(a, b)` 的出现次数（一个词内同一个对在不同位置各计一次；所有词累加）。 2. **停止判断**：若不存在任何相邻对，或出现次数的**最大值 < `min_frequency`** （`min_frequency < 1` 时按 `1` 处理），则停止迭代。 3. **选对**：取出现次数**最大**的对。若多个对的次数并列最大， **取字典序最小的 `(a, b)`**——先比较 `a`，`a` 相同再比较 `b`，按 Unicode 码点序比较（等价于 Python 中元组 `(a, b)` 的比较；注意符号可能是多字符，比较的是**字符串**，例如 `"aa" < "b"`）。 4. **合并**：把选中的对 `(a, b)` 追加到 `merges`，并对**每个词**的符号序列执行一次**最左非重叠**替换：自左向右扫描，遇到相邻的 `a` 紧跟 `b` 就输出合并后的新符号 `a + b` 并跳过这两个位置，否则输出当前符号并前进一位。例如序列 `[a, a, a]` 与对 `(a, a)` 合并后为 `[aa, a]`（不是 `[a, aa]`，也不是 `[aa, aa]`）。合并产生的新符号在后续轮次中**照常参与**相邻对统计（因此 `"aa"` 之后还能与 `"aa"` 合并出 `"aaaa"`）。 > 由于规则是「先按频次、再按字典序」确定的，训练过程**完全确定**： > 相同输入必然得到相同 `merges`。 ## 编码规则（`encode`）给定规则列表 `merges`，先构造 **rank 表**： $$ \text{rank}[(a, b)] = \text{该对在 merges 中\ \textbf{首次}\ 出现的下标} $$ 若 `merges` 中同一对出现多次，**只有首次下标有效**（重复出现的规则被忽略）。对每个词（按「通用约定」切出）执行： 1. 把词表示成单字符符号序列； 2. **循环**： - 找出当前序列中**所有相邻对里 rank 最小**的那一对 `(a, b)`；未被 rank 表登记的对不参与（视为不可合并）； - 若不存在任何已登记的相邻对，结束循环； - 否则对该对执行一次**最左非重叠**全局替换（与训练第 4 步相同的替换规则）； 3. 循环结束后剩下的符号序列就是该词的 token。把所有词的 token 按文本从左到右的顺序拼接即为 `tokens`。 > ⚠️ **注意：这不是「按 merges 列表顺序逐条应用规则」。** > 本题的语义是**每轮挑当前 rank 最小的相邻对**，所以一条排在后面的规则可能在 > 「前面的规则合并出新符号之后」才被触发。反例（务必理解）： > > ```json > {"task": "encode", "text": "xab", "merges": [["x", "ab"], ["a", "b"]]} > ``` > > 第一轮：序列为 `[x, a, b]`，相邻对为 `(x,a)`（未登记）与 `(a,b)`（rank 1）， > 最小 rank 是 1，于是合并 `(a,b)` → `[x, ab]`。 > 第二轮：相邻对 `(x,ab)` 的 rank 是 0，比刚才更小，于是继续合并 → `[xab]`。 > 因此正确答案是 `{"tokens": ["xab"]}`； > 若误按「列表顺序逐条应用」，会在第一步就卡在 `(x,ab)` 匹配不上， > 得到错误的 `["x", "ab"]`。 **未见字符的处理**：本题词表是字符级的，**没有 ``**。任何字符（无论是否在任何规则中出现过，包括中文、emoji、生僻符号）都能作为**单字符 token** 输出；它只会在没有适用规则时保持单字符，绝不会被丢弃或替换成未知标记。 **空输入**：`text` 为空串或只含空白时，`tokens` 为空数组 `[]`。 ## 示例 ### 示例 1（训练：并列频次的打破方式）输入： ```json {"task": "train", "corpus": ["yxy"], "vocab_size": 4, "min_frequency": 1} ``` 输出： ```json {"merges": [["x", "y"], ["y", "xy"]]} ``` 说明：语料只有 `yxy` 一个词，初始不同字符为 `{x, y}`，$C = 2$， `max_merges = 4 - 2 = 2`。第一轮相邻对 `(y,x)` 与 `(x,y)` 各出现 1 次**并列**，取字典序最小的 `(x, y)`（`"x" < "y"`），合并后符号序列为 `[y, xy]`；第二轮只剩 `(y, xy)` 可合并，得到 `[yxy]`。 ### 示例 2（编码：多轮合并）输入： ```json {"task": "encode", "text": "lowest", "merges": [["e", "s"], ["es", "t"], ["l", "o"], ["lo", "w"]]} ``` 输出： ```json {"tokens": ["low", "est"]} ``` 说明：`[l,o,w,e,s,t]` 中最初已登记的相邻对只有 `(e,s)`（rank 0）；合并后得到 `[l,o,w,es,t]`，此时 `(es,t)`（rank 1）可合并 → `[l,o,w,est]`；再合并 `(l,o)`（rank 2）→ `[lo,w,est]`；最后合并 `(lo,w)`（rank 3）→ `[low,est]`。每一步都取「当前 rank 最小」的对。 ### 示例 3（编码：未见字符与码点级切分）输入： ```json {"task": "encode", "text": "a😀b 你好", "merges": [["a", "b"], ["你", "好"]]} ``` 输出： ```json {"tokens": ["a", "😀", "b", "你好"]} ``` 说明：文本切出两个词 `a😀b` 与 `你好`。第一个词里 `a` 与 `b` **不相邻** （中间隔着 `😀`），所以规则 `["a","b"]` 不生效，`😀` 作为单字符 token 保留（未见字符不会被丢弃，也不需要 ``）；第二个词里 `(你,好)` 登记在案，合并成 `"你好"`。空格是分隔符，不产生 token。 ### 示例 4（训练：`vocab_size` 小于初始字符集）输入： ```json {"task": "train", "corpus": ["banana"], "vocab_size": 3, "min_frequency": 1} ``` 输出： ```json {"merges": []} ``` 说明：`banana` 的不同字符是 `{b, a, n}`，$C = 3$，`max_merges = 3 - 3 = 0`，因此不执行任何合并（`vocab_size` 更小时同理）。 ## 数据范围与限制评测数据**不会超过**以下范围（按这个量级准备即可）： - `corpus`：元素个数 $\le 200$，拼接后的总字符数 $\le 5000$；元素个数可以为 0 - `vocab_size` $\in [-10, 1000]$ - `min_frequency` $\in [-10, 1000]$ - `text` 长度 $\le 10000$ - `merges` 长度 $\le 50$，每条规则的两个符号长度均在 $[1, 200]$ 之间 - 所有字符串均为合法 UTF-8 文本（含中文、emoji 等） - 时间限制：$2000\text{ms}$ / 用例；内存限制：$256\text{MB}$ > 上限按「能在时限内跑完」标定：最重的规模用例是 5000 字符语料配 > `vocab_size = 1000`（约 970 轮合并），参考实现单例约 $0.4\text{s}$。 > 单用例超时（记 `TimeLimitExceeded`）与选手代码抛异常（记 `RuntimeError`）都**只影响 > 该用例**（该用例 0 分），评测继续执行其余用例——一条用例崩溃不会连带丢掉其余用例的 > 得分；只有 Solution 进程崩溃、评测通道断开等**评测侧**故障才会使整份评测失败。 > 单用例超时（记 `TimeLimitExceeded`）与选手代码抛异常（记 `RuntimeError`）都**只影响 > 该用例**（该用例 0 分），评测继续执行其余用例——一条用例崩溃不会连带丢掉其余用例的 > 得分；只有 Solution 进程崩溃、评测通道断开等**评测侧**故障才会使整份评测失败。 ## 评分 - 正式得分**只来自隐藏用例**，各用例等权，满分 **100** 分。 - 判定为**精确比对**（离散结果，无浮点容差）： - `train`：`merges` 的长度、顺序、每条规则的两个符号必须完全一致； - `encode`：`tokens` 的长度、顺序、每个 token 字符串必须完全一致。 - 题面中的 4 个示例会作为可见用例运行并展示输入/期望/实际，但**不计分**。

题库