一种基于重叠有向图的WEB服务匹配方法

摘要

本发明提供了一种基于重叠有向图的WEB服务匹配方法，涉及计算机信息分析与数据处理领域，通过将大量的WEB服务结点的描述文件（WSDL）载入服务器端内存，形成海量WEB描述源数据，为了匹配到指定的服务，建立了空位种子匹配模型，并在此基础上构建重叠有向图，通过连通性和重叠数两个关键指标对种子进行评价，找到最优种子，最终完成WEB服务的匹配，是一种快速寻找合适的WEB服务方法。本发明可广泛应用在WEB服务结点大量存在，对WEB服务寻找要求较高的环境中，如面向服务的架构（SOA）、云计算等环境中。

说明书

技术领域

本发明属于计算机信息分析与数据处理领域，具体涉及一种基于重叠有向 图的WEB服务匹配方法。

背景技术

Web服务（WebService）是基于XML和HTTP的一种服务，每个web服务 对应了一个WSDL（WebServicesDescriptionLanguage)描述文件。WSDL描 述文件是一个用来描述Web服务和说明客户端如何与Web服务通信的XML语言 文件。

每一个WSDL描述文件都封装了若干可供调用接口及其说明文档，但当WSDL 描述文件大量存在时，如何迅速找到需要的服务接口，是需要解决的一个问题。

1.WEB服务描述

面向服务体系架构（Service-OrientedArchitecture，SOA）带来了一种 新的集成思想，根据它可以构造出灵活的以服务为中心的架构。SOA凭借其松 耦合的特性，可以把企业现有的应用作为服务来发布，服务拥有独立于硬件平 台、操作系统和编程语言的接口。因此，不同系统之间可以通过这种定义良好 的服务的交互实现系统之间的通信，不仅可以实现海量数据集成与异构业务系 统的协同工作，还可以按照模块化的方式来添加新服务或更新现有服务，以解 决新的业务需求。

SOA的核心就是WEB服务，它向外界暴露出一个能够通过Web进行调用的 应用程序接口(ApplicationProgramInterface,API)，能够用编程的方法通 过Web来调用这个应用程序。Web服务平台是一套标准，它定义了应用程序如 何在Web上实现互操作性。你可以用任何你喜欢的语言，在任何你喜欢的平台 上写Web服务，只要我们可以通过Web服务标准对这些服务进行查询和访问。

Web服务平台需要一套协议来实现分布式应用程序的创建。任何平台都有 它的数据表示方法和类型系统。要实现互操作性，Web服务平台必须提供一套 标准的类型系统，用于沟通不同平台、编程语言和组件模型中的不同类型系统。 在传统的分布式系统中，基于界面(interface)的平台提供了一些方法来描述 界面、方法和参数（如COM和COBAR中的IDL语言）。同样的，Web服务平台 也必须提供一种标准来描述Web服务，让客户可以得到足够的信息来调用这个 Web服务。

如何把来自客户端的关键词语与网络中服务端大量存在的WSDL描述文件 进行匹配并找到这些关键词语最匹配的WSDL描述文件从而实现合适的web服 务是网络信息搜索技术领域亟待解决的问题。

2.WEB服务匹配

在网络上的WEB服务的数量可能会非常大，如何根据关键字或基本信息寻找 到匹配的WEB服务，是一个十分重要的问题。将WEB服务的WSDL描述文件作为数 据源，将需要匹配的关键字和基本信息作为基本要素，寻找合适的WEB服务的过 程，即WEB服务的匹配。

为了在海量数据源的情况下迅速找到合适的WEB服务（即WSDL描述文件），本 发明引入基于空位种子的信息局部搜索方法，完成WEB服务的匹配。本方法主要 基于现有技术“序列比对方法”对匹配序列进行评估。

序列比对的定义是将两条序列字符进行两两匹配。在匹配过程上中，可能出 现以下三种情况：(1)一个字符代替了另一个字符，即发生了突变而产生字符失 配；(2)插入一个或多个字符；(3)删除一个或多个字符。因此，在序列比对过 程中，并不是简单的字符一一对应，除了匹配和失配以外，还会在序列中引入 空位(用符号“-”表示)来反映第2、3种变化。

