李鳳英，楊恩乙，董榮勝

(桂林電子科技大學(xué)可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

1 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)規(guī)模以前所未有的方式不斷增長(zhǎng)，數(shù)據(jù)結(jié)構(gòu)也呈現(xiàn)出復(fù)雜性和多樣性。如何對(duì)其有效地描述、存儲(chǔ)和分析已成為當(dāng)前的研究熱點(diǎn)和難點(diǎn)。圖通常被看成是一系列節(jié)點(diǎn)和節(jié)點(diǎn)關(guān)系的集合[1]，節(jié)點(diǎn)對(duì)應(yīng)于實(shí)體，邊對(duì)應(yīng)于實(shí)體關(guān)系，非常適合描述關(guān)聯(lián)性數(shù)據(jù)及內(nèi)部有一定結(jié)構(gòu)的數(shù)據(jù)，如社交網(wǎng)絡(luò)[2]、知識(shí)圖譜[3]等。

研究表明，大多數(shù)領(lǐng)域的問(wèn)題都可以通過(guò)圖的相關(guān)理論來(lái)解決。在Web網(wǎng)絡(luò)分析[4]中，實(shí)體和它們的關(guān)系可以表示成有向無(wú)權(quán)圖，節(jié)點(diǎn)表示網(wǎng)頁(yè)，邊表示網(wǎng)頁(yè)之間的鏈接，節(jié)點(diǎn)標(biāo)識(shí)表示不同的域名。在這種表示形式下，查詢給定的實(shí)體關(guān)系和偵測(cè)特定的團(tuán)體，可以轉(zhuǎn)化為圖的鄰居查詢和子圖匹配[5 - 7]問(wèn)題。在化學(xué)數(shù)據(jù)分析中，從給定的化合物集中挖掘常見(jiàn)的原子團(tuán)，可以轉(zhuǎn)化為頻繁子圖查詢[8]問(wèn)題。在蛋白質(zhì)交互網(wǎng)絡(luò)分析中，衡量給定的某2個(gè)蛋白質(zhì)發(fā)生作用的概率時(shí)，可以用不確定圖[9,10]建模得以解決?？梢?jiàn)，圖在眾多領(lǐng)域都有著重要的研究?jī)r(jià)值。

隨著圖在各個(gè)領(lǐng)域的廣泛應(yīng)用，傳統(tǒng)的圖存儲(chǔ)結(jié)構(gòu)已經(jīng)不能支持超大規(guī)模圖數(shù)據(jù)的管理和分析。比如具有一百萬(wàn)個(gè)節(jié)點(diǎn)的社交網(wǎng)絡(luò)，鄰接矩陣的大小(2個(gè)節(jié)點(diǎn)之間的1條邊存儲(chǔ)空間為1 bit)大約為116 GB，大多數(shù)計(jì)算機(jī)不會(huì)有如此大的主存儲(chǔ)器來(lái)加載圖并執(zhí)行社交網(wǎng)絡(luò)分析。中國(guó)互聯(lián)網(wǎng)絡(luò)中心2018年發(fā)布的《第41次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r報(bào)告》[11]中提到，網(wǎng)頁(yè)的數(shù)量約為2 600億。若采用圖模型存儲(chǔ)上述網(wǎng)頁(yè)節(jié)點(diǎn)及節(jié)點(diǎn)關(guān)系，至少需要42 TB的存儲(chǔ)空間。并且隨著因特網(wǎng)的不斷發(fā)展，需要的存儲(chǔ)開(kāi)銷(xiāo)也越來(lái)越大。如何存儲(chǔ)和操作上億萬(wàn)個(gè)節(jié)點(diǎn)的圖數(shù)據(jù)，國(guó)內(nèi)外研究人員主要從以下3個(gè)方向做了大量的研究：

(1)外部存儲(chǔ)技術(shù)[12,13]：針對(duì)大規(guī)模圖數(shù)據(jù)無(wú)法一次裝入內(nèi)存問(wèn)題，研究人員一方面將圖數(shù)據(jù)存儲(chǔ)到價(jià)格低廉、容量大的外部存儲(chǔ)器(硬盤(pán)或軟盤(pán))，另一方面設(shè)計(jì)更加高效的I/O算法來(lái)避免更多的I/O開(kāi)銷(xiāo)。

