基于差分編碼的RDF分組壓縮

伍偉鑫,韓京宇,朱 曼

(南京郵電大學(xué) 計算機(jī)學(xué)院,南京 210023)

0 概述

為使計算機(jī)更好地理解人類創(chuàng)造的網(wǎng)絡(luò)資源,TIM等人于1998年提出了語義網(wǎng)的概念[1]。在語義網(wǎng)中,計算機(jī)可以理解文檔中的詞語和概念,從而使整個互聯(lián)網(wǎng)成為一個通用的信息交換介質(zhì)。W3C聯(lián)盟于1999年發(fā)布了基于XML語法的概念模型資源描述框架(Resource Description Framework,RDF)[2]用于實現(xiàn)語義網(wǎng),其在邏輯上以圖的形式表示,圖中節(jié)點(diǎn)代表資源或資源的屬性值,節(jié)點(diǎn)間連線代表節(jié)點(diǎn)間關(guān)系。RDF圖存儲為文件時以三元組的形式描述每條數(shù)據(jù),每個三元組由被描述的資源(主語)、資源的屬性(謂語)和屬性對應(yīng)的值(賓語)組成[3],形式化為(s,p,o)∈(U∪B)×U×(U∪B∪L),其中,U為統(tǒng)一資源標(biāo)識符,B為空白節(jié)點(diǎn),L為RDF文本內(nèi)容[4]。RDF模型憑借簡單、靈活、易擴(kuò)展等特點(diǎn)迅速成為知識領(lǐng)域主流的半結(jié)構(gòu)數(shù)據(jù)模式,被廣泛應(yīng)用于生命科學(xué)、地理學(xué)和維基百科等綜合知識領(lǐng)域。

雖然RDF在邏輯層面表現(xiàn)優(yōu)異,但其在物理層面可擴(kuò)展性較差,原因在于RDF為了增強(qiáng)數(shù)據(jù)在邏輯層面的表現(xiàn)力而引入了大量重復(fù)的內(nèi)容,即數(shù)據(jù)實際存儲所占用空間遠(yuǎn)大于數(shù)據(jù)絕對空間[5],使得RDF數(shù)據(jù)集較其他存儲格式需要更多的存儲空間。例如數(shù)據(jù)集DBpedia,其利用靈活的RDF結(jié)構(gòu)有效地整合了維基百科中不同領(lǐng)域的異質(zhì)資源。最新版本的DBpedia中包含130億個三元組,描述了人類、地點(diǎn)、組織、電影、種類、疾病等多種信息,該數(shù)據(jù)集被應(yīng)用于語義搜索、實體消歧和翻譯等多種服務(wù)。盡管DBpeida可以通過調(diào)用不同的API進(jìn)行在線查詢,但一些需要完整數(shù)據(jù)集支持的應(yīng)用和服務(wù)必須在本地存儲和處理這個龐大的數(shù)據(jù)集,在資源受限的場景如輕量級的客戶端或者低性能的網(wǎng)絡(luò)場景中,如此大量的運(yùn)算是一個巨大的挑戰(zhàn),而由此產(chǎn)生的RDF分布式管理技術(shù)[6-8]和壓縮處理技術(shù),則可作為可擴(kuò)展技術(shù)來解決龐大RDF數(shù)據(jù)集的管理難題。

雖然目前已存在一些有效的RDF壓縮方法,但其中仍存在不足,如包含尚未處理的冗余、壓縮過程中引入了新的冗余等。為此,本文提出一種基于差分編碼的RDF分組壓縮算法。通過構(gòu)建連接賓語的謂語組合,利用賓語和謂語之間相對唯一的映射關(guān)系減少不同謂語組合中的謂語冗余,并根據(jù)謂語組合將RDF數(shù)據(jù)分組存儲,以消除賓語冗余。在此基礎(chǔ)上,對分組后的主語序列進(jìn)行差分編碼,以序列間的偏移量代替數(shù)值本身,在不引入額外輔助索引的前提下優(yōu)化主語序列的存儲空間。