如两个序列AATCTATA和AAGATA，下面给出了其中3种序列比对情况：

AATCTATA      AATCTATA      AATCTATA

AAG-AT-A      AA-G-ATA      AA--GATA

为了对序列比对结果进行量化，引入分数机制对序列比对进行打分，以得到 最优的序列比对。引入空位后，根据不同的比对情况，可以得到序列比对得分。 打分规则其定义如下：

Score(S₁,S₂)表示两个序列S₁、S₂的匹配得分，i为自然数用于表示序列中的某个 位置，n代表较长序列的最大字符数，所述字符可以为中文字符也可以为英文字 符。

其中k_i≥0(1≤i≤3)分别代表了匹配、失配和空位的情况。从打分公式可以看 出，匹配将得到一个正的分数，而失配或空位将得到0分或负分。由于可能的序 列比对情况千变万化，不同的比对可能得到相同的分数。

WEB服务技术广泛地应用在分布式计算、WebService、SOA等现代信息技术 中，在WEB服务海量存在的环境中，如何根据关键字快速找到匹配的WEB服务， 是现代WEB框架发展的重要手段，但传统的关键字查找的方法效率低下，无法适 应海量WEB信息查询的情况。

发明内容

为了克服传统WEB服务匹配方法的弊端，本发明设计了一种基于重叠有向图 的WEB服务匹配方法，采用基于空位种子的匹配技术和重叠有向图模型，对WEB 服务进行匹配，大大提高WEB服务匹配速率和处理效率。

本发明的技术方案为：一种基于重叠有向图的WEB服务匹配方法，包括以 下步骤：

步骤1：将WEB服务的描述文件即WSDL文件通过网络载入服务器端的内存， 形成WEB描述源数据；

步骤2：建立空位种子匹配模型，将WEB服务描述源数据与目标服务数据 以空位种子的形式进行描述，得到空位种子匹配框架；

步骤3：构建面向不同空位种子的重叠有向图，针对每一个重叠有向图计 算其连通性和重叠数；

步骤4：以最大的连通性和最小的重叠数为标准寻找最优空位种子，并通 过重叠有向图权重ODW描述最优空位种子；

步骤5：将最优空位种子与目标WEB服务描述源数据进行匹配，得到最优 的WEA服务匹配结果，找到需要的WEB服务结点。

作为优选：步骤1的具体方法为：采用超文本传输协议连接所有需要的远 程WSDL文件地址，将WEB服务描述文件通过文档对象树模型进行解析，其解 析格式为超文件标记格式，针对解析的文档对象树，将所有包含 <wsdl:documentation>的结点载入服务器端的内存。

作为优选：步骤2中所述的空位种子，其定义为：

一个空位种子S是定义在字符集Α={1,*}上的，并规定以1开始，1结束的固 定模式串；其中1表示匹配，*是一个通配符，表示在该位置可以是1匹配或0 失配；S表示为：

$S={\left(1\right)}^{i_1}{(*)}^{k_1}{\left(1\right)}^{i_2}{(*)}^{k_2}...{\left(1\right)}^{i_{n-1}}{(*)}^{k_{n-1}}{\left(1\right)}^{i_n}$

其中(1)^j和(*)^k表示连续j个1和连续k个*；

空位种子的长度(length)是S中所有1和*的个数，表示为|S|：

$\mathrm{length}\left(S\right)=\left|S\right|=\underset{j=1}{\overset{n}{\Sigma }}{i}_j+\underset{j=1}{\overset{n-1}{\Sigma }}{k}_j$

空位种子的权值w定义为所有1的个数：

$\mathrm{weight}\left(S\right)=w=\underset{j=1}{\overset{n}{\Sigma }}{i}_j$

空位种子的模式是将S中所有*替换为1或0形成的表示串，总共有2^|s|-w个 不同的模式。

作为优选：步骤3包括以下步骤：

a)建立结构有向图：自上而下的节点是按照种子对应元素从左到右的1或 0，其中1代表节点1，*代表两个节点：1和0，每条有向边标有相似度 p或q=1-p；

