刻面和規(guī)約描述相結(jié)合的構(gòu)件檢索

陳杜英，劉韶濤

（華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建廈門361021）

刻面和規(guī)約描述相結(jié)合的構(gòu)件檢索

陳杜英，劉韶濤

（華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建廈門361021）

通過(guò)分析基于刻面分類和構(gòu)件規(guī)約語(yǔ)法的檢索方法，發(fā)現(xiàn)刻面分類及其檢索方法側(cè)重于構(gòu)件的靜態(tài)特征描述，沒有考慮構(gòu)件的行為描述等，而構(gòu)件規(guī)約語(yǔ)法描述部分偏重于構(gòu)件的行為描述，構(gòu)件規(guī)約對(duì)構(gòu)件中每個(gè)功能的語(yǔ)法描述具有獨(dú)立性.設(shè)計(jì)一種基于字符串匹配的軟構(gòu)件刻面檢索算法，同時(shí)考慮到刻面檢索沒有支持組裝這一需求，提出在檢索過(guò)程中，插入基于構(gòu)件規(guī)約的語(yǔ)法匹配過(guò)程，以提供較準(zhǔn)確的構(gòu)件組裝信息和提高復(fù)用效率.

構(gòu)件檢索；刻面分類；規(guī)約描述；字符串匹配

軟件復(fù)用被認(rèn)為是解決軟件危機(jī)的有效途徑，而基于構(gòu)件的軟件開發(fā)方法是軟件復(fù)用的重要手段，因此需要構(gòu)件庫(kù)提供合理的構(gòu)件描述組織方式，并提供方便的構(gòu)件檢索機(jī)制.復(fù)用者從構(gòu)件庫(kù)中檢索構(gòu)件，組裝成新的應(yīng)用系統(tǒng)，從而達(dá)到提高軟件開發(fā)效率的目的，所以構(gòu)件的描述應(yīng)能夠滿足組裝的需要，反映構(gòu)件組裝信息.刻面分類方法包括刻面模式、同義詞辭典和概念距離圖，從不同的具有代表性的刻面維度對(duì)構(gòu)件進(jìn)行描述，是目前應(yīng)用最廣泛的構(gòu)件檢索法方法.基于構(gòu)件規(guī)約語(yǔ)法描述的檢索方法具有較高的查準(zhǔn)率.然而，刻面描述方法不具有對(duì)構(gòu)件行為方面的描述，對(duì)于軟構(gòu)件復(fù)用者的組裝需求無(wú)法給予很好的滿足.本文采用以刻面分類為主，語(yǔ)法規(guī)約描述相結(jié)合的方法對(duì)構(gòu)件進(jìn)行分類［1］.

1 基于刻面的構(gòu)件描述模型

1.1 基于XML技術(shù)的構(gòu)件表示［2］

XML（可擴(kuò)展標(biāo)記語(yǔ)言）是萬(wàn)維網(wǎng)聯(lián)盟于1998年2月發(fā)布的一種標(biāo)準(zhǔn)［3］.XML主要用于描述數(shù)據(jù)，在定義標(biāo)記方面具有較大的靈活性和伸縮性.使用XML描述軟構(gòu)件信息體現(xiàn)了一些優(yōu)越性，主要表現(xiàn)在：可以任意選擇具有代表性的屬性進(jìn)行描述，較清晰地對(duì)軟構(gòu)件信息進(jìn)行分層和組織，以及定義軟構(gòu)件實(shí)體之間的約束關(guān)系等.因此，文中采用基于XML的構(gòu)件刻面描述方法，對(duì)軟構(gòu)件的刻面進(jìn)行描述，把每一個(gè)軟構(gòu)件描述成一棵軟構(gòu)件描述樹，將查詢信息轉(zhuǎn)換成一棵查詢樹.

根據(jù)參考樹匹配模型［4－5］，采用松弛匹配模型以達(dá)到較高的查全率.松弛匹配模型，只要求軟構(gòu)件描述樹與查詢樹的葉子節(jié)點(diǎn)之間保持閾值范圍內(nèi)即可，且通過(guò)節(jié)點(diǎn)的邏輯操作，包括插入、刪除、修改計(jì)算匹配代價(jià)，要求查詢樹的所有葉子節(jié)點(diǎn)在描述樹中找到對(duì)應(yīng)的匹配節(jié)點(diǎn).

