閆學(xué)偉

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

1 引言

ERP構(gòu)件庫作為支持ERP系統(tǒng)實現(xiàn)構(gòu)件化開發(fā)的一個重要基礎(chǔ)設(shè)施，關(guān)鍵的目標(biāo)是支持使用者高效而準(zhǔn)確地發(fā)現(xiàn)他們所需要的可復(fù)用構(gòu)件，與這一目標(biāo)有關(guān)的主要技術(shù)問題是ERP構(gòu)件的分類和檢索方法。ERP構(gòu)件的分類方法有很多種，其中隸屬信息科學(xué)領(lǐng)域的刻面分類方法正逐步得到重視與應(yīng)用。本文將ERP構(gòu)件以刻面分類模式的基礎(chǔ)上，借鑒樹匹配模型，提出了一種新的基于刻面分類模式的構(gòu)件檢索方法，這種方法既能檢索到與檢索條件精確匹配的構(gòu)件，又能兼顧對所檢索構(gòu)件的不完全描述，對構(gòu)件的檢索具有一定的張弛能力。因此能夠兼顧構(gòu)件檢索的查全率和查準(zhǔn)率，并且有較好的檢索效率。

2 刻面分類技術(shù)介紹

刻面分類檢索方法[2-3]是通過反映構(gòu)件本質(zhì)特性的視角（刻面）對構(gòu)件進行精確的分類。一個刻面分類模式由一組描述構(gòu)件本質(zhì)特性的刻面組成，每個刻面從不同的側(cè)面對構(gòu)件庫中的構(gòu)件進行分類。每個刻面由一組術(shù)語組成，稱為術(shù)語空間，描述子由不同的刻面中不同術(shù)語組成，用來描述構(gòu)件庫中特定的構(gòu)件。通過用戶構(gòu)造描述子形成查詢條件，在構(gòu)件庫中檢索符合條件的構(gòu)件，這樣對于用戶來說可以直觀的從不同角度指明待檢索的構(gòu)件，有利于用戶對構(gòu)件的理解。

3 樹匹配模型的概念

設(shè)Q為一棵查詢樹,Qsub是Q的結(jié)點集的一個子集，T為一棵構(gòu)件的刻面描述樹，Tsub是T結(jié)點集的一個子集。

子樹匹配 (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))表示兩個標(biāo)簽的距離在一定的！值范圍內(nèi);

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

|C(v1)|=|C(f(v1))|。(表示 C(v1)與 C(f(v1))具有相同的勢)

在子樹匹配中 與T的子樹 (T中所標(biāo)的與Q相對應(yīng)字母的子樹)是同構(gòu)的，如圖1中Q到T的匹配 (圖中結(jié)點內(nèi)字母相同的結(jié)點表示一個映射對)。

區(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))，表示兩個標(biāo)簽的距離在一定的閉值范圍

v1=parent(v2)f(v1)=parent(f(v2))可見區(qū)域匹配比子樹匹配的條件更張馳一些，在區(qū)域匹配中并沒有對映射對結(jié)點雙方的兒子結(jié)點的集合的勢進行約束。區(qū)域匹配如圖2所示的Q到T的匹配：

4 路徑匹配算法

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

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

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

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

5 實驗及驗證結(jié)論

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

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

6 結(jié)語與展望

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

[1]王淵峰.基于刻面描述的構(gòu)件檢索算法研究[D].博士學(xué)位論文，復(fù)旦大學(xué)，2002.

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

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

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