b)标记步骤：从顶部节点到底部按顺序从序号1开始标记每个节点，放到 节点值后面用括号括起来，然后删除标记p或q，同时，将首节点序号 标记在每条有向边上；

c)重叠步骤：重叠步骤是一系列重复迭代的过程，依次以每层节点值为1 的节点作为开始节点构造结构有向图，下一步从第二层节点中值1节点 开始，以此类推，最终停留在L-1层，经过重叠步骤后，得到空位种子 的重叠有向图模型。

作为优选：重叠有向图的连通性定义为：

有两个有公共结点的边e₁和e₂,即e₁的结束节点是e₂的开始节点，设B₁是 e₁标记的集合，B₂是e₂标记的集合，称B₁和B₂具有连通性或是连通的当且仅当

重叠有向图的重叠数的定义为：

设B是边e的标记集合，定义重叠数：

oc(e)=|B|。

作为优选：计算重叠有向图权重ODW包括以下步骤：

a)构建重叠惩罚函数：

其中c=oc(e)，可见当p<1时，是c的减函数；

b)构建奖励边连通性的“奖励函数”：

其中是重叠惩罚函数的值，对于结点N，定义w(N)=w(e)*w(e′)，用于 计算结点的权值；

c)构建重叠有向图权重：

$\mathrm{ODW}\left(G\right)=\underset{j=1}{\overset{ϵ}{\Sigma }}w\left(N_j\right)$

根据此模型，对于相同长度和权重的空位种子，更优质的种子有更高的重 叠有向图权重，在计算候选种子的ODW(G)后就可以找到优质种子。

作为优选：步骤5包括以下步骤：

a)首先确定一个终止值d、连续种子长度w和一个阈值t,d值通常是基于 统计学的原理指明一个预期的终止E值，然后在考虑搜索背景性质的基础上计 算出合适的d值；

b)根据空位种子模式对内存中的WEB服务描述源数据进行局部匹配，当有 一个匹配串的分值高于t时，则找到了一个选中的字串，即增强点；

c)当一个分值高于t的字串选中后，进行基于动态规划算法的局部延伸寻 优，规定比对的最低分值是d，当比对延伸时会遇到一些负的分值，使得比对 的分值下降，当下降的分值小于d时，命中的延伸就会终止，这时这段比对中 具有最高分值的片段便成为一段命中的匹配，从而找到符合要求的WEB服务结 点。

本发明的有益效果为：本发明设计了一种在大量的WSDL描述文件中匹配目 标的方法，提出了空位种子模型，并通过重叠有向图寻找最优空位种子，完成 对目标WEB服务的匹配。当需要在海量WSDL描述文件中寻找目标时，克服了传统 的依次逐一匹配方式存在的速度慢的缺点，本发明通过设计性能优良的空位种 子，利用种子模型去匹配WSDL描述文件，从而大大提高匹配效率，进而有效地 提高Web服务的性能，这对日益发展的互联网服务扩展有着重要的意义。

附图说明

图1为空位种子1*1*1的结构有向图；

图2为空位种子11**1的结构有向图；

图3为空位种子1*1*1结构有向图的首次修改；

图4为空位种子11**1结构有向图的首次修改；

图5为空位种子1*1*1的重叠有向图；

图6为空位种子11**1的重叠有向图。

具体实施方式

为了便于本领域技术人员的理解，下面结合附图和具体的实施例对本发明 做进一步的说明。

本发明将按照WSDL描述文件载入、空位种子的建立、重叠有向图的生成、 连通性和重叠数的计算、基于最优空位种子的匹配五个步骤进行详细描述：

步骤1：服务器端从网络中的WEB服务器载入大量的WSDL描述文件在服务器 端形成海量WSDL描述文件源数据,此步骤为现有技术。

步骤1的具体方法为：采用超文本传输协议连接所有需要的远程WSDL文件地 址，将WEB服务描述文件通过文档对象树模型进行解析，其解析格式为超文件标 记格式，针对解析的文档对象树，将所有包含<wsdl:documentation>的结点载 入服务器端的内存。

步骤2：空位种子的建立