(2)分布式存儲(chǔ)技術(shù)[14]：將圖數(shù)據(jù)分割為多個(gè)部分，存儲(chǔ)到不同的分布式計(jì)算機(jī)中，但這會(huì)帶來(lái)更多的通信開(kāi)銷(xiāo)和CPU資源消耗。

(3)圖數(shù)據(jù)壓縮技術(shù)[15 - 17]：主要思想是消除圖數(shù)據(jù)中的冗余信息，將圖數(shù)據(jù)以壓縮的形式存儲(chǔ)到內(nèi)存中。

相對(duì)前2種技術(shù)，第(3)種技術(shù)時(shí)間開(kāi)銷(xiāo)相對(duì)降低，而且可以適用于任何類(lèi)型的圖數(shù)據(jù)。

本文主要從3個(gè)方面討論圖數(shù)據(jù)壓縮技術(shù):

(1)基于鄰接矩陣的壓縮技術(shù)，主要思想是盡可能地壓縮鄰接矩陣中的“0”元素。

(2)基于鄰接表的壓縮技術(shù)，主要思想是利用節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集的相似性和局部引用性來(lái)進(jìn)行壓縮。

(3)基于形式化方法的壓縮技術(shù)，主要思想是對(duì)所給的圖進(jìn)行編碼，使其轉(zhuǎn)化為布爾代數(shù)，再利用決策圖對(duì)布爾代數(shù)進(jìn)行表示和化簡(jiǎn)。

本文的結(jié)構(gòu)如下：首先介紹3類(lèi)壓縮技術(shù)，分別為基于鄰接矩陣的壓縮技術(shù)、基于形式化方法的壓縮技術(shù)和基于鄰接表的壓縮技術(shù)。在此基礎(chǔ)上，為了充分說(shuō)明形式化方法對(duì)于圖數(shù)據(jù)壓縮的優(yōu)勢(shì)，我們給出了相關(guān)的實(shí)驗(yàn)數(shù)據(jù)對(duì)比，并預(yù)測(cè)了未來(lái)圖數(shù)據(jù)壓縮發(fā)展方向。

2 基于鄰接矩陣的壓縮技術(shù)

Broder等人[18]和Raghavan等人[19]的研究表明，大量的圖特征函數(shù)服從冪律分布，其鄰接矩陣往往具有一定的稀疏性和聚類(lèi)性。Brisaboa等人[20]利用鄰接矩陣的特征提出了k2-tree，取得了較好的時(shí)間/空間均衡。k2-tree的構(gòu)造過(guò)程主要包括以下2個(gè)步驟：

步驟1對(duì)于1個(gè)給定的n×n鄰接矩陣，首先判斷n是否為k的冪。若滿足條件，轉(zhuǎn)到步驟2；若n不是k的冪，增加矩陣中的行和列使得n=ks(s為正整數(shù))，其中增加的行和列的元素用“0”填充，然后再轉(zhuǎn)到步驟2進(jìn)行遞歸劃分。

步驟2進(jìn)行遞歸劃分：根據(jù)MXQuntree規(guī)則[21]把矩陣劃分為k2個(gè)大小一致的子矩陣。如果子矩陣中的元素至少有1個(gè)為1，那么把這種矩陣標(biāo)記為1,否則標(biāo)記為0,自上而下，自左而右排列這些值，它們將作為根節(jié)點(diǎn)的4個(gè)兒子節(jié)點(diǎn)，樹(shù)的第1層節(jié)點(diǎn)構(gòu)造完畢。將標(biāo)記為1的矩陣再進(jìn)行遞歸處理，它們的值將作為樹(shù)的第2層節(jié)點(diǎn)，如此重復(fù)直到劃分后的矩陣全部為0或者已經(jīng)劃分到原始矩陣中的某個(gè)元素，遞歸停止。

如圖1所示是1個(gè)具有4個(gè)節(jié)點(diǎn)的網(wǎng)頁(yè)圖所對(duì)應(yīng)的鄰接矩陣以及k2-tree(n是k的冪)。圖2所示是1個(gè)具有11個(gè)節(jié)點(diǎn)的網(wǎng)頁(yè)圖所對(duì)應(yīng)的鄰接矩陣以及k2-tree(n不是k的冪)，矩陣中的深色部分是為滿足條件所增加的行和列。

Figure 1 k2-tree corresponding to 4*4 adjacency matrix(k=2)圖1 4×4 鄰接矩陣所對(duì)應(yīng)的k2-tree(k=2)

