【正文】 這中存儲方式對算法的實現(xiàn)帶來方便。為此提出 Indexed Lookup Eager Algorithm。在整個畢業(yè)設(shè)計期間，您不斷地給予我?guī)椭椭笇?，使我不但完成了我的設(shè)計任務，還學到了很多相關(guān)的專業(yè)知識，同時在對于我研究生復試的事情，也給予很大的支持，我非常感謝陳老師的理解和幫助。其中，對用戶要求較低，有著良好用戶友好度的XML關(guān)鍵字查詢?nèi)找娉蔀檠芯康臒狳c，也有著較為廣闊的發(fā)展前景。通過改正錯誤的設(shè)計和實現(xiàn)部分，保證了圖書借閱管理系統(tǒng)可以完成需求分析中制定的需求。在整個測試中，采用了白盒測試和黑盒測試相結(jié)合的方法。（1）單元測試。 for(int k=0。i++) { ArrayListArrayListInteger al=new ArrayListArrayListInteger()。在啟動畫面消失后，屏幕將顯示一個對話框，提示用戶選擇工作空間的目錄位置，這個目錄用于存放用戶創(chuàng)建的項目文檔（這個是自選的任意目錄），最后進入MyEclipse的工作環(huán)境。 安裝MySQL數(shù)據(jù)庫本關(guān)鍵字查詢系統(tǒng)的后臺數(shù)據(jù)庫管理選擇的是MySQL數(shù)據(jù)庫，在Windows系統(tǒng)下，MySQL數(shù)據(jù)庫的下載、安裝和配置過程如下：（1） 下載和安裝MySQL。本系統(tǒng)數(shù)據(jù)庫各個表的結(jié)構(gòu)如下所示。本系統(tǒng)設(shè)計的主要實體及其屬性為：（下劃線部分為主鍵）關(guān)鍵字索引表：（關(guān)鍵字名稱，節(jié)點個數(shù)，節(jié)點編碼）ID索引表：（ID號，關(guān)鍵字名稱）ER模型的聯(lián)系用于刻畫實體間的關(guān)聯(lián)。 if(c != d) { break。 } else { int a=(0)。amp。若有一個參數(shù)為空則返回另一個，若都為空則返回空。i=n。 if ((((0)))=((0))) { return (i)。 i 0) { return (i1)。i++) { ArrayListInteger pCur=new ArrayListInteger()。5. 求B中每個節(jié)點v在中的左匹配和右匹配6. 求節(jié)點v和它的左（右）匹配的最低公共祖先（LCA）7. 如果v在中的左匹配和有匹配都存在則定有一個節(jié)點是父親節(jié)點一個是孩子節(jié)點，將孩子節(jié)點（descendant）是x；8. 判斷x是否符合SLCA的條件符合則加入result中9. 返回result，重復49，直到in。自動增長會帶來數(shù)據(jù)向新數(shù)組的重新拷貝，因此，如果可預知數(shù)據(jù)量的多少，可在構(gòu)造ArrayList時指定其容量。null但是，ILE算法存在如下不足：一是必須修改B+樹結(jié)構(gòu)支持必要的Dewey碼操作，實現(xiàn)較為復雜。第6行，u=0是x=，判斷條件不符合，所以，第8行處u=。因為v=，所以第6行不執(zhí)行，而在第8行代碼執(zhí)行后，v=0．1．1作為SLCA節(jié)點被輸出。假設(shè)p=3。之后，獲取對應給定關(guān)鍵字序列的Dewey碼集合，每個關(guān)鍵字對應一個包含該關(guān)鍵字的節(jié)點的Dewey碼集合，并將全部集合按照集合內(nèi)元素的多少j即集合的勢，從小到大排序，用，…，表示，其中S對應元素數(shù)目最小的Dewey碼集合。綜上，該性質(zhì)表示，當一個Dewey 碼v與其左匹配的公共前綴i=lca(v,lm(v，S))和它右匹配的公共前綴j=lca(v，rm(v，S))時，且i和中的最小者為r，則r為包含v對應的關(guān)鍵字與S對應的關(guān)鍵字的SLCA。Dewey碼u中所有被“．”分割的整數(shù)的個數(shù)表示該Dewey碼u的長度以表示。前綴編碼的一個重要性質(zhì)是他們的字典有序性：以節(jié)點，．為根的子樹中的任意一個節(jié)點u，它的前綴編碼c(u)大于(小于)它的左兄弟子樹(右兄弟子樹)中所有節(jié)點的前綴編碼。之后，根據(jù)節(jié)點的信息(例如節(jié)點的編碼)求解SLCA節(jié)點。因此，SLCA的問題就是求解XML文檔樹中所有滿足如下條件的子樹的根節(jié)點：(1)子樹必須包含所有關(guān)鍵字序列，關(guān)鍵字序列中的任一關(guān)鍵字必然分布于該子樹的葉節(jié)點；(2)子樹中不存在更小的子樹同樣包含所有的關(guān)鍵字。例如，在圖2．3中，用戶希望查詢題目中包含“IR”并且作者中有“John”的文章，則輸入的關(guān)鍵字集合為{“IR”，“John”}，根據(jù)LCA的定義，節(jié)點paper(15) 是這兩個關(guān)鍵字的一個LCA，所以paper(15)是查詢的一個輸出。為給出LCA的準確定義，首先明確XML樹中的一些概念。 一個XML文檔通常由5部分組成：聲明、元素、注釋、字符引用和處理指令，圖3．1即為一個實際的XML文檔的示例?xml version=”1．0”encoding=”UIF一8”? proceedings issue articles article titlebibliography On data design／title authors author position=0Karen Botnich/author ／authors ／article article titleface recognition／title authors author position=OCola Cohen／author ／authors ／article ／articles publisher year2003／year address countryGermany／country ／address ／publisher ／issue ／proceedings圖3．1 XML文檔舉例在實際處理XML數(shù)據(jù)時，更為常見的是XML標簽有向圖模型，由XPath 規(guī)范描述。XML數(shù)據(jù)有兩個基本特點：一是自描述，XML數(shù)據(jù)本身就已經(jīng)包含了元數(shù)據(jù)——關(guān)于數(shù)據(jù)本身的信息，表現(xiàn)為不同語義的標記(例如元素、屬性等等)。Java語言在MyEclipse下，使用快捷，易于上手。 : 這里面是所有輸入輸出有關(guān)的類，比如文件操作等。javadoc – 文檔生成器，從源碼注釋中提取文檔。 JDK介紹JDK(Java Development Kit)是Sun Microsystems針對Java開發(fā)的產(chǎn)品。SQL語句可以用來執(zhí)行各種各樣的操作，例如更新數(shù)據(jù)庫中的數(shù)據(jù)，從數(shù)據(jù)庫中提取數(shù)據(jù)等。 MyEclipse介紹MyEclipse企業(yè)級工作平臺（MyEclipse Enterprise Workbench ，簡稱MyEclipse）是對EclipseIDE的擴展，利用它我們可以在數(shù)據(jù)庫和JavaEE的開發(fā)、發(fā)布以及應用程序服務器的整合方面極大的提高工作效率。Java ME 為在移動設(shè)備和嵌入式設(shè)備（比如手機、PDA、電視機頂盒和打印機）上運行的應用程序提供一個健壯且靈活的環(huán)境。它允許開發(fā)和部署在桌面、服務器、嵌入式環(huán)境和實時環(huán)境中使用的 Java 應用程序。（5）第5章為軟件測試。該章主要包括對系統(tǒng)開發(fā)環(huán)境和開發(fā)工具的選擇和介紹，這些技術(shù)是本系統(tǒng)開發(fā)的前提和保障。本文針對SLCA對索引查找有效算法進行研究，通過將算法逐步展開得出相應的可實現(xiàn)的查詢程序。其中，對SLCA的研究相對較多，SLCA的發(fā)展也較為成熟，被認為是最好的最緊致片段的定義，本文將圍繞SLCA展開。在XML關(guān)鍵字查詢中．，最基本的問題就是獲得所有滿足關(guān)鍵字組合語義的最緊致片段。XML關(guān)鍵字查詢根據(jù)查詢請求描述特點的不同，可概括為可概括為兩大類查詢模式：XML結(jié)構(gòu)化查詢和XML關(guān)鍵字查詢。XML結(jié)構(gòu)查詢首先定義精確的查詢描述語言，用戶借助它來描述自己感興趣的模式，將用戶的模式交由實際的XML數(shù)據(jù)處理系統(tǒng)處理，然后返回與模式相匹配的結(jié)果。通常在web上的關(guān)鍵字檢索，比如Google或者百度，他們的返回結(jié)果是包含用戶提供的關(guān)鍵字的整個網(wǎng)頁，屬于文檔級。 XML上關(guān)鍵字檢索研究畢業(yè)論文 目 錄摘要 IAbstract II第1章 緒論 1 選課目的 1 1 2 3 4 4第2章 相關(guān)技術(shù)介紹 6 6 Java語言介紹 6 MyEclipse介紹 7 MySQL介紹 7 JDK介紹 8 9第3章 Index Lookup Eager算法原理與實現(xiàn) 10 最緊致片段及SLCA相關(guān)概念 10 10 13 SLCA概念詳述 14 ILE算法原理 15 15 Dewey編碼 16 17 ILE算法示例及分析 18 ILE算法的實現(xiàn) 21 23 24 25 26 27第4章 SLCA查詢系統(tǒng)的實現(xiàn) 28 數(shù)據(jù)庫的實現(xiàn) 28 28 29 配置開發(fā)環(huán)境 31 31 安裝MySQL數(shù)據(jù)庫 31 安裝MyEclipse 32 頁面設(shè)計和實現(xiàn)方法 32 32 34 35 35第5章 軟件測試 36 36 36 單元測試 36 集成測試 37 驗收測試 37 評價 37結(jié)論 38參考文獻 39致謝 41附錄1 開題報告 42附錄2 中期報告 48附錄3 文獻綜述 52附錄4 外文原文 57附錄5 外文翻譯 11I參考文獻 第1章 緒論 選課目的隨著計算機網(wǎng)絡(luò)和Internet的發(fā)展，在萬維網(wǎng)上的文檔資料越來越豐富。但如果對大XML文檔上的關(guān)鍵字檢索，由于XML文檔被建模成樹形，有著層次嵌套的關(guān)系，用戶通常希望得到最小結(jié)果片段，此時查詢的粒度不再是文檔級別而是元素級。這就要求用戶掌握XML文檔結(jié)構(gòu)及查詢語言。XML結(jié)構(gòu)查詢下的算法偏向于傳統(tǒng)的結(jié)構(gòu)化查詢算法，即采用了正則表達式的描述形式。相關(guān)研究中，最早出提出的最緊致片段的定義LCA(Lowest Common Ancestor)，LCA指在XML文檔樹中，包含所有查詢關(guān)鍵字節(jié)點的最近公共祖先節(jié)點，該節(jié)點的任意子節(jié)點都不再包含所有的關(guān)鍵字節(jié)點。在獲取了所有包含給定關(guān)鍵字的最緊致片段后，另一個重要的問題就是XML片段相似程度的計算。并對實際文檔進行操作，將XML文檔通過解析程序解析為倒排表的形式，進而生成相應的數(shù)據(jù)庫，整個查詢系統(tǒng)由JAVA代碼實現(xiàn)。（3）第3章為Index Lookup Eager算法原理與實現(xiàn)。該章主要是通過對軟件進行測試，發(fā)現(xiàn)其中可能存在的錯誤，這是軟件開發(fā)中最重要的環(huán)節(jié)。Java SE 包含了支持 Java Web 服務開發(fā)的類，并為 Java Platform，Enterprise Edition（Java EE）提供基礎(chǔ)。Java ME 包括靈活的用戶界面、健壯的安全模型、許多內(nèi)置的網(wǎng)絡(luò)協(xié)議以及對可以動態(tài)下載的連網(wǎng)和離線應用程序的豐富支持。它是功能豐富的JavaEE集成開發(fā)環(huán)境，包括了完備的編碼、調(diào)試、測試和發(fā)布功能，完整支持HTML ,Struts ,JSP ,CSS ,Javascript ,Spring ,SQL ,Hibernate。絕大多數(shù)流行的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)都采用了SQL語言標準。自從Java推出以來，JDK已經(jīng)成為使用最廣泛的Java SDK。jdb – debugger，查錯工具。 ：這里面是與網(wǎng)絡(luò)有關(guān)的類，比如URL,URLConnection等。 第3章 Index Lookup Eager算法原理與實現(xiàn) 最緊致片段及SLCA相關(guān)概念對于XML關(guān)鍵字查詢來說，基本操作就是找到包含給定關(guān)鍵字的最緊致片段。在所有標記中，元素標記最為重要。通常簡化為XML標簽有向樹模型，G=(V，E，r，A)，其中的V表示G中所有節(jié)點的集合，E表示G中所有邊的集合，r表示G的根節(jié)點，A是所有節(jié)點所帶標簽的集合。在XML樹中，我們用v表示一個節(jié)點。LCA是XML關(guān)鍵字查詢中最緊致片段的基礎(chǔ)定義，在LCA的基礎(chǔ)上，相繼又提出了Smallest LCA（SLCA）、Valuable LCA(VLCA)、Meaningful LCA MLCA)等概念來提高XML關(guān)鍵字查詢的性能和準確率。下面，給出SLCA的準確定義：定義3．3：SLCA，在XML文檔D中，給定查詢關(guān)鍵字集合K={,．．． }， 節(jié)點y∈LCASet。為了實現(xiàn)這一過程，賦予節(jié)點的編碼信息應當具有重構(gòu)XML片段的能力，這就要求能夠根據(jù)編碼得到路徑上其他節(jié)點信息。因此，前綴編碼不僅能夠有效地支持包含關(guān)系等結(jié)構(gòu)上的查詢運算等操作，而且能夠有效地支持文檔的位置關(guān)系的運算。取XML樹中根節(jié)點r所在的層為1，那么稱Dewey碼u中與第i層節(jié)點對應的整數(shù)為該Dewey碼的第i層整數(shù)，表示為。文獻給出了該計算方法的正確性的證明，這里不再重復。以上計算可以通過另外一個以關(guān)鍵字為條目的B+樹來存儲對應的倒排表，從而加速運算。在算法3．2的第一次迭代過程中，經(jīng)過第2行代碼的執(zhí)行過后，在第3行代碼處， B={，}。第10行代碼過后，v被賦予新值0．1．2，此時B為空，所以第1l行輸出也為null。第三次迭代，x=descendant(1ca(，lm(，))，lca(，rm(, )))=descendant(lca(，null)，lca(，))=descendant(nul