1 研究背景

RDF壓縮技術(shù)可分為物理壓縮和邏輯壓縮兩種方法,前者通過減少符號與句法冗余,將原數(shù)據(jù)轉(zhuǎn)化為更簡潔的存儲形式,后者致力于尋找一部分可以推導(dǎo)剩余數(shù)據(jù)的規(guī)則數(shù)據(jù),最終只需要存儲規(guī)則數(shù)據(jù)。

最簡單的物理壓縮方法是通用壓縮算法,如gzip和bzip2,其優(yōu)點(diǎn)在于簡單且運(yùn)行效率高,可以輕易地集成到其他工作流中協(xié)同完成任務(wù),但此類算法沒有利用RDF數(shù)據(jù)的結(jié)構(gòu)特性,并且在壓縮過程中破壞了原數(shù)據(jù)的結(jié)構(gòu),無法進(jìn)一步在壓縮數(shù)據(jù)上進(jìn)行查詢檢索等復(fù)雜操作。

HDT[9-10]是一種基于BitmapTriple的RDF專用物理壓縮算法,其將原始RDF數(shù)據(jù)轉(zhuǎn)化為一個包含多個深度為3的樹的森林,每棵樹的根節(jié)點(diǎn)代表主語,第2層是與根節(jié)點(diǎn)每個主語對應(yīng)的謂語列表,第3層是對應(yīng)每個(主語,謂語)組合的賓語列表。整個森林只需要存儲謂語列表、賓語列表和對應(yīng)代表分支信息的比特序列。這個簡單的編碼方法具有比通用壓縮算法更高的壓縮比率,并且可以通過遍歷森林中的根節(jié)點(diǎn)解決壓縮數(shù)據(jù)中基于主語的查詢問題。HDT++算法[11]在HDT的表達(dá)方式上進(jìn)行了改進(jìn),其根據(jù)謂語組合對主語分組,大幅減少了謂語冗余,并且根據(jù)謂語對賓語進(jìn)行二次分組,在分組中使用局部編碼代替全局編碼,以更小的比特數(shù)存儲賓語,獲得了比HDT更好的壓縮效果。k2-triple算法[12]根據(jù)不同謂語將原始數(shù)據(jù)劃分成多個以主語為橫坐標(biāo)、以賓語為縱坐標(biāo)的二維0-1矩陣,對這些稀疏的二維矩陣?yán)胟2-tree算法[13]進(jìn)行矩陣壓縮,同時該算法可實現(xiàn)針對壓縮數(shù)據(jù)常見的查詢操作。

邏輯壓縮方法的重點(diǎn)在于尋找規(guī)則子圖的方式。文獻(xiàn)[14-15]提出了基于lean subgraph的邏輯壓縮算法。lean subgraph是原始數(shù)據(jù)圖的一個子圖,是原始圖實例的最小子圖,由lean subgraph所移除的三元組數(shù)量強(qiáng)依賴于原始圖的特征,最少可移除數(shù)量約為空白節(jié)點(diǎn)的兩倍。然而,lean graph中的部分三元組仍然可以由其他三元組推導(dǎo)得出,說明lean subgraph并不能完全移除冗余三元組[15]?；谝?guī)則的邏輯壓縮RB算法[16]通過頻繁項集挖掘技術(shù)檢測intra-property和inner-property兩種模式,intra-property在指定謂語的前提下挖掘重復(fù)出現(xiàn)的(主語->賓語)映射,inner-property挖掘重復(fù)出現(xiàn)的(主語->(謂語,賓語))映射,挖掘所得映射將轉(zhuǎn)化為規(guī)則用于移除冗余數(shù)據(jù)。然而這兩種模式并不都有效,只有inner-property可以移除大量冗余三元組。文獻(xiàn)[17]指出頻繁項集不能很好地捕獲數(shù)據(jù)中的語義冗余,并提出一種更具表現(xiàn)力的喇叭規(guī)則,只要三元組能夠匹配喇叭規(guī)則的頭部即可被移除出數(shù)據(jù)集。存儲的喇叭規(guī)則可以再次利用RB算法進(jìn)行壓縮,其壓縮性能較單獨(dú)使用RB算法有所提升,但同時也引入了較高的延遲。PIC算法[18]將原始數(shù)據(jù)轉(zhuǎn)化為以主語為橫軸、以(謂語,賓語)二元組為縱軸的二維0-1矩陣,并將矩陣中的每一行0-1數(shù)組序列轉(zhuǎn)化為一個新的三元組,原數(shù)據(jù)集的三元組可以由新產(chǎn)生的三元組計算得到,通過存儲數(shù)量遠(yuǎn)小于原三元組的新三元組實現(xiàn)數(shù)據(jù)壓縮。