Figure 2 Extension of matrix and construction of k2-tree when k=2圖2 k=2 時(shí)矩陣的拓展和k2-tree 構(gòu)建

如圖2所示，若用鄰接矩陣來(lái)存儲(chǔ)節(jié)點(diǎn)數(shù)為11的網(wǎng)頁(yè)圖，需要的存儲(chǔ)空間為121 bit。若采用k2-tree存儲(chǔ)，存儲(chǔ)空間為72 bit?？梢?jiàn)k2-tree比鄰接矩陣具有更好的空間利用率，并且隨著圖節(jié)點(diǎn)數(shù)目的不斷增加，k2-tree節(jié)省的存儲(chǔ)空間會(huì)越來(lái)越多。不僅如此，k2-tree還支持在常數(shù)時(shí)間范圍內(nèi)查詢節(jié)點(diǎn)的直接鄰居和反向鄰居。

k2-tree能夠緊湊地表示圖數(shù)據(jù)，但傳統(tǒng)的k2-tree對(duì)于圖的鄰接矩陣的壓縮還存在不足：(1)網(wǎng)頁(yè)圖中的節(jié)點(diǎn)和鏈接分布嚴(yán)重依賴于URL排序。若采用傳統(tǒng)的k2-tree思想機(jī)械地劃分網(wǎng)頁(yè)圖，會(huì)導(dǎo)致稠密區(qū)域和稀疏區(qū)域劃分到同1個(gè)子矩陣中，這會(huì)使得空間利用率降低。(2)k2-tree的鄰居查詢時(shí)間與k2-tree的高度成正比，面對(duì)上億個(gè)節(jié)點(diǎn)的圖數(shù)據(jù)，若不對(duì)其進(jìn)行處理，鄰居查詢時(shí)間會(huì)大大增加。

為了更加有效、緊湊地壓縮表示網(wǎng)頁(yè)圖，Claude等人[22]利用網(wǎng)頁(yè)圖中域特有的規(guī)律，提出了k2-partition。他們沿著對(duì)角線把圖劃分成不同的域，對(duì)不同的域用傳統(tǒng)的k2-tree表示，實(shí)現(xiàn)了較好的時(shí)間/空間均衡。以下用實(shí)例來(lái)說(shuō)明如何對(duì)圖數(shù)據(jù)進(jìn)行k2-partition表示。

采用傳統(tǒng)的k2-tree表示圖2中的矩陣需要72 bit的存儲(chǔ)空間，而采用k2-partition表示圖3和圖4中的矩陣，需要的存儲(chǔ)空間為64 bit，存儲(chǔ)空間需求有所改善，并且隨著圖節(jié)點(diǎn)的增加，效果會(huì)越來(lái)越明顯。在傳統(tǒng)的k2-tree中查詢給定節(jié)點(diǎn)的鄰居信息的時(shí)間與樹(shù)的高度成正比，在k2-partition中由于降低了樹(shù)的高度，因此能獲得更好的查詢時(shí)間。

Figure 3 Dividing the graph into domains圖3 對(duì)圖進(jìn)行分域處理

Figure 4 k2-tree representation of different domains圖4 不同域的k2-tree表示

出于對(duì)多維數(shù)據(jù)如時(shí)序圖(節(jié)點(diǎn)關(guān)系隨時(shí)間改變的動(dòng)態(tài)圖)、社交網(wǎng)絡(luò)圖和引文網(wǎng)絡(luò)圖緊湊表示的需要，Caro等人[23]利用k2-tree的構(gòu)造思想提出了kd-tree。kd-tree是k2-tree的一般化形式，通常用來(lái)表示d維的二元矩陣，對(duì)于1個(gè)規(guī)模為n1×n2×…×nd的d維矩陣，將其遞歸地劃分為kd個(gè)子矩陣，為了簡(jiǎn)化分析，假設(shè)對(duì)于每一個(gè)i(d≥i≥1)都有ni=n，其中每1個(gè)樹(shù)中的節(jié)點(diǎn)都擁有kd個(gè)兒子節(jié)點(diǎn)來(lái)表示對(duì)應(yīng)的子矩陣。對(duì)于每1個(gè)子矩陣，按照從高維到低維的次序來(lái)確定kd-tree中的第1層至最后1層的值，如果子矩陣存在“1”值的元素，使用“1”來(lái)表示，如果為“0”，使用“0”來(lái)表示。圖5表示了不同維度下kd-tree(k=2)表示方法。