1)空位种子按照以下公式进行定义：

一个空位种子S是定义在字符集Α={1,*}上的，并规定以1开始，1结束的固 定模式串。其中1表示匹配，*是一个通配符，表示在该位置可以是1(匹配)或0(失 配)。S可以表示为：

$S={\left(1\right)}^{i_1}{(*)}^{k_1}{\left(1\right)}^{i_2}{(*)}^{k_2}...{\left(1\right)}^{i_{n-1}}{(*)}^{k_{n-1}}{\left(1\right)}^{i_n}$

举个实施例：如1**1*1就是一个空位种子。

其中(1)ⁱ和(*)^k表示连续i个1和连续k个*，i_j表示i的不同取值，j∈[1,n]， 其中n为自然数；k_j表示k的不同取值，j∈[1,n-1]其中n为自然数。可以看出， 空位种子S由若干个连续多个1组成的“1块(1blocks)”和连续多个*组成的“* 块(*blocks)”构成。由于规定S必须以1开头和1结尾，所以“1块”的个数等 于“*块”的个数加1。

空位种子S的长度(length)是S中所有1和*的个数，表示为|S|：

$\mathrm{length}\left(S\right)=\left|S\right|=\underset{j=1}{\overset{n}{\Sigma }}{i}_j+\underset{j=1}{\overset{n-1}{\Sigma }}{k}_j$

空位种子的权值w定义为所有1的个数：

$\mathrm{weight}\left(S\right)=w=\underset{j=1}{\overset{n}{\Sigma }}{i}_j$

空位种子的模式是将S中所有*替换为1或0形成的表示串。显然，总共有 2^|s|-w个不同的模式。

步骤3：重叠有向图的生成：

为了快速找到最优或接近最优的空位种子，我们引入了种子重叠的概念。 种子的命中可以重叠，但重叠的命中将检测出同一处的匹配。因此，种子灵敏 度反比于重叠命中数，即良好的种子应该有低的重叠命中数。即使不同的空位 种子具有相同的长度和权重，其仍有不同的灵敏度和重叠性。

1)构造空位种子结构有向图：

由种子结构产生的自上而下的有向图。自上而下的节点是按照种子对应元 素从左到右的1或0，其中1代表节点1，*代表两个节点：1和0。每条有向边标有 相似度p或q=1-p，读作“以概率p(或q)出现”。

为了解释不同的种子具有相同的长度和权重的不同结构，我们不采用最简 单的空位种子1*1作为我们的第一个例子，因为其只有一个候选种子，即1*1， 其长度为3和权重为2。我们以长度为5权重为3的空位种子开始。这里有两个候 选种子(除去对称的)：1*1*1和11**1。

图1和图2显示了种子1*1*1和11**1对应的两个不同种子结构有向图。

根据空位种子的定义，每一个结构有向图都由节点1开始和结束。对于一个 长度L和重量w的空位种子，从顶级节点到底部有L层，每一层都至少有一个 节点，如节点1。下层节点以边p(下层节点为1)或边q(下层节点为0)与上层节 点相连。显然，在一个基本结构有向图中有w+2(L-w)个节点。

空位种子的结构有向图是一个用来检测相同长度和权重种子之间的结构差 异的基本模型。节点中的值为1或0，称为节点值。空位种子的重叠有向图，是 对结构有向图的扩展。为了使有向图保存更多的种子结构信息，我们需要对它 进行修改，包括标记步骤和重叠步骤。

2)标记步骤

首先，我们从顶部节点到底部按顺序从序号1开始标记每个节点，放到节点 值后面用括号括起来，然后删除标记p或q，因为我们可以从下层节点(1对应 p,0对应q)分析得到；同时，将首节点序号标记在每条有向边上。由于这是建 立重叠有向图的第一步，因此所有的边都以起始节点(1)进行标记，从第二步开 始，起始节点将改变为下层中值为1的节点。

图3和图4显示了空位种子1*1*1和11**1的修改结果。结构有向图的开始节 点是顶级节点。这种有向图可以作为重叠有向图的初级版本，即无重叠有向图。

3)重叠步骤

