基于ＸＭＬ的樹匹配構件檢索算法的研究與實現

摘要：針對構件檢索的特點，結合模式分析中的樹匹配思想，提出了構件樹匹配模型，并在此基礎上針對基于XML的刻面描述構件表示，實現了基于XML的樹匹配構件匹配檢索算法。該算法可以在保持構件查準率的前提下有效提高構件的查全率。實驗結果證明了該算法的可行性與有效性。

關鍵詞：刻面分類； 可擴展標記語言； 構件檢索； 樹匹配

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2008)04－1013－03

隨著軟件復用實踐的深入和軟件構件庫規模的擴大，軟件構件技術研究得到了學術界和產業界越來越多的重視。構件表示與檢索技術是可復用軟件構件庫的兩個最重要的核心技術[1]。有效的構件檢索機制能夠降低構件查找和理解的成本，從而提高構件的復用率和軟件產品的開發效率。

刻面分類方式可以較大地提高檢索效率，而且有助于復用者理解構件和目標領域，所以構件的刻面表示以及在此基礎上的構件檢索技術已得到軟件復用界的重視。鑒于刻面描述構件表示方法已有成熟的理論和實踐基礎，XML規范天生具有極強的信息表達能力，它允許自定義標記，因此可以定義一套用于構件信息表示的標記語言來描述構件。

1構件相關技術

1．1構件相關概念

目前對構件[2]的定義，在軟件學術界和產業界還未形成統一的認識。廣義上講，構件是指可以被明確標志的軟件制品，它可以是需求分析、設計、代碼、測試用例、文檔或軟件開發過程中的其他產品。狹義上講，軟件構件是指可復用的、提供明確接口、完成特定功能的程序代碼塊（包括源代碼、二進制代碼或可執行代碼）。構件庫（component repository）是可復用軟件構件的集合，主要目的是提供軟件生存周期產品的重用機制以滿足特定的軟件代價（效益和生產率），并作為開發可重用軟件構件和基于可重用構件開發這兩個生存周期的聯系體系。具體地說，構件庫就是類似于用來存儲、檢索和管理構件的數據庫，是開發可重用構件和使用可重用構件的中間媒介。

1．2構件分類描述與檢索

對構件庫中構件的合理分類和組織將有助于軟件開發人員從構件庫中迅速找到所需要的構件。目前，有很多關于構件的分類和檢索方法， 根據復雜度和檢索效果的不同可以分為基于文本、基于詞法描述子和基于規約的編碼和檢索；從構件表示出發可以分為人工智能、超文本和信息科學三類方法。在實際應用系統中，基于構件的復用應用較為成功的是枚舉、屬性值、正文檢索、關鍵詞和刻面等幾種，其中又以關鍵詞分類和刻面分類[3]兩種應用最多。

構件檢索方法主要歸結為如下三類：

a)基于外部索引的檢索，如常見的關鍵詞檢索、刻面檢索和基于屬性的檢索等。這類檢索大多采用控制詞典、屬性等外部索引對構件進行檢索。幾乎所有的研究都認為提供自動化支持是必要的，自動索引、分層瀏覽和查詢條件的簡單規約和自動生成有助于提高效率、增加復用機會和提高復用質量。W.Frakes 的研究表明，各種分類法基礎上的檢索在輔助不同用戶的理解上并無太大差異，需要考慮同一個系統中支持多種基于分類法的組合使用。

b)基于內部靜態索引的檢索。根據構件自身的結構元素進行索引構件，以構件規約的語法和語義匹配技術等為主要方法。到目前為止，規約的語法匹配已研究得比較充分，語義匹配也形成了一般性方法。

c)基于內部動態索引的檢索。利用構件的可執行特征（如構件的輸入與輸出空間）進行檢索，這類檢索中常見的檢索方法是基于行為的檢索。由于實際應用的復雜性，目前基于行為的檢索只停留在理論研究階段。

1．3構件刻面分類模式

刻面分類模式[3，4]由一組描述構件本質特征的刻面組成，每個刻面從不同角度對構件庫中的構件進行精確分類；每個刻面具有一組術語，術語之間具有一般/特殊關系而形成的結構化術語空間。刻面分類方法是從若干不同的維度描述復雜對象，具有枚舉、屬性/值和關鍵詞等分類方法的優點。也正是其諸多優點使得它被NATO采納和推薦使用，成為一種目前使用最為廣泛的分類模式。

2XML技術在軟件構件中的應用

由于XML規范具有極強的信息表達能力，它允許自定義標記，可以定義一類用于構件信息表示的標記語言(目前已有CML、CBL及IFX等數百種基于XML的自定義標記語言)，將這套標記語言作為構件信息表示的規范。使用XML來表示構件信息具有六個優點[5]：a)可以使用最能反映構件信息特征的標記來表示構件信息；b)有助于構件信息進行合理的分層和組織；c)準確地定義構件信息的數據類型；d)當信息實體間有內在關系時，可以定義這些實體間的約束關系；e)當所描述的構件信息必須滿足某種模式時，可以指定與構件信息匹配的正則表達式；f)對于信息實體在必要時還應該指定其出現的頻率。