1.2 構(gòu)件的描述

為了檢索和組裝的方便，給出其刻面和構(gòu)件的規(guī)約語(yǔ)法描述信息.刻面描述是對(duì)應(yīng)構(gòu)件的語(yǔ)義描述，構(gòu)件的規(guī)約是其語(yǔ)法描述，具有唯一性.給出構(gòu)件的5個(gè)刻面，分別是使用環(huán)境（AE），功能（FUNn），應(yīng)用領(lǐng)域（AA），表示方法（REP）和層次（LAY）.使用環(huán)境包括硬件環(huán)境、操作系統(tǒng)、數(shù)據(jù)庫(kù)和編程環(huán)境等方面；功能是對(duì)構(gòu)件所提供的功能描述；應(yīng)用領(lǐng)域是對(duì)該構(gòu)件可能應(yīng)用到的領(lǐng)域的名稱；表示方法是用來(lái)描述構(gòu)件內(nèi)容的表達(dá)方法；層次是表示構(gòu)件描述的抽象層次.每個(gè)刻面都有相應(yīng)的標(biāo)準(zhǔn)刻面值，這些刻面值還具有一個(gè)達(dá)到一定閾值的語(yǔ)義同義詞表.展示的一個(gè)構(gòu)件的XML描述文檔，如圖1所示.

圖1 構(gòu)件的XML文檔描述形式Fig.1 Document description form of the component′s XML

為了滿足組裝的需求，即滿足第二次規(guī)約語(yǔ)法匹配的需要，對(duì)入庫(kù)的每個(gè)構(gòu)件要求提供對(duì)規(guī)約語(yǔ)法的描述，包括填寫構(gòu)件對(duì)外需求的服務(wù)，以及對(duì)外提供的服務(wù)，包括填寫接口描述信息，服務(wù)個(gè)數(shù)，每個(gè)服務(wù)的服務(wù)名、參數(shù)名、類型列表信息和返回值名及返回值類型等信息.

1.3 為構(gòu)件建立后綴排列構(gòu)件庫(kù)

用字符串代表某刻面屬性路徑，即將路徑匹配轉(zhuǎn)換為字符串的匹配，應(yīng)用相應(yīng)的高效字符串查詢方法來(lái)實(shí)現(xiàn)構(gòu)件查詢的目的.把構(gòu)件的每一條路徑用字符串來(lái)表示，用字符串代表刻面路徑，把“＃”，“－”兩個(gè)特殊符號(hào)用于構(gòu)件樹的路徑匹配轉(zhuǎn)換.“＃”用來(lái)分隔不同的路徑，“－”用來(lái)連接不同的字符［6］，如對(duì)應(yīng)圖1所示，軟構(gòu)件描述轉(zhuǎn)換成字符串形式為COM－AA－MIS＃COM－AE－DB－Oracle＃COM－AE－Memory－1G＃COM－AE－OS－linux＃COM－FUN－fileDownload＃COM－LAY－design＃COM－REP－IDL.

為后續(xù)構(gòu)件刻面查詢方便，在每次構(gòu)件入庫(kù)或有構(gòu)件修改時(shí)，實(shí)時(shí)更新后綴排列（stuffx array）構(gòu)件庫(kù)，將構(gòu)件庫(kù)中的所有構(gòu)件按照從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑順序組成字符串，并按字典順序路徑串組成后綴排列.

對(duì)構(gòu)件庫(kù)中的所有構(gòu)件樹產(chǎn)生后綴排列構(gòu)件庫(kù)算法［6］有如下幾個(gè)步驟：

輸入為構(gòu)件庫(kù)D，輸出為后綴排列構(gòu)件庫(kù)SD，并保存更新后的SD；

1）SD＝Φ；

2）for軟件庫(kù)中的每一棵構(gòu)件描述樹；

3）｛；

4）按照先序遍歷構(gòu)件樹的所有從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑，用字符串表示，將所有路徑字符串按分隔符分開；

5）按照字典順序?qū)λ新窂介L(zhǎng)度字符串進(jìn)行后綴排列；

6）把所有的字符串連接成一個(gè)長(zhǎng)的字符串S，把S加入到SD中；

7）｝；

8）return（SD）；

9）update（SD）.

