基于语义相关的XML文档关键字检索排序方法

摘要

本发明公开了一种基于语义相关的XML文档关键字检索排序方法，依次解析XML文档，计算主题节点与属性节点的语义相关度、属性节点与关键字的语义相关度，优化检索时间，对所输入的查询关键字进行单词归根处理，在倒排索引中取出关键字对应的主题节点信息以及相关度信息，对距离关键字最近的主题进行检索，对检索结果进行相关度从高到低排序，对距离关键字次近的主题进行检索，根据结果的Dewey码返回信息片段给用户。本发明针对XML数据独有的结构语义特点，提出了SRank相关度检索模型及方法，可以提高检索结果的准确率。

说明书

技术领域

本发明属于可扩充标记语言(XML)关键字检索技术领域，具体涉及一种XML文档关键字检索排序方法。

背景技术

作为一种互联网上和企业应用中信息描述和信息交换的国际标准，XML(eXtensible Markup Language)具有语义标示、易扩展、开放性和互操作性等诸多优点。随着XML技术的推广和XML数据的不断增大，针对XML文档的信息检索技术已经成为信息检索和数据库等相关领域的研究热点。

传统的信息检索技术主要是针对文本文档和HTML文档。XML文档区别于文本和HTML文档的重要特征是其包含了丰富的语义和结构信息，这些信息有助于判断XML文档与用户信息需求之间的相关性。另一方面，与文本和HTML检索不同，XML信息检索要求返回的是以XML文档中某个元素(Element)为根结点的片段，不必返回整个文档，提高了检索效率。与XML文档查询语言比如XQuery，XPath，XQL等相比，基于关键字的XML信息检索技术的主要优势就是用户不需要学习复杂的查询语言，也不需要对XML文档的结构有深入的了解，用户仅仅需要输入相应的关键字即可。因此，基于关键字的XML信息检索技术在现阶段有着更多的需求和更好的应用前景。

目前，基于XML关键字检索的方法大都是基于LCA(Lowest Common Ancestor)的思想(如V.Hristidis，N.Koudas，Y.Papakonstantinou，and D.Srivastava.Keyword Proximity Search inXML Trees.In IEEE Trans.Knowl.Data Eng.2006，18(4)；pages525-539.)，首先定位LCA结点(包含所有关键字)，然后再返回以该LCA结点为根结点的片段。文献“L.Guo，F.Shao，C.Botev，and J.Shanmugasundaram.XRank：Ranked keyword search over xml documents.In SIGMOD，2003；pages 16-27.”中XRANK提出的ELCA(Exclusive LCA)就是借助LCA的思想来解决关键字完全匹配问题。文献“Y.Xu and Y.Papakonstantinou.Efficient keyword search for smallest lcas in xml databases.In SIGMOD，2005，pages 527-538.”提出了SLCA(Smallest Lowest Common Ancestor)，即最小最低公共祖先的概念，以SLCA为根节点的子树被定义为包含所有关键字，并且任意一棵它的子树都不包含所有关键字的子树。文献“Guoliang.Li，Jianhua Feng，Jianyong Wang and Lizhu Zhou Effective keyword search for valuable LCAs  over XMLdocument in CIKM pages 30-41，2007.”提出了VLCA(Valuable Lowest Common Ancestor)的概念，如果构成LCA的关键字结点是同构的，那么此LCA就是一个VLCA。文献“Y.Xu and Y.Papakonstantinou.Efficient LCA based Keyword Search in XML Data.In EDBT，2008.”结合XRANK和SLCA给出了一种可以更有效地计算ELCA的算法-IS(Indexed Stack)。虽然上述方法在LCA思想基础上提出了各自判断查询结果的相关性的方法，但仍未能准确的反映出XML的结构语义对查询结果相关度的影响，效果并不理想。

例如图1中显示了XML文档的树形结构，记录了一个会议的名字、主席以及收录的论文等信息。每个节点用其标签标示，标签上面的数字是它的Dewey编码。如果用户输入查询Q＝{chen，XML}则按照SLCA的思想，结果包含以节点0.0为根和以0.1.1为根和的子树，而没有以节点0.1为根的子树。

发明内容

为了克服现有技术未能准确的反映出XML的结构语义对查询结果相关度的影响的不足，本发明提供一种基于语义相关的XML文档关键字检索排序方法，较好的解决了检索目标与用户信息需求的一致性问题，并确保了查询结果的信息完整性。

本发明解决其技术问题所采用的技术方案包含以下步骤：

