XML文档相似性的仿真研究

XML文档相似性的计算是XML文档分类中的一个难题。文中描述了一种基于结构的方法，通过序列化模式挖掘方法，挖掘出两个文档之间的最大相似路径，从而可以通过计算最大相似的路径的节点数目和所有路径的节点数目的比值，得到两个文档之间的相似度。文章提出了一种新的最小化XML文档的方法，并且综合考虑了文档节点的语义相似度和结构相似度，从而进一步地提高了计算文档相似度的精度。实验表明，该方法有着良好的应用前景。     

基于语义和结构的XML文档相似度的计算方法

个性化信息服务通过了解用户的兴趣爱好,为不同的用户提供不同的信息服务。XML是一种标示语言,是Web文档表示和交换的常用相关标准,因此XML文档之间相似度计算问题对于个性化推荐与信息检索非常重要,为此提出了一个计算XML文档之间的语义和结构相似度的方法XMLSim。首先,基于节点标记对之间的语义相似度和编辑距离计算节点标记对之间的相似度;在分析了路径上节点具有的偏序关系之后,将路径之间相似度问题抽象为最大相似子序列(MSS,Maximal Similar Subsequence)问题,并利用动态规划对MSS问题求解得到路径相似度NpathSim。最后,XML文档之间的相似度XMLSim通过路径集合之间的最大NPathSim的平均值得到。     

基于路径特征的XML文档结构相似性度量

针对现有XML文档结构相似性度量方法大多不能完全反映XML文档的结构特征,相似度计算结果精确度不高,导致聚类效果不够理想的问题,提出一种改进的相似度计算方法 SSPF(Similarity based on Sequence,Position and Frequency)。该方法充分利用提取的DOM树路径信息,对树路径间序列和位置的相似度计算进行优化,并考虑了路径频率对相似度的影响,使得文档间的相似性更为合理。实验结果表明,SSPF方法具有更加准确的相似度计算结果,聚类的各项评价指标均有所提高。     

基于核矩阵学习的XML文档相似度量方法

XML文档作为一种新的数据形式,成为当前的研究热点.XML文档间相似度的计算是XML文档分析、管理及文本挖掘的基础.结构链接向量模型(structuredlink vector model,简称SLVM)是一种综合考虑XML文档结构信息与内容信息进行XML文档相似度量的方法.体现XML文档结构单元关系的核矩阵在结构链接向量模型中扮演着重要角色.为自动捕获XML文档结构单元关系,提出了两种核矩阵的学习算法,分别是基于支持向量机(support vector machine,简称SVM)的回归学习算法和基于矩阵迭代的学习算法.相似搜索实验对比结果表明,基于核矩阵学习方法的XML文档相似度量方法的准确性明显优于其他方法.进一步实验表明,基于矩阵迭代学习的核矩阵学习算法与基于支持向量机的回归学习算法相比,不仅具有更高的准确性,而且所需训练文档更少、计算代价更小.     

基于矩阵存储的XML相似度检测算法*

以完成对杂乱无章的XML文档进行自动分类为目的,提出了一种基于下三角矩阵的XML文档表示方法,经过数学建模后,XML文档间的相似度比较问题转化成了矩阵之间的相似度计算。为了验证其执行效果,在采用该算法进行相似度计算的基础上,运用最近邻分类算法对XML测试文档集进行自动分类。实验结果表明,这种基于矩阵存储的XML相似度计算方法应用于分类中效果良好。     

用带权重的pq-gram算法计算XML文档相似度

XML文档聚类是高效管理XML文档的重要手段,XML文档相似度计算正是其中的关键步骤。pq-gram算法是解决XML文档相似度计算问题的有效手段,但忽略了XML文档结点的有序性。带权重的pq-gram算法是在此基础上,依据XML文档的结构性,首先为结点赋予相应权重,然后基于结点的权重对pq-gram赋予权重,最后将设定的权重应用到XML文档相似度计算中。实验结果表明,带权重的pq-gram算法更好地描述结点在XML文档相似度计算中的贡献度,提高了XML文档相似度计算的精度。     

基于XML文档相似性的构件聚类分析

构件聚类时,提出了一种计算基于XML描述的构件问相似度的递归算法,能有效度量构件XML描述文档包含的结构和语义信息.构造文档相似矩阵,利用遗传算法将高维样本映射到二维平面上,使用k-means算法聚类,获得全局最优的构件聚类.最后,在构件库测试模型上进行实验,实验结果表明,基于XML相似度的构件聚类算法在构件查询实践中具有可行性和有效性.     

基于模式的XML文档相似度算法

提出一种基于XML模式的文档相似度算法,其中,XML模式间的相似度是XML文档聚类的重要依据,元素是XML模式的主体,模式的相似度由元素相似度组成,该算法综合考虑XML模式中元素的结构和语义信息,进一步提高计算相似度的精度。另外,该算法通过计算XML模式间的相似度,可以降低算法的复杂度,提高聚类的准确性,易于提取聚簇的通用XML模式。     

基于张量的XML相似度计算方法

扩展标记语言(XML) 带有一定的结构和语义信息, 与普通文本相比, XML具有描述精确、表现形式丰富等特点, 但同时也使得传统的自然语言处理和数据挖掘等技术不能直接应用. 根据XML内容和结构并非独立, 内容影响结构, 结构作用于内容, 提出一种基于张量的XML特征降维及综合相似度计算方法. 针对XML文档, 使用张量表示并采用基于最大互信息的方法对其进行降维, 采用将XML结构和内容相融合的综合相似度度量方法确定结构和内容的内在联系及共同作用方式, 提高XML综合相似度计算性能. 实验及结果分析验证了所提出方法的有效性.

     

