本体可视化方法及其应用

1. 模式文件动态解析和分割

模式文件的分割是基于模式文件的模式图 (或树) 进行的，当前，有许多工作对模式片段的构建做了研究。如J.Seidenberg (2006) 通过对本体中某个具体的实体中所有不同链接 (如属性) 的遍历来构建一个独立的模式片段。它通过应用OWL本体中详细的语义关系来生成高度相关的片段。H.Stuckenschmidt (2007) 使用基于分布式描述逻辑为模块化本体定义了一种框架，但是设计的模块化方法并没有定义操作的模块大小。K.Tu (2005) 提供了一种新的本体可视化方法，生成本体的一个整体镜像，这个镜像包括本体类的一个语义轮廓，对分布式实例和实例关系也一样进行了可视化，并且对不同数目的实例使用不同的颜色来表示，而对于不同数目的实例关系，则使用不同颜色的线进行表示。K.Tu使用的是一种数据聚类算法 (切割演算法) 来对一个大的本体进行分割，其基本思想是通过先把一个本体转换成图，接着使用一种聚类算法对图进行分割，但是这种方法不能够对任何包含空节点的三元组提供保护机制。Sana Sellami (2009) 等首先把模式文件转换为XML树，接着对XML树中的频繁子树进行识别和挖掘，再找出两棵XML树中相关的频繁子树，最后把这些频繁子树从XML树中分割出来。在本书中，我们在COMA++提出的基于片段模式匹配方法基础上，设计了一种新的基于模式 (片段) 相似度的模式分割方法。即对所有源模式文件中的片段，通过在目的模式文件搜索与其相似的模式片段，然后以这些模式片段为粒度对目的模式文件进行分割。目的模式文件分割的过程也是一个不断寻找相似片段的过程，而源模式文件的分割则是基于模式文件复杂度，通过一种直接的模式树分裂法把一个复杂模式文件分割成几个简单模式片段。这种分割方法有如下几个好处:

(1) 分割粒度合理，目的明确。我们以源模式文件 (片段) 作为分割目的模式片段的依据，目的模式文件分割粒度以源模式片段粒度为基准，避免目的模式分割的盲目性。对源模式文件根据其复杂度进行简单分割，简单可行，而Sellami等人提出的方法中，通过识别两个模式树中相关的频繁子树来对XML树进行分割，由于频繁子树的识别工作量很大，而且频繁子树的粒度各不相同，对源XML树的分割容易造成太多“碎片”。

(2) 简化了片段识别工作。模式分割过程同时发现了两个模式文件中所有可能的相似片段，从而降低了模式片段识别阶段模式片段识别范围，有效地提高识别效率。

(3) 由于分割粒度合理，相似片段最大限度地保证包含了两个模式文件所有可能的映射。分割粒度过大，失去分割意义，分割粒度太小，不仅增加了片段匹配工作，而且很容易丢失映射。

模式分割按如下两个步骤进行:

步骤1. 对输入的模式文件进行动态解析和表示。

为了更好的处理大尺度模式、XSD、Web OWL及其他XML模式语言允许一个模式文件分布式地存储在几个文档和名称空间中，并且每一个XSD文档被分配一个所谓的目的名称空间，并向XSD提供不同定向来把在一个文档中定义的部分导入到一个新文档。一个模式可能包含多个子模式，如不同的消息格式，它们都可单独实例化。为了处理方便，通过把对分布的相关文档进行解析并把导入或交叉引用部分转换到一个文档中然后再处理。在模式文件进行解析时，顺序读取模式中每个元素，然后对每个元素作如下处理: 如果元素的名称是schema，就根据属性信息得到target Namespace内容; 如果元素的名称是restriction或extension，说明有继承类型，根据属性信息得到继承的基类类型; 如果元素的名称是include或import，表示要导入新的模式文件，根据属性信息得到模式文件的URL地址和导入的模式文件名，根据URL地址和文件名动态到OGC网站去下载模式文件，文件下载后保存到本地并用同样方法对模式文件进行解析，解析过程中如发现有新的要导入模式文件，则继续动态下载新的模式文件并对文件进行解析，直至文件解析完毕;如果元素的名称是complex Type、single Type、element、attribute、group、attribute Group等则对这些元素名称和类型进行处理，模式元素读入结束后把每个元素相关信息保存在数据库中，这些信息包括: 模式文件名，ID号，元素名，元素类型，元素命名空间，元素类型空间，元素的元数据类型，注释等，同时如果一个模式元素是另一个元素子元素，则还需保存两个元素间的一个关系，关系信息包括: 子元素模式文件名，子元素ID，父元素模式文件名，父元素ID，父子间关系 (此处为IS_ A) 等。模式文件解析结束后，模式文件所有元数据信息保存到了数据库中，模式文件在模式管理器中被统一用有向图 (或树) (Zeidenberg和Rector，2006) 进行了表示。图6-3表示的是模式元素解析流程。