為了更好地組織構件信息、更精確地表示信息實體間的內在關系，鑒于XML的上述特點，本文采用了基于XML的構件刻面描述方法，并且基于XML刻面構件描述方法很容易轉換為構件刻面描述樹，可以將查詢過程中出現的刻面、子刻面以及術語構造為一棵構件查詢樹，借鑒成熟的樹匹配理論思想。這樣就可以將構件的檢索轉換為構件查詢樹與構件刻面描述樹之間的匹配問題，查詢結果為滿足查詢條件的構件描述樹。這樣能夠兼顧構件的查全率和查準率。

3樹松弛匹配構件檢索算法

3．1有關基本概念

1)樹的概念

樹是n(n≥0)個有限數據元素的集合。一棵樹可以用T來表示：T（V，E，root(T)）。其中：V表示一個有限的節點集;root(T)∈V表示樹的根節點;E表示邊集，它是V上的一個二元關系，滿足反自反、反對稱、可傳遞性。如果（u，v）∈E，則稱u節點為v節點的父節點，記為u=parent(v)或v=child(u)。如果樹中兄弟節點左右順序沒有任何意義，則稱此樹為無序樹。

2)樹映射的概念[6，7]

3．2樹匹配模型對構件檢索的適用性分析

由樹匹配模型定義可以看出，上述三種樹匹配模型的約束條件由強到弱的順序依次為子樹匹配→包含匹配→松弛匹配。其中，子樹匹配要求保持節點對的父子關系，即查詢樹中父子關系的術語在構件描述樹中也是嚴格的父子關系，而且要求查詢樹中的葉子節點在構件描述樹中同樣為葉子節點，是一種結構上的精確匹配。結果僅為與檢索條件精確匹配的條件。

包含匹配在子樹匹配的基礎上放寬了節點信息之間的對應關系，只要求保持節點的祖先后代關系，允許某些參與映射的節點信息出現錯層的情況，從而提高查全率。

松弛匹配不僅放寬了節點信息之間的對應關系，而且允許查詢樹中的葉子在構件描述樹中不為葉子節點，進一步放寬了匹配條件，在保持原查準率的前提下有效地提高了查全率[8，10]。

3．3術語空間編碼

描述構件的每個刻面是由一組基本術語所構成的，術語之間具有一般/特殊關系而形成結構化術語空間。一般/特殊關系的引入能夠描述不同構件在通用性與專用性方面的差異，并隱含地表達構件之間的相似關系。復用者可以在術語空間中周游，對所需構件的抽象層次權衡取舍。在進行構件檢索時，構件描述樹和構件查詢樹中的術語均來自術語空間。為了方便檢索，根據術語空間的一般/特殊關系對術語空間中的術語進行編碼。每個術語的編碼稱為術語ID。具體編碼策略如下：

a)術語與其編碼一一對應，編碼是術語的惟一ID；

b)編碼中的第一位記錄刻面信息表示的是構件的刻面，取值是刻面ID；

c)編碼中的每一位表示術語空間的一層，第一位表示術語空間的第一層（刻面），前兩位表示第二層，依此類推；

d)具有相同父術語的術語編碼按字典順序排定；

e)編碼中的每一位取值表示層次樹中術語的相對位置，在此規定其取值范圍是A，B，C，…，Z。

術語空間編碼示意圖如圖4所示。

術語的編碼策略通過對術語空間中的術語進行簡單編碼，為術語空間中的每一個術語確定了一個惟一的術語ID。該術語ID也隱含地反映了術語之間的關系。由于構件描述樹和構件查詢樹中的術語均來自于術語空間，通過該編碼策略為構件描述樹和構件查詢樹中的每個節點都確定了一個惟一的術語ID，為構件檢索過程中建立索引提供了依據。

3．4構件樹索引的建立

由于不同的構件具有不同的形態，在使用術語空間中的術語對構件進行描述時，可以嚴格按照術語空間的層次構造構件樹，也允許不嚴格按照術語空間的層次結構構建構件樹，即構件樹中為父子關系的節點對在術語空間中可以為祖先關系，同時用戶在進行構件檢索時最關心的是葉子節點。基于以上兩點，對每棵構件樹根據其葉子節點來建立索引，以供檢索時使用。對于每棵構件描述樹用兩個字符串（即術語串ST1和層次串ST2）來為其建立索引。術語串ST1為構件樹中所有葉子節點的術語ID按字典順序排序，并用分隔符分隔后連接而成的一個長字符串；層次串ST2為對應的每個葉子節點的層次ID按字典順序排序，并用分隔符分隔后連接而成的一個長字符串。

