基于您提供的 table_cell_matcher.py 代码,_match_html_rows_to_paddle_groups 方法实现了一个全局动态规划 (Global Dynamic Programming) 算法。
这个算法的核心目标是解决两个序列(HTML 表格行序列 vs PaddleOCR 文本行序列)的非线性对齐问题。
以下是该算法的详细原理解析:
传统的“贪婪算法”是逐行匹配,如果第 1 行匹配错了,第 2 行就会基于错误的位置继续找,导致“一步错,步步错”。
动态规划 (DP) 的思想是:不急着做决定。它会计算所有可能的匹配路径的得分,最后回溯找出一条总分最高的路径。即使中间某一行匹配分值较低,只要它能让整体结构最合理,DP 就会选择它。
在代码中,dp 矩阵定义如下:
dp[n_html][n_paddle]dp[i][j] 表示 “HTML 的前 i 行” 成功匹配到了 “Paddle 的前 j 组” 时,所能获得的最大累计得分。-inf (负无穷):表示此状态不可达(例如 HTML 第 5 行不可能匹配到 Paddle 第 1 组,因为顺序不对)。float:表示当前的累计相似度分数。为了性能,代码预先计算了 Paddle 组的合并文本。
merged_cache[(j, k)]:存储从 Paddle 第 j 组开始,合并 k 个组后的文本。处理 HTML 的第 0 行 (i=0)。
0 到 SEARCH_WINDOW 组。1 到 MAX_MERGE (4) 个 Paddle 组。相似度 - 跳过惩罚。dp[0][end_j]。这是算法最复杂的部分,遍历每一行 HTML (i 从 1 到 N)。对于当前行,有两种选择:
选择 A:跳过当前 HTML 行 (The "Skip" Strategy)
SKIP_HTML_PENALTY。代码:
score_skip = dp[i-1][prev_j] - SKIP_HTML_PENALTY
if score_skip > dp[i][prev_j]:
dp[i][prev_j] = score_skip
path[(i, prev_j)] = (prev_j, prev_j + 1) # 标记未消耗新组
作用:防止“链条断裂”。即使这一行匹配失败,状态也能传递给下一行。
选择 B:匹配 Paddle 组 (The "Match" Strategy)
prev_j。start_j = prev_j + 1 + gap。start_j 开始的 1 到 4 个 Paddle 组视为一行。代码:
total_score = prev_score + current_score
if total_score > dp[i][end_j]:
dp[i][end_j] = total_score
path[(i, end_j)] = (prev_j, start_j) # 记录路径
当填满 dp 表后,我们需要找出最优路径:
n_html-1) 中找到得分最高的 j。如果最后一行没匹配上,就往前找倒数第二行,以此类推。path 字典,从终点一步步回到起点。
path[(i, j)] 存储了 (prev_j, start_j)。start_j <= j:说明 HTML 行 i 对应了 Paddle 组 [start_j, ..., j]。start_j > j:说明 HTML 行 i 被跳过了(对应空列表)。DP 找的是“主干路径”,可能会漏掉一些没能进入最优路径的 Paddle 组(Orphans)。
MAX_MERGE = 4:
SEARCH_WINDOW = 15:
SKIP_HTML_PENALTY = 0.3:
SKIP_PADDLE_PENALTY = 0.1:
这个算法将表格行匹配问题转化为了一个寻找最大权值路径的图论问题。
(HTML行索引, Paddle组索引)这种方法极其鲁棒,能够同时处理:OCR 分行、OCR 漏行、OCR 噪音、HTML 空行以及轻微的顺序错乱问题。