OCR 文字纠错
P6085. OCR 文字纠错
场次:2026年10月23日-AI方向 · 来源:CodeFun2000 P6085
题目描述
某智能终端内置了一套基于朴素贝叶斯的字符级 OCR 纠错模块。可识别的字符集为 26 个小写英文字母 ,记 。
模块用两组统计量描述模型:
- 发射计数 :训练语料里,真实字符 被识别成 的次数;
- 先验计数 :训练语料里,真实字符 出现的次数。
发射概率与先验概率均做加 拉普拉斯平滑( 为正整数):
纠错规则:对待纠错串里的每个字符 单独决策
若多个候选同时取到最大得分,则取字典序最小者()。
自训练流程:除了 条人工标注的「识别串 → 真实串」样本外,系统还保存着 条只有 OCR 输出、没有真实文本的样本,并迭代 轮。每一轮依次做两件事:
用当前模型逐条解码这 条未标注样本,得到伪真实串;
用 条标注样本,再加上这 条「识别串, 伪真实串」,重新统计 与 ,得到本轮的新模型。
每轮重新统计时,伪标注只使用本轮的,不与上一轮的累积;原始的 条标注每轮都参与。
轮结束后,用最终的模型对测试串纠错并输出。
数值稳定性:为避免浮点误差,比较两个候选 、 时应使用整数交叉相乘:
其中 ,。分母 与候选 无关,比较时可以约去。
输入格式
第一行四个整数 、、、,依次表示带标注样本数、未标注样本数、迭代轮数与平滑系数。
接下来 行,每行两个等长字符串 与 ,表示第 条带标注样本的识别结果与真实文本。
再接下来 行,每行一个字符串,表示一条未标注样本的 OCR 输出。
最后一行一个字符串,表示待纠错的测试 OCR 串。
所有字符串只含小写字母。
输出格式
输出一行一个字符串,表示测试串经最终模型纠错后的结果。
数据范围
- ,
- ,
- 所有字符串的长度 满足
- 同一条标注样本的两个字符串长度相等
示例
示例 1
输入:
1 3 1 2
pc ok
q
q
q
pq输出:
kk说明:
初始模型只有一条标注 ,即 、、,其余字符的计数全为 。三条未标注样本都是 ,而 从未作为任何字符的识别结果出现,此时 与 的得分同为 ,并列按字典序取 ,于是第一轮把三条 都伪标注成 。重新统计后 上多出 、,再用它解码测试串 : 处 的得分 已高于 的 , 处 的得分 也最大,输出 。若 , 处 的 高于 的 ,结果会是 。
示例 2
输入:
3 0 0 1
nkc art
nkd arm
nke ant
nk输出:
ar说明:
三条标注里 一直被识别成 (共 次)、 一直被识别成 (共 次),而 分别对应到 各一次。测试串 的第一位 上候选 的得分 明显高于其他候选;第二位 上候选 的得分 最高,输出 。
示例 3
输入:
2 1 2 1
bx cd
by cd
bz
bz输出:
cc说明:
初始模型里 与 的先验同为 ,而 只被识别成 (两次),所以测试串 中的 解码为 ; 没有任何观测, 与 的得分同为 ,并列取 。第一轮把 伪标注成 ,重新统计后 、,第二轮 上 的得分升到 ,伪标注仍是 ,最终模型输出 。
解题思路
整件事其实是四个动作的循环
题面把流程写得很细,去掉描述性的部分,剩下的就是四个动作:
- 数计数:把 条标注逐字符对齐,累加 与 ;
- 解码:给一个识别串,逐字符在 26 个候选里取分数最高的那个;
- 伪标注:用当前模型解码 条未标注样本,得到「识别串 → 伪真实串」;
- 重新统计: 条标注 + 本轮 条伪标注,从零再数一遍。
第 3、4 步合起来重复 轮(每轮先解码出伪标注,再用它和 条标注重数一遍),最后用最终模型解码测试串。全程没有需要「想」的地方,正确性完全等于把口径复现准确——这也意味着口径上有几处必须留意:分数用整数比、候选平局取小、伪标注每轮不累积。
分数比较:先把与候选无关的分母约掉,再交叉相乘
分母里第二个括号 对所有候选 都是同一个数(它是全部先验计数之和加 ),比较时可以直接丢掉。于是每个候选只剩一个分式:
、 都是整数,比较两个分数用交叉相乘,永远不碰浮点:
if num * best_den > best_num * den: # num/den > best_num/best_den
best_c, best_num, best_den = c, num, den平局怎么办:题目要求取字典序最小的候选。让 从 a 开始按字母升序遍历,只在严格大于时才替换当前保存的候选,先到者(字母更小的那个)就自然留在 best_c 上——和排序里「升序遍历 + 严格比较」是同一个套路,不需要单独写平局分支。
def decode(emit, prior, denom, s):
res = []
for ch in s:
co = ord(ch) - 97
best_c = 0
best_num = (emit[0][co] + alpha) * (prior[0] + alpha)
best_den = denom[0]
for c in range(1, 26): # 升序遍历
num = (emit[c][co] + alpha) * (prior[c] + alpha)
den = denom[c]
if num * best_den > best_num * den: # 严格大于才替换
best_c, best_num, best_den = c, num, den
res.append(chr(best_c + 97))
return "".join(res)三张表:emit、prior、每个候选自己的分母
统计只需要一遍 zip:真实字符是行、识别字符是列。
def build(pairs):
emit = [[0] * 26 for _ in range(26)] # emit[真][识]
prior = [0] * 26
for ocr, truth in pairs:
for o, c in zip(ocr, truth): # 逐字符对齐
emit[ord(c) - 97][ord(o) - 97] += 1
prior[ord(c) - 97] += 1
denom = [sum(row) + alpha * 26 for row in emit] # D_c = 行和 + αK
return emit, prior, denomdenom[c] 就是公式里的 :它是「真实字符 被识别成任意字符」的总次数再加 。注意行和要按全部 26 列求和,而不是只求出现过的列——平滑项 本身就是按整个字符集算的。
自训练:每轮的伪标注都从零参与,不累积
这一条是题面专门点出来的:伪标注只使用本轮的。所以循环里每一轮都是「拿 条原始标注 + 本轮 条伪标注,重新 build 一次」,而不是把伪标注追加到一个不断变长的列表里。
emit, prior, denom = build(labeled)
for _ in range(rounds):
pseudo = [(u, decode(emit, prior, denom, u)) for u in unlabeled]
emit, prior, denom = build(labeled + pseudo) # 每轮从零重数labeled + pseudo 每次都是一份新的完整列表,上一轮的 pseudo 在下一轮被整体丢弃。
为什么平局真的会出现
从来没有作为识别结果出现过时(示例 1 的 就是这样),所有候选的 都是 ,分数退化成
它只由「先验有多高」和「这个字符的历史发射总量有多大」决定。示例 1 里 ,而且两个字符的发射总量都是 ,于是两个分数都是 ——一模一样。此时平局规则不是「理论上应该写」的细节,而是直接决定伪标注内容的那一步:取 (字母更小)会让 、;取 则会让 涨上去,最终输出变成 。
完整代码实现
import sys
K = 26
ORD_A = ord("a")
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
p = 0
n_lab = int(data[p])
m_unlab = int(data[p + 1])
rounds = int(data[p + 2])
alpha = int(data[p + 3])
p += 4
labeled = []
for _ in range(n_lab):
labeled.append((data[p].decode(), data[p + 1].decode()))
p += 2
unlabeled = [data[p + i].decode() for i in range(m_unlab)]
p += m_unlab
test = data[p].decode()
def build(pairs):
"""统计 emit[c][o]、prior[c],并预先把每个候选的分母算好。"""
emit = [[0] * K for _ in range(K)]
prior = [0] * K
for ocr, truth in pairs:
for o, c in zip(ocr, truth):
co = ord(o) - ORD_A
cc = ord(c) - ORD_A
emit[cc][co] += 1
prior[cc] += 1
denom = [sum(emit[c]) + alpha * K for c in range(K)]
return emit, prior, denom
def decode(emit, prior, denom, s):
"""逐字符取 argmax P(o|c)P(c);并列保留字典序更小的 c。"""
res = []
for ch in s:
co = ord(ch) - ORD_A
best_c = 0
best_num = (emit[0][co] + alpha) * (prior[0] + alpha)
best_den = denom[0]
for c in range(1, K): # 升序遍历
num = (emit[c][co] + alpha) * (prior[c] + alpha)
den = denom[c]
if num * best_den > best_num * den: # 交叉相乘,严格大于才替换
best_c, best_num, best_den = c, num, den
res.append(chr(best_c + ORD_A))
return "".join(res)
emit, prior, denom = build(labeled)
for _ in range(rounds):
pseudo = [(u, decode(emit, prior, denom, u)) for u in unlabeled]
emit, prior, denom = build(labeled + pseudo) # 每轮从零重数,不累积
print(decode(emit, prior, denom, test))
if __name__ == "__main__":
solve()示例推演
示例 1:一轮自训练把 从 改成
、、、,唯一一条标注是 。
初始模型:逐字符对齐得到
- ,,;
- ,,;
- 其余字符:,。
第一轮伪标注:三条未标注样本都是 。对 和 来说 ,所以
分数 、、其余 。前两个并列,取字典序小的 。三条 全部伪标注成 。
重新统计( 条标注 + 条伪标注):
| 字符 | 行 | 行和 | ||
|---|---|---|---|---|
解码测试串 :
- 字符 :,,其余 。比较 与 :,所以 。
- 字符 :,,其余 。 最大(),所以 。
输出 kk。
顺带看 的情形:模型还是初始那一份, 处 得 、 得 ,; 处两者仍并列取 。结果 ok——一轮自训练就把第一位翻了过来,靠的正是 从 涨到 带来的 这一项。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每轮重统计 + 浮点评分 | 每个候选算两次除法,并列要靠 级容差判 | ||
| 每轮重统计 + 整数交叉相乘(最优) | 比较只做整数乘法,并列是精确相等,不依赖容差 |
两行的渐进式一样,因为「每个字符把 26 个候选都试一遍」这件事无法回避。差别在常数和正确性:、、、 时,最重的一轮是 次比较,纯 Python 也在零点几秒量级;而浮点版在「两个候选本该并列」时会看到 级的差,平局规则随时可能失效。
空间上 emit 是 的表,prior、denom 各 26 项,其余都是字符串本身。
易错点总结
1. 平局用 >= 替换,挑到了字母更大的那个
if num * best_den >= best_num * den: 会把「并列」也当成「更优」,于是升序遍历里后到的(字母更大的)候选人获胜。示例 1 第一步就翻车: 上 与 同为 ,用 >= 会选中 ,三条伪标注变成 , 涨到 ,最终输出 而不是 。判据必须是严格大于——这样平局时先到的(字母更小的)留在 best_c 上。
2. 比较时丢掉 ,只比
N_c=(emit[c][o]+\alpha)(prior[c]+\alpha) 只是分子, 才是分数。写成「谁 大谁赢」时,一个历史发射总量很大的字符会因为分母被忽略而虚高。三组样例里各字符的行和都只在 到 之间,丢掉分母恰好没有改变任何一个字符的赢家,所以样例全绿;换一份行和相差几十倍的语料,解码结果就会整片漂移。
3. 伪标注跨轮累积
循环里写成 labeled.append((u, pseudo))(或把上一轮的 pseudo 留着继续用),第 轮统计时就会混进前面各轮的伪标注。示例 3 第二轮的计数会从 变成 、 从 变成 ,答案恰好仍是 ;但只要某个字符在伪标注里反复出现,它的 prior 就会被重复计数,几轮之后就压过真实标注的影响。口径是「每轮用 条原始标注 + 本轮 条伪标注重数一遍」,代码里对应 build(labeled + pseudo) 每次新建列表。