文档介绍：第卷第期武汉理工大学学报. 。
年月、胭.
:./..—...
基于加权层次结构的文档相似度算法
孙霞,程宏斌
常熟理工学院计算机科学与工程学院,常熟
摘要: 提出了一种基于加权层次结构的文档相似度算法。根据文档的层次结构信息,该算法能够快速的
进行文档相似度的计算,并识别出具有相同结构的文档,实验表明该算法有效降低了解决问题的复杂度。该算法
还可以用于文档聚类、文档结构抽取、文档的变换检测等方面,具有较好的普遍适用性。
关键词: ; 相似度; 层次结构
中图分类号: 文献标识码: 文章编号:——

,
,,,
: .
.
..
,,
,.
: ; ;
随着互联网技术的发展,以其合理的数据组织结构和可扩展的特性,成为各种复杂数据¨特别是
半结构化数据表示和处理的良好工具,越来越多的应用领域已经将其作为主要的存储格式和传输媒体。因
此对文档进行有效地处理,从而实现对文档的检索、自动分类和聚类成为研究的热点,而文档
处理的核心问题是计算文档的相似度。
树的编辑距离方法是计算文档相似度的一种常用的方法,但是当树要描述文档的全部结构
信息时,树的结构将会很复杂庞大,这样很难处理,并且时间复杂度很大;另一方面,对于文档中存在的
重复元素和嵌套元素的问题树结构不能很好处理。文献提出一个自底向上、逐级比较、逐级整合的
文档相似度计算方法,首先计算个文档叶子节点的相似度,然后依次计算叶子节点的父节点、父节点的父
节点的相似度,直到计算根节点之间的相似度,完成两个文档的相似度计算;这种方法要求待比较的文档结
构类似,只适合由同一或者定义的文档。文献提出用傅里叶变换技术作为计算文
档相似度的机制,基本思想是将的结构转换为一个数字序列,然后使用傅里叶变换将该序列转换为一
收稿日期:—.
基金项目:湖北省教育厅青年科学基金.
作者简介:孙霞一,女,讲师.—:.
第卷第期孙霞,程宏斌:基于加权层次结构的文档相似度算法
个信号波,通过计算两个文档信号波之间的关系来度量两个文档之问的相似度;该方法比较新颖,但是不够
直观,而且时间复杂度较大。在文档对象模型的基础上提出了一种基于层次结构的模型来描述文档的
结构,并根据这种模型给出了相应的相似度的计算方法。这种模型比树结构要简单,并且体现了文档中每个
元素所在的层次信息,能够快速有效的进行相似度计算,实验表明该算法降低了解决问题的复杂度。
文档层次结构
. 文档树
一个文档可表示为一棵带标记的结点树
Ⅳ,,,其中
表示根结点,任一棵文档树有且仅有一个根结点;
Ⅳ表示结点的集合,每个结点∈对应文档中的一个元素或属性,结点用其元素名或属性名作标
记。
表示边的集合,每一对, ∈建立Ⅳ中两个节点之间的关系。如果“, ∈,那么则
称是的父亲, 是的孩子。
图给出了个文档对应的结点树。
【
图文档树
实际上,文档中通常包含有大量的重复,这使得结点树的结构庞大并且嵌套层次很深。即使
是基于相同或的文档,但是由于结点的重复和嵌套也会使两棵结点树具有较大的结
构差异:一个文档中的部分可能与另外一个文档中的不同部分相似;另外同样的子树