题目重点：用前缀最优状态找最高概率切分，条件概率追问把上一词纳入状态，说明未知词、平局与复杂度。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版要求整串被词表完全覆盖，不允许未知词；每个词有 (0,1] 概率，初版切分分数是各词概率乘积。无可行切分返回 None，平局取词序列字典序最小。
- 条件版用 P(word|previous)，首词 previous='<BOS>'；仅一阶 Markov 转移。题目只说“往前多看一层”，未公开确切条件表、结束符概率、长度归一化或其它语言模型语义。
- 代码用 Fraction 保存有理数字符串以便独立对照；长文本生产实现可改 log 概率，比较平局时要定义数值容差。
解题路线
- 独立概率：设 dp[i] 为覆盖 text[:i] 的最高分与切分路径。对每个可匹配的词 w，把 dp[i]×P(w) 更新到 dp[i+len(w)]；比较先按分数，再按确定的平局规则。
- 条件概率打破只存 dp[i] 的最优子结构：两个到达同一位置的路径若末词不同，下一词概率可能不同。状态必须是 dp[i][lastWord]，转移乘 P(next|lastWord)，所有末词状态到终点后再取最优。
- DFS+memo 也能实现，但 memo 键在条件版必须包含位置和上一词；只记位置会错误合并未来概率不同的路径。若词表大，用 Trie 沿文本前进，避免每个位置扫描全部词。
- 若题目要返回概率而非切分，应同时返回终点分数；若未知词可回退或允许大小写归一化，须将其惩罚和规范化纳入模型，而非默默跳过字符。
手动走一遍
训练文本 `linkedin` 可切成 `linked`+`in`，概率 1/2×1/2=1/4；也可作 `linkedin`，概率 1/3，后者胜。条件例 `aa`：P(a|BOS)=1、P(a|a)=1/2，路径 a,a 得 1/2；P(aa|BOS)=1/4，前者胜。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training variants of LinkedIn's vocabulary-probability segmentation prompt.
The original post states independent token probabilities and a conditional
follow-up, but does not specify unknown-word or tie behavior. This file uses
exact rational probabilities and lexicographically smallest tie-breaking.
"""
from fractions import Fraction
def best_independent(text: str, probabilities: dict[str, str]) -> tuple[str, ...] | None:
if "" in probabilities:
raise ValueError("empty token would create a cycle")
n = len(text)
best: list[tuple[Fraction, tuple[str, ...]] | None] = [None] * (n + 1)
best[0] = (Fraction(1), ())
for i in range(n):
if best[i] is None:
continue
score, path = best[i]
for word, raw_probability in probabilities.items():
p = Fraction(raw_probability)
if not 0 < p <= 1:
raise ValueError("probability outside (0,1]")
if text.startswith(word, i):
end = i + len(word)
candidate = (score * p, path + (word,))
old = best[end]
if old is None or candidate[0] > old[0] or (candidate[0] == old[0] and candidate[1] < old[1]):
best[end] = candidate
return None if best[n] is None else best[n][1]
def best_conditional(
text: str, conditional: dict[tuple[str, str], str]
) -> tuple[str, ...] | None:
"""P(next | previous), with '<BOS>' as previous before the first token."""
vocabulary = {word for _, word in conditional}
if "" in vocabulary:
raise ValueError("empty token would create a cycle")
n = len(text)
states: list[dict[str, tuple[Fraction, tuple[str, ...]]]] = [dict() for _ in range(n + 1)]
states[0]["<BOS>"] = (Fraction(1), ())
for i in range(n):
for previous, (score, path) in states[i].items():
for word in vocabulary:
raw = conditional.get((previous, word))
if raw is None or not text.startswith(word, i):
continue
p = Fraction(raw)
if not 0 < p <= 1:
raise ValueError("probability outside (0,1]")
end = i + len(word)
candidate = (score * p, path + (word,))
old = states[end].get(word)
if old is None or candidate[0] > old[0] or (candidate[0] == old[0] and candidate[1] < old[1]):
states[end][word] = candidate
if not states[n]:
return None
return min(states[n].values(), key=lambda item: (-item[0], item[1]))[1]
if __name__ == "__main__":
assert best_independent("linkedin", {"linked": "1/2", "in": "1/2", "linkedin": "1/3"}) == ("linkedin",)
assert best_conditional("aa", {("<BOS>", "a"): "1", ("a", "a"): "1/2", ("<BOS>", "aa"): "1/4"}) == ("a", "a")
复杂度
文本长度 N、词表 V、最长词长 L：朴素初版扫描匹配 O(NVL) 字符检查，状态空间 O(N) 加路径输出；条件版每个位置最多 V 个上一词、每态试 V 个词，O(NV²L) 时间、O(NV) 状态。Trie 可减词匹配成本，精确有理数乘法的位复杂度另计。
易错点与追问
容易失分的边界
- 条件版仍只缓存位置，丢掉上一词上下文。
- 直接乘大量浮点小概率导致下溢。
- 允许空词产生零长度循环。
- 只给最高分而没说明同分路径的稳定输出。
- 把未在词表里的字符悄悄丢掉。
继续深挖
- 概率是 P(word) 还是 P(word|previous)？
- 词表数百万时如何用 Trie/前缀索引提速？
- 如果依赖前两个词，DP 状态和成本如何变？
- 怎么处理未知词、空串和概率为零？
- 怎样用 log-sum 而非 Viterbi max 求所有切分的总概率？
