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

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

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

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