## TEDS算法详解
详细说明TEDS(Tree-Edit-Distance-based Similarity)算法及其在PaddleOCR中的应用。
### 1. 算法概述
**TEDS (Tree-Edit-Distance-based Similarity)** 是专门用于**表格识别评估**的指标，由IBM研究院开发。它通过计算预测表格HTML结构与真实表格HTML结构之间的树编辑距离来评估表格识别的准确性。
### 2. 核心原理
#### 2.1 树编辑距离计算
TEDS基于**APTED (All-Pairs Tree Edit Distance)**算法：
```python
def evaluate(self, pred, true):
"""计算单个样本的TEDS分数"""
# 解析HTML为树结构
pred = html.fromstring(pred, parser=parser)
true = html.fromstring(true, parser=parser)
# 转换为TableTree格式
tree_pred = self.load_html_tree(pred)
tree_true = self.load_html_tree(true)
# 计算树编辑距离
distance = APTED(tree_pred, tree_true, CustomConfig()).compute_edit_distance()
# 归一化为相似度分数
return 1.0 - (float(distance) / n_nodes)
```
#### 2.2 TableTree结构
```python
class TableTree(Tree):
def __init__(self, tag, colspan=None, rowspan=None, content=None, *children):
self.tag = tag # HTML标签 (table, tr, td等)
self.colspan = colspan # 列跨度
self.rowspan = rowspan # 行跨度
self.content = content # 单元格内容
self.children = list(children) # 子节点
```
### 3. 评估指标计算
#### 3.1 节点比较策略
```python
class CustomConfig(Config):
def rename(self, node1, node2):
"""比较两个节点的相似度"""
# 结构不匹配的惩罚
if ((node1.tag != node2.tag) or
(node1.colspan != node2.colspan) or
(node1.rowspan != node2.rowspan)):
return 1.0
# td节点的内容比较
if node1.tag == "td":
if node1.content or node2.content:
return Levenshtein.normalized_distance(node1.content, node2.content)
return 0.0
```
#### 3.2 多种比较模式
**1. 标准模式 (CustomConfig)**
- 同时考虑结构和内容
- 使用Levenshtein距离比较文本内容
**2. 忽略短文本模式 (CustomConfig_del_short)**
```python
if len(node1_content) < 3:
node1_content = ["####"] # 替换短文本为占位符
```
**3. 忽略空格模式 (CustomConfig_del_block)**
```python
while " " in node1_content:
node1_content.pop(node1_content.index(" ")) # 移除所有空格
```
### 4. 在PaddleOCR中的应用
#### 4.1 性能表现
根据文档显示，在PubTabNet数据集上的评估结果：
| 算法 | Acc | TEDS | Speed |
|------|-----|------|-------|
| EDD | - | 88.30% | - |
| TableRec-RARE | 71.73% | **93.88%** | 779ms |
| SLANet | 76.31% | **95.89%** | 766ms |
#### 4.2 评估流程
```mermaid
graph TD
A[输入表格图像] --> B[文本检测OCR]
B --> C[表格结构识别]
C --> D[OCR结果与结构匹配]
D --> E[生成预测HTML]
E --> F[加载真实HTML]
F --> G[HTML解析为树结构]
G --> H[计算树编辑距离]
H --> I[归一化为TEDS分数]
B --> B1[检测框坐标dt_boxes]
B --> B2[识别结果rec_res]
C --> C1[表格结构structure_res]
D --> D1[match函数匹配]
G --> G1[TableTree转换]
G --> G2[tokenize单元格内容]
H --> H1[APTED算法]
H --> H2[CustomConfig比较策略]
style A fill:#e1f5fe
style I fill:#e8f5e8
style H fill:#fff3e0
```
### 5. 具体使用方法
#### 5.1 表格评估脚本
使用[`eval_table.py`]eval_table.py )进行完整的表格识别评估：
```bash
python ppstructure/table/eval_table.py \
--det_model_dir=inference/en_PP-OCRv3_det_infer \
--rec_model_dir=inference/en_PP-OCRv3_rec_infer \
--table_model_dir=inference/en_ppstructure_mobile_v2.0_SLANet_infer \
--image_dir=train_data/table/pubtabnet/val/ \
--rec_char_dict_path=../ppocr/utils/dict/table_dict.txt \
--table_char_dict_path=../ppocr/utils/dict/table_structure_dict.txt \
--det_limit_side_len=736 \
--det_limit_type=min \
--rec_image_shape=3,32,320 \
--gt_path=path/to/gt.txt
```
#### 5.2 GT数据格式
```txt
PMC5755158_010_00.png | Weaning | Week 15 | Off-test |
| Weaning | – | – | – |
| Week 15 | – | 0.17 ± 0.08 | 0.16 ± 0.03 |
| Off-test | – | 0.80 ± 0.24 | 0.19 ± 0.09 |
```
#### 5.3 直接使用TEDS类
```python
from ppstructure.table.table_metric import TEDS
# 初始化TEDS评估器
teds = TEDS(n_jobs=16) # 支持多进程加速
# 批量评估HTML
pred_htmls = ["", ...]
true_htmls = ["", ...]
scores = teds.batch_evaluate_html(pred_htmls, true_htmls)
avg_teds = sum(scores) / len(scores)
print(f"TEDS: {avg_teds:.4f}")
```
### 6. 算法特点
#### 6.1 综合评估能力
- **结构评估**: 表格的行列结构、跨度属性
- **内容评估**: 单元格内的文本内容准确性
- **整体一致性**: 表格的完整性和一致性
#### 6.2 灵活配置
- **structure_only**: 仅评估结构，忽略内容
- **ignore_nodes**: 忽略特定HTML节点
- **多进程支持**: 大规模数据集的高效评估
#### 6.3 鲁棒性
- **容错处理**: 处理不完整或格式错误的HTML
- **多种比较策略**: 适应不同的评估需求
- **归一化分数**: 0-1范围内的直观分数
### 7. 评估输出示例
```bash
# 运行评估后的输出
[2022/08/10 05:22:23] ppocr INFO: teds: 95.89
```
### 8. 与其他指标的对比
| 指标 | 评估维度 | 适用场景 | 优势 |
|------|----------|----------|------|
| **TEDS** | 结构+内容 | 表格识别 | 综合评估、国际标准 |
| Acc | 仅结构 | 结构识别 | 简单直观 |
| BLEU | 序列相似度 | 文本生成 | 流畅度评估 |
| Edit Distance | 字符级别 | 文本识别 | 精确匹配 |
TEDS作为表格识别领域的黄金标准，为PaddleOCR的表格识别算法提供了权威、可靠的评估机制，特别适用于需要同时考虑结构准确性和内容准确性的复杂表格识别任务。