2 基于刻面描述的構(gòu)件規(guī)約語(yǔ)法匹配

2.1 規(guī)約語(yǔ)法匹配方法

構(gòu)件規(guī)約是對(duì)構(gòu)件復(fù)用信息的形式化描述，服務(wù)作為語(yǔ)法描述信息的重要部分，每個(gè)服務(wù)都是不可分割的一個(gè)獨(dú)立存在，如圖2所示.因此，將服務(wù)作為語(yǔ)法匹配的原子單位［7］.

圖2 基于規(guī)約語(yǔ)法匹配的原理Fig.2 Principle based on the specification syntax matching

服務(wù)中，每個(gè)Function代表構(gòu)件提供或請(qǐng)求的一種功能.由于服務(wù)參數(shù)類型和返回值類型的不可更替性，被作為服務(wù)匹配的基調(diào).基調(diào)匹配是基于基本類型匹配的，類型主要分為4種，即簡(jiǎn)單數(shù)據(jù)類型；結(jié)構(gòu)類型（結(jié)構(gòu)、聯(lián)合和枚舉）；數(shù)組類型和自定義類型.任意替換兩個(gè)等價(jià)類型不會(huì)影響程序的運(yùn)行，基調(diào)匹配正是建立在類型等價(jià)原理之上的，而規(guī)約語(yǔ)法匹配是基于參數(shù)類型和返回值類型的匹配.

2.2 基于刻面描述的構(gòu)件匹配過(guò)程

結(jié)合刻面和規(guī)約描述的構(gòu)件匹配流程圖，如圖3所示.刻面檢索過(guò)程中，首先用戶輸入刻面描述查詢信息，系統(tǒng)將查詢信息自動(dòng)生成構(gòu)件查詢樹，并組成按字典順序排好序的后綴排列查詢字符串.其次，檢索系統(tǒng)將調(diào)用刻面檢索字符串匹配算法，將查詢字符串與后綴排列構(gòu)件庫(kù)中的每一棵構(gòu)件樹的字符串進(jìn)行匹配處理.最后，返回滿足匹配條件的字符串序列代表的構(gòu)件，用戶選擇是否繼續(xù)進(jìn)行規(guī)約語(yǔ)法匹配查詢，如選擇繼續(xù)匹配，用戶輸入規(guī)約語(yǔ)法查詢信息，系統(tǒng)對(duì)檢索出的構(gòu)件進(jìn)行按規(guī)約語(yǔ)法匹配結(jié)果返回構(gòu)件集合.

圖3 結(jié)合刻面和規(guī)約描述的構(gòu)件匹配流程圖Fig.3 Matching flow chart combined with facet and specification description

2.3 構(gòu)件的檢索

將用戶輸入的刻面查詢信息生成查詢樹Q，并生成字符串T，與后綴排列構(gòu)件庫(kù)SD中的每一棵構(gòu)件描述樹的字符串S進(jìn)行比較.如果字符串匹配不成功，則退出循環(huán)；否則，結(jié)合軟構(gòu)件樹的插入、刪除、修改節(jié)點(diǎn)操作來(lái)計(jì)算構(gòu)件匹配代價(jià).按照匹配代價(jià)，輸出滿足查詢條件的軟構(gòu)件集.

構(gòu)造查詢樹路徑字符串算法［6］主要有如下幾個(gè)步驟：

輸入為查詢樹Q，輸出為查詢字符串T；

1）T為空；

2）按先序遍歷查詢樹Q的所有從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑，建立字符串，并用分隔符分開路徑字符串；

3）按照字典順序?qū)λ新窂介L(zhǎng)度字符串進(jìn)行后綴排列；

4）把所有的字符串連接成一個(gè)長(zhǎng)的字符串T；

5）return T.

軟構(gòu)件的查詢轉(zhuǎn)換成查詢字符串T與軟構(gòu)件后綴排序構(gòu)件庫(kù)SD的匹配為題，即轉(zhuǎn)換為子串查找問(wèn)題，模式字符串T在主串SD中是否出現(xiàn)，以及出現(xiàn)的位置問(wèn)題.

軟構(gòu)件的查詢算法有如下幾個(gè)主要步驟：

輸入為軟構(gòu)件查詢樹字符串T，軟構(gòu)件庫(kù)形成的后綴排列字符串SD，而輸出為符合查詢條件的軟構(gòu)件集合R；

