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（<unk> / <bos> 等），
也不做正则预分词：切分规则完全由下文给出，请严格按照题面实现。

输入格式

一行 JSON 对象（input_str 即该 JSON 文本）。公共字段：

字段	类型	说明
task	字符串	"train" 或 "encode"（只会是这两个值之一）

task == "train" 时另有：

字段	类型	说明
corpus	字符串数组	语料，每个元素是一段文本；可以为空数组
vocab_size	整数	目标词表大小；可以为 0 或负数
min_frequency	整数	可选，缺省为 1；最低频次阈值

task == "encode" 时另有：

字段	类型	说明
text	字符串	待编码文本；可以为空串
merges	二维字符串数组	合并规则，顺序即优先级；可以为空数组

输出格式

一行 JSON 对象。task == "train" 时输出：

{"merges": [["l", "o"], ["lo", "w"], ["e", "s"]]}

task == "encode" 时输出：

{"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）

记语料切出的全部词为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>w</mi><mn>1</mn></msub><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><msub><mi>w</mi><mi>m</mi></msub></mrow><annotation encoding="application/x-tex">w_1, \dots, w_m</annotation></semantics></math>w1​,…,wm​（重复出现的词按出现次数重复计入，
即保留重数）。初始时每个词表示成它的单字符符号序列。

初始词表为语料中出现过的全部不同字符（去重后的大小记为 $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 中 首次 出现的下标}$$

若 merges 中同一对出现多次，只有首次下标有效（重复出现的规则被忽略）。

对每个词（按「通用约定」切出）执行：

1. 把词表示成单字符符号序列；
2. 循环：
   • 找出当前序列中所有相邻对里 rank 最小的那一对 (a, b)；
     未被 rank 表登记的对不参与（视为不可合并）；
   • 若不存在任何已登记的相邻对，结束循环；
   • 否则对该对执行一次最左非重叠全局替换（与训练第 4 步相同的替换规则）；
3. 循环结束后剩下的符号序列就是该词的 token。

把所有词的 token 按文本从左到右的顺序拼接即为 tokens。

⚠️ 注意：这不是「按 merges 列表顺序逐条应用规则」。
本题的语义是每轮挑当前 rank 最小的相邻对，所以一条排在后面的规则可能在
「前面的规则合并出新符号之后」才被触发。反例（务必理解）：

{"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"]。

未见字符的处理：本题词表是字符级的，没有 <unk>。任何字符（无论是否在
任何规则中出现过，包括中文、emoji、生僻符号）都能作为单字符 token 输出；
它只会在没有适用规则时保持单字符，绝不会被丢弃或替换成未知标记。

空输入：text 为空串或只含空白时，tokens 为空数组 []。

示例

示例 1（训练：并列频次的打破方式）

输入：

{"task": "train", "corpus": ["yxy"], "vocab_size": 4, "min_frequency": 1}

输出：

{"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（编码：多轮合并）

输入：

{"task": "encode", "text": "lowest", "merges": [["e", "s"], ["es", "t"], ["l", "o"], ["lo", "w"]]}

输出：

{"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（编码：未见字符与码点级切分）

输入：

{"task": "encode", "text": "a😀b 你好", "merges": [["a", "b"], ["你", "好"]]}

输出：

{"tokens": ["a", "😀", "b", "你好"]}

说明：文本切出两个词 a😀b 与 你好。第一个词里 a 与 b 不相邻
（中间隔着 😀），所以规则 ["a","b"] 不生效，😀 作为单字符 token 保留
（未见字符不会被丢弃，也不需要 <unk>）；第二个词里 (你,好) 登记在案，合并成
"你好"。空格是分隔符，不产生 token。

示例 4（训练：vocab_size 小于初始字符集）

输入：

{"task": "train", "corpus": ["banana"], "vocab_size": 3, "min_frequency": 1}

输出：

{"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 个示例会作为可见用例运行并展示输入/期望/实际，但不计分。