题目重点：按公开面经的 app/apple/UNK 样例实现贪心最长匹配，用 Trie 优化，并核对连续未知字符折叠、空词表及非回溯语义。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版从左向右做局部最长匹配；有匹配时取最长词，不做全局最少 token 的回溯。
- UNK 是专用键，必须有独立 id；不允许空字符串词，否则游标不前进。
- 若当前字符无词匹配，消耗一个字符并输出 UNK；相邻未知字符只保留一个 UNK。题目没有定义 Unicode 规范化、大小写折叠或并列词，本文均不做。
解题路线
- 先建立 Trie，每条边是一个字符，终止节点保存词的 token id。每个游标位置顺 Trie 向前走，记录最近一次命中的终止节点；走不动后消费最长命中。
- 没有命中时消费一个字符；若上一个输出已是 UNK，不再追加。这一步与吞掉整段不在词表的字符等价，但每走一格仍检查是否出现新的可识别词前缀。
- 若词表较小，直接从当前位置枚举候选长度也可；Trie 避免每次反复构造大量子串，并把匹配工作界定为实际走过的字符数。
手动走一遍
vocab={app:1, apple:2, UNK:-1}：apple 选长度 5 的 apple，输出 [2]；appbbbapp 先得到 app，再把三个 b 折成一个 -1，最后命中 app，输出 [1,-1,1]。空输入输出 []；只有 UNK 的词表把任意非空输入变为 [-1]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections.abc import Mapping
def tokenize(text: str, vocab: Mapping[str, int]) -> list[int]:
"""Greedy longest-match tokenizer; consecutive unknown chars form one run."""
if "UNK" not in vocab:
raise ValueError("vocab needs an UNK id")
words = {word: token for word, token in vocab.items() if word != "UNK"}
if "" in words:
raise ValueError("empty token would never advance the cursor")
unknown = vocab["UNK"]
if unknown in words.values():
raise ValueError("UNK id must be distinct from ordinary token ids")
trie: dict = {}
for word, token in words.items():
node = trie
for character in word:
node = node.setdefault(character, {})
node[None] = token
result: list[int] = []
i = 0
while i < len(text):
node = trie
j = i
best_end = i
best_token = None
while j < len(text) and text[j] in node:
node = node[text[j]]
j += 1
if None in node:
best_end = j
best_token = node[None]
if best_token is not None:
result.append(best_token)
i = best_end
else:
if not result or result[-1] != unknown:
result.append(unknown)
i += 1
return result
复杂度
建 Trie 用 O(Σ|word|) 时间与空间；文本长度 n、最大词长 L 时扫描最坏 O(nL) 时间，输出 O(n)。单词很长且大量相同前缀时仍可能重复扫描，不能宣称总是 O(n)。
易错点与追问
容易失分的边界
- 题目示意代码 append(vocab) 会追加字典而非 token id，直接复制会让样例类型错误。
- 先把所有未知字符全吞掉会错过后面可匹配的 app。
- 把贪心最长匹配误解成全局分词最少个数；两者可能产生不同答案。
- 允许空词会造成无限循环；把普通 token id 设为 UNK id 会让折叠规则混淆。
继续深挖
- 如果要全局最少 token 数或最高词频分数，如何改用 DP/Viterbi？
- 海量词表如何压缩 Trie，冷启动与在线更新如何处理？
- 跨块流式输入时，最右边保留多少未决字符才能保证最长匹配？