我们使用WFS1.1.0版本的“wfs.xsd”模式文件和 WFS 1.0.0版本的“WFS_basic.xsd’”模式文件来阐述模式文件解析的流程。如图6-4所示，“wfs.xsd”模式文件导入了三个分布式模式文件: “gml.xsd”、“filter.xsd”和“ows All.xsd”; 而“WFS_basic.xsd’”模式文件包含两个分布式的模式文件: “feature.xsd”和“filter.xsd”，所有的模式文件都有不同的命名空间。虽然，导入的“filter.xsd”模式文件具有相同的命名空间，但是一个是1.1.0版本，而另一个是1.0.0版本。这两个版本的模式包含一系列分散式的简单和复杂元素，并且载入后均可以用树图表示。

步骤2: 把模式图 (树) 分割成片段。

在本书中，我们使用的是基于相似片段搜索的分割方法，边搜索边分割。即对源模式文件中所有模式片段寻找它在目的模式文件中的相似片段，如果查找成功则分割结束，如果在目的模式 (片段) 中找不到相似片段，则对目的模式 (片段) 进行一次分割，然后在分割后的模式片段中继续搜索相似片段，直到所有源模式片段都找到了其在目的模式片段中的相似片段为止。特别说明的是，这里的源模式文件是低版本模式文件，目的模式文件是高版本模式文件，我们还假定高版本模式文件是对低版本模式文件的扩展和补充，所有低版本模式文件片段在高版本中都能找到它的相似片段。

图6-3 模式文件解析流程图

图6-4 WFS模式文件解析例子

图6-5是两棵简单的模式树分割过程。由图中可以看出，模式树分割从总体上分三个步骤，即模式树分裂、识别相似候选模式片段和输出候选相似片段对。模式树分裂有两种: 源模式树分裂和目的模式树分裂。源模式树分裂主要根据模式树复杂度来确定是否需要分裂，对目的模式树的分裂则是根据源模式树中的模式片段在目的模式树中的查找过程进行的，主要看能否找到与源模式树中的模式片段相似的模式片段，如果不能找到则需要对模式树进行一次分裂。

图6-5 模式树分割过程