1)本方法采用有序标签树模型作为XML文档模型。对树模型遍历拥有多种形式，本方法采用深度优先法遍历树模型，解析XML文档。采用Porter Stemming算法对全部单词进行归根处理。确定所有主题节点，使用Dewey编码的方式对主题进行编码。所述的主题节点是以其为根的树中包含以另外一个节点为根的子树的节点。

2)计算主题节点与属性节点的语义相关度、属性节点与关键字的语义相关度。

所述的属性节点是以其为根的子树只包含文本内容的节点。计算方法如下：

主题节点与属性节点的语意相关度用他们之间的距离的倒数来表示，属性节点与关键字的语义相关度其中perc(k，e_r)表示在以e_r为根节点的XML树中以L_a为标签的属性中包含关键字k的比例，freq(L_a)表示以e_r为标签的所有XML子树中包含以L_a为标签的属性的个数，freq(k，L_a)表示以e_r为标签的所有XML子树中包含以L_a为标签的属性的个数，并且该属性包含关键字k。

3)将关键字对应的最低主题节点(该节点为主题节点，并且在该节点与关键字之间不存在另外的主题节点)位置信息和步骤2)所计算出的主题节点与属性节点以及属性节点与关键字的语意相关度封装在一起保存在倒排索引中，并对位置信息中的Dewey码建立B+树索引，通过该索引结构优化检索时间。

4)用户输入查询关键字。对所输入的查询关键字采用Porter Stemming算法进行单词归根处理。

5)在倒排索引中取出关键字对应的主题节点信息以及相关度信息。关键字的倒排索引中保存包含这个关键字的一系列主题位置，以及关键字与属性节点、属性节点与主题节点的语意相关度。倒排表按照包含这个节点的最低主题节点的Dewey码排序(Dewey codes of the Lowest element node，LED)。如果一个节点是属性节点，那么它的LED为其父节点的Dewey码。

6)对距离关键字最近的主题进行检索，如果一个LED包含了所有的关键字，那么这个LED将被作为一个结果计算其相关度。计算方法如下：k表示返回属性关键字，sc(k′，L_a)表示查询条件，k′表示条件值关键字，L_a表示条件属性关键字。如果一个LED没有包含所有的关键字，那么将该LED的父节点加入到查询队列中。

7)对检索结果进行相关度从高到低排序，当检索完所有结果(即索引为空)或者达到用户要求的K个结果时算法结束，并输出结果。

8)对距离关键字次近的主题进行检索，重复步骤6)和步骤7)。

9)根据结果的Dewey码返回信息片段给用户。

本发明的有益效果是：本发明在深入分析用户信息需求和XML结构语义的基础上，同时结合传统检索中tf-idf相关度计算模型，针对XML数据独有的结构语义特点，提出了SRank相关度检索模型及方法。如果将这种方法应用于XML文档关键字检索领域，可以提高检索结果的准确率。

下面结合附图和实施例对本发明进一步说明。

附图说明

图1为一个XML树形表示，原始Dewey编码。

图2为一个XML树形表示，主题Dewey编码。

图3为本发明工作流程图。

具体实施方式

与本发明有关的一些概念和定义：

定义1.主题节点：对于节点n，如果以n为根的树T(n)中包含另外一个以m节点为根的子树T(m)，则n为主题节点。

定义2.属性节点：对于节点n，如果以n为根的子树只包含文本值的内容，则n为属性节点。

定义3.条件属性关键字：条件属性关键字是一类属性节点的名字，它表明了用户的查询条件。例如，查询Q＝{article、title、XML}，表明用户想查找title中包含XML关键字的article信息，其中title是条件属性关键字。

定义4.返回属性关键字：表明用户查询返回的关键字。例如，查询Q＝{article、XML、author}，表明用户想查找关于XML的article的auhor信息，其中author是条件属性关键字。

定义5.条件值关键字：查询条件的文本值关键字。例如，查询Q＝{article、title、XML}其中XML为条件值关键字。

与本发明有关的一些性质：

性质1.如果关键字出现的属性与主题的距离越近，那么这个属性与主题的相关度越高。

性质2.对于一个主题，关键字k出现在不同类的属性中，如果关键字出现在某类属性下的比例越高，则关键字与该属性相关度越高。

性质3.对于不同的检索结果，查询中的关键字出现的次数越多，则与用户的相关性越高。