1）R＝φ；

2）根據(jù)字符串T中符號(hào)“＃”出現(xiàn)次數(shù)，計(jì)算查詢樹的路徑數(shù)m；

3）for SD中的每一棵軟構(gòu)件樹對(duì)應(yīng)的字符串S；

4）采用字符串匹配算法，計(jì)算T在S中出現(xiàn)的情況，以判斷軟構(gòu)件是否符合查詢條件；

5）if沒有找到符合距離閾值的子字符串，則退出本次循環(huán)；

6）else對(duì)于在T中出現(xiàn)未在S中出現(xiàn)的字符（樹的節(jié)點(diǎn)），根據(jù)概念距離圖計(jì)算插入代價(jià)；對(duì)于未在T中出現(xiàn)而在S出現(xiàn)的字符（節(jié)點(diǎn)），計(jì)算節(jié)點(diǎn)刪除代價(jià)；對(duì)于在無(wú)法通過(guò)刪除或修改操作而成為閾值范圍內(nèi)的節(jié)點(diǎn)，計(jì)算修改代價(jià)，并將這3種代價(jià)之和作為匹配近似度的參考值；

7）統(tǒng)計(jì)查詢樹字符串T與構(gòu)件樹字符串S匹配路徑數(shù)目k；

8）if（k＝＝m），將該查詢字符串對(duì)應(yīng)構(gòu)件樹加入結(jié)果集R；

9）退出for循環(huán)；

10）返回結(jié)果集R（根據(jù)匹配代價(jià)從小到大排序）.

假設(shè)查詢樹有k條路徑，構(gòu)件樹中有k條路徑與查詢樹字符串子串匹配，則說(shuō)明滿足查詢要求，該方法描述了松弛匹配的過(guò)程.

2.4 構(gòu)件的匹配

基于上述檢索方法中得到的構(gòu)件不一定能夠滿足復(fù)用者對(duì)組裝的要求，為了進(jìn)一步提高查準(zhǔn)率，特安排第二次匹配.在此，采用構(gòu)件的規(guī)約語(yǔ)法匹配方法進(jìn)行精確匹配.

構(gòu)件規(guī)約語(yǔ)法描述的重要組成部分是構(gòu)件接口，包括構(gòu)件對(duì)外提供的服務(wù)描述和對(duì)外需求的服務(wù)描述兩部分組成，構(gòu)件規(guī)約的語(yǔ)法匹配特指構(gòu)件接口的語(yǔ)法匹配.接口的服務(wù)的參數(shù)類型列表和返回值類型部分是語(yǔ)法匹配的重要信息.然后，根據(jù)服務(wù)的參數(shù)類型和返回值類型的語(yǔ)義相似程度來(lái)判斷構(gòu)件的規(guī)約語(yǔ)法匹配的高低等級(jí)，按照此匹配等級(jí)重新排列構(gòu)件結(jié)果集給復(fù)用者.

2.5 軟構(gòu)件檢索過(guò)程的實(shí)例分析

圖4 系統(tǒng)生成的構(gòu)件查詢樹Fig.4 Component query tree of the system generated

通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明如何在檢索過(guò)程中利用刻面檢索和規(guī)約語(yǔ)法匹配技術(shù)進(jìn)行構(gòu)件檢索的.假定用戶需要查詢一個(gè)“管理用戶”構(gòu)件，軟構(gòu)件檢索有3個(gè)主要過(guò)程.

1）用戶填寫刻面描述信息.使用環(huán)境為OS，windows DB，oracle，所屬領(lǐng)域?yàn)镸IS，件功能為user management，表示方法為C＋＋，抽象層次為design.

2）系統(tǒng)自動(dòng)將用戶的輸入信息轉(zhuǎn)化為構(gòu)件刻面查詢樹（圖4），并將查詢樹與構(gòu)件庫(kù)中的構(gòu)件描述樹的后綴排列匹配，將查詢結(jié)果返回給用戶.按字典順序排好序的生成字符串為：component－AA－MIS＃component－AE－DB－oracle＃component－AE－OS－windows＃component－FUN－user management＃component－LAY－design＃component－REP－C＋＋.