3．5匹配算法的描述

由本文以上的描述可知，每棵構件樹的術語串和層次串隱含地表達了該構件樹的信息。這樣就將構件描述樹和構件查詢樹的樹匹配問題轉換成了兩棵樹中葉子節點的術語串和層次串的兩個字符串之間的匹配問題，并根據匹配類型的不同得到了一個按匹配程度排序的構件集合。該匹配算法過程如下：

輸入：構件描述樹的術語串ST1，構件查詢樹的ST1′，構件描述樹的層次串ST2，構件查詢樹ST2′；

輸出：按匹配程度排序的構件集C。

a)從構件查詢樹的術語串中依次取出術語ID t′。

b)判斷t′在構件描述樹的術語串ST1是否存在。若存在，則跳轉d)。

c)判斷t′在構件描述樹的術語串ST1是否為某個術語ID的前綴。若是，則符合樹松弛匹配，將匹配結果存入集合C3；否則，返回a)繼續判斷下一棵構件描述，直到退出循環。

d)判斷t′所對應的層次ID是否相等，若對應的層次ID相等，則符合子樹匹配，將匹配結果存入集合C1；否則，符合樹包含匹配，將匹配結果存入集合C2。返回a)，繼續判斷下一棵構件描述樹，直到退出循環。

e)返回檢索到的符合條件的構件集合C。C=C1+C2+C3。

鑒于篇幅的限制，本文只給出了匹配算法的自然語言描述，源代碼實現部分從略。

3．6實驗及驗證結論

本實驗是在Microsoft Visual Studio.NET 2003(實現語言為C#)、Microsoft SQL Server 2000環境下設計并實現了上述匹配思想。在對構件庫中刻面描述的構件(3 000個)建立索引后， 可以直接對索引文件進行查詢， 并可保持索引文件與構件信息同步更新。

在對此構件庫的測試過程中，筆者為測試人員提供了所需構件(10個) 的一段文字描述， 由他們使用構件庫提供的刻面檢索功能在構件庫中進行查找。將他們所查找到的構件集合進行統計可得：總能在查找到的構件列表的前3位出現所需構件；相似程度較高的構件總能在前10位出現。這說明本文的思想在構件檢索的查準率和查全率方面是可行的。如圖5所示，完成匹配所需要的時間為300 ms左右(100個葉子節點)，所以此種檢索方法在效率上也是可行的。

4結束語

基于XML的構件刻面描述是結構化描述，不僅易于被人理解，而且易于被計算機理解；并且基于XML構件刻面描述方法很容易轉換為構件刻面描述樹，可以將查詢過程中出現的刻面、子刻面以及術語構造為一棵構件查詢樹。借鑒成熟的樹匹配理論思想，這樣就可以將構件的檢索轉換為構件查詢樹與構件刻面描述樹之間的匹配問題。通過上述對算法的描述，并經實驗驗證可以得出該算法具有如下特點：a)將構件描述樹與構件查詢樹之間的匹配問題轉換為兩棵樹葉子節點的術語串和層次串兩個串的匹配問題，具有較高的檢索效率；b)術語串的術語ID按字典順序排列，匹配效率高；c)通過層次ID的建立，允許對構件樹的不完全描述，因此對匹配具有一定的松弛匹配能力，具有較高的查全率。基于XML的構件描述，不但可以實現構件高效檢索，而且有利于基于構架的構件自動化組裝。

參考文獻:

[1]PRIETO－DIAZ R. Implementing faceted classification for software reuse[J]. Communications of ACM， 1991，34(5):88－97.

[2]MILI H， MILI A. Reuse based software engineering[R]. New York: Wiley， 2002:444－459.

[3]DeLUCENA V F Jr. Facet－based classification scheme for industrial automation software components[EB/OL]. http:research.microsoft.com/~cszypers/events/WCOP2001/Lucena.pdf.

[4]SCHLIEDER T.ApproXQL:design and implementation of an approximate pattern matching language for XML， B01－02[R]. Berlin: Freie University， 2001.

[5]KILPELAINEN P. Tree matching problems with applications to structured text database[R]. Helsinki: Department of Computer Science， University of Helsinki， 1992.

[6]TORSHEN S，NAUMANN F.Approximate tree embedding for que－rying XML data[C]//Proc of ACM SIGIR Workshop on XML and Information Retrieval. Athens:[s.n.]， 2000.

[7]SHASHA D， TSONG J， WANG L. Exact and approximate algorithm for unordered tree matching[J]. IEEE Trans on Systems， Man and Cybernetics， 1994，24(4):668－678.

[8]WANG Zhong－jie，ZHAN De－chen， XU Xiao－fei.A component retrie－val method based on feature tree matching[J]. International Journal of Information Technology， 2006，12(8):60－72.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”