2 相關(guān)定義

2.1 RDF數(shù)據(jù)的結(jié)構(gòu)化程度

結(jié)構(gòu)化數(shù)據(jù)也稱為行數(shù)據(jù),是由二維表結(jié)構(gòu)進(jìn)行邏輯表達(dá)和實現(xiàn)的數(shù)據(jù),行數(shù)據(jù)嚴(yán)格遵循相同的數(shù)據(jù)格式與長度規(guī)范,主要通過關(guān)系型數(shù)據(jù)庫進(jìn)行存儲和管理。RDF數(shù)據(jù)是一種靈活的半結(jié)構(gòu)化數(shù)據(jù),并不強(qiáng)求所有數(shù)據(jù)都具有相同的數(shù)據(jù)格式,因此,不同RDF數(shù)據(jù)集中數(shù)據(jù)的結(jié)構(gòu)完整性也各不相同。

定義2(RDF數(shù)據(jù)的結(jié)構(gòu)化程度) RDF數(shù)據(jù)的結(jié)構(gòu)化程度定義為謂語數(shù)量與連接主語的謂語組合數(shù)量的比值:|P|/|G|,其中,P為謂語集合,G為RDF數(shù)據(jù)集中謂語組合的集合。

2.2 基于模式的冗余

HDT++算法[11]將與主語相關(guān)聯(lián)的謂語歸納為謂語組合,再利用謂語組合對主語進(jìn)行分組,使得每個主語只被存儲一次,謂語通過謂語組合的形式只被存儲較少的次數(shù)。這樣分組的意義在于:對于不同的主語,可能存在多個謂語對其進(jìn)行描述,如“人”這個主語可能存在的謂語包括身高、體重、籍貫、膚色等,在結(jié)構(gòu)化程度高的數(shù)據(jù)集中,同一類型的主語大多具有相同的描述(謂語)。例如,對于A和B都存在身高、體重、膚色、籍貫的謂語描述,因此,將這樣的主語由(身高、體重、膚色、籍貫)的謂語組合進(jìn)行分組保存可以減少謂語的重復(fù)出現(xiàn)。但是在結(jié)構(gòu)化程度低的數(shù)據(jù)集中,對于同一類型的不同主語,對其描述的謂語各不相同。例如,對于A的描述有身高、體重、膚色、籍貫,對于B的描述只有身高、體重、膚色,而沒有籍貫的描述,對于C的描述只有身高、體重,這樣就會產(chǎn)生(身高、體重、膚色、籍貫)、(身高、體重、膚色)和(身高、體重)3種不同的謂語組合。上述3種謂語組合只存在少數(shù)謂語的差異,但因為組合不完全相等,所以相同的謂語就需要被存儲多次,由此產(chǎn)生冗余。

2.3 差分編碼

差分編碼[19]又稱增量編碼,其是以數(shù)字序列間差異進(jìn)行存儲,而不存儲數(shù)字本身的一種編方式,表示為:{a1,a2,…,an}→{a1,a2-a1,…,an-an-1}。顯然,差分編碼的優(yōu)點(diǎn)在于:當(dāng)序列中數(shù)字之間的偏移量較小時,差分編碼可以節(jié)省大量空間。此外,差分編碼在減少序列存儲空間的同時無需引入額外的中間變量,通過編碼方法自身即可完成序列的編碼與解碼。

