table_cell_matcher.py 38 KB

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