非結(jié)構(gòu)數(shù)據(jù)的檢索方法研究

非結(jié)構(gòu)數(shù)據(jù)的檢索方法研究

1非結(jié)構(gòu)數(shù)據(jù)的管理在信息爆炸的今天，大量結(jié)構(gòu)性數(shù)據(jù)和非結(jié)構(gòu)數(shù)據(jù)顯著增加。如果采用人工處理的方式,由于非結(jié)構(gòu)數(shù)據(jù)的結(jié)構(gòu)化過程受限于人工處理速度,導(dǎo)致非結(jié)構(gòu)數(shù)據(jù)的增長遠遠超過結(jié)構(gòu)化數(shù)據(jù)。如何有效的管理每天出現(xiàn)大量的文本、圖像和視頻等非結(jié)構(gòu)數(shù)據(jù)成為一個巨大的挑戰(zhàn)。王建民等研究了基于特征非結(jié)構(gòu)數(shù)據(jù)管理建模框架。李青等研究了基于相似度矩陣的非結(jié)構(gòu)化數(shù)據(jù)分類算法。文龍等研究了如何將XML應(yīng)用于非結(jié)構(gòu)數(shù)據(jù)的管理。楊岳等研究了非結(jié)構(gòu)化數(shù)據(jù)統(tǒng)一訪問平臺及索引技術(shù)。鄒波等研究了海量非結(jié)構(gòu)化數(shù)據(jù)的文件組織格式等問題。本文進行了基于R樹的非結(jié)構(gòu)數(shù)據(jù)的索引的研究,并且在搜狗語料數(shù)據(jù)集和SceneClass13數(shù)據(jù)集上取得了不錯的效果。本文第二節(jié)是非結(jié)構(gòu)數(shù)據(jù)在R樹上的查找,插入和刪除的實現(xiàn)。第三節(jié)是在搜狗語料數(shù)據(jù)集和SceneClass13數(shù)據(jù)集上進行實驗的情況。最后是全文總結(jié)和對未來工作的展望。2面向非結(jié)構(gòu)的r樹的數(shù)據(jù)節(jié)點距離R樹是一種高度平衡的樹。它的葉節(jié)點包含了指向直接數(shù)據(jù)記錄的指針。在這種樹形索引結(jié)構(gòu)的幫助下,多維數(shù)據(jù)檢索只需要搜索很少的節(jié)點,而不需要遍歷所有數(shù)據(jù)。本文面向非結(jié)構(gòu)數(shù)據(jù)的R樹的索引節(jié)點(IndexNode)定義如下:<NodeID,ParentID,CurCount,DataType,Accessible,Distance,Radius,Area,ChildNodes>。NodeID表示本節(jié)點的編號。ParentID表示父節(jié)點的編號,根節(jié)點的ParentID為空。CurCount表示節(jié)點目前的子節(jié)點數(shù)量,在實際使用時會設(shè)置最多子節(jié)點數(shù)目Max和最少子節(jié)點數(shù)目Min。DataType表示這一棵R樹是保存何種類型的非結(jié)構(gòu)數(shù)據(jù),目前支持文本數(shù)據(jù)和圖像數(shù)據(jù)。Accessible表示目前這個節(jié)點是正在使用還是已經(jīng)被廢棄。Distance是一個Max*Max大小的矩陣,記錄不同子節(jié)點之間的歐式距離。Area表示每一維數(shù)據(jù)最大值與最小值距離的平方和。Radius表示當前索引節(jié)點的覆蓋范圍,可以表示為。ChildNodes指向當前節(jié)點的子節(jié)點,可以表示為vector<IndexNode>。本文面向非結(jié)構(gòu)數(shù)據(jù)的R樹的數(shù)據(jù)節(jié)點(DataNode)定義如下:<NodeID,DataType,Feature>。NodeID表示本節(jié)點的編號。DataType表示這一棵R樹是保存何種類型的非結(jié)構(gòu)數(shù)據(jù),目前支持文本數(shù)據(jù)和圖像數(shù)據(jù)。Feature表示非結(jié)構(gòu)數(shù)據(jù)經(jīng)過特征提取后所得到的特征值,可以表示為。本文基于R樹的非結(jié)構(gòu)數(shù)據(jù)的查找,插入和刪除算法如下所述。2.1r樹葉節(jié)點保護本算法的目的是查找目標數(shù)據(jù)所在的葉節(jié)點。對文本數(shù)據(jù)而言,每一維的特征是<單詞:出現(xiàn)的次數(shù)>。對于圖像數(shù)據(jù)而言,本文采用邊緣直方圖特征作為圖像特征。初始時node是R樹的根節(jié)點,target是需要查找的數(shù)據(jù)。本文使用vector<IndexNode>保存所有滿足條件的葉節(jié)點。1)如果node不是葉節(jié)點,判斷target是否在node覆蓋范圍里面。如果target不在node覆蓋范圍里面則退出算法;否則遞歸的找到在node覆蓋范圍里面的葉節(jié)點2)如果node已經(jīng)是葉節(jié)點并且Accessible為true,則將node存入vector<IndexNode>如果是需要查找非結(jié)構(gòu)數(shù)據(jù),則順序遍歷vector<IndexNode>中葉節(jié)點所指向的數(shù)據(jù)。2.2生成葉節(jié)點本算法的目的是向現(xiàn)有的R樹插入一條新的非結(jié)構(gòu)數(shù)據(jù)。本算法的流程如下:1)通過運行search＿leaf算法得到候選葉節(jié)點集合vector<IndexNode>2)如果vector<IndexNode>只包含一個元素,則直接插入到這個葉節(jié)點;如果vector<IndexNode>包含多個元素,則選擇Area最小的葉節(jié)點;如果vector<IndexNode>為空,則選擇插入target后Area增加最少的葉節(jié)點,如果增量相同則選擇Area最小的葉節(jié)點3)將target插入到選擇的葉節(jié)點,如果葉節(jié)點的CurCount不大于Max,則結(jié)束算法4)利用距離矩陣Distance找到距離最遠的兩條記錄node1,node25)利用Prim算法和node1,node2這兩個節(jié)點將子節(jié)點集合分割為兩個互不相交的無向圖,每個無向圖集合作為一個新的葉節(jié)點集合,同時將本葉節(jié)點的Accessible置為false6)調(diào)整父節(jié)點覆蓋范圍,使其包含子節(jié)點的所有數(shù)據(jù)7)調(diào)整的curCount,如果未超過Max,則結(jié)束算法8)利用Prim算法將父節(jié)點分割為兩個互不相交的無向圖,每個無向圖作為一個新的葉節(jié)點9)重復(fù)第6步,直到根節(jié)點調(diào)整完畢,結(jié)束算法2.3調(diào)整葉節(jié)點radius本算法的目的是刪除R樹中的一條非結(jié)構(gòu)數(shù)據(jù)。本算法的流程如下:1)通過運行search＿leaf算法找到葉節(jié)點2)在葉節(jié)點中查找非結(jié)構(gòu)數(shù)據(jù)并刪除,調(diào)整葉節(jié)點的覆蓋范圍Radius3)如果葉節(jié)點curCount>=Min,則遞歸調(diào)整父節(jié)點Radius,結(jié)束算法4)將Accessible設(shè)為false,將這個葉節(jié)點的非結(jié)構(gòu)數(shù)據(jù)依次通過insert＿unstructured＿data算法重新插入R樹5)如果R樹調(diào)整后根節(jié)點只有一個孩子,則將根節(jié)點的Accessible設(shè)為false,讓孩子節(jié)點成為R樹新的根節(jié)點,結(jié)束算法3系統(tǒng)的設(shè)計和實驗3.1udis檢測本文實現(xiàn)了基于R樹的非機構(gòu)數(shù)據(jù)索引系統(tǒng)(UnstructuredDataIndexSystem,UDIS)。如圖1所示,本系統(tǒng)包含非結(jié)構(gòu)數(shù)據(jù)文件系統(tǒng)模塊,非結(jié)構(gòu)數(shù)據(jù)索引模塊和可視化人機交互模塊。3.2基于b950的內(nèi)核處理器實驗平臺的硬件部分由1臺PC機組成,采用IntelB950雙核處理器,擁有4GBDDR3內(nèi)存和500GB機械硬盤,軟件部分為Windows7OS,JDK1.6和ApacheTomcat6.0。3.3enecluss13數(shù)據(jù)集本文采用搜狗語料庫數(shù)據(jù)集作為文本數(shù)據(jù)集,采用SceneClass13數(shù)據(jù)集作為圖像數(shù)據(jù)集。其中搜狗語料庫數(shù)據(jù)集中每一個文件都是以txt結(jié)尾的文本文件,SceneClass13則是jpg格式的圖像。3.4尾網(wǎng)字符檢索針對實驗數(shù)據(jù)集,UDIS通過輸入字符串的末尾字符串決定是檢索圖像還是文本。當檢索關(guān)鍵字以”jpg”結(jié)尾時檢索圖像,如圖2所示。在以其它字符串結(jié)尾時搜索文本,如圖3所示。4在檢查機構(gòu)內(nèi)添加scear