3 基于形式化方法的壓縮技術(shù)

Figure 5 Construction of kd -tree in different dimensions(d is the dimension of data,k=2)圖5 不同維度的kd-tree的構(gòu)建(d為數(shù)據(jù)的維度，k=2)

二叉決策圖BDD(Binary Decision Diagram)作為一種新型的數(shù)據(jù)結(jié)構(gòu)，不僅是解決布爾代數(shù)表示與計(jì)算的最為有效的工具[24 - 26],還是符號(hào)模型檢驗(yàn)技術(shù)[27,28]的核心。2007年,楊志飛等人[29]將符號(hào)計(jì)算運(yùn)用到大規(guī)模圖數(shù)據(jù)的壓縮表示中，核心思想是將圖中的節(jié)點(diǎn)進(jìn)行二進(jìn)制編碼，把圖中的鏈接關(guān)系轉(zhuǎn)化為布爾代數(shù)，進(jìn)一步布爾代數(shù)可以通過(guò)有序二叉決策圖OBDD(Ordered Binary Decision Diagram)求解。利用布爾代數(shù)中節(jié)點(diǎn)取值的冗余，衍生出OBDD的化簡(jiǎn)規(guī)則和刪除規(guī)則，以此來(lái)共享子圖，提高存儲(chǔ)效率。在這種表示形式下，查詢圖中節(jié)點(diǎn)的度數(shù)、判斷2個(gè)節(jié)點(diǎn)是否存在鏈接關(guān)系、向圖中增加或者刪除邊和圖的同構(gòu)問(wèn)題分別可以轉(zhuǎn)化為OBDD的可滿足性問(wèn)題、OBDD的求值操作、OBDD的apply操作和OBDD的等價(jià)性判定[30]。將圖轉(zhuǎn)化為OBDD的具體思想為：對(duì)于1個(gè)具有n個(gè)節(jié)點(diǎn)的有向圖，利用布爾變量對(duì)節(jié)點(diǎn)和邊進(jìn)行編碼，將其轉(zhuǎn)化為布爾表達(dá)式。如圖6a中具有4個(gè)節(jié)點(diǎn)，故需要2個(gè)布爾變量。對(duì)于圖6a中的有向邊，則需要2組布爾變量來(lái)分別表示有向邊的起點(diǎn)和終點(diǎn)，設(shè)有向邊的起點(diǎn)用x=x1x2表示，終點(diǎn)用y=y1y2表示，其中x1，x2，y1，y2∈{0,1}，由于節(jié)點(diǎn)0和節(jié)點(diǎn)1存在有向邊，設(shè)節(jié)點(diǎn)0的編碼為x′1x′2(表示x1取1，x2取1)，節(jié)點(diǎn)1的編碼為y′1y2(表示y1取1，y2取1)，則有向邊可表示為x′1x′2y′1y2?；谏鲜龇椒?，編碼每1條邊，便可得到該圖對(duì)應(yīng)的OBDD，如圖6b所示是圖6a有向圖所對(duì)應(yīng)的OBDD。由于OBDD的終節(jié)點(diǎn)只能為0或1,所以它只能表示無(wú)權(quán)圖。Bahar等人[31]提出了代數(shù)決策圖ADD(Algebraic Decision Diagram)，進(jìn)一步把布爾代數(shù)拓展到偽布爾代數(shù)，將無(wú)權(quán)圖拓展到帶權(quán)圖，進(jìn)一步豐富了圖的布爾代數(shù)表示方法。將圖轉(zhuǎn)化為ADD的思想和OBDD類(lèi)似，其中的區(qū)別在于ADD的終節(jié)點(diǎn)不再是0或1，而是圖中存在的每1條邊的權(quán)重值。如圖7所示是4個(gè)節(jié)點(diǎn)的帶權(quán)有向圖所對(duì)應(yīng)的鄰接矩陣MG以及代數(shù)決策圖。

Figure 6 An OBDD representation of a digraph圖6 有向圖的OBDD表示

Figure 7 An ADD representation of a weighted graph圖7 帶權(quán)圖的ADD表示