本发明提出了基于语义相关的XML文档关键字检索排序方法，较好的解决了检索目标与用户信息需求的一致性问题。已有一些研究利用XML数据的结构判断查询结果是否相关，所采用的判断方法比较简单，效果并不理想。我们主要从两个层次深入的研究了这个问题。第一个层次考虑用户的查询目标与查询结果的主题一致性问题，所关注的是用户的查询目标主题。XML数据中的信息片段代表特定主题，而信息片段根节点的标签是对这种主题的描述。当用户的查询目标与查询结果实体一致时，用户的查询目标与返回信息片段根节点描述的实体是相同的。一方面，我们考虑关键字与主题的相关度来推断用户的查询主题，通过对查询对象的数据统计分析，计算出关键字与各个主题的关联程度，关联程度作为影响推断用户查询主题的因素之一；另一方面，我们利用关键字所代表的实体与返回结果根节点之间的距离来进行判断，当距离越近时，我们认为查询目标实体与查询结果实体更一致。

本发明还解决了传统与关键字LCA为根节点的子树作为返回结果的信息部完整性问题。以关键字LCA为根节点的子树作为返回结果是当前XML数据关键字检索的主要思想，这种方法可以获取包含所有输入关键字的最小信息片段，但在一些情况下，关键字LCA为根的子树所包含的信息是不完整的。例如：当用户信息需求为一篇有关针对XML数据查询的文章时，所输入的关键字为“XML，查询”。如果一篇文章的题目同时包含这两个关键字的时候，这篇文章极可能与用户需求一致，而根据关键字LCA的思想，将返回“XML，查询”的LCA(文章的题目)为根的信息片段，用户的信息需求是一篇文章，文章题目作为返回结果的信息是不完整的。针对这个缺陷，我们提出了主题的概念，从关键字查询的特点和XML数据的结构分析，提出XML文档中的信息片段满足一定的结构才是主题，而主题能够确保所包含信息的完整性，查询结果都是以主题为单位，这样就确保了查询结果的信息完整性。

为了利用包含在文档中的丰富的语义信息来计算关键字与各个主题的关联程度，进而计算返回结果与用户查询目标的相关度，本方法经过以下几个步骤：

1)采用有序标签树模型作为XML文档模型，采用深度优先法遍历树模型，解析XML文档。采用Porter Stemming算法对全部单词进行归根处理。根据定义1确定所有主题节点，使用Dewey编码的方式对主题进行编码，如图2所示。

2)计算主题节点与属性节点(定义2)的语义相关度、属性节点与关键字的语义相关度。计算方法如下：在图1中，name、chair、title和auhor节点都是属性节点，根据定义，他们只包含文本信息；paper、conference和bib都是主题节点，以为以这些节点为根的子树里面包含了更小的子树。属性节点与其所在主题节点的相关度用他们之间的距离的倒数来表示，例如关键字paper与paper节点(0.0.1)的相关度为而title关键字与paper节点(0.0.1)的相关度为属性与关键字的语义相关度，其中perc(k，e_r)表示在以e_r为根节点的XML树中，以L_a为标签的属性中，包含关键字k的比例。freq(L_a)表示以e_r为标签的所有XML子树中包含以L_a为标签的属性的个数。freq(k，L_a)表示以e_r为标签的所有XML子树中包含以L_a为标签的属性的个数，并且该属性包含关键字k。

3)将关键字对应的最低主题节点(该节点为主题节点，并且在该节点与关键字之间不存在另外的主题节点)位置信息和步骤2)所计算出的主题节点与属性节点以及属性节点与关键字的语意相关度封装在一起保存在倒排索引中，并对位置信息中的Dewey码建立B+树索引，通过该索引结构优化检索时间。

4)用户输入查询关键字。对所输入的查询关键字采用Porter Stemming算法进行单词归根处理。

5)在倒排索引中取出关键字对应的主题节点信息以及相关度信息。关键字的倒排索引中保存包含这个关键字的一系列主题位置，以及关键字与属性节点、属性节点与主题节点的语意相关度。倒排表按照包含这个节点的最低主题节点的Dewey码排序(Dewey codes of the Lowest element node，LED)。如果一个节点是属性节点，那么它的LED为其父节点的Dewey码。

6)对距离关键字最近的主题进行检索，如果一个LED包含了所有的关键字，那么这个LED将被作为一个结果计算其相关度。计算方法如下：k表示返回属性关键字(定义4)，sc(k′，L_a)表示查询条件，k′表示条件值关键字(定义5)，L_a表示条件属性关键字(定义3)。如果一个LED没有包含所有的关键字，那么将该LED的父节点加入到查询队列中。

7)对检索结果进行相关度从高到低排序，当检索完所有结果(即索引为空)或者达到用户要求的K个结果时算法结束，并输出结果。

8)对距离关键字次近的主题进行检索，重复步骤6)和步骤7)。

9)根据结果的Dewey码返回信息片段给用户。