3 基于差分編碼的RDF分組壓縮算法

基于上節(jié)所討論的冗余與編碼方式,本文構(gòu)建一種新的RDF數(shù)據(jù)分組表示方法用于減少低結(jié)構(gòu)化程度RDF數(shù)據(jù)中的謂語冗余。首先歸納與賓語相對應(yīng)的謂語組合,然后利用謂語組合對賓語進(jìn)行分組表示,減少謂語冗余并去除賓語冗余,最后對分組后的主語序列應(yīng)用差分編碼,以更小的空間存儲RDF中的全部主語。

3.1 基于謂語-賓語的分組表示

將RDF原始數(shù)據(jù)圖轉(zhuǎn)化為字典與ID圖,字典表示為RDF中的URI或字面值與其唯一ID的映射,ID圖為通過ID表示的原始三元組關(guān)系。URI或字面值通常是一串較長的字符串,如果重復(fù)存儲將造成存儲空間浪費(fèi),而通過字典將字符串映射為ID后只需要在字典中存儲一次。本文在此基礎(chǔ)上,將ID圖轉(zhuǎn)化為根據(jù)賓語歸納的謂語組合對賓語分組的形式,如圖1所示。其中,樹形結(jié)構(gòu)的根節(jié)點(diǎn)為賓語,第2層節(jié)點(diǎn)為與根節(jié)點(diǎn)賓語對應(yīng)的謂語組合,第3層節(jié)點(diǎn)為與(賓語,謂語)對應(yīng)的主語列表。不同的賓語如果對應(yīng)相同的謂語組合,則將其合并為一組,如圖2所示。例如,圖1中第1棵樹與第2棵樹的謂語組合相同,則將圖2中第1棵樹和第2棵樹的謂語組合合二為一共同存儲。

圖1 基于謂語組合的RDF數(shù)據(jù)分組表示

圖2 分組表示后相同謂語組合的歸納合并

根據(jù)謂語對賓語分組的意義在于:

1)存在一部分賓語同時與多個謂語相關(guān)聯(lián),將這些賓語的共同謂語抽取出來作為分組的規(guī)則對賓語進(jìn)行分組,可以減少不同賓語的相同謂語重復(fù)存儲。

3)由于賓語只與很少數(shù)量的謂語相關(guān)聯(lián),因此由賓語歸納的謂語組合中包含謂語的數(shù)量非常少,即使在不同謂語組合間存在重復(fù)謂詞,重復(fù)謂詞的數(shù)量也會被限制,從而限制了謂語總數(shù)的增長。

3.2 主語差分編碼

原始RDF數(shù)據(jù)被轉(zhuǎn)化為分組表示后,主語也被對應(yīng)的謂語組合分到對應(yīng)的分組中,為對主語進(jìn)行差分編碼,需要進(jìn)行以下處理:

1)對主語序列按照新的順序重新由小到大編碼,使主語序列可以發(fā)揮差分編碼的最大性能。值得注意的是,重新編碼指的是將字典中的唯一ID替換為新的根據(jù)分組位置的新ID,無須額外存儲新編碼的中間映射,而只需要在字典中進(jìn)行ID更新。

2)將分組后的主語列表根據(jù)組內(nèi)的(賓語,謂語)三元組劃分成為不同的數(shù)字序列,對每個數(shù)字序列進(jìn)行差分編碼。