隨著圖數(shù)據(jù)規(guī)模的不斷增長(zhǎng)，如何更加有效地緊湊表示圖數(shù)據(jù)，成為當(dāng)前的一個(gè)研究重點(diǎn)。文獻(xiàn)[20]提到k2-tree能很好地壓縮鄰接矩陣，實(shí)現(xiàn)較好的時(shí)間/空間均衡，但k2-tree還面臨以下問(wèn)題：(1)k2-tree中還存在大量的同構(gòu)子樹(shù)。(2)k2-tree只能對(duì)稀疏圖進(jìn)行壓縮。(3)k2-tree只能表示靜態(tài)圖，不能向其中增加或者刪除邊。

針對(duì)上述問(wèn)題，董榮勝等人[32]把多值決策圖MDD(Multi-value Decision Diagram)[33]和k2-tree進(jìn)行結(jié)合,提出了k2-MDD，利用MDD的刪除規(guī)則和化簡(jiǎn)規(guī)則以及多變量取值性質(zhì)進(jìn)行相同子圖的合并，構(gòu)造過(guò)程主要包括3步：

步驟1將所給的鄰接矩陣用傳統(tǒng)的k2-tree表示。

步驟2刪除k2-tree中所有的0節(jié)點(diǎn)，合并k2-tree葉子節(jié)點(diǎn)中為1的節(jié)點(diǎn)。

步驟3對(duì)k2-tree每個(gè)分支進(jìn)行二進(jìn)制編碼(k=2)，節(jié)點(diǎn)值相等且兒子節(jié)點(diǎn)相同的節(jié)點(diǎn)合并(共享子圖)。

圖8所示是11個(gè)頂點(diǎn)的鄰接矩陣的k2-tree表示。圖9所示是傳統(tǒng)的k2-tree中的同構(gòu)子樹(shù)的分布，相同的子樹(shù)用大小相等的方框注明。圖10表示k2-tree的MDD。

Figure 8 k2-tree representation of an adjacency matrix圖8 鄰接矩陣的k2-tree表示

Figure 9 Isomorphic subtree distribution of k2-tree圖9 k2-tree的同構(gòu)子樹(shù)分布

Figure 10 MDD representation of a k2-tree圖10 k2-tree的MDD表示

4 基于鄰接表的壓縮技術(shù)

根據(jù)研究表明，如果所有網(wǎng)頁(yè)圖的URLs按照字典序排序，大多數(shù)的網(wǎng)頁(yè)圖具有以下2種特性[34,35]:

(1)局部性：對(duì)于某個(gè)頁(yè)面來(lái)說(shuō)，它的直接鄰居集合彼此之間挨得很近。

(2)相似性：位置上靠得很近的一些網(wǎng)頁(yè)集，它們的后繼集很相似。

利用網(wǎng)頁(yè)的局部性，Boldi等人[36]提出了空隙編碼,其思想為用2個(gè)連續(xù)的節(jié)點(diǎn)標(biāo)簽值來(lái)替代原始節(jié)點(diǎn)標(biāo)簽值，設(shè)A(x)=(a1,a2,a3,…,an)，x為第x個(gè)節(jié)點(diǎn)的標(biāo)簽值，a1,a2,a3,…,an為x的直接鄰居，則x對(duì)應(yīng)的空隙編碼為B(x)=(c(a1-x),a2-a1-1,a3-a2-1,…,an-an-1-1)。式(1)為計(jì)算A(x)中a1的空隙編碼標(biāo)簽值。

(1)

表1是網(wǎng)頁(yè)圖中截取的小部分鄰接表，表2是鄰接表對(duì)應(yīng)的空隙編碼。

Table 1 Traditional adjacency table representation表1 傳統(tǒng)的鄰接表表示

Table 2 Void coding representation表2 空隙編碼表示

圖數(shù)據(jù)規(guī)模的不斷增長(zhǎng)使得節(jié)點(diǎn)標(biāo)簽值的位數(shù)不斷增加，空隙編碼的本質(zhì)為壓縮節(jié)點(diǎn)的標(biāo)簽值，減少所需要的存儲(chǔ)空間。

利用網(wǎng)頁(yè)的相似性，Suel等人[37]提出了參考?jí)嚎s，其思想是用1個(gè)節(jié)點(diǎn)的鄰接表來(lái)表示其余的鄰接表，設(shè)s(x),s(y)分別為2個(gè)節(jié)點(diǎn)的出度表，s(x)稱為參考表，s(y)稱為復(fù)制表，y-x稱為參考系數(shù)，用r表示。若s(x)的后繼在s(y)中也存在，那么復(fù)制表中對(duì)應(yīng)位置為1，否則為0。進(jìn)一步若s(y)的后繼在s(x)中不存在，記這些節(jié)點(diǎn)為額外節(jié)點(diǎn)。表3是鄰接表的參考?jí)嚎s。

