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

2021-07-21 本文已影响0人 ltochange

内容来自论文

@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$ 上的结点.

$A=\left(R_{\mathrm{A}}, A_{1}, \cdots, A_{m}\right) \\ B=\left(R_{\mathrm{B}}, B_{1}, \cdots,B_{n}\right)$

其中， $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}}$ 是 $\left\langle A_{1}, A_{2}, \cdots, A_{m}\right\rangle$ 和 $\left\langle B_{1},B_{2}, \cdots, B_{n}\right\rangle$ 的最大匹配。 $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文档也就越相似。

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

将HTML网页表示成树结构

简单树匹配算法

计算网页结构相似度

猜你喜欢

热点阅读