table_cell_matcher.py 36 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919
  1. """
  2. 表格单元格匹配器
  3. 负责将 HTML 表格单元格与 PaddleOCR bbox 进行匹配
  4. """
  5. from typing import List, Dict, Tuple, Optional
  6. from bs4 import BeautifulSoup
  7. import numpy as np
  8. try:
  9. from rapidfuzz import fuzz
  10. except ImportError:
  11. from fuzzywuzzy import fuzz
  12. try:
  13. from .text_matcher import TextMatcher
  14. from .bbox_extractor import BBoxExtractor
  15. except ImportError:
  16. from text_matcher import TextMatcher
  17. from bbox_extractor import BBoxExtractor
  18. class TableCellMatcher:
  19. """表格单元格匹配器"""
  20. def __init__(self, text_matcher: TextMatcher,
  21. x_tolerance: int = 3,
  22. y_tolerance: int = 10,
  23. skew_threshold: float = 0.3):
  24. """
  25. Args:
  26. text_matcher: 文本匹配器
  27. x_tolerance: X轴容差(用于列边界判断)
  28. y_tolerance: Y轴容差(用于行分组)
  29. skew_threshold: 倾斜校正阈值(度数)
  30. """
  31. self.text_matcher = text_matcher
  32. self.x_tolerance = x_tolerance
  33. self.y_tolerance = y_tolerance
  34. self.skew_threshold = skew_threshold # 倾斜校正阈值(度数)
  35. def enhance_table_html_with_bbox(self, html: str, paddle_text_boxes: List[Dict],
  36. start_pointer: int, table_bbox: Optional[List[int]] = None) -> Tuple[str, List[Dict], int, float]:
  37. """
  38. 为 HTML 表格添加 bbox 信息(优化版:使用行级动态规划)
  39. Returns:
  40. (enhanced_html, cells, new_pointer, skew_angle):
  41. 增强后的HTML、单元格列表、新指针位置、倾斜角度
  42. """
  43. soup = BeautifulSoup(html, 'html.parser')
  44. cells = []
  45. skew_angle = 0.0
  46. # 🔑 第一步:筛选表格区域内的 paddle boxes
  47. table_region_boxes, actual_table_bbox = self._filter_boxes_in_table_region(
  48. paddle_text_boxes[start_pointer:],
  49. table_bbox,
  50. html
  51. )
  52. if not table_region_boxes:
  53. print(f"⚠️ 未在表格区域找到 paddle boxes")
  54. return str(soup), cells, start_pointer, skew_angle
  55. print(f"📊 表格区域: {len(table_region_boxes)} 个文本框")
  56. # 🔑 第二步:将表格区域的 boxes 按行分组
  57. grouped_boxes, skew_angle = self._group_paddle_boxes_by_rows(
  58. table_region_boxes,
  59. y_tolerance=self.y_tolerance,
  60. auto_correct_skew=True,
  61. skew_threshold=self.skew_threshold
  62. )
  63. # 🔑 第三步:在每组内按 x 坐标排序
  64. for group in grouped_boxes:
  65. group['boxes'].sort(key=lambda x: x['bbox'][0])
  66. grouped_boxes.sort(key=lambda g: g['y_center'])
  67. # 🔑 第四步:智能匹配 HTML 行与 paddle 行组
  68. html_rows = soup.find_all('tr')
  69. row_mapping = self._match_html_rows_to_paddle_groups(html_rows, grouped_boxes)
  70. print(f" HTML行: {len(html_rows)} 行, 映射: {len([v for v in row_mapping.values() if v])} 个有效映射")
  71. # 🔑 第五步:遍历 HTML 表格,使用 DP 进行行内匹配
  72. for row_idx, row in enumerate(html_rows):
  73. group_indices = row_mapping.get(row_idx, [])
  74. if not group_indices:
  75. continue
  76. # 合并多个组的 boxes
  77. current_boxes = []
  78. for group_idx in group_indices:
  79. if group_idx < len(grouped_boxes):
  80. current_boxes.extend(grouped_boxes[group_idx]['boxes'])
  81. # 再次按 x 排序确保顺序
  82. current_boxes.sort(key=lambda x: x['bbox'][0])
  83. html_cells = row.find_all(['td', 'th'])
  84. if not html_cells:
  85. continue
  86. # 🎯 核心变更:使用行级 DP 替代原来的顺序匹配
  87. # 输入:HTML 单元格列表, OCR Box 列表
  88. # 输出:匹配结果列表
  89. dp_results = self._match_cells_in_row_dp(html_cells, current_boxes)
  90. print(f" 行 {row_idx + 1}: {len(html_cells)} 列, 匹配到 {len(dp_results)} 个单元格")
  91. # 解析 DP 结果并填充 cells 列表
  92. for res in dp_results:
  93. cell_idx = res['cell_idx']
  94. match_info = res['match_info']
  95. cell_element = html_cells[cell_idx]
  96. cell_text = cell_element.get_text(strip=True)
  97. matched_boxes = match_info['boxes']
  98. matched_text = match_info['text']
  99. score = match_info['score']
  100. # 标记 box 为已使用
  101. paddle_indices = []
  102. for box in matched_boxes:
  103. box['used'] = True
  104. paddle_indices.append(box.get('paddle_bbox_index', -1))
  105. # 计算合并后的 bbox (使用原始坐标 original_bbox 优先)
  106. merged_bbox = self._merge_boxes_bbox(matched_boxes)
  107. # 注入 HTML 属性
  108. cell_element['data-bbox'] = f"[{merged_bbox[0]},{merged_bbox[1]},{merged_bbox[2]},{merged_bbox[3]}]"
  109. cell_element['data-score'] = f"{score:.4f}"
  110. cell_element['data-paddle-indices'] = str(paddle_indices)
  111. # 构建返回结构 (保持与原函数一致)
  112. cells.append({
  113. 'type': 'table_cell',
  114. 'text': cell_text,
  115. 'matched_text': matched_text,
  116. 'bbox': merged_bbox,
  117. 'row': row_idx + 1,
  118. 'col': cell_idx + 1,
  119. 'score': score,
  120. 'paddle_bbox_indices': paddle_indices
  121. })
  122. print(f" 列 {cell_idx + 1}: '{cell_text[:15]}...' 匹配 {len(matched_boxes)} 个box (分值: {score:.1f})")
  123. # 计算新的指针位置 (逻辑保持不变:基于 used 标记)
  124. used_count = sum(1 for box in table_region_boxes if box.get('used'))
  125. new_pointer = start_pointer + used_count
  126. print(f" 总计匹配: {len(cells)} 个单元格")
  127. return str(soup), cells, new_pointer, skew_angle
  128. def _merge_boxes_bbox(self, boxes: List[Dict]) -> List[int]:
  129. """辅助函数:合并多个 box 的坐标"""
  130. if not boxes:
  131. return [0, 0, 0, 0]
  132. # 优先使用 original_bbox,如果没有则使用 bbox
  133. def get_coords(b):
  134. return b.get('original_bbox', b['bbox'])
  135. x1 = min(get_coords(b)[0] for b in boxes)
  136. y1 = min(get_coords(b)[1] for b in boxes)
  137. x2 = max(get_coords(b)[2] for b in boxes)
  138. y2 = max(get_coords(b)[3] for b in boxes)
  139. return [x1, y1, x2, y2]
  140. def _match_cells_in_row_dp(self, html_cells: List, row_boxes: List[Dict]) -> List[Dict]:
  141. """
  142. 使用动态规划进行行内单元格匹配
  143. 目标:找到一种分配方案,使得整行的匹配总分最高
  144. """
  145. n_cells = len(html_cells)
  146. n_boxes = len(row_boxes)
  147. # dp[i][j] 表示:前 i 个单元格 消耗了 前 j 个 boxes 的最大得分
  148. dp = np.full((n_cells + 1, n_boxes + 1), -np.inf)
  149. dp[0][0] = 0
  150. # path[i][j] = (prev_j, matched_info) 用于回溯
  151. path = {}
  152. # 允许合并的最大 box 数量
  153. MAX_MERGE = 5
  154. for i in range(1, n_cells + 1):
  155. cell = html_cells[i-1]
  156. cell_text = cell.get_text(strip=True)
  157. # 如果单元格为空,允许继承状态(相当于跳过该单元格)
  158. if not cell_text:
  159. for j in range(n_boxes + 1):
  160. if dp[i-1][j] > -np.inf:
  161. dp[i][j] = dp[i-1][j]
  162. path[(i, j)] = (j, None)
  163. continue
  164. # 遍历当前 box 指针 j
  165. for j in range(n_boxes + 1):
  166. # 策略 A: 当前单元格不匹配任何 box (Cell Missing / OCR漏检)
  167. if dp[i-1][j] > dp[i][j]:
  168. dp[i][j] = dp[i-1][j]
  169. path[(i, j)] = (j, None)
  170. # 策略 B: 当前单元格匹配了 k 个 boxes (从 prev_j 到 j)
  171. # 限制搜索范围:最多往前看 MAX_MERGE 个 box
  172. search_limit = max(0, j - MAX_MERGE)
  173. # 允许中间跳过少量噪音 box (例如 prev_j 到 j 之间跨度大,但只取了部分)
  174. # 但为了简化,这里假设是连续取用 row_boxes[prev_j:j]
  175. for prev_j in range(j - 1, search_limit - 1, -1):
  176. if dp[i-1][prev_j] == -np.inf:
  177. continue
  178. candidate_boxes = row_boxes[prev_j:j]
  179. # 组合文本 (使用空格连接)
  180. merged_text = " ".join([b['text'] for b in candidate_boxes])
  181. # 计算得分
  182. score = self._compute_match_score(cell_text, merged_text)
  183. # 只有及格的匹配才考虑
  184. if score > 50:
  185. new_score = dp[i-1][prev_j] + score
  186. if new_score > dp[i][j]:
  187. dp[i][j] = new_score
  188. path[(i, j)] = (prev_j, {
  189. 'text': merged_text,
  190. 'boxes': candidate_boxes,
  191. 'score': score
  192. })
  193. # --- 回溯找最优解 ---
  194. best_j = np.argmax(dp[n_cells])
  195. if dp[n_cells][best_j] == -np.inf:
  196. return []
  197. results = []
  198. curr_i, curr_j = n_cells, best_j
  199. while curr_i > 0:
  200. step_info = path.get((curr_i, curr_j))
  201. if step_info:
  202. prev_j, match_info = step_info
  203. if match_info:
  204. results.append({
  205. 'cell_idx': curr_i - 1,
  206. 'match_info': match_info
  207. })
  208. curr_j = prev_j
  209. curr_i -= 1
  210. return results[::-1]
  211. def _compute_match_score(self, cell_text: str, box_text: str) -> float:
  212. """
  213. 纯粹的评分函数:计算单元格文本与候选 Box 文本的匹配得分
  214. 包含所有防御逻辑
  215. """
  216. # 1. 预处理
  217. cell_norm = self.text_matcher.normalize_text(cell_text)
  218. box_norm = self.text_matcher.normalize_text(box_text)
  219. if not cell_norm or not box_norm:
  220. return 0.0
  221. # --- ⚡️ 快速防御 ---
  222. len_cell = len(cell_norm)
  223. len_box = len(box_norm)
  224. # 长度差异过大直接 0 分 (除非是包含关系且特征明显)
  225. if len_box > len_cell * 3 + 5:
  226. if len_cell < 5: return 0.0
  227. # --- 🔍 核心相似度计算 ---
  228. cell_proc = self._preprocess_text_for_matching(cell_text)
  229. box_proc = self._preprocess_text_for_matching(box_text)
  230. # A. Token Sort (解决乱序)
  231. score_sort = fuzz.token_sort_ratio(cell_proc, box_proc)
  232. # B. Partial (解决截断/包含)
  233. score_partial = fuzz.partial_ratio(cell_norm, box_norm)
  234. # C. Subsequence (解决噪音插入)
  235. score_subseq = 0.0
  236. if len_cell > 5:
  237. score_subseq = self._calculate_subsequence_score(cell_norm, box_norm)
  238. # --- 🛡️ 深度防御逻辑 ---
  239. # 1. 短文本防御
  240. if score_partial > 80:
  241. import re
  242. has_content = lambda t: bool(re.search(r'[a-zA-Z0-9\u4e00-\u9fa5]', t))
  243. # 纯符号防御
  244. if not has_content(cell_norm) and has_content(box_norm):
  245. if len_box > len_cell + 2: score_partial = 0.0
  246. # 微小碎片防御
  247. elif len_cell <= 2 and len_box > 8:
  248. score_partial = 0.0
  249. # 覆盖率防御
  250. else:
  251. coverage = len_cell / len_box if len_box > 0 else 0
  252. if coverage < 0.3 and score_sort < 45:
  253. score_partial = 0.0
  254. # 2. 子序列防御
  255. if score_subseq > 80:
  256. if len_box > len_cell * 1.5:
  257. import re
  258. if re.match(r'^[\d\-\:\.\s]+$', cell_norm) and len_cell < 12:
  259. score_subseq = 0.0
  260. # --- 📊 综合评分 ---
  261. final_score = max(score_sort, score_partial, score_subseq)
  262. # 精确匹配奖励
  263. if cell_norm == box_norm:
  264. final_score = 100.0
  265. elif cell_norm in box_norm:
  266. final_score = min(100, final_score + 5)
  267. return final_score
  268. def _filter_boxes_in_table_region(self, paddle_boxes: List[Dict],
  269. table_bbox: Optional[List[int]],
  270. html: str) -> Tuple[List[Dict], List[int]]:
  271. """
  272. 筛选表格区域内的 paddle boxes
  273. 策略:
  274. 1. 如果有 table_bbox,使用边界框筛选(扩展边界)
  275. 2. 如果没有 table_bbox,通过内容匹配推断区域
  276. Args:
  277. paddle_boxes: paddle OCR 结果
  278. table_bbox: 表格边界框 [x1, y1, x2, y2]
  279. html: HTML 内容(用于内容验证)
  280. Returns:
  281. (筛选后的 boxes, 实际表格边界框)
  282. """
  283. if not paddle_boxes:
  284. return [], [0, 0, 0, 0]
  285. # 🎯 策略 1: 使用提供的 table_bbox(扩展边界)
  286. if table_bbox and len(table_bbox) == 4:
  287. x1, y1, x2, y2 = table_bbox
  288. # 扩展边界(考虑边框外的文本)
  289. margin = 20
  290. expanded_bbox = [
  291. max(0, x1 - margin),
  292. max(0, y1 - margin),
  293. x2 + margin,
  294. y2 + margin
  295. ]
  296. filtered = []
  297. for box in paddle_boxes:
  298. bbox = box['bbox']
  299. box_center_x = (bbox[0] + bbox[2]) / 2
  300. box_center_y = (bbox[1] + bbox[3]) / 2
  301. # 中心点在扩展区域内
  302. if (expanded_bbox[0] <= box_center_x <= expanded_bbox[2] and
  303. expanded_bbox[1] <= box_center_y <= expanded_bbox[3]):
  304. filtered.append(box)
  305. if filtered:
  306. # 计算实际边界框
  307. actual_bbox = [
  308. min(b['bbox'][0] for b in filtered),
  309. min(b['bbox'][1] for b in filtered),
  310. max(b['bbox'][2] for b in filtered),
  311. max(b['bbox'][3] for b in filtered)
  312. ]
  313. return filtered, actual_bbox
  314. # 🎯 策略 2: 通过内容匹配推断区域
  315. print(" ℹ️ 无 table_bbox,使用内容匹配推断表格区域...")
  316. # 提取 HTML 中的所有文本
  317. from bs4 import BeautifulSoup
  318. soup = BeautifulSoup(html, 'html.parser')
  319. html_texts = set()
  320. for cell in soup.find_all(['td', 'th']):
  321. text = cell.get_text(strip=True)
  322. if text:
  323. html_texts.add(self.text_matcher.normalize_text(text))
  324. if not html_texts:
  325. return [], [0, 0, 0, 0]
  326. # 找出与 HTML 内容匹配的 boxes
  327. matched_boxes = []
  328. for box in paddle_boxes:
  329. normalized_text = self.text_matcher.normalize_text(box['text'])
  330. # 检查是否匹配
  331. if any(normalized_text in ht or ht in normalized_text
  332. for ht in html_texts):
  333. matched_boxes.append(box)
  334. if not matched_boxes:
  335. # 🔑 降级:如果精确匹配失败,使用模糊匹配
  336. print(" ℹ️ 精确匹配失败,尝试模糊匹配...")
  337. for box in paddle_boxes:
  338. normalized_text = self.text_matcher.normalize_text(box['text'])
  339. for ht in html_texts:
  340. similarity = fuzz.partial_ratio(normalized_text, ht)
  341. if similarity >= 70: # 降低阈值
  342. matched_boxes.append(box)
  343. break
  344. if matched_boxes:
  345. # 计算边界框
  346. actual_bbox = [
  347. min(b['bbox'][0] for b in matched_boxes),
  348. min(b['bbox'][1] for b in matched_boxes),
  349. max(b['bbox'][2] for b in matched_boxes),
  350. max(b['bbox'][3] for b in matched_boxes)
  351. ]
  352. # 🔑 扩展边界,包含可能遗漏的文本
  353. margin = 30
  354. expanded_bbox = [
  355. max(0, actual_bbox[0] - margin),
  356. max(0, actual_bbox[1] - margin),
  357. actual_bbox[2] + margin,
  358. actual_bbox[3] + margin
  359. ]
  360. # 重新筛选(包含边界上的文本)
  361. final_filtered = []
  362. for box in paddle_boxes:
  363. bbox = box['bbox']
  364. box_center_x = (bbox[0] + bbox[2]) / 2
  365. box_center_y = (bbox[1] + bbox[3]) / 2
  366. if (expanded_bbox[0] <= box_center_x <= expanded_bbox[2] and
  367. expanded_bbox[1] <= box_center_y <= expanded_bbox[3]):
  368. final_filtered.append(box)
  369. return final_filtered, actual_bbox
  370. # 🔑 最后的降级:返回所有 boxes
  371. print(" ⚠️ 无法确定表格区域,使用所有 paddle boxes")
  372. if paddle_boxes:
  373. actual_bbox = [
  374. min(b['bbox'][0] for b in paddle_boxes),
  375. min(b['bbox'][1] for b in paddle_boxes),
  376. max(b['bbox'][2] for b in paddle_boxes),
  377. max(b['bbox'][3] for b in paddle_boxes)
  378. ]
  379. return paddle_boxes, actual_bbox
  380. return [], [0, 0, 0, 0]
  381. def _group_paddle_boxes_by_rows(self, paddle_boxes: List[Dict],
  382. y_tolerance: int = 10,
  383. auto_correct_skew: bool = True,
  384. skew_threshold: float = 0.3) -> Tuple[List[Dict], float]:
  385. """
  386. 将 paddle_text_boxes 按 y 坐标分组(聚类)- 增强版本
  387. Args:
  388. paddle_boxes: Paddle OCR 文字框列表
  389. y_tolerance: Y 坐标容忍度(像素)
  390. auto_correct_skew: 是否自动校正倾斜
  391. Returns:
  392. 分组列表,每组包含 {'y_center': float, 'boxes': List[Dict]}
  393. """
  394. skew_angle = 0.0
  395. if not paddle_boxes:
  396. return [], skew_angle
  397. # 🎯 步骤 1: 检测并校正倾斜(使用 BBoxExtractor)
  398. if auto_correct_skew:
  399. skew_angle = BBoxExtractor.calculate_skew_angle(paddle_boxes)
  400. if abs(skew_angle) > skew_threshold:
  401. max_x = max(box['bbox'][2] for box in paddle_boxes)
  402. max_y = max(box['bbox'][3] for box in paddle_boxes)
  403. image_size = (max_x, max_y)
  404. print(f" 🔧 校正倾斜角度: {skew_angle:.2f}°")
  405. # 计算校正角度 (顺时针旋转)
  406. correction_angle = -skew_angle
  407. paddle_boxes = BBoxExtractor.correct_boxes_skew(
  408. paddle_boxes, correction_angle, image_size
  409. )
  410. # 🎯 步骤 2: 按校正后的 y 坐标分组
  411. boxes_with_y = []
  412. for box in paddle_boxes:
  413. bbox = box['bbox']
  414. y_center = (bbox[1] + bbox[3]) / 2
  415. boxes_with_y.append({
  416. 'y_center': y_center,
  417. 'box': box
  418. })
  419. # 按 y 坐标排序
  420. boxes_with_y.sort(key=lambda x: x['y_center'])
  421. groups = []
  422. current_group = None
  423. for item in boxes_with_y:
  424. if current_group is None:
  425. # 开始新组
  426. current_group = {
  427. 'y_center': item['y_center'],
  428. 'boxes': [item['box']]
  429. }
  430. else:
  431. if abs(item['y_center'] - current_group['y_center']) <= y_tolerance:
  432. current_group['boxes'].append(item['box'])
  433. # 更新组的中心
  434. current_group['y_center'] = sum(
  435. (b['bbox'][1] + b['bbox'][3]) / 2 for b in current_group['boxes']
  436. ) / len(current_group['boxes'])
  437. else:
  438. groups.append(current_group)
  439. current_group = {
  440. 'y_center': item['y_center'],
  441. 'boxes': [item['box']]
  442. }
  443. if current_group:
  444. groups.append(current_group)
  445. print(f" ✓ 分组完成: {len(groups)} 行")
  446. return groups, skew_angle
  447. def _match_html_rows_to_paddle_groups(self, html_rows: List,
  448. grouped_boxes: List[Dict]) -> Dict[int, List[int]]:
  449. """
  450. 智能匹配 HTML 行与 paddle 分组(增强版 DP:支持跳过 HTML 行,防止链条断裂)
  451. """
  452. if not html_rows or not grouped_boxes:
  453. return {}
  454. mapping = {}
  455. # 🎯 策略 1: 数量相等,简单 1:1 映射
  456. if len(html_rows) == len(grouped_boxes):
  457. for i in range(len(html_rows)):
  458. mapping[i] = [i]
  459. return mapping
  460. # --- 准备数据 ---
  461. # 提取 HTML 文本
  462. html_row_texts = []
  463. for row in html_rows:
  464. cells = row.find_all(['td', 'th'])
  465. texts = [self.text_matcher.normalize_text(c.get_text(strip=True)) for c in cells]
  466. html_row_texts.append("".join(texts))
  467. # 预计算所有组的文本
  468. group_texts = []
  469. for group in grouped_boxes:
  470. boxes = group['boxes']
  471. texts = [self.text_matcher.normalize_text(b['text']) for b in boxes]
  472. group_texts.append("".join(texts))
  473. n_html = len(html_row_texts)
  474. n_paddle = len(grouped_boxes)
  475. # ⚡️ 优化 3: 预计算合并文本
  476. MAX_MERGE = 4
  477. merged_cache = {}
  478. for j in range(n_paddle):
  479. current_t = ""
  480. for k in range(MAX_MERGE):
  481. if j + k < n_paddle:
  482. current_t += group_texts[j + k]
  483. merged_cache[(j, k + 1)] = current_t
  484. else:
  485. break
  486. # --- 动态规划 (DP) ---
  487. # dp[i][j] 表示:HTML 前 i 行 (0..i) 匹配到了 Paddle 的前 j 组 (0..j) 的最大得分
  488. # 初始化为负无穷
  489. dp = np.full((n_html, n_paddle), -np.inf)
  490. # 记录路径:path[i][j] = (prev_j, start_j)
  491. # prev_j: 上一行结束的 paddle index
  492. # start_j: 当前行开始的 paddle index (因为一行可能对应多个组)
  493. path = {}
  494. # 参数配置
  495. SEARCH_WINDOW = 15 # 向前搜索窗口
  496. SKIP_PADDLE_PENALTY = 0.1 # 跳过 Paddle 组的惩罚
  497. SKIP_HTML_PENALTY = 0.3 # 关键:跳过 HTML 行的惩罚
  498. # --- 1. 初始化第一行 ---
  499. # 选项 A: 匹配 Paddle 组
  500. for end_j in range(min(n_paddle, SEARCH_WINDOW + MAX_MERGE)):
  501. for count in range(1, MAX_MERGE + 1):
  502. start_j = end_j - count + 1
  503. if start_j < 0: continue
  504. current_text = merged_cache.get((start_j, count), "")
  505. similarity = self._calculate_similarity(html_row_texts[0], current_text)
  506. penalty = start_j * SKIP_PADDLE_PENALTY
  507. score = similarity - penalty
  508. # 只有得分尚可才作为有效状态
  509. if score > 0.1:
  510. if score > dp[0][end_j]:
  511. dp[0][end_j] = score
  512. path[(0, end_j)] = (-1, start_j)
  513. # 选项 B: 第一行就跳过 (虽然少见,但为了完整性)
  514. # 如果第一行跳过,相当于没有消耗任何 paddle 组,状态难以用 dp[0][j] 表达
  515. # 这里简化处理,假设第一行必须匹配点什么,或者由后续行修正
  516. # --- 2. 状态转移 ---
  517. for i in range(1, n_html):
  518. html_text = html_row_texts[i]
  519. # 获取上一行所有有效位置
  520. valid_prev_indices = [j for j in range(n_paddle) if dp[i-1][j] > -np.inf]
  521. # 剪枝
  522. if len(valid_prev_indices) > 30:
  523. valid_prev_indices.sort(key=lambda j: dp[i-1][j], reverse=True)
  524. valid_prev_indices = valid_prev_indices[:30]
  525. # 🛡️ 关键修复:允许跳过当前 HTML 行 (继承上一行的状态)
  526. # 如果跳过当前行,Paddle 指针 j 不变
  527. for prev_j in valid_prev_indices:
  528. score_skip = dp[i-1][prev_j] - SKIP_HTML_PENALTY
  529. if score_skip > dp[i][prev_j]:
  530. dp[i][prev_j] = score_skip
  531. # 记录路径:start_j = prev_j + 1 表示没有消耗新组 (空范围)
  532. path[(i, prev_j)] = (prev_j, prev_j + 1)
  533. # 如果是空行,直接跳过计算,仅保留继承的状态
  534. if not html_text:
  535. continue
  536. # 正常匹配逻辑
  537. for prev_j in valid_prev_indices:
  538. prev_score = dp[i-1][prev_j]
  539. max_gap = min(SEARCH_WINDOW, n_paddle - prev_j - 1)
  540. for gap in range(max_gap):
  541. start_j = prev_j + 1 + gap
  542. for count in range(1, MAX_MERGE + 1):
  543. end_j = start_j + count - 1
  544. if end_j >= n_paddle: break
  545. current_text = merged_cache.get((start_j, count), "")
  546. # 长度预筛选
  547. h_len = len(html_text)
  548. p_len = len(current_text)
  549. if h_len > 10 and p_len < h_len * 0.2:
  550. continue
  551. similarity = self._calculate_similarity(html_text, current_text)
  552. # 计算惩罚
  553. # 1. 跳过惩罚 (gap)
  554. # 2. 长度惩罚 (防止过度合并)
  555. len_penalty = 0.0
  556. if h_len > 0:
  557. ratio = p_len / h_len
  558. if ratio > 2.0: len_penalty = (ratio - 2.0) * 0.2
  559. current_score = similarity - (gap * SKIP_PADDLE_PENALTY) - len_penalty
  560. # 只有正收益才转移
  561. if current_score > 0.1:
  562. total_score = prev_score + current_score
  563. if total_score > dp[i][end_j]:
  564. dp[i][end_j] = total_score
  565. path[(i, end_j)] = (prev_j, start_j)
  566. # --- 3. 回溯找最优路径 ---
  567. # 找到最后一行得分最高的结束位置
  568. best_end_j = -1
  569. max_score = -np.inf
  570. # 优先找最后一行,如果最后一行没匹配上,往前找
  571. found_end = False
  572. for i in range(n_html - 1, -1, -1):
  573. for j in range(n_paddle):
  574. if dp[i][j] > max_score:
  575. max_score = dp[i][j]
  576. best_end_j = j
  577. best_last_row = i
  578. if max_score > -np.inf:
  579. found_end = True
  580. break
  581. mapping = {}
  582. used_groups = set()
  583. if found_end:
  584. curr_i = best_last_row
  585. curr_j = best_end_j
  586. while curr_i >= 0:
  587. if (curr_i, curr_j) in path:
  588. prev_j, start_j = path[(curr_i, curr_j)]
  589. # 如果 start_j <= curr_j,说明消耗了 Paddle 组
  590. # 如果 start_j > curr_j,说明是跳过 HTML 行 (空范围)
  591. if start_j <= curr_j:
  592. indices = list(range(start_j, curr_j + 1))
  593. mapping[curr_i] = indices
  594. used_groups.update(indices)
  595. else:
  596. mapping[curr_i] = []
  597. curr_j = prev_j
  598. curr_i -= 1
  599. else:
  600. break
  601. # 填补未匹配的行
  602. for i in range(n_html):
  603. if i not in mapping:
  604. mapping[i] = []
  605. # --- 4. 后处理:未匹配组的归属 (Orphans) ---
  606. unused_groups = [i for i in range(len(grouped_boxes)) if i not in used_groups]
  607. if unused_groups:
  608. print(f" ℹ️ 发现 {len(unused_groups)} 个未匹配的 paddle 组: {unused_groups}")
  609. for unused_idx in unused_groups:
  610. unused_group = grouped_boxes[unused_idx]
  611. unused_y_min = min(b['bbox'][1] for b in unused_group['boxes'])
  612. unused_y_max = max(b['bbox'][3] for b in unused_group['boxes'])
  613. above_idx = None
  614. below_idx = None
  615. above_distance = float('inf')
  616. below_distance = float('inf')
  617. for i in range(unused_idx - 1, -1, -1):
  618. if i in used_groups:
  619. above_idx = i
  620. above_group = grouped_boxes[i]
  621. max_y_box = max(above_group['boxes'], key=lambda b: b['bbox'][3])
  622. above_y_center = (max_y_box['bbox'][1] + max_y_box['bbox'][3]) / 2
  623. above_distance = abs(unused_y_min - above_y_center)
  624. break
  625. for i in range(unused_idx + 1, len(grouped_boxes)):
  626. if i in used_groups:
  627. below_idx = i
  628. below_group = grouped_boxes[i]
  629. min_y_box = min(below_group['boxes'], key=lambda b: b['bbox'][1])
  630. below_y_center = (min_y_box['bbox'][1] + min_y_box['bbox'][3]) / 2
  631. below_distance = abs(below_y_center - unused_y_max)
  632. break
  633. closest_used_idx = None
  634. merge_direction = ""
  635. if above_idx is not None and below_idx is not None:
  636. if above_distance < below_distance:
  637. closest_used_idx = above_idx
  638. merge_direction = "上方"
  639. else:
  640. closest_used_idx = below_idx
  641. merge_direction = "下方"
  642. elif above_idx is not None:
  643. closest_used_idx = above_idx
  644. merge_direction = "上方"
  645. elif below_idx is not None:
  646. closest_used_idx = below_idx
  647. merge_direction = "下方"
  648. if closest_used_idx is not None:
  649. target_html_row = None
  650. for html_row_idx, group_indices in mapping.items():
  651. if closest_used_idx in group_indices:
  652. target_html_row = html_row_idx
  653. break
  654. if target_html_row is not None:
  655. if unused_idx not in mapping[target_html_row]:
  656. mapping[target_html_row].append(unused_idx)
  657. mapping[target_html_row].sort()
  658. print(f" • 组 {unused_idx} 合并到 HTML 行 {target_html_row}({merge_direction}行)")
  659. used_groups.add(unused_idx)
  660. # 🔑 策略 4: 第三遍 - 按 y 坐标排序每行的组索引
  661. for row_idx in mapping:
  662. if mapping[row_idx]:
  663. mapping[row_idx].sort(key=lambda idx: grouped_boxes[idx]['y_center'])
  664. return mapping
  665. def _calculate_similarity(self, text1: str, text2: str) -> float:
  666. """
  667. 计算两个文本的相似度,结合字符覆盖率和序列相似度 (性能优化版)
  668. """
  669. if not text1 or not text2:
  670. return 0.0
  671. len1, len2 = len(text1), len(text2)
  672. # ⚡️ 优化 1: 长度快速检查
  673. # 如果长度差异过大(例如一个 50 字符,一个 2 字符),直接认为不匹配
  674. if len1 > 0 and len2 > 0:
  675. min_l, max_l = min(len1, len2), max(len1, len2)
  676. if max_l > 10 and min_l / max_l < 0.2:
  677. return 0.0
  678. # 1. 字符覆盖率 (Character Overlap)
  679. from collections import Counter
  680. c1 = Counter(text1)
  681. c2 = Counter(text2)
  682. intersection = c1 & c2
  683. overlap_count = sum(intersection.values())
  684. coverage = overlap_count / len1 if len1 > 0 else 0
  685. # ⚡️ 优化 2: 覆盖率低时跳过昂贵的 fuzz 计算
  686. # 如果字符重叠率低于 30%,说明内容基本不相关,没必要算序列相似度
  687. if coverage < 0.3:
  688. return coverage * 0.7
  689. # 2. 序列相似度 (Sequence Similarity)
  690. # 使用 token_sort_ratio 来容忍一定的乱序
  691. seq_score = fuzz.token_sort_ratio(text1, text2) / 100.0
  692. return (coverage * 0.7) + (seq_score * 0.3)
  693. def _preprocess_text_for_matching(self, text: str) -> str:
  694. """
  695. 预处理文本:在不同类型的字符(如中文和数字/英文)之间插入空格,
  696. 以便于 token_sort_ratio 更准确地进行分词和匹配。
  697. """
  698. if not text:
  699. return ""
  700. import re
  701. # 1. 在中文和非中文(数字/字母)之间插入空格
  702. # 例如: "2024年" -> "2024 年", "ID号码123" -> "ID号码 123"
  703. text = re.sub(r'([\u4e00-\u9fa5])([a-zA-Z0-9])', r'\1 \2', text)
  704. text = re.sub(r'([a-zA-Z0-9])([\u4e00-\u9fa5])', r'\1 \2', text)
  705. return text
  706. def _calculate_subsequence_score(self, target: str, source: str) -> float:
  707. """
  708. 计算子序列匹配得分 (解决 OCR 噪音插入问题)
  709. 例如: Target="12345", Source="12(date)34(time)5" -> Score close to 100
  710. """
  711. # 1. 仅保留字母和数字,忽略符号干扰
  712. t_clean = "".join(c for c in target if c.isalnum())
  713. s_clean = "".join(c for c in source if c.isalnum())
  714. if not t_clean or not s_clean:
  715. return 0.0
  716. # 2. 贪婪匹配子序列
  717. t_idx, s_idx = 0, 0
  718. matches = 0
  719. while t_idx < len(t_clean) and s_idx < len(s_clean):
  720. if t_clean[t_idx] == s_clean[s_idx]:
  721. matches += 1
  722. t_idx += 1
  723. s_idx += 1
  724. else:
  725. # 跳过 source 中的噪音字符
  726. s_idx += 1
  727. # 3. 计算得分
  728. match_rate = matches / len(t_clean)
  729. # 如果匹配率太低,直接返回
  730. if match_rate < 0.8:
  731. return match_rate * 100
  732. # 4. 噪音惩罚 (防止 Target="1", Source="123456789" 这种误判)
  733. # 计算噪音长度
  734. noise_len = len(s_clean) - matches
  735. # 允许一定比例的噪音 (例如日期时间插入,通常占总长度的 30%-50%)
  736. # 如果噪音长度超过目标长度的 60%,开始扣分
  737. penalty = 0
  738. if noise_len > len(t_clean) * 0.6:
  739. excess_noise = noise_len - (len(t_clean) * 0.6)
  740. penalty = excess_noise * 0.5 # 每多一个噪音字符扣 0.5 分
  741. penalty = min(penalty, 20) # 最多扣 20 分
  742. final_score = (match_rate * 100) - penalty
  743. return max(0, final_score)