重叠步骤是一系列重复迭代的过程。迭代过程以步骤为基础，依次以每层 节点值为1的节点作为开始节点构造结构有向图，但起始节点采用下层中值为1 的点。结构有向图的首次修改是从第一层开始进行，因此下一步必须从第二层 节点中值1节点开始，以此类推。

当到最后一层时，我们可以看出它第一层相同，因此我们停在L-1层。

经过重叠步骤操作后就创建了重叠有向图。

图5和图6是空位种子1*1*1和11**1的有向图完整版本。重叠有向图的层 数：N(layers)=2L-2。

步骤4：计算连通性和重叠数

1)连通性计算：有两个有公共结点的边e₁和e₂,即e₁的结束节点是e₂的开 始节点，设B₁是e₁标记的集合，B₂是e₂标记的集合。称B₁和B₂具有连通性或是 连通的当且仅当

例如，在空位种子1*1*1的重叠有向图中，公共结点节点(3)的两条边有 连通性，因为B₁={1}且B₂={1}那么但对于具有公共节点(2) 的两条边(最左边)不连通，因为B₁={1}且B₂={2}那么

路径上所有的边都是连通的路径称为连通的路径。当且仅当一条连通的路 径中的L条边都包含相同的某个标记，才说路径中包含空位种子的模式。

2)重叠数计算：设B是边e的标记集合，定义重叠数：

oc(e)=|B|

连通性和重叠数是判断空位种子质量的两个主要因素。如果某空位种子有 高的连通性，称其是优质的，因为可以检测出更多的连通路径从而可以找到更 多的模式。另一方面，优质空位种子要有低的重叠数，因为重叠的命中将检测 出同一处的匹配，那么低重叠数将有高的敏感度。

步骤5：基于最优空位种子的匹配

1)边权重的计算：边的权重是连通性和重叠数的函数。定义如下：

其中oc(e)是e的重叠数，是“重叠惩罚函数”；

2)定义重叠惩罚及连通奖励函数：

其中c=oc(e)。可见当p<1时，是c的减函数。

是奖励边连通性的“奖励函数”，也就是说，如果e与其具有公共 结点的边是连通的则w(e)应该增加。设e′是e的某个具有公共结点的边，在本 发明中，定义如下：

其中是重叠惩罚函数的值。

对于结点N，定义w(N)=w(e)*w(e′)，用于计算结点的权值。

3)计算重叠有向图权重

重叠有向图权重定义为图中每条边的权值之和。给定一个重叠有向图G， 设ε是G的边数那么重叠有向图的权重ODW(G)定义如下：

$\mathrm{ODW}\left(G\right)=\underset{j=1}{\overset{ϵ}{\Sigma }}w\left(N_j\right)$

某重叠有向图的ODW(G)值主要基于空位种子的结构，重叠数，连通性和 相似度等等。由于涉及更多的参数且允许用户自定义函数来计算，重叠有向图 模型将更加完整，精确而灵活。

根据此模型，对于相同长度和权重的空位种子，更优质的种子有更高的重 叠有向图权重，在计算候选种子的ODW(G)后就可以找到优质种子。

4)基于最优空位种子的匹配

按照重叠有向图权重最大值针对每一个候选种子进行计算，寻找最优空位 种子，并以些为标准进行WEB服务描述匹配，其特征在于包括以下步骤：

a)首先确定一个终止值d、连续种子长度w和一个阈值t。d值通常是基 于统计学的原理指明一个预期的终止E值，然后在考虑搜索背景性质的基础上 计算出合适的d值。

b)根据空位种子模式对内存中的WEB服务描述源数据进行局部匹配，当有 一个匹配串的分值高于t时，则找到了一个选中的字串，即增强点。

c)当一个分值高于t的字串选中后，进行局部延伸寻优，规定比对的最低 分值是d，当比对延伸时会遇到一些负的分值，使得比对的分值下降，当下降 的分值小于d时，命中的延伸就会终止，这时这段比对中具有最高分值的片段 便成为一段命中的匹配，从而找到符合要求的WEB服务结点。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理 解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和 实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种 不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明 的保护范围内。