3）規(guī)約語(yǔ)法匹配查詢階段.主要提供源代碼級(jí)構(gòu)件更精確的查找.用戶輸入軟構(gòu)件的語(yǔ)法描述信息，系統(tǒng)將用戶輸入的規(guī)約信息經(jīng)語(yǔ)法分析器轉(zhuǎn)換成規(guī)范化的語(yǔ)法信息，與軟構(gòu)件庫(kù)中的候選構(gòu)件的規(guī)范化語(yǔ)法信息進(jìn)行語(yǔ)法匹配算法匹配，得出候選匹配結(jié)果集，用戶輸入的語(yǔ)法信息如圖5所示.

以上給出的構(gòu)件檢索與匹配模型及算法分析，為精確查找到滿足組裝需要的構(gòu)件提供了可能.

圖5 用戶輸入規(guī)約語(yǔ)法查詢信息Fig.5 User′s input specification syntax information

3 結(jié)論

文中分析了當(dāng)前研究的各種軟構(gòu)件檢索方法，詳細(xì)研究當(dāng)前應(yīng)用比較成功的基于構(gòu)件刻面描述的檢索方式，并設(shè)計(jì)一種基于字符串匹配的軟構(gòu)件刻面檢索算法.在考慮刻面檢索沒有支持組裝這一需求的同時(shí)，提出在檢索過(guò)程中插入基于構(gòu)件規(guī)約的語(yǔ)法匹配過(guò)程，以提供較準(zhǔn)確的構(gòu)件組裝信息及提高復(fù)用效率.

由于刻面描述方法，不具有對(duì)構(gòu)件行為方面的描述，對(duì)于軟構(gòu)件復(fù)用者的組裝需求無(wú)法很好滿足，因此，文中采用以刻面分類為主，語(yǔ)法規(guī)約描述相結(jié)合的方法對(duì)構(gòu)件進(jìn)行分類.在同一系統(tǒng)中支持多種分類模式和檢索方法的組合使用，以較好地滿足構(gòu)件檢索的查全率和查準(zhǔn)率的要求

［1］ FRALES W B，POLE T P.Proteus：A software reuse library system that supports multiples representations methods［J］.ACM SIGER Forum，1990，24（3）：43－55.

［2］ 鄧勇.基于本體與刻面相結(jié)合的構(gòu)件檢索方法研究［D］.武漢：華中師范大學(xué)，2007：14－16.

［3］ 韓忠明.XML數(shù)據(jù)查詢與信息檢索系統(tǒng)［M］.北京：中國(guó)水利水電出版社，2010：3－4.

［4］ SHASHA D，TSONG J，WANG L.Exact and approximate algorithm for unordered tree matching［J］.IEEE Trans on Systems，Man and Cybemetrics，1994，24（4）：668－678.

［5］ WANG Zhong－jie，ZHANG De－chen，XU Xiao－fei.A component retrieval method based on feature tree matching［J］.International Journal of Information Technology，2006，12（8）：60－72.

［6］ 姚全珠，劉波.一種高效的基于刻面分類的構(gòu)件檢索算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（2）：118－120.

［7］ 張弛，吳健，胡正國(guó).基于規(guī)約匹配的軟件組件組裝［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2005，23（5）：623－627.

Research on Component Retrieval Based on Facet and Specification Description

CHEN Du－ying，LIU Shao－tao
（College of Computer Science and Technology，Huaqiao University，Xiamen 361021，China）

By analysis of components retrieval methods based on facet classification and component specification syntax.We find that the faceted classification and retrieval methods focus on the components′static characteristics，without considering the component behavior description.While component specification syntax description focuses on emphasize the aspect of component behavior description of the statutes of the components which is independent of the semantics of each function in the component description.We design a software component facets retrieval algorithm based on the string matching，and considering the facets retrieval didn′t support for the demand of the assembly.In the retrieval process，insert specification syntax matching process based on component specification，to provide accurate information of the component composition and improve the efficiency of reuse.

component retrieval；facet classification；specification description；string matching

TP 311.13

A

（責(zé)任編輯：錢筠 英文審校：吳逢鐵）

1000－5013（2012）05－0513－05

2012－04－02

劉韶濤（1969－），男，副教授，主要從事軟件體系結(jié)構(gòu)與軟件復(fù)用的研究.E－mail：shaotaol＠hqu.edu.cn.

國(guó)務(wù)院僑辦科研基金資助項(xiàng)目（09QZR02）