上述2種技術(shù)都要求節(jié)點(diǎn)的直接鄰居集合是有序的，如果網(wǎng)頁(yè)圖需要保存最原始的鏈接順序，上面的方法并不適用。

Adler和Faust等人[38,39]2010年發(fā)現(xiàn)，

Table 3 Reference compressed of adjacency table表3 鄰接表的參考?jí)嚎s

鄰接表的節(jié)點(diǎn)之間的后繼有許多相似的信息，這意味著數(shù)據(jù)還存在一定的冗余[38,39]，Repair算法[40]應(yīng)運(yùn)而生。其算法思想是把所有節(jié)點(diǎn)的后繼看成1個(gè)序列T，每1次在序列中用s(s為從來(lái)沒(méi)有在T中出現(xiàn)的符號(hào))替換T中最頻繁的符號(hào)對(duì)，直到序列T不再出現(xiàn)頻繁模式。假設(shè)圖G=(V,E)，T(G)=v1v1.1v1.2v1.3…v1.nv2v2.1v2.2v2.3…v2.n…vnvn.1vn.2vn.3…vn.n，其中v1為第1個(gè)節(jié)點(diǎn)的標(biāo)簽值，v1.n為第1個(gè)節(jié)點(diǎn)的后繼。Ptrs[m]為1個(gè)指針數(shù)組，記錄每1個(gè)節(jié)點(diǎn)在序列T中的起始位置。圖11是給定圖的鄰接表的Repair壓縮。

Figure 11 Repair compression of an adjacent table圖11 鄰接表的Repair壓縮

Repair算法將1個(gè)鄰接表壓縮成1個(gè)字典規(guī)則R的集合，1個(gè)指針數(shù)組ptrs，1個(gè)序列T。每次查詢節(jié)點(diǎn)的信息時(shí)，僅僅需要找到該節(jié)點(diǎn)的起始位置和終止位置，然后進(jìn)行部分解壓縮即可。但是，對(duì)于大規(guī)模圖而言，由于每次都要添加新的規(guī)則，字典規(guī)則R的集合越來(lái)越大，Bille等人[41]對(duì)該算法進(jìn)行了改進(jìn),取得了很好的時(shí)間/空間均衡。

另1種基于鄰接表的壓縮稱為L(zhǎng)Z78算法[42]，由Ziv和Lempel提出，其思想為建立1個(gè)字典表，每讀入1個(gè)字符，判斷其是否在字典表中，若不存在，則保存字符并建立索引。若存在，則保存索引并加上新的字符作為這個(gè)字符串的表示。

具體的算法流程如下[43]：

步驟1建立字典表，并將字典表設(shè)置為空。

步驟2依次讀取文本中的1個(gè)新的字符，設(shè)新字符為C。

步驟3在詞典中查找當(dāng)前的前綴和新的字符的組合，也就是P+C：

(1)如果在字典表中找到了這個(gè)新組合，那么就把前綴P重新進(jìn)行改寫(xiě)，需要加上新讀取的字符C。

(2)如果字典表中沒(méi)有這個(gè)新組合,就要執(zhí)行保存新組合的操作：

①輸出當(dāng)前前綴的索引以及字符C。

②把前綴和新讀取的字符串保存在字典表中。

③重新改寫(xiě)前綴P，將其設(shè)置為空。

(3)重復(fù)步驟2和步驟3，直到所有的字符串都完成編碼。

LZ78算法和Repair算法在對(duì)文本壓縮時(shí)有1個(gè)區(qū)別：T(G)=v1.1v1.2v1.3…v1.nv2.1v2.2v2.3…v2.n…vn.1vn.2vn.3…vn.n，表4所示是圖11所示的鄰接表的LZ78壓縮。

Table 4 LZ78 compression表4 LZ78壓縮結(jié)果

