内容来自论文

@article{何昕2007基于简单树匹配算法的,
  title={基于简单树匹配算法的Web页面结构相似性度量},
  author={何昕 and 谢志鹏},
  journal={计算机研究与发展},
  number={z3},
  pages={1--6},
  year={2007}
}

简单树匹配算法SimPle Tree Matching 最初在软件工程上用于比较两个计算机程序，后引入网页结构相似度计算。主要考虑页面的结构信息，假设含有相似信息的页面也具有相似的结构。

将HTML网页表示成树结构

原始的HTML文档可以通过深度优先遍历树重构出来

文档 1 和 2 对应的网页表示：

文档 1 和 2 对应的html表示：

文档 1 和 2 对应的网页结构树表示：

简单树匹配不允许结点的替换和跨层匹配，从而大大提高了算法的运行效率。

简单树匹配算法

两棵树的匹配定义为:

对于映射$M$，任意的结点对$(i,j)$,$(i,j)\in M$ ($i,j$ 是非根结点)，$(parent(i),parent(j))\in M$成立，则结点对$(i,j)$匹配.

最大匹配是指匹配到的结点对数目最多的匹配.

算法流程

令$A$ 和$B$为两棵树, $i$ 和 $j$ 分别为$A$和$B$上的结点.

$$\begin{gathered} A=\left(R_{\mathrm{A}},A_1,\cdots ,A_m\right) \\ B=\left(R_{\mathrm{B}},B_1,\cdots ,B_n\right) \end{gathered}$$

其中，$R_{\mathrm{A}}$ 和$R_{\mathrm{B}}$是$A$和$B$的根结点，$A_i$ 和$B_j$分别是$A$和$B$的第$i$个和第$j$个第1层子树.

（1）当$R_A$和$R_B$的标记相同时, $A$和$B$的最大匹配为$M_{A,B}+1$, 其中$M_{A,B}$ 是$⟨A_1,A_2,\cdots ,A_m⟩$ 和 $⟨B_1,B_2,\cdots ,B_n⟩$ 的最大匹配。$M_{\mathrm{A},\mathrm{B}}$ 可以通过动态规划算法得到。
（2）当$R_A$和$R_B$的标记不相同时，返回0

计算网页结构相似度

给定两个HTML文档，它们对应的结构树为 $T_1$，$T_2$。$T_1$ 和 $T_2$ 中每一个结点标记对应HTML文件中一个标签.
定义$T_1$ 与 $T_2$ 的相似度为：

$$\text{ Similarity }\left(T_1,T_2\right)=\frac{\text{ Simple TreeMatching }\left(T_1,T_2\right)}{\left(\left|T_1\right|+\left|T_2\right|\right)/2}$$

其中，$\left|T_1\right|$,$\left|T_2\right|$ 分别表示两棵树中结点数目，SimpleTreeMatching$\left(T_1,T_2\right)$ 表示这两棵树的最大匹配结点数.

两棵树的最大匹配结点数越多，则两颗树越相似，它们所代表的 HTML文档也就越相似。