在圖3中,主語序列(第1列)到第2列的轉(zhuǎn)化展示了主語序列重新編碼的過程,第2列到第3列的轉(zhuǎn)化展示了根據(jù)(賓語,謂語)二元組劃分的主語序列進(jìn)行差分編碼的過程。在存儲到文件中時,對于每個主語序列,序列中數(shù)值以變長長度存儲,由于差分編碼產(chǎn)生的偏移量之間可能大小差距較大,因此變長長度可以最大化節(jié)省空間。圖3中最后一列比特序列用于區(qū)分不同主語序列,一串連續(xù)的0-bit與一個單獨(dú)的1-bit表示其所對應(yīng)的主語序列歸屬于同一個(謂語,賓語)二元組。例如圖3中比特序列的前4個比特數(shù)為[0,0,0,1],說明其所對應(yīng)的主語序列[1,1,1,1]皆對應(yīng)二元組(1,1),而接下來的比特序列[0,0,1]所對應(yīng)的主語序列[5,1,1]則對應(yīng)二元組(1,3),可以發(fā)現(xiàn)二元組的第2個元素由1變成了3。由于3是該組謂語組合的最后一位,因此下一個比特序列所對應(yīng)的二元組變?yōu)?2,1)。在解壓縮時,依此類推即可逆向還原所有三元組。

圖3 主語序列重編碼及差分編碼

算法1描述了本文算法的壓縮過程,具體步驟如下:

1)聲明object2predicaet、objPred2subject為映射,bitSeq為字符串(第1行)。

2)遍歷原始數(shù)據(jù)三元組,統(tǒng)計賓語與謂語的映射關(guān)系和(賓語、謂語)二元組與主語的映射關(guān)系(第2行～第5行)。

3)將賓語、謂語映射關(guān)系中的謂語組合去重歸納得到賓語組合與對應(yīng)的謂語組合(第6行)。

4)從賓語組合、謂語組合中生成的(賓語、謂語)二元組對主語進(jìn)行歸納,在歸納過程中對每個二元組對應(yīng)的主語序列進(jìn)行差分編碼(第7行和第8行),同時通過比特序列界定不同主語序列的界限(第9行)。

5)將賓語組合、謂語組合、主語序列和比特序列返回存儲到文件中(第10行)。

算法1壓縮算法

輸入原始三元組triples

輸出謂語組合predicateGroups,賓語根據(jù)謂語組合所分組合 objectGroups,對應(yīng)(賓語,謂語)二元組的主語列表subjectList,主語切換標(biāo)記比特序列bitSeq

1.object2predict← map,objPred2subject ← map,bitsequence ←string

2.for subject,predicate,object← triples:

3.object2predicate[object].add(predicate)

4.objPred2subject[(object,predicate)].add(subject)

5.end for

6.predicateGroups,objectGroups ←reduce(object2predicate)

7.for (o,p) ←predicateGroup,objectGroups:

8.subjectList.add(deltaEncoding(objPred2subject[(o,p)]))

9.bitSeq.add(len(objPred2subject[(o,p)]) * ‘0’+‘1’)

10.returnobjectGroups,predicateGroups,subjectList,bitSeq

算法1的空間復(fù)雜度主要源于object2predicate和objPred2subject的臨時存儲。object2predicate存儲內(nèi)容為賓語到謂語組合的映射,其中,key的數(shù)量為賓語數(shù)量|Object|,value的總數(shù)為三元組的數(shù)量n。objPred2subject存儲內(nèi)容為賓語與謂語的二元組到主語的映射,其中,所有元素的總量小于等于3倍的三元組數(shù)量。因此,算法1的空間復(fù)雜度為O(|Object|+n+3n)=O(n)。

算法2描述了本文算法的解壓縮過程,具體步驟如下:

1)將分組表示的賓語、謂語和主語從文件中讀出后,迭代每個謂語組合和對應(yīng)的賓語組合生成(賓語,謂語)二元組(第1行和第2行)。

2)逐個訪問主語列表,在訪問過程中逐步還原差分編碼(第3行～第10行)。

3)根據(jù)bitSeq中連續(xù)的0-bit和一個單獨(dú)的1-bit界定對應(yīng)當(dāng)前(謂語,賓語)二元組的主語序列的終止位置(第6行和第13行)。

4)將符合條件的主語與二元組組成三元組添加到originalTriples中并最終返回。

算法2解壓縮算法

