1. TEDS从表格识别到网页结构的跨越第一次接触TEDSTree Edit Distance-based Similarity是在处理表格识别项目时。当时我们团队正为OCR系统输出的表格结构准确性发愁——传统方法只能检查非空单元格的直接关系对空单元格错位这类常见错误完全无能为力。直到发现TEDS这个基于树编辑距离的评估方法才真正解决了表格结构相似度量化的难题。TEDS的核心思想非常巧妙把表格结构转化为树形表示。想象一棵倒置的树根节点是整个表格下面分出thead表头和tbody表体两个分支每行是tr节点最终叶子节点是包含rowspan/colspan属性的td单元格。通过计算两棵树之间的编辑距离就能准确量化它们的相似程度。这个方法的通用性让我惊讶。在网页开发中DOM树本质上也是树结构。比如一个电商商品页顶层是 节点下面分出 和 里又包含、等节点——这与表格的树形表示惊人地相似。于是我开始尝试将TEDS迁移到网页比对场景。2. 树编辑距离的魔法原理要理解TEDS得先掌握树编辑距离Tree Edit Distance这个基础概念。它就像字符串编辑距离的升级版计算把一棵树变成另一棵树需要的最少操作次数。这些操作包括插入节点在目标树添加新节点删除节点从原树移除节点替换节点修改节点类型或属性移动节点调整节点在树中的位置以网页DOM树为例假设原始树是div ├─ h1 └─ p修改后的树是section ├─ h2 └─ div编辑距离为2h1→h2替换div→section替换。TEDS值就是1 - (编辑距离 / 最大树尺寸)结果越接近1说明相似度越高。实际计算时我们常用Zhang-Shasha算法。它通过动态规划填表时间复杂度O(n^4)。虽然看起来复杂但Python已有现成实现from zss import simple_distance tree1 Node(div, [Node(h1), Node(p)]) tree2 Node(section, [Node(h2), Node(div)]) distance simple_distance(tree1, tree2)3. 网页结构比对的实战技巧在电商价格监控系统中我们成功应用TEDS实现了竞品网页结构比对。具体分三步走3.1 DOM树预处理首先用BeautifulSoup解析HTML过滤掉