基于刻面分类的ERP构件检索

闫学伟

(哈尔滨理工大学 计算机科学与技术学院，黑龙江 哈尔滨 150080)

1 引言

ERP构件库作为支持ERP系统实现构件化开发的一个重要基础设施，关键的目标是支持使用者高效而准确地发现他们所需要的可复用构件，与这一目标有关的主要技术问题是ERP构件的分类和检索方法。ERP构件的分类方法有很多种，其中隶属信息科学领域的刻面分类方法正逐步得到重视与应用。本文将ERP构件以刻面分类模式的基础上，借鉴树匹配模型，提出了一种新的基于刻面分类模式的构件检索方法，这种方法既能检索到与检索条件精确匹配的构件，又能兼顾对所检索构件的不完全描述，对构件的检索具有一定的张弛能力。因此能够兼顾构件检索的查全率和查准率，并且有较好的检索效率。

2 刻面分类技术介绍

刻面分类检索方法[2-3]是通过反映构件本质特性的视角（刻面）对构件进行精确的分类。一个刻面分类模式由一组描述构件本质特性的刻面组成，每个刻面从不同的侧面对构件库中的构件进行分类。每个刻面由一组术语组成，称为术语空间，描述子由不同的刻面中不同术语组成，用来描述构件库中特定的构件。通过用户构造描述子形成查询条件，在构件库中检索符合条件的构件，这样对于用户来说可以直观的从不同角度指明待检索的构件，有利于用户对构件的理解。

3 树匹配模型的概念

设Q为一棵查询树,Qsub是Q的结点集的一个子集，T为一棵构件的刻面描述树，Tsub是T结点集的一个子集。

子树匹配 (Ms)如果存在Qsub到Tsub的一个映射满足以下4个条件，则称该映射f是Q到T的一个子树匹配。

v1=v2 f(v1)=f(v2)，v1,v2∈Qsub f(v1),f(v2)∈Tsub(表示 f为单射)

.label(v1)label(f(v1))表示两个标签的距离在一定的！值范围内;

v1=parent(v2)f(v1)=parent(f(v2))

|C(v1)|=|C(f(v1))|。(表示 C(v1)与 C(f(v1))具有相同的势)

在子树匹配中 与T的子树 (T中所标的与Q相对应字母的子树)是同构的，如图1中Q到T的匹配 (图中结点内字母相同的结点表示一个映射对)。

区域匹配 (Mr)如果存在Qsub到Tsub的一个映射f，满足以下3个条件，则称该映射f是Q到T的一个区域匹配。

v1=v2 f(v1)=f(v2)，v1,v2∈Qsub，f(v1),f(v2)∈Tsub(表示f为单射);

label(v1)label(f(v1))，表示两个标签的距离在一定的闭值范围

v1=parent(v2)f(v1)=parent(f(v2))可见区域匹配比子树匹配的条件更张驰一些，在区域匹配中并没有对映射对结点双方的儿子结点的集合的势进行约束。区域匹配如图2所示的Q到T的匹配：

4 路径匹配算法

在无序标签树中，结点的祖先后代的顺序是有意义的，而兄弟结点的左右顺序无关紧要，所以根据包涵匹配模型，把基于刻面描述的ERP构件树用组成构件的路径字符串连接表示，就可以实现ERP构件树匹配从相应结点到路径字符串匹配的转换问题。用子字符串代表某刻面属性路径，即将路径匹配转换为字符串的匹配，应用相应的高效字符串查询方法来实现构件查询目的。图3分别表示了ERP构件树及其路径描述，其中图3(a)为3个构件的树描述，图3(b)很形象、清晰地表示了3个构件的所有路径。

算法包括两个步骤。首先是形成构件树后缀排序字符串阶段，对ERP构件库中所有构件对应的构件树建立后缀排列 (suffix array):将ERP构件按照从根结点到叶结点的路径顺序组成字符串，并按照字典顺序将路径串组成后缀排列。其次是查询阶段，将后缀排列构件库中的路径字符串与查询树路径组成的字符串相比较，满足条件的字符串即是满足条件的ERP构件，从而实现ERP构件的查询。

建立后序排列数据库后缀排列是一种有效查询大字符串的数据结构，由按字典顺序排列的子字符串组成.如图3(a)中的树T2有两条路径，“d-a-c”，和“d-a-b”，树 T2 建立后序排列如图4所示:

算法是在路径匹配算法中的查询阶段完成的，因此仍然按照原路径匹配算法对ERP构件库进行后缀排序建立索引，这里不再赘述。

5 实验及验证结论

为了验证基于路径匹配算法的有效性，该实验选取了134个构件描述信息，它们来源于512个构件的构件库。对库中所有的构件建立基于路径的后缀数组的索引。通过采用路径匹配算法和基于关键字的算法，从系统中检索40个构件得到如图5所示的构件的平均查全率和查准率。

构件的查全率=检索到的相关集合/库中所有相关构件集合，查准率=检索到的相关集合/检索到的所有构件集合。A为基于刻面的路径查询的查准率和查全率，B为基于关键字的查询的查准率和查全率。通过以上实验可知，提出的基于刻面的路径匹配算法能够保证对构件具有很高的查全率和查准率。该方法在实践中是可行的。

6 结语与展望

基于刻面的ERP构件描述是ERP构件检索的一个重要方法，在基于刻面分类方法的基础上结合树匹配的相应理论提出了一种基于刻面的路径匹配的ERP构件查询方法，并给出了具体算法。该算法可以实现刻面信息的交错和分解，只要保证节点的最先后代关系，就可以有效屏蔽不同构件分类的差异。因此对ERP构件的查询具有模糊查询的能力。同时为了提高查询的效率，每棵ERP构件树按后缀字典顺序对应一棵后缀索引树，以减少检索时路径搜索的次数。通过实验证明该算法具有很高的查准率和查全率。今后的研究重点是如何改进该算法的性能，并使该算法适于不同ERP构件库的检索。

[1]王渊峰.基于刻面描述的构件检索算法研究[D].博士学位论文，复旦大学，2002.

[2]常继传，李克勤，郭立峰等.青鸟系统中可复用软件构件的表示与查询 [J].电子学报，2006,28(8):20-23.

[3]王渊峰，张涌，任洪敏等.基于刻面描述的构件检索闭.软件学报，2002，13(8):46-56.

[4]何霆，占德臣，徐晓飞，王平.新一代ERP系统功能构件标准化问题研究[J].计算机集成制造系统，2004，10：177-182.