輸入謂語組合predicateGroups,賓語根據(jù)謂語組合所分組合objectGroups,對應(yīng)(賓語,謂語)二元組的主語列表subjectList,主語切換標(biāo)記比特序列bitSeq

輸出ID表示的完整三元組originalTriples

1.for (object,predicate) ← predicateGroups,objectGroups:

2.//獲取每一對(賓語,謂語)二元組

3.for subject,bit← subjectList,bitSeq:

4.//通過bit確定subject的終止位置

5.if subject.forwardBit=0:

6.subject=subject+subject.forward

7.//對差分編碼進(jìn)行解碼

8.originalTriples←(subject,predicate,object)

9.end if

10.end for

11.//構(gòu)成一條完整三元組

12.until bit=1

13.returnoriginalTriples

算法2的時間復(fù)雜度主要源于迭代賓語、謂語二元組的for循環(huán),該for循環(huán)執(zhí)行次數(shù)與算法1中第2個for循環(huán)執(zhí)行次數(shù)相等。因此,算法的時間復(fù)雜度為O(|Object|×|P|)。由于算法2的計算過程不需要除輸入輸出外的額外空間,因此其空間復(fù)雜度為O(1)。

4 實驗與結(jié)果分析

本文實驗基于處理器為Intel Core i5 3.1 GHz,內(nèi)存為16 GB 2 133 MHz LPDDR3的計算機(jī)。分別選擇不同領(lǐng)域、不同大小和不同結(jié)構(gòu)化程度的數(shù)據(jù)集,數(shù)據(jù)集描述如表1所示,其中,Archives Hub是檔案文件描述數(shù)據(jù)集,Linkedmdb是電影領(lǐng)域數(shù)據(jù)集,rdfabout是綜合領(lǐng)域數(shù)據(jù)集,dbtune是音樂領(lǐng)域數(shù)據(jù)集。以上述4個數(shù)據(jù)集分析DGC的實驗結(jié)果,對DGC壓縮與解壓縮時間進(jìn)行對比,與HDT++算法對分組數(shù)量和分組謂語總數(shù)進(jìn)行對比,并與Plain(直接存儲)、HDT、HDT++算法對壓縮后空間容量進(jìn)行對比。

表1 數(shù)據(jù)集描述

DGC算法在不同數(shù)據(jù)集上壓縮與解壓縮的時間對比如圖4所示。一般而言,壓縮時間隨著三元組數(shù)量的增長而增長,但同時也受到謂語數(shù)量的影響,從rdfabout到DBpedia的時間陡增論證了這一點(diǎn),DBpedia不僅在三元組數(shù)量上是dbtune的7.3倍,在謂語數(shù)量上更是有146倍的增長,這使得DBpedia存在更多的分組,每個分組中也存在著更多的謂語。因此,需要更多的計算,導(dǎo)致時間的陡增。解壓縮時間雖然也隨著數(shù)據(jù)量的增大而增多,但其增長幅度相對較小,一方面由于解壓縮所需的計算量較少,另一方面可以對不同分組進(jìn)行并行處理以加快速度。

圖4 壓縮與解壓縮的運(yùn)行時間對比

在HDT++連接主語的謂語組合(PS分組)和DGC連接賓語的謂語組合(PO分組)兩種分組方式下,不同數(shù)據(jù)集謂語組合數(shù)量和謂語總數(shù)的對比如表2所示。可以看出,除數(shù)據(jù)集dbtune的PO分組數(shù)大于PS分組數(shù)外,其余數(shù)據(jù)集的PO分組數(shù)均小于PS分組組數(shù),這是由于dbtune的結(jié)構(gòu)化程度高于Archives Hub、Linkedmdb、rdfabout和DBpedia,說明dbtune數(shù)據(jù)集中與主語相連的謂語組合較為完整,可以很好地對主語進(jìn)行分組,而對于結(jié)構(gòu)化程度較低的另外4個數(shù)據(jù)集,謂語組合不能對主語進(jìn)行有效分組,但對賓語分組得到了很好的分組效果。

