简单树匹配算法STM-理论篇

内容来自论文

@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 对应的网页结构树表示：
在这里插入图片描述

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

简单树匹配算法

两棵树的匹配定义为:

对于映射，任意的结点对, ( 是非根结点)，成立，则结点对匹配.

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

算法流程

令 和为两棵树, 和 分别为和上的结点.

其中， 和是和的根结点， 和分别是和的第个和第个第1层子树.

（1）当和的标记相同时, 和的最大匹配为, 其中 是 和 的最大匹配。 可以通过动态规划算法得到。
（2）当和的标记不相同时，返回0

在这里插入图片描述

计算网页结构相似度

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

其中，, 分别表示两棵树中结点数目，SimpleTreeMatching 表示这两棵树的最大匹配结点数.

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