基于语义的领域构件接口名称匹配方法.doc

基于语义的领域构件接口名称匹配方法 张正 左春 王裕国 蔡玉宝 中国科学院 软件研究所 北京 100080 摘 要 提出了一种基于语义的领域构件接口名称的匹配方法 首先要对已有的构件库中的构件接口名称进行 基于命名规则库 维度记录模型 词根表 环境和操作分类表的解析 得到解析构件库 基于解析构件库的匹 配根据使用者对环境 对象 含义和组成信息 操作的输入查询解析构件库 根据环境和操作信息过滤掉不符合 要求的接口 基于设定的阈值对领域对象进行名称相似度和组成相似度的计算 得到匹配程度 基于该方法的 构件匹配工具在实际工作中进行了应用 并取得了较好的效果 关键词 构件匹配 领域构件 接口名称 语义 中图分类号 TP311文献标识码 A文章编号 1000 436X 2007 05 0073 07 Domain component interface identifier matching based on semantic ZHANG Zheng ZUO Chun WANG Yu guo CAI Yu bao Institute of Software Chinese Academy of Sciences Beijing 100080 China Abstract A domain component interface identifier matching method based on semantic was provided The original interfaces in component library were parsed based on naming rule base DRM dimension record model root base operation classification and environment classification Then the parsed component library was generated The proposed method searched in parsed component library based on environment object and operation information provided by user First the method filtered interface by environment and object then the name similarity and construction similarity are calculated by defined threshold matching degree is got The tool based on the way was applied in practical work and have achieved good results Key words component matching domain component interface identifier semantic 1 引言 1 随着对软件复用研究的不断深入 软件构件 受到了学术界和工业界的多重关注 按复用范围 的不同 软件构件被分为通用构件和领域构件两 类 基于在行业应用软件领域的多年经验 我们 发现 在一个行业应用软件系统中 被复用的领 域构件要远远大于通用构件 在与本文相关的一 个电信运营支撑系统中 领域构件与通用构件的 代码行数之比达到了 4 1 另外 领域构件的复用 也是行业应用软件 工程化 的前提 总的来说 收稿日期 2007 02 08 修回日期 2007 04 06 领域构件的复用对行业应用来说是至关重要的 构件匹配是构件复用的基础和前提 也是目 前国内外的一个研究热点 按粒度粗细划分 构 件匹配分为基于整个构件的描述模型的匹配 1 3 和 对构件的接口匹配两类 4 5 基于构件描述模型的 匹配方法有很多 有基于关键字的 1 基于 XML 的 2 基于刻面分类的 3 等 但是应用这些方法都 无法实现对细粒度的构件接口的检索 导致在程 序员进行构件的复用时 仍然需要人工的查看构 件的接口描述 编写相应的代码去调用构件的功 能 构件接口匹配的难点在于对构件接口的解析 第 28 卷第 5 期通 信 学 报Vol 28 No 5 2007 年 5 月Journal on CommunicationsMay 2007 74 通 信 学 报第 28 卷 以及对解析结果的匹配和处理 对构件接口进行 匹配的研究不多 ELGEDAWY I 针对构件接口提 出了基于目标和上下文的匹配方法 4 并采用概念 替换图 concept substitutability graph 描述概念之间 的关系 其能够应用于构件的自动化组装 且在 概念层次进行了讨论 其缺点是概念替换图需要 手工构造 实现难度较大 不少研究者提出了利 用 Schema Matching 实现接口匹配的方法 5 对接 口的属性 attribute 进行基于同义词词典 缩写词 典以及 WordNet 等词汇集的比较 但是这种方法 缺乏对接口的有效解析 将接口信息转为 Schema 较难实现 除了直接调用之外 由于领域存在诸多的 相似性 如业务的处理对象不同 但方式类似 构件的复用还有 模仿 这种形式 即参考已 有的实现方式 而且在实际的工作中应用较多 本文以构件的接口名称匹配为研究对象 提出了 基于语义的接口匹配方法 它支持构件的两种复 用方式 大大减轻了终端编程人员在复用构件时 的工作量 2 总体思路 事实上 构件的设计者在进行接口的命名时 总是力图使命名既简明又能充分表明该接口的功 能 6 设计者会使用adsl expense query 而不是 f 表示对 ADSL 业务开通费用的查询 这种接口的 标识符提供了其功能的丰富信息 通过对大量的程 序代码进行考察 发现构件接口的命名总是基于一 定的规则 另外 行业应用中对业务的处理往往反 映在对业务实体的操作上 如一个库存的管理系统 是围绕着对进货记录 库存记录以及出货记录展开 的 一个电信业务支撑系统的业务运作最终体现在 各种记录和单据上 因此有如下的假设 假设 1 行业应用软件中 构件接口的命名是 有规则的 假设 2 行业应用软件中处理的业务对象是 结构化的 基于这样的假设 本文给出方法的总体思路 如图 1 所示 包括对原有构件解析和构件匹配 2 个部分 对原有构件库中的构件接口进行基于命名规 则库 维度记录模型 词根表 环境和操作分类 表的解析 将构件接口名称划分为环境 对象和 操作三类信息 其中 对象 由其 含义 和 组成 两项构成 其 含义 项与词根表中的 图 1 方法总体思路 第 5 期张正等 基于语义的领域构件接口名称匹配方法 75 词条相对应 组成 项是一个领域对象模型 它 由若干维度记录中的若干元素组成 而维度记录 与库表一一对应 并被表示成鱼刺图的形式 构件匹配分为几个步骤 首先由查询者提出 查询需求 根据其需求和命名规则库 系统可以 给出一个命名供参考确认 也可由查询者直接给出 命名 被确认的接口名 包括环境 对象和操作信 息 将与解析构件库中的已有接口名进行环境匹配 操作匹配 以及对象名称匹配度 对象组成匹配 度的计算 最后按一定的阈值 查看匹配的函数 如确定复用策略 直接调用 模仿 则结束 否则 进行重新命名和匹配 维度记录模型 词根表 环境分类表和操作分类表构成了解析和匹配的语 义基础 3 相关概念 3 1 维度记录模型 由假设 2 行业应用软件中处理的业务对象是 结构化的 事实上 结构化的对象往往被映射 为库表记录 对库表记录的组成通常采用实体的 属性来描述 但是 事实上 业务对象的组成元 素是有规律的 而且不同的元素对于库表记录的 确定的贡献是不同的 因此 定义了组成元素的 角色 即维度 度量值和一般属性 基于此 本 文给出了维度记录模型的概念 定义 1 维度记录模型 DRM dimension record model 采用维度记录模型来表示库表记录 一个记录可以定义为一个四元组 DRM RN A Role Weight 其中 RN record name 表示记录的 名称 A attribute 表示记录的属性 Role Dimension Measurement Generic 表示属性 所属的角色 即维度 度量值和一般属性 维度 是是决定实体变化的独立的属性 是分析问题的 角度 蕴涵着一定的分类特征和层级关系 度量 值表示记录中关注的具有数量特征的属性 一般 属性是指除维度和度量值之外的记录属性 Weight 是各个属性的权重 维度记录模型有效的表示了记录的组成 标 识了各个组成成分的角色 维度 度量值和一般 属性 并对不同角色的属性给出了相对应的权重 值 使得接口的匹配更有针对性 采用鱼刺图表 示维度记录 对属性按角色进行了分类 比较直 观 如图 2 所示的是一个 业务开通申请单 对 象的维度记录模型 它包括地区维 申请日期维 机构维 客户维 4 个维度 手续费 材料费 2 个 度量值和服务类型 优惠方式等 4 个一般属性 并且标注了部分属性的权值 图 2 维度记录模型实例 业务开通申请单 3 2 领域对象模型 领域对象模型是用于描述领域对象组成的 一个领域对象由若干个维度记录中的部分或全部 属性组成 如图 1 a 所示 其中领域对象 A 由 dr1 dr2 dr3组成 dr1中的相关属性有 a1 a2 a3 a4 a6 其中 a5是不相关的 用阴影 标出 3 3 词根表 WordNet 和 Hownet 是目前存在的一些 较成熟的常识知识库 WordNet 采用词汇分类 来描述英文的词汇语义 HowNet 是一个利用 一种知识词典描述语言来描述概念与概念之间的 关系以及概念的属性与属性之间的关系的知识系 统 由于 WordNet 和 Hownet 侧重于描述常 识性知识 所以将其直接用于领域构件的匹配效 果不理想 本文参考 WordNet 和 Hownet 的体系结 构 构造了一个电信领域的词汇集 称之为词根 表 词根表中的词汇是领域对象的名称和属性 除了词汇的含义描述之外 词根表也描述了其在 接口命名时的缩写约定 其中每个词被表示为一 个词条 每个词条包括中文名 英文名 词根 含义 分类 5 个部分 例 1 是一个词条 例 词根表词条 中文名 计费方式 英文名 billing type 词根 BillTp 含义 计量费用的方式 包括包月 计时等 分类 金额 费用 在本文构造的电信领域词根表中 本文按业 务主题和环节对词根进行了分类 这些分类构成 76 通 信 学 报第 28 卷 了概念间名称相似度的基础 3 4 环境和操作分类表 在领域应用范围内 环境和操作的取值是一 定的 因此 本文按照领域应用的实际情况对环 境和操作的取值进行分类汇总 形成了环境和操 作分类表 如将环境划分用户界面层 User Interface 业务逻辑层 Business Logic 数据层 Database Layer 通用层 Utility 四类 将操 作划分为 增 删 改 查 验证 五大类 每 一大类又进行具体的细分 4 解析构件库生成 由假设 1 构件接口的命名是有规则的 在这 一步 要根据这些规则对构件进行解析 如图 1 a 所示 对原构件库进行解析 将生成解析构件库 在对构件进行解析时 多根据需要按照不同的刻 面分类解析构件 7 8 与刻面分类类似 本文将对 领域构件接口名称解析得到的特征词 tokens 划分 为三类 分别是环境 Environment 领域对象 Domain Object 和操作 Action 其中环境表示接口 所处的应用层次和复用的范围 操作是接口对领 域对象的动作 而领域对象是接口处理的对象 在解析阶段 对接口进行简化 elimination 扩展化 expansion 和特征化 tokenization 三种范化 操作 简化 elimination 是指删除对匹配没有意义 的前缀 后缀等 扩展化 expansion 是指根据词根 表中标记的形式 用全称代替缩写 如用 billing type 代替 BillTp 特征化 tokenization 是指根据接 口中的分隔符 等 以及其他大小写变化等规 则从接口中抽取出特征词 在范化之后 将生成的特征词划分为环境 对象 操作这三类 范化和分类的语义依据是命 名规则库 维度记录模型 操作分类表 环境分 类表 词根表等等 对特征词中的领域对象 不仅仅包括对其名 称的描述 通过对构件源代码的扫描 可以生成 对其组成的描述 如图 1 a 所示 其名称与词根表 中的一个词条相对应 组成由一个领域对象模型 来表示 将原有构件库的构件接口都进行解析 就生成了解析构件库 5 构件接口名称匹配 在解析构件库的基础上 就可以进行匹配计 算了 匹配计算的第一步是利用环境分类和操作 分类对构件接口进行过滤 过滤掉不匹配的构件 接口 这一步是较容易实现的 按照环境分类表 和操作分类表的约定即可 本文不在赘述 第二 步是对对领域对象进行基于名称和组成的语义匹 配 得到匹配度的量化值 由于领域对象的变化 性大 抽象程度高 因此 这一步是匹配的重点 和难点 领域对象的匹配是构件接口匹配的关键 目 前的研究大多是从名称上对对象的语义进行匹配 事实上 在行业应用领域 由于领域对象的抽象 程度很高 领域对象的组成不能完全体现在其命 名中 因此 对其组成进行匹配是很必要的 如 在电信运营支撑系统中 业务开通订单 的 条 目 和 明细 是两个不同的名称 但他们的组 成可能是相同的 比如都包含多条的服务类型 计费方式 费用等信息 因此 领域对象的匹配 度由两部分组成 名称匹配度 Sname name similarity 和 组成匹配度 Sconstruction construction similarity 领域对象匹配度的计算见式 1 Sobject wname Sname wconstructionSconstruction 1 其中 wname和 wconstruction分别是名称匹配度和组成 匹配度对应的权值 且有 wname wconstruction 1 并且 其取值在 0 到 1 之间 5 1 领域对象名称匹配度的计算 本文采用概念的词汇语义相似度的计算方法 进行领域对象名称匹配度的计算 根据领域对象 在词根表的分类 词根表可以被组织成一棵棵概 念层次树 在概念层次树的基础上 本文采用 Wu and Palmer 的计算方式 9 计算领域对象的名称匹配 度 Sname 如 name 2depth lso len lso len lso 2depth lso A B S AA BBA BA B 2 式 2 计算的是词汇 A 和 B 的语义相似度 并且 有 Sname A B 0 1 其中 lso A B 是最低级的 A 和 B 的共同祖先 depth C 是元素 C 在概念层次树 中的深度 len A B 是概念 A 和 B 之间的最优距离 若 A B 不在一棵树上 则约定其名称匹配度为 0 5 2 领域对象组成匹配度的计算 对于 2 个领域对象的组成匹配度 是从概念的 第 5 期张正等 基于语义的领域构件接口名称匹配方法 77 组成角度来考察概念的相似程度 如图3 所示 领 域对象由若干个相关的维度记录中的某些属性组成 将 2 个领域对象的组成相似度定义为其配对的 维度记录相似度的加权和 构件请求中的领域对象 A 和构件库中构件接口中领域对象B 的组成相似度 为 3 constructiondr 1 1 max m n iij j i SA BwSA B a 领域对象 A b 领域对象 B 图 3 领域操作对象组成相似度计算 其中 表示领域对象 A 和 B 中的第 i dr ij SA B 个维度记录和第 j 个维度记录的维度记录相似度 wi是 Ai的权重 m 为 A 中维度记录的个数 n 为 B 中维度记录的个数 维度记录相似度的计算需要对记录的属性 dr S 进行两两配对 使其角色相匹配 且相似度的和 最大 匈牙利算法是较好的解决两两配对的问题 的算法 其时间复杂度是 O n3 但本文中的两两 配对有其特殊性 第一是不同的属性具有不同的 角色 不能统一处理 第二是 2 个属性在匹配度 已经较高的情况下 较少会出现其与其他属性相 配对的情况 因此 在匈牙利算法的基础上 在 构造相似矩阵时进行了改进 从而提高了算法的 效率 计算维度记录相似度的算法如下 算法 1 维度记录相似度计算 s dr dr1 dr2 输入 dr1 dr2是两个维度记录 阈值 a 输出 维度记录相似度 s dr 1 对 dr1 dr2的度量值生成配对的 2 个词汇集 合分别为 dr1 M 和 dr2 M 2 比较 dr1和 dr2的维度名称 具有相同的维 度名称的维度的属性集构成配对的词汇集和 记 做 dr1 Di和 dr2 Di i 1 2 n 3 将未形成配对的角色为维度和度量值的属 性和一般属性一起 构成两个配对的词汇集合 记做 dr1 G 和 d2 G 4 构造 1 个度量值相似矩阵 n 个维度属性 相似矩阵和一个一般属性相似矩阵 按式 2 计算 nsim Li Nj Li和 Nj代表两个配对的词汇集中的第 i 个和第 j 个词汇 1 i l 1 j n 排到矩阵的第 i 行 第 j 列 如果其大于指定的阈值 a 则令其 所在的行和列上的其他元素均为 0 并不再计算这 些元素对应的词汇相似度的值 5 对每一个相似矩阵 重复 6 13 步 6 用各行元素的最大值减去各行元素 7 将每列元素减去本列中的最小值 此时每 行及每列中必然都含有零元素 8 从包含零最少的行 或列 开始 取一个零 作上标记 划去其所在行和列 9 重复步骤 8 直到所有的 0 被标记或者被 划去 如被标记的 0 的个数不够 min l n 则继续 如果被标记的 0 有 min l n 个 则按每个 0 所在的 行列分别取原词汇相似度值与其对应的在 dr1中的 权值相乘 累加到 sim dr 并转 5 计算下一个 相似矩阵 如计算完所有矩阵 则返回 s dr 算法 完 78 通 信 学 报第 28 卷 10 对没有标记 0 的行标 对标了 的行的 所有 0 对应的列标 对标了 的列上所有标记了 0 的行标 知道不能标 为止 11 将没有标 的行与标了 的列划上直线 这样 用最少的直线覆盖了所有的 0 12 找出没有被直线覆盖的所有元素中的最 小元素记为 xij 13 对标记了 的行减去 xij 对标记了 的列 加上 xij 返回 8 算法完 算法 1 完成了两次配对的工作 1 到 3 行是对 维度记录中属性的角色进行配对 形成配对的词汇 集合 4 到 13 行是对形成配对的词汇集合中的 词汇两两配对 得到最佳组合并进行相似度的计算 5 3 领域对象匹配度的计算实例 如图 3 所示 假设所有对应元素的名称相似 度为 1 其余为 0 即 name 1 0 ij ij Sa a ij 2 个权重 name 1 0 ij ij Sb b ij wname 0 2 wconstruction 0 8 阈值 a 0 7 设 A B 的名称匹配度 Sname A B 0 8 计算 2 个领域对象 A 和 B 的组成相似度 按 照算法 1 其步骤如下 计算 sdr dr1 dr1 0 2Sname a1 a1 0 2 Sname a2 a2 0 2Sname a4 a4 0 1Sname a6 a6 0 2 1 0 2 1 0 2 1 0 1 1 0 7 同理 计算 sdr dr2 dr2 0 2 1 0 2 1 0 2 1 0 3 1 0 9 根据假设 sdr dr3 dr4 0 所以 A B 的组成匹配度为 Sconstruction A B 0 4 0 7 0 5 0 9 0 73 则按式 1 有 Sobject 0 2 0 8 0 8 0 73 0 744 大于阈值 0 7 匹配成功 6 应用和实验 本文提出的基于语义的领域构件接口名称匹 配方法在电信运营支撑系统的开发中得到了初步 的应用 在该项目中 开发了基于该方法的构件 检索工具并发挥了很好的作用 该工具主要分为 3 个模块 辅助命名 接口检索和管理维护 辅助 命名是指根据用户的检索条件命名构件的接口名 接口检索包括模糊检索 高级检索以及分类检索 三类检索功能 并可以查询领域对象模型 XML 描述 图 4 显示的就是对检索结果中一个领域对 象的 XML 描述 管理维护包括对维度记录模型 词根表 环境分类 操作分类的加载和管理机制 以及对解析构件库的管理维护 该工具在程序员对构件复用时形成了很大的 帮助 由于熟练程度不同的程序员在对所查找构 件的描述上有一定的差距 因此 基于构件库 本文组织了三组不同熟练程度的程序员 分别针 对同样的查询任务 采用基于关键词的方法和本 文提出的方法 进行检索 结果如图 5 所示 对 任何类型的程序员 本文提出的方法在查准率和 查全率方面都比关键词的方法好 而且随着程序 员熟练程度的降低 本文提出的方法下降较少 也就是说其不依赖于程序员的熟练程度 对于复 用构件库的新手尤其适用 Component Retrieve Workshop V2 0Component Retrieve Workshop V2 0 文件 F 菜单项 加载 U 视图 V 帮助 H 检索 R 高级检索 构件检索完成 环境 对象 操作 And And bl pub adsl order form get 浏览 浏览 浏览 扩展检索条件 匹配度阈值 0 5 检索结果 component formmgr pubformget blformget blformquery pubformgetcount pubformgetinfo pubformcustgetinfo adslmgr pubadslformgetinfo pubadslgetcount pubadslitemget pubadslcustsearch 环境 对象 操作 pub adslform getinfo 按重用次数按匹配程度 adslform Commision charge material charge Product Class type Kind Org Branch Handler Customer CustType CustName Date submitdate 领域对象概念模型 pubadslinfoquery 检索 图 4 构件检索集成环境 另外 实验表明 使用该工具进行构件的查 询比查询未经解析的构件名称的效率提高了 20 左右 这主要是因为解析构件库事先对构件进行 了解析 匹配变的很容易 而基于关键词的匹配 将大量时间用于字符串的比较上了 第 5 期张正等 基于语义的领域构件接口名称匹配方法 79 图 5 2 种方法查全率和查准率的比较 7 结束语 本文提出的构件接口名称匹配方法 以构件 接口名称为匹配的对象 对接口进行了基于命名 规则库 维度记录模型 词根表以及环境分类和 操作分类的解析 将提取的特征词分成环境 对 象和操作三类 形成了解析构件库 在匹配阶段 利用维度记录模型计算领域对象的组成相似度 由于维度记录模型灵活的描述了记录组成各属性 的角色和权重 因此提高了构件检索的查全率 查准率和效率 并减轻了程序员的工作量 同时 该方法规划了构件接口命名 通过直接调用和模 仿两种复用方式 使得应用中对相似的结构采用 了相似的处理方式 是实现行业应用软件开发的 工程化管理的基础 在今后的工作中 将研究采 用 参考程序 的方法对模仿这种复用机制进行 具体的规划 参考文献 1 FRAKES W B POLE T P An empirical study of representation methods for reusable software components J IEEE Transactions on Software Engineering 1994 120 8 617 630 2 TORSHEN S ApproXQL Design and Implementation of an Approximate paUem Matching Language for XML R Technical Report BOl 02 Freie University at Berlin 2001 3 徐如志 钱乐秋