一種改進的基于Dewey編碼的XML最緊致片段求解方法的研究與實現(xiàn).pdf

1、可擴展標(biāo)記語言(XML，Extensible Markup Language)常被應(yīng)用于簡化數(shù)據(jù)的存儲和共享，同時它也逐漸成為了一套規(guī)范的語義標(biāo)簽語言，使得人們在計算機中定義數(shù)據(jù)類型更加容易。如今網(wǎng)絡(luò)應(yīng)用發(fā)展迅速，XML也已經(jīng)廣泛地應(yīng)用于Web Service（Web服務(wù)）、內(nèi)容管理、Web集成、配置數(shù)據(jù)存儲和電子商務(wù)等。因此如何從XML數(shù)據(jù)中提取用戶所需要的信息，就成為了在XML關(guān)鍵字搜索領(lǐng)域研究的主要問題。
　　在XML關(guān)鍵字

2、搜索領(lǐng)域中，返回用戶所期望查詢結(jié)果的XML片段，稱作最緊致片段，這種片段不僅滿足用戶的需求，也具有一定的語義信息。因此，最緊致片段的求解算法及其性能成為XML關(guān)鍵字搜索領(lǐng)域的重要問題之一。
　　最小最低公共子樹(SLCA)是目前公認(rèn)的有意義的最緊致片段，SLCA返回帶有所有關(guān)鍵字節(jié)點的最小子樹。本文是在SLCA的理論基礎(chǔ)上進行改進，將XML文檔解析成樹形結(jié)構(gòu)，然后對每一個節(jié)點以Dewey編碼的形式進行編碼。之后基于Dewey編碼對

3、XML樹進行前序遍歷，并提出了前序遍歷關(guān)鍵字集合算法（PHTKSA算法）來求解XML文檔中最緊致片段SLCA。
　　本文還研究了兩類錯誤——丟棄錯誤和重復(fù)錯誤。針對丟棄問題構(gòu)造了影響因子，根據(jù)影響因子來判斷XML文檔是否存在丟棄錯誤的可能，通過擴展關(guān)鍵字集合找到所有包含關(guān)鍵字的XML文檔片段，以便發(fā)現(xiàn)符合用戶所期望的最緊致片段。針對重復(fù)問題提出了節(jié)點標(biāo)簽及關(guān)鍵字集合的概念，用于找出關(guān)鍵字節(jié)點的標(biāo)簽和內(nèi)容，利用裁剪算法，刪除重復(fù)節(jié)點