閆學偉

(哈爾濱理工大學 計算機科學與技術學院，黑龍江 哈爾濱 150080)

1 引言

ERP構件庫作為支持ERP系統(tǒng)實現(xiàn)構件化開發(fā)的一個重要基礎設施，關鍵的目標是支持使用者高效而準確地發(fā)現(xiàn)他們所需要的可復用構件，與這一目標有關的主要技術問題是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的匹配 (圖中結點內字母相同的結點表示一個映射對)。

區(qū)域匹配 (Mr)如果存在Qsub到Tsub的一個映射f，滿足以下3個條件，則稱該映射f是Q到T的一個區(qū)域匹配。

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))可見區(qū)域匹配比子樹匹配的條件更張馳一些，在區(qū)域匹配中并沒有對映射對結點雙方的兒子結點的集合的勢進行約束。區(qū)域匹配如圖2所示的Q到T的匹配：

4 路徑匹配算法

在無序標簽樹中，結點的祖先后代的順序是有意義的，而兄弟結點的左右順序無關緊要，所以根據(jù)包涵匹配模型，把基于刻面描述的ERP構件樹用組成構件的路徑字符串連接表示，就可以實現(xiàn)ERP構件樹匹配從相應結點到路徑字符串匹配的轉換問題。用子字符串代表某刻面屬性路徑，即將路徑匹配轉換為字符串的匹配，應用相應的高效字符串查詢方法來實現(xiàn)構件查詢目的。圖3分別表示了ERP構件樹及其路徑描述，其中圖3(a)為3個構件的樹描述，圖3(b)很形象、清晰地表示了3個構件的所有路徑。

算法包括兩個步驟。首先是形成構件樹后綴排序字符串階段，對ERP構件庫中所有構件對應的構件樹建立后綴排列 (suffix array):將ERP構件按照從根結點到葉結點的路徑順序組成字符串，并按照字典順序將路徑串組成后綴排列。其次是查詢階段，將后綴排列構件庫中的路徑字符串與查詢樹路徑組成的字符串相比較，滿足條件的字符串即是滿足條件的ERP構件，從而實現(xiàn)ERP構件的查詢。

建立后序排列數(shù)據(jù)庫后綴排列是一種有效查詢大字符串的數(shù)據(jù)結構，由按字典順序排列的子字符串組成.如圖3(a)中的樹T2有兩條路徑，“d-a-c”，和“d-a-b”，樹 T2 建立后序排列如圖4所示:

算法是在路徑匹配算法中的查詢階段完成的，因此仍然按照原路徑匹配算法對ERP構件庫進行后綴排序建立索引，這里不再贅述。

5 實驗及驗證結論

為了驗證基于路徑匹配算法的有效性，該實驗選取了134個構件描述信息，它們來源于512個構件的構件庫。對庫中所有的構件建立基于路徑的后綴數(shù)組的索引。通過采用路徑匹配算法和基于關鍵字的算法，從系統(tǒng)中檢索40個構件得到如圖5所示的構件的平均查全率和查準率。

構件的查全率=檢索到的相關集合/庫中所有相關構件集合，查準率=檢索到的相關集合/檢索到的所有構件集合。A為基于刻面的路徑查詢的查準率和查全率，B為基于關鍵字的查詢的查準率和查全率。通過以上實驗可知，提出的基于刻面的路徑匹配算法能夠保證對構件具有很高的查全率和查準率。該方法在實踐中是可行的。

6 結語與展望

基于刻面的ERP構件描述是ERP構件檢索的一個重要方法，在基于刻面分類方法的基礎上結合樹匹配的相應理論提出了一種基于刻面的路徑匹配的ERP構件查詢方法，并給出了具體算法。該算法可以實現(xiàn)刻面信息的交錯和分解，只要保證節(jié)點的最先后代關系，就可以有效屏蔽不同構件分類的差異。因此對ERP構件的查詢具有模糊查詢的能力。同時為了提高查詢的效率，每棵ERP構件樹按后綴字典順序對應一棵后綴索引樹，以減少檢索時路徑搜索的次數(shù)。通過實驗證明該算法具有很高的查準率和查全率。今后的研究重點是如何改進該算法的性能，并使該算法適于不同ERP構件庫的檢索。

[1]王淵峰.基于刻面描述的構件檢索算法研究[D].博士學位論文，復旦大學，2002.

[2]常繼傳，李克勤，郭立峰等.青鳥系統(tǒng)中可復用軟件構件的表示與查詢 [J].電子學報，2006,28(8):20-23.

[3]王淵峰，張涌，任洪敏等.基于刻面描述的構件檢索閉.軟件學報，2002，13(8):46-56.

[4]何霆，占德臣，徐曉飛，王平.新一代ERP系統(tǒng)功能構件標準化問題研究[J].計算機集成制造系統(tǒng)，2004，10：177-182.