基于TreeMiner算法的XML文档结构相似度量方法*

提出了一种基于TreeMiner算法挖掘频繁子树的文档结构相似度量方法,解决了传统的距离编辑法计算代价高而路径匹配法无法处理重复标签的问题。该方法架构了一个新的检索模型—频繁结构向量模型,给出了文档的结构向量表示和权重函数,构造了XML文档结构相似度量计算公式;同时从数据结构和挖掘程序上对TreeMiner 算法进行了改进,使其更适合大文档数据集的结构挖掘。实验结果表明,该方法具有很高的计算精度和准确率。     

Authorization Translation for XML Document Transformation

XML access control models proposed in the literature enforce access restrictions directly on the structure and content of an XML document. Therefore access authorization rules (authorizations, for short), which specify access rights of users on information within an XML document, must be revised if they do not match with changed structure of the XML document. In this paper, we present two authorization translation problems. The first is a problem of translating instance-level authorizations for an XML document. The second is a problem of translating schema-level authorizations for a collection of XML documents conforming to a DTD. For the first problem, we propose an algorithm that translates instance-level authorizations of a source XML document into those for a transformed XML document by using instance-tree mapping from the transformed document instance to the source document instance. For the second problem, we propose an algorithm that translates value-independent schema-level authorizations of non-recursive source DTD into those for a non-recursive target DTD by using schema-tree mapping from the target DTD to the source DTD. The goal of authorization translation is to preserve authorization equivalence at instance node level of the source document. The XML access control models use path expressions of XPath to locate data in XML documents. We define property of the path expressions (called node-reducible path expressions) that we can transform schema-level authorizations of value-independent type by schema-tree mapping. To compute authorizations on instances of schema elements of the target DTD, we need to identify the schema elements whose instances are located by a node-reducible path expression of a value-independent schema-level authorization. We give an algorithm that carries out path fragment containment test to identify the schema elements whose instances are located by a node-reducible path expression.     

概率XML文件树结点概率的查询算法

概率XML文件是概率数据的网络数据交换和表示标准,元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型,定义了概率XML文件树的基本路径和扩展路径,提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法,根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法,并通过实验进行了比较分析.实验结果表明:这两种方法是有效的;与前一种方法比较,后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询,计算过程较简单.     

基于编辑图的XML文档相似性研究

目前关于XML文档相似性算法有很多种,其中基于编辑距离的方法是很重要的一类。目前已发表的基于编辑距离的算法中,编辑图算法由于其计算高效率的特点成为研究的出发点。首先介绍了编辑图算法的思想,由于它在计算过程中对同层兄弟节点的顺序有很强的依赖性,因此不能准确有效地比较数据无序的数据中心的XML文档相似性。针对该问题,在编辑图算法思想的基础上,结合路径算法的思想提出拆分编辑图算法。实验结果表明,拆分编辑图算法降低了编辑图算法中对兄弟节点次序的依赖性,更适合于数据中心的XML文档相似性比较,而且所得结果更加准确有效。     

基于编码的XML关系数据库存储

在XML的发展过程中,如何有效地利用关系数据库技术存储和查询XML数据已经成为一个研究热点．提出了一种基于前、后序编码的XML关系数据库存储方法,该方法采用的模式映射方法能够使基于不同DTD（或schema）的XML文档保存在同一个关系表中,支持快速的XML路径查询,且具有较高的XML文档重组效率．对该方法中递归模式的处理技术也进行了讨论．实验表明,与XRel,Florescu和Kossman等人提出的XML关系数据库存储方法相比,该方法能够缩短复杂XML路径查询（如带条件谓词约束的路径查询）的响应时间．     

一种基于XML文档关键字检索的结构索引

XML数据索引对其检索效率有较大的影响。在深入分析现有XMI、结构索引之后,结合XML文档特点,提出了一种基于关键字检索的结构索引--LSS(Level Structure Summary) . LSS采用了把具有相同标签路径的结点进行合并的策略,具有高效判断结点之间同构异构关系的能力。实现了LSS索引生成算法CSCAN,并在LSS索引的基础上设计了XML关键字检索算法LSSearch。该算法依据LSS索引,将各个关键字的原始倒排表集合分拆成不同类型的子集合,最后在所有子集合上进行查询。实验结果表明,LSS可以帮助减少XML文档中关键字倒排表的规模,提高检索效率。     

一种基于Schema的XML索引结构

XML Schema作为一种描述XML文档模式信息即结构信息的标准，对于XML索引的建立及查询效率的提高有着重要的作用。现有的大部分XML索引结构着重研究XML文档的结构查询，而对于XML文档的更新支持却不多，对无效查询也不能作出快速的判断。该文基于已有的XML文档的编码方式，提出了一种基于Schema的XML索引结构，不仅能支持基于有效性验证的动态更新，使得XML文档和XML Schema保持一致，而且对用户提出的无效的路径查询也能在较短时间内作出判断。     

XSD: A Hierarchical Access Method for Indexing XML Schemata

Search operations and browsing facilities over an XML document database require special support at the physical level. Typical search operations involve path queries. This paper proposes a hierarchical access method to support such operations and to facilitate browsing. It advocates the idea of searching large XML collections by administering efficiently XML schemata. The proposed approach may be used for indexing XML documents according to their structural proximity. This is obtained by organizing the schemata of a large XML document collection in a hierarchical way by merging structurally close schemata. The proposed structure, which is called XML Schema Directory (XSD), is a balanced tree and it may serve two purposes: (1) to accelerate XML query processing and (2) to facilitate browsing. Received 15 March 2001 / Revised 12 April 2001 / Accepted in revised form 11 May 2001