嵌入式構件中的自適應機制與策略
2009-01-01 00:00:00萬云強陳文宇張艷
計算機應用研究 2009年3期
（電子科技大學 計算機科學與工程學院， 成都 610054）
摘 要：為了對嵌入式構件進行智能管理，提出了一種基于實例的學習算法。該適應算法能對經XML形式化表達過的構件進行自適應調整，從而在軟件復用過程中減少人工干預。它比由自然語言描述的構件有更強的通用性、靈活性、自治性。
關鍵詞：機器學習; 擴展標記語言解析器; K近鄰法; 擴展標記語言; 樹匹配
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)03091403
Adaptive mechanism and strategy in embedded component
WAN Yunqiang， CHEN Wenyu， ZHANG Yan
(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)
Abstract:The paper proposed an instancebased learning algorithm for the conducting of some intelligence management on embedded component. This selfadaptive algorithm leaded to the components reuse writing with XML with less human interfere. Components formalized by XML are more universal， flexible and autonomous than those described by nature languages.
Key words：machine learning; XML parser; KNN; XML; tree matching
0 引言
基于復用的軟件開發可以有效地提高軟件開發的質量和效率[1]。隨著對軟件復用的研究與深入，軟件構件庫作為軟件復用的一項重要基礎設施，已得到產業界與學術界越來越多的重視[2]。
針對構件的復用，國內外的研究人員做了許多有益的研究工作。例如Schantz等人針對綁定所有系統行為說明到一個地方和將有關質量服務的人工管理集作為一個單個、可重復利用行為靈活地插入到應用中去，提出了將低層的抽象、規范和執行綁定成高層抽象，再加上管理層預先提供的質量服務自適應行為方法[3]。它能實現一定程度的軟件復用，但它存在一個問題。其運用一些簡單邏輯語言和自然語言來描述接口、適應行為、合同，與形式化語言相比，缺少通用性和不利于自動化處理。XML具有嚴格語法定義的形式語言，并且自定義靈活。本文首先提出一種實例學習的算法，它們的實例就是用XML形式化表達，并加上一定的模糊性，可能解決構件復用的問題。最后，從一定程度上證明其可行性和有效性。
本項目是一個嵌入式項目的子項目，嵌入式構件與一般構件本身沒有區別。但在成熟平臺上，W3C是提供解析的工具，而筆者必須自己寫解析器來解析XML文件給出策略。
該解析器的設計方案就是本文的主題。它的存儲方式是二叉樹存儲，筆者對樹的層次進行了改進。
本文給出XML簡單表示，并用樹來表示；給出孩子兄弟表示法存儲結構，提出二叉樹的構建、插入、刪除和檢索的基于實例學習算法。
1 基于實例的學習[4]
對于這類算法，學習過程只是簡單地存儲已知的訓練數據。當遇到新的查詢實例時，一系列相似的實例被從存儲器中取出，并用來分類新的查詢實例。
針對不同的構件描述形式，人們已提出了許多相應的檢索方法。例如Podgurski等人[5]針對構件的行為表示提出基于構件行為采樣的檢索；Zaremski等人[6]針對構件的形式化規格說明提出基調匹配(接口規約)和規約匹配 (功能規約)。許多研究者還提出了將神經網絡[7]、模糊數學[8]、關聯傳動[9]等方法應用于構件的檢索。
構件的檢索，本文采用兩步走的方法：首先找到構件各屬性所在最小公倍數子樹；然后采用決策樹加數理邏輯方法來檢索該子樹，屬性匹配采用帶權K近鄰法來作模糊匹配。它是基于實例學習的思維來做的。
2 XML及樹性存儲
XML是W3C(World Wide Web Consortium)推薦的一種可置標語言，其設計動機是在網絡上規范化文檔傳輸。它具有嚴格語法定義的形式語言，但較一般的形式語言簡捷和通用。XML實際上是一種定義語言，即使用者可以定義無窮無盡的標記來描述文件中的任何數據元素，從而突破了HTML固定標記集合的約束，使文件的內容更豐富、更復雜，并組成一個完整的信息體系。XML主要的優點有良好的可擴展性、嚴格的語法要求、內容與形式分離、較好的保質性。
用尋找P2P下載服務的例子來說明本文提出的動態策略的用法。在尋找某臺可以服務的終端時，必須知道端口號、IP地址和它的系統平臺。需要以上條件才能搜索到相應的策略，并根據該策略連接到該終端。
一個可置標語言XML描述為一棵樹。
〈? xml version=\"1．0\" ?〉
〈server〉
〈serveraddress〉
〈ip〉221.132.23.62〈/ip〉
〈port〉2388〈/port〉
〈/serveraddress〉
〈 serveropsystem〉
〈window〉
〈 windowme/〉
〈 window98/ 〉
〈 window2000/ 〉
〈 windowxp/ 〉
〈/ window 〉
〈linux 〉
〈 redhat/〉
〈 blue/ 〉
〈/ linux 〉
〈 /serveropsystem〉
〈/server〉
XML文件轉換為樹的邏輯表示形式，如圖1所示。
樹轉換為二叉樹形式，如圖2所示。
3 K近鄰算法[4，10]
所有的實例對于n維空間中的點Rn。一個實例的最近鄰是根據標準歐氏距離定義的，精確地講，把任意的實例x表示為下面的特征向量：
〈a1(x)， a2(x)， …，an(x)〉
其中：ar(x)表示實例x的第r個屬性值。那么兩個實例xi和xj間的距離定義為
d(xi，xj)=∑nr=1(ar(xi)-ar(xj))2
即其中各項帶上權值調整項與項之間的重要程度。
d(xi，xj)=∑nr=1wr×(ar(xi)-ar(xj))2
同時，本文運用專家定義的門閥τ值，大于門閥就生成新的策略來匹配；否則就用原來的策略去匹配。
4 樹的相關算法
樹提供搜索的一種方式。本文設計的機制是不用人工干預就可以自動地插入新的子樹。本文有人工的干預是對機器學習中增強實例學習的一種加實例的方法。也可以自己去刪除一棵子樹，本文稱其為舊策略的刪除（在這里一般都認為這些策略不適應現在的需求）。它在機器學習里稱為假設空間搜索。
構建整個樹的算法應用一般二叉樹的構建算法，即先看左子樹是否為空，不為空時，遞歸左子樹；為空時，看右子樹，非空，遞歸右子樹，為空，向父節點找，到根節點停止。構建樹采用遞歸算法，本文未同別的一起給出是因其簡單。
檢索整個樹的算法，本文采用樹的層次遍歷。找到要找的最小公倍數子樹；再細遍歷子樹，找到所有屬性用匹配的全部屬性來進行模糊匹配。本文用決策樹或數理邏輯來分析該子樹。本文僅給出查找最小公倍數子樹的算法。
Tree Query(Tree root， Type value)
{ p=root;
while(1)
{
p=p->leftchild;
if(p->value==value)
return p;
inQueue(p);
while(p->rightchild){
if(p->value==value)
return p;
inQueue(p)
}
outQueue(p);
}
}
插入時先檢索到子樹，筆者找到適當地方插入具體生成的小樹，并且提供人工干預的界面和接口函數。小樹的插入需要K近鄰法各因子的總和數及小樹的直接父節點。
void InsertTree(Tree root， Type value)
{
p= Tree Query(root， value);
p=p->leftchild;
while(p->rightchild)
min=(value-calculate (p));
if(min＜τ)
exit();
else
buildall(p);
}
刪除子樹時必須先檢索到子樹，筆者找到適當地方刪除具體的小樹。小樹的刪除僅需要小樹的直接父節點。
void DeleteTree(Tree root， Type value)
{
p= Tree Query(root， value);
q=p->rightchild;
parent=p->parent;
if(!q)
{
qparent=parent;
parent->child=q;
}
else
deleteAll(p);
}
5 刻面描述形式化方法
對一個刻面描述方案，本文將其中的刻面、子刻面分別映射為樹中對應的父節點、子節點，對采用某個刻面描述方案描述的構件，可以將其相應的刻面描述術語映射為對應的葉子節點。例如：PrietoDiaz最早提出來的刻面描述方案為兩個主刻面，即功能和環境，且每個主刻面分別有三個子刻面(作用、對象、媒介)和(應用領域、系統類型、客戶類型)。在該刻面描述方案下描述的某個構件可以用如圖3所示的刻面樹來表示。對于構件的查詢也可以相應地表示為一棵查詢樹，即將查詢中出現的刻面名、子刻面名轉換為相應層次的父節點和子節點，將查詢的刻面術語值轉換為葉節點，并用一個虛擬的根節點將它們組合為一棵查詢樹。
6 結束語
從文獻[11，12]中可以推出構件到后面的匹配必先找到該子樹，再在該子樹中找到屬性匹配。筆者提出一種構件匹配的解決方案，對樹查找到該子樹的算法優化會更好。用決策樹來匹配決策子樹，將不同于刻面檢索。本文提出一個樹型的形式化方案，用子節點來構成父節點，例子分析如下：
Window:=me｜98｜2000｜xp
Linux:=redhat｜bluepoint
Serveropsystem:=window｜linux
Serveraddress:=ip｜port
Server:= Serveraddress｜Serveropsystem
構件方面的工作有文獻[11~14]提出的在XML構件上查找，而本文提出一種基于機器學習的解決方案。當然，筆者的工作目的不一樣，但就XML構件上查找是一樣的。筆者用實例學習和分析學習結合的機制來解讀構件，認為這是一種新的方法，有可能解決這類問題。筆者將文獻[11~14]提出的檢索稱為靜態檢索；本文提出的稱為動態檢索，在機器學習中稱為假設空間搜索。本文很少提到策略，是因為策略在XML文件中。
參考文獻：
［1］IVAR J. Software reuse:architecture，process and organization for business success[M].Reading：AddisonWesley Publishing Company，l997:415.
[2]MILI H，MILI A. Reuse based software engineering[M]. New York：Wiley，2002:444459.
[3]SCHANTZ R，LOYALL J，ATIGHETCHI M， et al. Packaging quality of service control behaviors for reuse[C]//Proc of the 5th IEEE International Symposium on Objectoriented Realtime Distributed Computing(ISORC).Washington DC:IEEE Computer Society， 2002:375.
[4]MITCHELL T. Machine learning[M].曾華軍，張銀奎，等譯.北京：機械工業出版社，2003：165169.
[5]PODGURSKI A，PIERCE L. Retrieving reusable software by sampling behavior[J]. ACM Trans on Software Engineering andMethodology，1993，2(3)：286303.
[6]ZAREMSKI A M. Signature and specification matching[D]. Pittsburgh:School of Computer Science，Carnegie Mellon University，l996.
[7]MERKL D，TJPOA A M， KAPPEL G. Learning the semantic similarity of reusable software components[C]//FRAKES W B. Proc of the 3rd International Conference on Software Reuse(ICSR’94)．Rio de Janeiro：IEEE Computer Society Press，1994:3341.
[8]DAMIANI E，FUGINI M G，BETTETTINI C. A hierarchy aware approach to faceted classification of objectedoriented components[J]. ACM Trans on Software Engineering and Methodology，1999，8(3)：215262.
[9]HENNINGER S．Supporting the process of satisfying information needs with reusable software libraries：an empirical study[C]//SAMADZADEH M H，MANSOUR K Z. Proc of the 17th International Conference on Software Engineering and Software Reusability．Seattle：ACM Press，1995:267270.
[10]邊肇祺，張學工. 模式識別[M].北京：清華大學出版社， 2002:136159.
[11]王淵峰，張涌，任洪敏，等. 基于刻面描述的構件檢索[J].軟件學報，2002，13(8):15461551.
[12]徐如志，錢樂秋，程建平，等. 基于XML的軟件構件查詢匹配算法研究[J].軟件學報， 2003，14(7):11951202.
[13]姚全珠，盂麗，崔杜武.基于CBR和XML的軟構件檢索方法[J].計算機應用，2007， 27(7):17111714.
[14]孫念民，李萬龍，鄭山紅，等.基于XML技術的軟件構件表示與檢索[J].計算機系統應用，2007，17(10):9497.
[15]W3C．Extensible markup language(XML)[EB/OL]. (20080706)[20080713].http://www.w3.org/XML/.
[16]常繼傳，李克勤，郭立峰，等.青鳥系統中可復用軟件構件的表示與查詢[J]．電子學報，2000，28(8)：2024.
[17]李曉博，繆淮扣，劉靜.基于形式規格說明的構件匹配[J].計算機應用與軟件，2006，23(10):1012.