图6-6是模式树分割的伪代码。算法输入的是源模式树与目的模式树的根节点，为了表示方便，每个模式树都用其根节点表示。算法首先判断源模式树是否需要分割，如果要分割，则使用树分裂法进行一次分割 (行1，2所示)。树分裂算法divide Tree根据模式树根节点对模式树进行分割，具体过程为: 删除树的根节点，删除根节点到其所有直接孩子的链接，有n个孩子的原树就被分割成n棵子树，每个孩子节点成为新的子树的根节点，分割后的子树统一用树的根节点表示，每棵子树成为了源模式文件的一个分割后的模式片段。源模式树分割完后，接着搜索源模式树的模式子树在目的模式树中的相似模式子树，如果所有源模式子树找到了相似模式子树，分割结束，否则对目的模式树使用树分裂法进行分割，然后再在分割后的模式子树中搜索相似子树。目的模式树分割过程为: 对每个源模式子树，搜索它在目的模式树中的相似子树，如果找到了所有与之相似的目的模式子树，则对所有相似的源模式子树和目的模式子树作删除标记 (行5，6所示)，如果源模式子树有多个，而目的模式树 (子树) 只有一个，则首先对目的模式树使用树分裂法进行一次分割，然后在分割后的模式子树中搜索相似子树 (行8～12所示)。如果源模式树根节点集合为空，即所有源模式子树都做了删除标志 (行13所示)，则说明所有源模式子树都找到了相似目的模式子树，模式文件分割结束，输出所有分割后的相似模式子树，算法结束 (行14所示)。否则使用相同的方法递归地对源模式树和目的模式树做进一步分割。实际中，为了防止有源模式子树找不到相似子树而使得分裂一直进行下去，可以对递归的次数给一个限定，一般不超过3次。在本书的网络服务模式片段分割实验中，通常一次分割就可完成所有相似片段的查找。分割后的模式片段类型通常分为两类: 内部模式片段和子模式片段。内部模式片段是指那些通过树分裂法分割后的模式片段，子模式片段则是那些解析后的独立的模式片段 (没有经过分割)，包括定义在模式文件中复杂的数据类型 (wcs Get Capabilities.xsd中的数据类型 Capabilities)，或者是一些独立的操作类型(wcs Get Capabilities.xsd中操作类型Get Capabilities)。分割后的模式片段也可能比较复杂，也可能是只包含一个叶子元素的简单元素。

图6-6 模式文件分割伪代码

根据模式片断类型，模式树的分割分成四种不同情形: 第一种情况是源模式树和目的模式树解析后都是独立的简单子树，源模式所有子树在目的模式子树中都能找到相似子树，两种模式树都不需要分割; 第二种情况是只需要分割目的模式树，源模式树解析成许多独立的简单子树，目的模式树是一棵独立复杂的树，这时只需要对目的模式树进行分割; 第三种情况与第二种情况相反，只需要对源模式树进行分割; 第四种情况的源模式树和目的模式树都需要进行再次分割。

图6-7显示的是模式文件的子模式片段。“wfs.xsd”模式文件包含10个独立的片段:Transaction、 Lock Feature、 Describe Feature Type、 Transaction Response、 Feature Collection、Get GMLObject、WFS_ Capabilities、Get Feature、Get Capabilities和Get Feature With Lock; 而“WFS_ basic.xsd”模式文件包含4个独立的片段: Feature Collection、Describe Feature Type、Get Feature和Get Capabilities。

图6-7 WFS模式文件片段分割结果

2. 相似模式片断的识别

在模式文件的分割过程中根据模式片断的根元素名称已经初步确定了源模式文件和目的模式文件中所有可能相似的模式片断，接着我们将从这些相似片断候选者中去精确发现那些真正相似的模式片断，以便能够从细节上对这些模式片断进行片断模式匹配，所以识别相似片断过程中不仅要对元素的名称进行比较，还要对片断的结构进行比较。结构比较过程中常常需要借助模式片段元数据信息，这些信息包含片段名字、模式树深度、叶子及其他统计数据等。模式片断识别基于模式片段的模式图 (树) 进行，对于每对要识别的模式片断，通过比较对应根元素命名是否相等和结构是否一致来判断两个模式片断是否充分相似，根据命名和结构相似值的组合值，选择相似组合值最大的模式片断为最终的相似模式片断。基本算法如下所示。

算法: 模式片断识别算法。

输入: 源模式片断S和目的模式片断T。

输出: 相似模式片断对。(www.xing528.com)

Identify Fragments (S，T)。

(1) 读入所有候选源模式片断S和候选目的模式片断T。

(2) 对每个目的模式片断Ti，首先使用公式 (3-1) 计算其根元素与所有候选相似源模式片断Sj根元素名字相似值，选择相似值最大一个作为根元素间名字相似值Es。

E(i，j)=Similarity(rooti，rootj)　(6-1)

式中，0＜i＜m，0＜j＜n，m，n为目的和源模式的片断数量; E (i，j) 为第i个目的片断与第j个源片断根节点相似值; rooti，rootj分别指第i个目的根节点和第j个源根节点。计算名字相似值的方法很多，主要是从语法和词义两方面进行比较，首先使用基本的基于字符比较的匹配器，主要看两个比较的词语是否来自同一个命名空间，在语义上是否相等，是否具有相同的同义词和超义词，编辑距离或发音是否相等等 (Chen等，2008)。在本书中，对算法Similarity(rooti，rootj) 定义如下:

①首先对rooti，rootj进行符号化，即根据字符串中的大小先把一个字符串分解成几个简单字符串，并把这些字符子串转换为小写，如果rooti，rootj都是简单字符串，则使用编辑距离法和它们在Word Net中词义距离来分别计算它们间相似值，返回相似值较大者，算法结束，否则转②。

②根据rooti，rootj所有组成字符字串词性赋予不同的权值，如，名词、动词、形容词和副词权值分别用wname、wverb、wadj和wadv表示，并且有wname≥wverb≥wadj≥wadv，wname+wverb+wadj+wadv=1.0，转③。

③使用步骤①相似值计算方法计算出rooti，rootj所有组成字符字串间的相似值，并根据不同词性字符串权值，计算所有字符串对的带权组合相似值，即为rooti，rootj的相似值，算法结束。

(3) 从结构上，将目的模式片断子树和源模式片断树的路径数目和长度上进行比较，如果对于目的模式子树的每条路径都能在源模式子树中找到一个对应路径，则相似值为1。否则用目的模式树路径与源模式子树路径匹配数目与目的模式路径总数比值表示相似值Ss。相似值计算公式为:

Ss=paths(s，t)/pathst　(6-2)

式中，paths(s，t)是源模式片断与目的模式片断匹配的路径数，pathst是指目的模式片断路径总数。

(4) 对每个目的模式片断，计算其与源模式所有片断间元素相似值和结构相似值的组合值，选择相似值最大的模式片断对作为相似片断对输出。组合相似值计算公式如下:

Sim(s，t)=αEs+ (1-α) Ss，0＜α＜1　(6-3)

式中，Es是元素相似值，Ss是结构相似值，α为权系数，根据经验权系数通常取0.6～0.7左右。

图6-8为经过上述识别过程获得的“wfs.xsd”和“WFS_ basic.xsd”模式文件的相似片段，包含Feature Collection、Describe Feature Type、Get Feature和Get Capabilities。

图6-8 “wfs.xsd”和“WFS_ basic.xsd”模式文件的相似片段

3. 模式片断匹配及匹配结果组合

识别了源模式片断与目的模式片断后，就可以对这些片断中的元素与属性使用各种匹配算法 (何杰等，2011) 来进行片断模式匹配了。图6-9是片断模式匹配过程，它由如下4个步骤组成:

图6-9 片断模式匹配过程

步骤1: 模式片断选择。模式片段识别部分中识别的模式片断被保存在片断管理器中，片断匹配执行时每次从片断管理器中顺序选择一对没有匹配的片断(如Ti←→Sj) 进行匹配。

步骤2: 片断匹配。每一相似片段对间的匹配问题都是一个独立匹配问题，对于每对模式片断间的匹配，我们使用通用的组合模式匹配方法——COMA来计算两个模式片断间元素映射关系，每对片断间的匹配结果被保存在一个中间映射文件中。

步骤3: 片断匹配结果组合。所有片断对间匹配完成后，对保存在映射文件中的所有映射进行组合形成两个模式文件最后的完全匹配结果。对不同的模式片断的类型选择不同的映射组合方法，即，如果两个模式片断都是独立的子模式片断，由于每个模式子树的根节点也是原模式树的一个根节点，所以组合时直接把所有映射进行合并即可; 如果模式片断是内部模式片断，则组合前先在那些内部模式片断的映射路径前加上从模式根节点到内部模式根节点的路径，然后再进行映射合并。组合结果是一系列包含模式元素对间的对应关系的映射。最后对片断模式匹配结果进行输出或把匹配结果保存在一个文件中为以后的匹配重用所使用 (何杰等，2011)。在本书中的匹配结果将输入到样式表生成器去生成XML文档间的转换规则。

图6-10为模式文件“wfs.xsd”和“WFS_ basic.xsd”的匹配结果，包含21个匹配的元素项。

图6-10 模式文件“wfs.xsd”和“WFS_ basic.xsd”匹配结果