表格行匹配算法可视化图示.md 17 KB
表格行匹配算法可视化图示
📐 数据结构可视化
输入数据
HTML表格行（7行）:
┌─────────────────────────────────────────────────────────┐
│ 行0: 部门Department: 01372403999 柜员Search Teller... │
├─────────────────────────────────────────────────────────┤
│ 行1: 账号/卡号Account/Card No: 6222621010026732125... │
├─────────────────────────────────────────────────────────┤
│ 行2: 查询起日Query Starting Date: 2023-08-12... │
├─────────────────────────────────────────────────────────┤
│ 行3: 查询时间Query Time: 2024年08月12日 11:21:23... │
├─────────────────────────────────────────────────────────┤
│ 行4: 证件种类 ID Type: 第二代居民身份证... │
├─────────────────────────────────────────────────────────┤
│ 行5: Serial Num | Trans Date | Trans Time | ... (表头) │
├─────────────────────────────────────────────────────────┤
│ 行6: 1 | 2023-08-12 | 13:04:52 | 网上银行卡转入... │
└─────────────────────────────────────────────────────────┘
OCR文本分组（48组）:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 组0 │ 组1 │ 组2 │ 组3 │ 组4 │ 组5 │ ... │ 组46│ 组47│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│部门 │账号 │查询 │查询 │证件 │序号 │ ... │司 │9646 │
│信息 │信息 │起日 │时间 │信息 │表头 │ │2023 │42s │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
🔄 DP状态转移可视化
阶段1：初始化第一行（i=0）
HTML行0的匹配搜索空间:
┌─────────────────────────────────────────────────────────────┐
│ OCR组索引: 0 1 2 3 4 5 ... 18 │
│ ┌────┐ │
│ │组0 │ ← 单独匹配 │
│ └────┘ │
│ ┌────┬────┐ │
│ │组0 │组1 │ ← 合并2组 │
│ └────┴────┘ │
│ ┌────┬────┬────┐ │
│ │组0 │组1 │组2 │ ← 合并3组 (最优: 得分0.98) │
│ └────┴────┴────┘ │
│ ┌────┬────┬────┬────┐ │
│ │组0 │组1 │组2 │组3 │ ← 合并4组 │
│ └────┴────┴────┴────┘ │
└─────────────────────────────────────────────────────────────┘
DP状态矩阵（初始化后）:
OCR组索引 j →
HTML 0 1 2 3 4 5 ... 47
行↓
0 [0.98] - - - - - ... -
↑
最优匹配: HTML行0 → OCR组[0,1,2]
阶段2：处理第二行（i=1）
从 dp[0][2] = 0.98 出发，搜索HTML行1的匹配:
搜索窗口（SEARCH_WINDOW=15）:
┌─────────────────────────────────────────────────────────────┐
│ 上一行结束位置: 组2 │
│ │
│ 搜索范围: 组3 到 组17 (最多向前15个组) │
│ │
│ 组索引: 2 [3] [4] [5] [6] ... [17] │
│ ↑ │ │ │ │ │ │
│ 起点 └────┴────┴────┴─────────┘ │
│ 搜索窗口 │
└─────────────────────────────────────────────────────────────┘
匹配尝试:
┌─────────────────────────────────────────────────────────────┐
│ gap=0, start_j=3, count=1 → end_j=3 │
│ 匹配: 组3单独 │
│ 相似度: 0.85, 得分: 0.98 + 0.85 = 1.83 │
│ │
│ gap=0, start_j=3, count=2 → end_j=4 │
│ 匹配: 组3+组4 │
│ 相似度: 0.92, 得分: 0.98 + 0.92 = 1.90 ✅ (最优) │
│ │
│ gap=1, start_j=4, count=1 → end_j=4 │
│ 匹配: 组4单独 │
│ 相似度: 0.20, 得分: 0.98 + 0.20 = 1.18 │
└─────────────────────────────────────────────────────────────┘
DP状态矩阵更新:
OCR组索引 j →
HTML 0 1 2 3 4 5 ... 47
行↓
0 [0.98] - - - - - ... -
1 - - - 1.83 [1.90] - ... -
↑ ↑
候选1 最优匹配
阶段3：完整DP过程（简化版）
DP状态矩阵（完整过程）:
OCR组索引 j →
HTML 0 1 2 3 4 5 6 7 ... 40 41 ... 47
行↓
0 [0.98] - - - - - - - ... - - ... -
│
└─→ 匹配组[0,1,2]
1 - - - 1.83 [1.90] - - - ... - - ... -
│ │
└─────┴─→ 匹配组[3,4]
2 - - - - - [2.85] - - ... - - ... -
│
└─→ 匹配组[5,6]
3 - - - - - - [3.80] - ... - - ... -
│
└─→ 匹配组[7,8,9]
4 - - - - - - - [4.75] ... - - ... -
│
└─→ 匹配组[10,11]
5 - - - - - - - - ... [5.20] - ... -
│
└─→ 匹配组[12..39]
6 - - - - - - - - ... - - ... [5.50]
│
└─→ 匹配组[40..47] ✅
🔍 回溯路径可视化
从最优终点回溯
最优终点: dp[6][47] = 5.50
回溯过程:
┌─────────────────────────────────────────────────────────────┐
│ 步骤1: (i=6, j=47) │
│ path[(6, 47)] = (prev_j=45, start_j=46) │
│ → HTML行6匹配OCR组[46, 47] │
│ → 移动到 (i=5, j=45) │
│ │
│ 步骤2: (i=5, j=45) │
│ path[(5, 45)] = (prev_j=39, start_j=40) │
│ → HTML行5匹配OCR组[40..45] │
│ → 移动到 (i=4, j=39) │
│ │
│ 步骤3: (i=4, j=39) │
│ path[(4, 39)] = (prev_j=37, start_j=38) │
│ → HTML行4匹配OCR组[38, 39] │
│ → 移动到 (i=3, j=37) │
│ │
│ ... 继续回溯 ... │
│ │
│ 步骤7: (i=0, j=2) │
│ path[(0, 2)] = (prev_j=-1, start_j=0) │
│ → HTML行0匹配OCR组[0, 1, 2] │
│ → 回溯结束 │
└─────────────────────────────────────────────────────────────┘
最终匹配结果:
HTML行0 ──────→ OCR组[0, 1, 2]
HTML行1 ──────→ OCR组[3, 4]
HTML行2 ──────→ OCR组[5, 6]
HTML行3 ──────→ OCR组[7, 8, 9]
HTML行4 ──────→ OCR组[10, 11]
HTML行5 ──────→ OCR组[12, 13, ..., 39]
HTML行6 ──────→ OCR组[40, 41, ..., 47]
🎯 关键概念图示
1. 合并文本缓存（merged_cache）
merged_cache[(start_j, count)] = 从start_j开始合并count个组的文本
示例: start_j=0, count=3
┌─────┬─────┬─────┐
│ 组0 │ 组1 │ 组2 │ → 合并文本: "部门department:...账号/卡号...查询起日..."
└─────┴─────┴─────┘
↑ ↑ ↑
└─────┴─────┘
count=3
2. Gap搜索机制
上一行结束位置: prev_j = 2
搜索窗口:
┌─────────────────────────────────────────────────────────────┐
│ prev_j=2 │
│ │ │
│ │ gap=0: start_j=3 (紧接上一行) │
│ │ gap=1: start_j=4 (跳过1个组) │
│ │ gap=2: start_j=5 (跳过2个组) │
│ │ ... │
│ │ gap=14: start_j=16 (最多跳过14个组) │
│ │ │
│ └──────────────────────────────────────────────────────────┘
│ SEARCH_WINDOW = 15
└─────────────────────────────────────────────────────────────┘
3. 跳过HTML行的处理
场景: HTML行i无法匹配任何OCR组
处理方式:
┌─────────────────────────────────────────────────────────────┐
│ HTML行i-1 → OCR组j (得分: 2.5) │
│ │ │
│ ├─→ HTML行i匹配OCR组j+1 (正常匹配) │
│ │ │
│ └─→ HTML行i跳过 (继承状态，得分: 2.5 - 0.3 = 2.2) │
│ → HTML行i+1可以从OCR组j开始匹配 │
└─────────────────────────────────────────────────────────────┘
📊 性能优化可视化
剪枝优化
剪枝前: 上一行有50个有效状态
┌─────────────────────────────────────────────────────────────┐
│ valid_prev_indices = [0, 1, 2, ..., 49] (50个状态) │
│ │
│ 需要计算: 50 × 15 × 4 = 3000 次匹配 │
└─────────────────────────────────────────────────────────────┘
剪枝后: 只保留得分最高的30个
┌─────────────────────────────────────────────────────────────┐
│ valid_prev_indices = [2, 5, 8, ..., 47] (30个状态) │
│ │
│ 需要计算: 30 × 15 × 4 = 1800 次匹配 (减少40%) │
└─────────────────────────────────────────────────────────────┘
长度预筛选
HTML文本长度: 100字符
OCR文本长度: 10字符
长度比例: 10 / 100 = 0.1 < 0.2 (阈值)
┌─────────────────────────────────────────────────────────────┐
│ ❌ 直接跳过，不计算相似度 │
│ 节省计算时间 │
└─────────────────────────────────────────────────────────────┘
🔄 完整流程图
开始
│
├─→ 提取HTML行文本 (7行)
│
├─→ 提取OCR组文本 (48组)
│
├─→ 检查行数是否相等?
│ ├─→ 是 → 验证对角线匹配
│ │ ├─→ 匹配良好 → 1:1映射 → 结束
│ │ └─→ 匹配不佳 → 继续DP
│ └─→ 否 → 继续DP
│
├─→ 预计算合并文本缓存 (merged_cache)
│
├─→ 初始化第一行 (i=0)
│ └─→ 搜索前15+4个组，找到最佳匹配
│
├─→ DP状态转移 (i=1..6)
│ ├─→ 获取上一行有效状态
│ ├─→ 剪枝（保留前30个）
│ ├─→ 允许跳过HTML行
│ └─→ 正常匹配（搜索窗口15，最多合并4组）
│
├─→ 回溯找最优路径
│ └─→ 从最优终点回溯，构建映射关系
│
├─→ 后处理
│ ├─→ 处理未匹配的OCR组（Orphans）
│ └─→ 按Y坐标排序
│
└─→ 返回映射结果
💡 实际案例数据流
用户提供的实际数据
HTML行数: 7
OCR组数: 48
HTML行0文本: '部门department:01372403999柜员searchteller:ebf0000...'
OCR组0文本: '部门department:01372403999柜员searchteller:ebf0000...'
→ 相似度: 0.95+ ✅
HTML行5文本: 'serialnum序号transdate交易日期transtime交易时间...'
OCR组5-39文本: 'serialtransdatetranstimetradingtypedcflg...'
→ 相似度: 0.85+ ✅
HTML行6文本: '12023-08-1213:04:52网上银行卡转入贷cr33.52...'
OCR组40-47文本: '2023-08-1213:04:5233.52554.5210*****69...'
→ 相似度: 0.80+ ✅
这个算法通过动态规划，成功地将7个HTML行与48个OCR组进行了智能匹配！