【文章內(nèi)容簡介】 予節(jié)點(diǎn)的編碼信息應(yīng)當(dāng)具有重構(gòu)XML片段的能力，這就要求能夠根據(jù)編碼得到路徑上其他節(jié)點(diǎn)信息?？疾飕F(xiàn)有的XML索引技術(shù)，前綴編碼具有此能力。其中，Dewey編碼以其簡單易理解而成為XML關(guān)鍵字查詢中解決SLCA問題的基本技術(shù).Dewey編碼是前綴編碼的一種，為此首先介紹前綴編碼的知識。前綴編碼直接將一個節(jié)點(diǎn)的雙親節(jié)點(diǎn)的編碼作為該節(jié)點(diǎn)編碼的前綴。例如，設(shè)XML樹T的一個節(jié)點(diǎn)u的前綴編碼為c(u)，則節(jié)點(diǎn)u的孩子節(jié)點(diǎn)v的編碼c(v)=c(u)．n。其中，n是節(jié)點(diǎn)v在節(jié)點(diǎn)u中所有孩子節(jié)點(diǎn)中的序號。 對于前綴編碼，要判斷一個節(jié)點(diǎn)v是否是另外一個節(jié)點(diǎn)u的后裔，只需要判斷字符串c（u）是否是字符串c（v）的前綴。前綴編碼的一個重要性質(zhì)是他們的字典有序性：以節(jié)點(diǎn)，．為根的子樹中的任意一個節(jié)點(diǎn)u，它的前綴編碼c(u)大于(小于)它的左兄弟子樹(右兄弟子樹)中所有節(jié)點(diǎn)的前綴編碼。因此，前綴編碼不僅能夠有效地支持包含關(guān)系等結(jié)構(gòu)上的查詢運(yùn)算等操作，而且能夠有效地支持文檔的位置關(guān)系的運(yùn)算。因此，前綴編碼被廣泛的用于XML關(guān)鍵字查詢之中。前綴編碼是一種全局編碼和局部編碼結(jié)合的編碼方式，即混合編碼。全局編碼有效的支持了祖先后代等包含先后關(guān)系的運(yùn)算，而局部編碼可以有效的進(jìn)行左右兄弟關(guān)系的判斷。前綴編碼作為全局編碼和局部編碼結(jié)合的方案的混合編碼，有效的繼承了前兩種編碼方案的優(yōu)點(diǎn)，這也是前綴編碼在XML文檔的關(guān)鍵字查詢中能被廣泛使用的原因之一。 Dewey編碼Dewey碼有效的實(shí)現(xiàn)了前綴編碼的思想，求解ILE算法中，使用的編碼是Dewey編碼或者Dewey碼的擴(kuò)展方案。：Dewey編碼，給定對應(yīng)XML文檔的標(biāo)簽有向樹G=(V,E,r,A)，G中任意節(jié)點(diǎn)的Dewey編碼由下列規(guī)則確定： (1)根節(jié)點(diǎn)r的Dewey編碼為0； (2)在對G進(jìn)行寬度優(yōu)先遍歷的過程中，如果節(jié)點(diǎn)v是節(jié)點(diǎn)u的第i個子節(jié)點(diǎn)，那么，節(jié)點(diǎn)v的Dewey碼為D(u)．(i1)，其中的D(u)表示節(jié)點(diǎn)u的Dewey編碼。Dewey碼u中所有被“．”分割的整數(shù)的個數(shù)表示該Dewey碼u的長度以表示。取XML樹中根節(jié)點(diǎn)r所在的層為1，那么稱Dewey碼u中與第i層節(jié)點(diǎn)對應(yīng)的整數(shù)為該Dewey碼的第i層整數(shù)，表示為。由1到i層整數(shù)組成的Dewey碼稱為該節(jié)點(diǎn)Dewey碼u的第i層前綴，表示為(i)。圖34給出了Dewey編碼的示例.圖33 前文已經(jīng)闡述了使用Dewey來進(jìn)行XML關(guān)鍵字查詢的優(yōu)勢，于是文獻(xiàn)在研究Dewey碼的性質(zhì)后，根據(jù)SLCA的特點(diǎn)，提出了以下四條Dewey編碼的性質(zhì)： slca({v}，S)={descendant(1ca(v，lm(v，S))，lca(v，rm(v，S)))} slca({v}，…，)=slca(slca({v}，…，)，)，k2 slca(，…，)=removeAncestor(slca({}，…，) slca(，…，)=slca(slca(，…，)，)，k2性質(zhì)3．1的lm(dewey,Keywords)方法是要進(jìn)行如下計(jì)算：當(dāng)dewey為包含一個關(guān)鍵字的Dewey碼，而Keywords為包含另外一個關(guān)鍵字的Dewey碼的集合的時候，lm方法返回一個Dewey碼x，x是Keywords中比dewey大的Dewey碼中的最小者。若不存在，則x為null。rm(dewey,Keywords)方法與lm類似，返回 Dewey碼y，y為Keywords中比dewey小的Dewey碼中的最大者，若不存在，則Y為null。lm和rm分別被稱作左匹配(Left Match)和右匹配(Right Match)。計(jì)算descendent(u，v)時，如果參數(shù)u，v其中之一為空，則返回另一個非空的Dewey碼：如果v包含u，則返回v，反之返回u。綜上，該性質(zhì)表示，當(dāng)一個Dewey 碼v與其左匹配的公共前綴i=lca(v,lm(v，S))和它右匹配的公共前綴j=lca(v，rm(v，S))時，且i和中的最小者為r，則r為包含v對應(yīng)的關(guān)鍵字與S對應(yīng)的關(guān)鍵字的SLCA。文獻(xiàn)給出了該計(jì)算方法的正確性的證明，這里不再重復(fù)。性質(zhì)3．2將性質(zhì)3．1擴(kuò)展到一個Dewey碼與多個關(guān)鍵字Dewey碼集合的計(jì)算中去，即先計(jì)算該節(jié)點(diǎn)與一個集合按照性質(zhì)3．1計(jì)算出的Dewey碼作為中間結(jié)果，再以此中間結(jié)果為種子，與下一個Dewey碼集合按照性質(zhì)3．1進(jìn)行計(jì)算，以此類推，最終得到SLCA節(jié)點(diǎn)。性質(zhì)3．3將一個集合中的每個Dewey碼v實(shí)施性質(zhì)3．2，從而計(jì)算出多個SLCA。之后，使用removeAncestor算法將非最緊致片段節(jié)點(diǎn)去除，即將待求解的Dewey碼集合中的每個元素使用性質(zhì)3．2。性質(zhì)3．4表示了實(shí)際計(jì)算SLCA過程中的迭代方案。ILE的基本思路可歸結(jié)為：首先，設(shè)計(jì)支持以關(guān)鍵字和Dewey碼組成的條目為數(shù)據(jù)格式的B+樹結(jié)構(gòu)(Dewey B．Plus Tree，簡稱DBPT)，并預(yù)先將XML 數(shù)據(jù)按照數(shù)據(jù)值的不同，分解保存到該數(shù)據(jù)結(jié)構(gòu)中去。B+樹結(jié)構(gòu)應(yīng)實(shí)現(xiàn)前文中涉及的兩個基本操作，即左匹配和右匹配操作，從而快速返回某個Dewey碼在另外一個關(guān)鍵字集合中的左匹配編碼和右匹配編碼。之后，獲取對應(yīng)給定關(guān)鍵字序列的Dewey碼集合，每個關(guān)鍵字對應(yīng)一個包含該關(guān)鍵字的節(jié)點(diǎn)的Dewey碼集合，并將全部集合按照集合內(nèi)元素的多少j即集合的勢，從小到大排序，用，…，表示，其中S對應(yīng)元素?cái)?shù)目最小的Dewey碼集合。以上計(jì)算可以通過另外一個以關(guān)鍵字為條目的B+樹來存儲對應(yīng)的倒排表，從而加速運(yùn)算。對于每個中的元素，使用性質(zhì)3．2進(jìn)行計(jì)算。最后，在經(jīng)過性質(zhì)3．3的removeAncestor操作，去除重復(fù)或者非SLCA節(jié)點(diǎn)的最終處理后，所得的SLCA編碼集合就是最終結(jié)果 ILE算法示例及分析R．E算法可以歸結(jié)如下：算法3．1 ILE(Indexed Lookup Eager)算法∥假設(shè)內(nèi)存中有能容納P個節(jié)點(diǎn)的緩存B0．IndexedLookupEager 0{ 1． v=null 2． While(there are more nodes in ){ 3． Read p nodes of into buffer B 4． For i= 2 to k 5． B=get_slca(B，) 6． If(v!=null amp。amp。 getFirstNode(B) is ancestor of v) 7． removeFirstNode(B) 8． If(v！=null amp。amp。 v is not ancestor of getFirstNode(B)) 9． Output v 1 0． v=removeLastNode(B) 11． Output B12. B={}13． ) 14． Output v15．)算法3．2 getslca(，)算法0．get_slca(，){ 1． Result={} 2． u=0 //u=root initially3． for each node v in { 4． x=descendant(1ca(v , lm(v，))，lca(V，rm(v，))) //pre() denotes the order of lefttoright and depthfirst 5． If(pre(u)=pre(x)){ 6． If(u is not x and u is not ancestor of x) 7． Result=Result {u} 8． u=x9． } 10． }11. Return Result {u} 12．}例如，給定查詢的關(guān)鍵字集合為{“John”，“Ben”，“Class”)，而它們對應(yīng)的Dewey碼集合為={，，)，={，．，)，= {，，)。假設(shè)p=3。在算法3．2的第一次迭代過程中，經(jīng)過第2行代碼的執(zhí)行過后，在第3行代碼處， B={，}。 經(jīng)過第4行代碼計(jì)算后，B=get_slca(get_slca([，]，)，)=getslca([]，)=[]。初始時，v=null，第6到第9行代碼沒有執(zhí)行。第10行和第11行代碼將上次計(jì)算的最后一個節(jié)點(diǎn)保留，因?yàn)檫@個結(jié)果需要被檢驗(yàn)，才能判定是否是SLCA節(jié)點(diǎn)。在第一次迭代結(jié)束后，第11行輸出null。第二次迭代開始后，第2行處，B讀取為B=[，]。經(jīng)過第4和第5行代碼計(jì)算后， B=getslca(get_slca([，]，)，)=getslca([，]，)={[]}。因?yàn)関=，所以第6行不執(zhí)行，而在第8行代碼執(zhí)行后，v=0．1．1作為SLCA節(jié)點(diǎn)被輸出。第10行代碼過后，v被賦予新值0．1．2，此時B為空，所以第1l行輸出也為null。在第2行，即第三次迭代的判定條件處，因?yàn)橹袥]有更多的元素，所以執(zhí)行第13行，將此時v=0．1．2作為SLCA輸出。 程序結(jié)束而在子程序算法3．2調(diào)用執(zhí)行時，如上面例子中的get_stca([，]，)，第l行處Result=null，第2行u=0。第3行v=，其左匹配為null，而這都是通過帶索引的關(guān)鍵字與對應(yīng)Dewey碼為條目的B+樹索引實(shí)現(xiàn)的。 x=descendant(1ca(，lm(，))，lca(，rm(，)))=descendant(lca(，null),lea(，))=descendant(null,0)=0，因?yàn)閐escendant會在一個參數(shù)為null時候，返回另一個參數(shù)。第5行pre(u=0)=pre(x=0)條件成立，但是第6行u=0等于x=0，判斷條件不符合，執(zhí)行到第8行u=x=0。第2次迭代x=descendant(lca(，lm(，))，lca(，rm(，))) = descendant(1ca(，null)，lca(，))=descendant(nuil,)=。第6行，u=0是x=，判斷條件不符合，所以，第8行處u=。第三次迭代，x=descendant(1ca(，lm(，))，lca(，rm(, )))=descendant(lca(，null)，lca(，))=descendant(null,)=。第6行判斷條件，u==，條件不成立，所以在第8行處，u=。最后一次迭代，因?yàn)闆]有待計(jì)算節(jié)點(diǎn)，所以至第10行，返回集合{}。ILE算法的復(fù)雜度為O(||kdlog|S|)，其中表示含有Dewey碼數(shù)目最少的關(guān)鍵字集合，k為關(guān)鍵字?jǐn)?shù)目，d為Dewey碼長度，也是descendant的復(fù)雜度，S取法與相反，即含有集合數(shù)目最多的集合。至于對k個關(guān)鍵字集合在計(jì)算時需要使用元素最少的集合作為的取值的原因，從算法復(fù)雜度中可以得出答案，即在k和d，以及查找B+樹結(jié)構(gòu)的復(fù)雜度log|S|作為固定值的情況下，|| 的取值決定了總體的時間復(fù)雜度。鑒于許多關(guān)鍵字的Dewey編碼變化量不大的事實(shí)，即B+樹索引的查找耗費(fèi)時間大于順序掃描時間的情況，ILE的另一個版本是Scan Eager(SE)算法。SE利用B+樹葉層次按序排序的事實(shí)，使用了游標(biāo)來完成左匹配和右匹配的操作，在此不做詳細(xì)介紹。但是，ILE算法存在如下不足：一是必須修改B+樹結(jié)構(gòu)支持必要的Dewey碼操作，實(shí)現(xiàn)較為復(fù)雜。而且，雖然B+樹索引結(jié)構(gòu)在現(xiàn)有的數(shù)據(jù)庫管理系統(tǒng)中普遍使用，但是都不適用于Dewey編碼數(shù)據(jù)。因此，如果試圖考慮在實(shí)際應(yīng)用中利用已有成熟的關(guān)系數(shù)據(jù)庫管理系統(tǒng)，代價(jià)較大。二是ILE算法計(jì)算SLCA的過程是“粗暴(brute)”的，即首先將全部XML 數(shù)據(jù)保存到改造過的B+樹；之后，獲取對應(yīng)不同關(guān)鍵字的Dewey碼集合；然后，反復(fù)調(diào)用Dewey碼的基本操作和B+樹上的匹配操作來求解SLCA節(jié)點(diǎn)。 ILE算法的實(shí)現(xiàn)ILE算法實(shí)現(xiàn)首先需要解決的是數(shù)據(jù)結(jié)構(gòu)的問題。在這次對ILE算法的實(shí)際實(shí)現(xiàn)中我采用的數(shù)據(jù)結(jié)構(gòu)是數(shù)組的形式，由于整個算法是由JAVA語言實(shí)現(xiàn)的這里援用ArrayList來實(shí)現(xiàn)數(shù)組功能。ArrayList是List接口的可變數(shù)組的實(shí)現(xiàn)。實(shí)現(xiàn)了所有可選列表操作，并允許包括null在內(nèi)的所有元素。除了實(shí)現(xiàn)List接口外，此類還提供一些方法來操作內(nèi)部用來存儲列表的數(shù)組的大小。每個ArrayList實(shí)例都有一個容量，該容量是指用來存儲列表元素的數(shù)組的大小。它總是至少等于列表的大小。隨著向ArrayList中不斷添加元素，其容量也自動增長。自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝，因此，如果可預(yù)知數(shù)據(jù)量的多少，可在構(gòu)造ArrayList時指定其容量。在添加大量元素前，應(yīng)用程序也可以使用ensureCapacity操作來增加ArrayList實(shí)例的容量，這可以減少遞增式再分配的數(shù)量。使用ArrayList中的get（），add（）等方法對多維數(shù)組的操作帶來方便。針對上節(jié)提出的ILE算法的不足，在本程序中對XML結(jié)構(gòu)樹的編碼使用類Dewey編碼，即先序遍歷結(jié)構(gòu)樹，每個節(jié)點(diǎn)的編碼即是本節(jié)點(diǎn)從根節(jié)點(diǎn)開始的所有祖先構(gòu)成的數(shù)組。如圖35中代表關(guān)鍵字xml的節(jié)點(diǎn)有17個，它的編碼可由二維數(shù)組表示（17，，，，，，，，，）。具體編碼可由下圖表示。圖35xml結(jié)構(gòu)樹編碼ILE算法SLCA的求解過程：1. 根據(jù)輸入的n個關(guān)鍵字在數(shù)據(jù)庫中查找關(guān)鍵字對應(yīng)的編碼；2. 將每個關(guān)鍵字的對應(yīng)的所有節(jié)點(diǎn)編碼作為二維數(shù)組存到一個ArrayList類型的三維數(shù)組中；3. 將三維數(shù)組的第一個二維數(shù)組即第一個關(guān)鍵字對應(yīng)的編碼看做4. 設(shè)定一個合理大?。╬）的緩沖區(qū)間B,將中的p個節(jié)點(diǎn)放入B中令i=2。5. 求B中每個節(jié)點(diǎn)v在中的左