LZ78算法和Repair最大的區(qū)別在于在壓縮時(shí)不用存儲(chǔ)和維護(hù)字典表，因?yàn)樽值浔硪越Y(jié)果形式輸出了，因此LZ78算法查詢節(jié)點(diǎn)信息的速度比Repair算法快，但由于每次解壓過(guò)程，從結(jié)果的最開(kāi)始開(kāi)始構(gòu)造字典R，所以只能對(duì)鄰接表的邊表進(jìn)行壓縮，限制了LZ78算法的性能。

5 圖數(shù)據(jù)壓縮技術(shù)比較

文獻(xiàn)[17]采用真實(shí)的網(wǎng)頁(yè)圖數(shù)據(jù)集和社交網(wǎng)絡(luò)數(shù)據(jù)集對(duì)其中提到的所有壓縮技術(shù)進(jìn)行了對(duì)比，其數(shù)據(jù)集來(lái)自于米蘭大學(xué)LAW[44]，表5給出了網(wǎng)頁(yè)圖數(shù)據(jù)集的相關(guān)屬性，表6給出了社交網(wǎng)絡(luò)數(shù)據(jù)集的相關(guān)屬性。通過(guò)一系列的實(shí)驗(yàn)對(duì)比，他們得出k2-tree的壓縮率明顯低于其他算法(Repair，LZ78等算法)的，能實(shí)現(xiàn)較好的時(shí)間/空間均衡。為了體現(xiàn)出符號(hào)計(jì)算對(duì)于大規(guī)模圖數(shù)據(jù)壓縮處理的優(yōu)勢(shì)，本文將k2-tree分別與OBDD，k2-MDD 2種壓縮技術(shù)做了實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果如表7和表8所示。

Table 5 Web graph data set表5 網(wǎng)頁(yè)圖數(shù)據(jù)集

Table 6 Social network data set表6 社交網(wǎng)絡(luò)數(shù)據(jù)集

Table 7 Experimental results of web graph表7 網(wǎng)頁(yè)圖實(shí)驗(yàn)結(jié)果 bit

Table 8 Experimental results of social network 表8 社交網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果 bit

實(shí)驗(yàn)結(jié)論：在k2-tree，k2-MDD,OBDD中，用1個(gè)位串T來(lái)記錄除最后1層節(jié)點(diǎn)的0值和1值，1個(gè)位串L來(lái)記錄最后1層節(jié)點(diǎn)的0值和1值，T和L的總和為需要的存儲(chǔ)空間。如表7所示，若采用OBDD來(lái)壓縮網(wǎng)頁(yè)圖，T和L的總和約為k2-tree的21%，若采用k2-MDD來(lái)壓縮網(wǎng)頁(yè)圖，T和L的總和約為k2-tree的3%，如表8所示，我們用社交網(wǎng)絡(luò)數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn)對(duì)比，分別在enron，dblp-1，dblp-2，dewiki數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，得到的T和L的總和分別為k2-tree的4.8%，5.1%，4.7%，3%，對(duì)存儲(chǔ)空間的需求得到有效的改善。

6 結(jié)束語(yǔ)

隨著圖在各個(gè)領(lǐng)域的廣泛應(yīng)用，傳統(tǒng)的圖存儲(chǔ)結(jié)構(gòu)已經(jīng)不能支持大規(guī)模圖數(shù)據(jù)的管理和操作，如何有效地緊湊表示圖數(shù)據(jù)并且支持快速的訪問(wèn)已經(jīng)成為一項(xiàng)重要的研究任務(wù)。本文首先介紹圖數(shù)據(jù)應(yīng)用概況和相關(guān)的圖數(shù)據(jù)壓縮表示技術(shù)，然后詳細(xì)闡述了3種圖數(shù)據(jù)壓縮技術(shù)，并給出了不同壓縮技術(shù)的優(yōu)缺點(diǎn)。通過(guò)分析發(fā)現(xiàn)，基于形式化方法的圖壓縮技術(shù)在處理大規(guī)模圖數(shù)據(jù)時(shí)，具有很好的壓縮效果，這也是我們下一步研究的重點(diǎn)。對(duì)于圖數(shù)據(jù)的壓縮，未來(lái)可能會(huì)結(jié)合機(jī)器學(xué)習(xí)的聚類(lèi)算法和形式化方法來(lái)更好地解決數(shù)據(jù)的冗余問(wèn)題。由于篇幅有限，本文不可能涵蓋該領(lǐng)域所有的研究?jī)?nèi)容，希望這篇綜述能對(duì)圖數(shù)據(jù)壓縮技術(shù)的研究起到一定的參考作用。