表2 謂語-賓語分組與謂語-主語分組后謂語組合數(shù)與謂語總數(shù)的比較

由表2可見,在Archives Hub、Linkedmdb、rdfabout、DBpedia數(shù)據(jù)集中,PO謂語總數(shù)都明顯低于PS謂語總數(shù),其中,在DBpedia數(shù)據(jù)集中將語總數(shù)從PS分組下的千萬量級減少到PO分組下的百萬量級,說明PO分組確實有效減少了大量謂語冗余,只有在dbtune數(shù)據(jù)集中PS分組獲得了更好的分組效果。但從另一個角度來看,dbtune的PO謂語組數(shù)是其PS謂語組數(shù)的2.5倍,而PO的謂語總數(shù)卻只是PS謂語總數(shù)的1.4倍,謂語總數(shù)的比例相對于組數(shù)的比例有所降低。反之,在Archives Hub中,PS的謂語組數(shù)是其PO謂語組數(shù)的2.6倍,與dbtune中PO組數(shù)對PS組數(shù)的比例類似,但PS的謂語總數(shù)是PO謂語總數(shù)15倍,在Linkedmdb和rdfabout數(shù)據(jù)集中也有相同的結(jié)論,這是由于PO分組冗余增長受限的特性限制了謂語冗余的產(chǎn)生,無論在結(jié)構(gòu)化程度高或低的數(shù)據(jù)集中,PO分組限制謂語冗余生成的特性都在發(fā)揮作用。

不同算法的壓縮結(jié)果比較如表3所示,其中,Plain列表示將原始數(shù)據(jù)的ID圖直接寫入文件所需空間大小。顯然,DGC算法在所有數(shù)據(jù)集上均取得了最優(yōu)結(jié)果。與Plain和HDT相比,其在不同數(shù)據(jù)集上都取得了超過40%的性能優(yōu)化,這是因為DGC處理了Plain和HDT沒有處理的謂語組合冗余,并利用差分編碼減少了主語序列存儲所需的大量空間。

表3 不同算法的壓縮結(jié)果比較

由表3可見,DGC在與HDT++的對比中也取得了平均18%的優(yōu)化:在結(jié)構(gòu)化程度低的數(shù)據(jù)集Archives Hub、Linkedmdb、rdfabout和DBpedia中,PO分組獲得了冗余更少的謂語組合,差分編碼進(jìn)一步優(yōu)化了壓縮結(jié)果,最終兩者結(jié)合后獲得了平均17%的性能提升;在結(jié)構(gòu)化程度高的dbtune數(shù)據(jù)集中,PO分組相對于PS分組所帶來更多冗余的負(fù)面影響被差分編碼的優(yōu)異效果所彌補(bǔ),獲得了23%的性能提升。同時,其在結(jié)構(gòu)化程度更低的Archives Hub、Linkedmdb、rdfabout和DBpedia數(shù)據(jù)集的性能提升程度反而不及結(jié)構(gòu)化程度更高的dbtune,主要因為這4個數(shù)據(jù)集本身所包含的冗余較少,分組后謂語組合所需空間只占存儲所需空間的較小部分,導(dǎo)致性能提升程度有限。

5 結(jié)束語

本文提出一種基于差分編碼的RDF壓縮算法。根據(jù)謂語對賓語進(jìn)行分組,以減少謂語冗余,同時對分組后的主語序列進(jìn)行差分編碼,從而優(yōu)化主語存儲所需空間。實驗結(jié)果表明,對于結(jié)構(gòu)化程度不同的數(shù)據(jù)集,該算法較Plain、HDT和HDT++算法均能獲得不同程度的性能提升。下一步將設(shè)計更具通用性的壓縮算法以適用于更多具有不同結(jié)構(gòu)化程度的數(shù)據(jù)集,并實現(xiàn)對壓縮數(shù)據(jù)進(jìn)行復(fù)雜查詢的功能。