[發明專利]一種稠密圖鄰接表壓縮方法

在審

• 申請號: 201710909521.2
• 申請日: 2017-09-29
• 公開（公告）號: CN107564075A
• 公開（公告）日: 2018-01-09
• 發明（設計）人: 李鳳英;張琪;常亮;古天龍
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: G06T9/00
• 分類號: G06T9/00
• 代理公司: 桂林市持衡專利商標事務所有限公司45107
• 代理人: 陳躍琳

技術領域

本發明涉及圖數據壓縮技術領域，具體涉及一種稠密圖鄰接表壓縮方法。

背景技術

數據壓縮是指保證有效信息不丟失的情況下，盡可能減少數據的存儲空間，并且仍能保持或提高數據的傳輸、存儲和處理效率的一種技術方法。該技術或者方法按照相應的算法，對所要壓縮的數據進行重新組織，以減少數據冗余和存儲空間。數據壓縮包括有損壓縮和無損壓縮。有損壓縮是指在壓縮過程中將某些必要數據移除，在讀取數據時將壓縮后的數據重構，重構后的數據與原來的數據有所不同且無法恢復，但不至于對所表達的意思產生誤解，還能大大提高壓縮比。無損壓縮是指利用數據的統計冗余進行壓縮，在讀取數據時將壓縮后的數據重構，重構后的數據與原來的數據完全相同，即可完全恢復原始數據而不引起任何失真。

圖是一種復雜的非線性數據結構，在圖形結構中，結點之間的關系是任意的，圖中任意兩個數據元素之間都有可能相關。這就使得對圖數據的壓縮更為困難。目前對圖的傳統表示方法有兩種：鄰接矩陣和鄰接表。基于鄰接表，根據圖數據對應的鄰接表構造一段字符序列，使用Re-Pair和LZ78算法對字符序列進行壓縮，以達到壓縮圖數據的目的。針對鄰接表壓縮提出的兩種壓縮算法是根據圖數據中許多結點的鄰居集合具有相似性，使得鄰接表中存儲的信息產生冗余這一特性，構造一段字符序列并對其進行壓縮，以達到壓縮圖數據的目的。但是，這兩種算法的壓縮效率仍具有一定的局限性。首先，這兩種算法的基本思想是尋找序列中的頻繁字符對，并使用新的符號進行替代。當頻繁字符串的長度較大時，僅僅尋找頻繁字符對無法達到最佳壓縮率。此外，使用字典R存儲替代規則，占用了額外的存儲空間，且在查詢時，需進行解壓縮操作，增加了查詢負擔。

發明內容

本發明所要解決的是現有基于圖的鄰接表表示形式上對數據進行壓縮存在局限性的問題，提供一種稠密圖鄰接表壓縮方法，其能夠有效提高圖數據的壓縮效率。

為解決上述問題，本發明是通過以下技術方案實現的：

一種稠密圖鄰接表壓縮方法，包括步驟如下：

步驟1、使用廣度優先搜索遍歷整個圖G的所有結點，從中找出出度最大的結點V，將該結點V的編碼設置為0并存儲在結點數組A的A[0]處；

步驟2、以結點V為起始結點，使用深度優先搜索遍歷整個圖G，按照圖G的深度優先搜索序依次為結點編碼，并將結點編碼依次存入結點數組A中；

步驟3、建立結點V的初始出邊表L₀，并將出邊表L₀作為參考出邊表L；

步驟4、對于結點V_i，判斷該結點V_i的編碼i是否包含于參考出邊表L中；若參考出邊表L中包含結點V_i的編碼i，則轉至步驟5，若參考出邊表L中不包含結點V_i的編碼i，則轉至步驟6；

步驟5、將編碼i與結點V_i的第一個鄰接結點V_j的編碼j進行比較；當i≤j時，轉至步驟5.1；當i＞j時，轉至步驟5.2；

步驟5.1、將結點V_i中從第一個鄰接結點開始的結點編碼與參考出邊表L中從結點V_i開始的結點編碼依次做比較；若有編碼相同的結點，則繼續比較，直到找到編碼不同的結點或所有結點全部比較結束且編碼相同為止；當找到編碼不同的結點后，在參考出邊表L中最后一個編碼相同的結點V_last處標記“i”；若始終沒有編碼相同的結點，則轉至步驟6；

步驟5.2、以結點V_j的出邊表L_j中從第一個鄰接結點開始的結點編碼與結點V_i的出邊表L_i中從第二個鄰接結點開始的結點編碼依次做比較，直到找到不同的編碼為止；若找到不同的編碼且不同編碼恰為i，則跳過該編碼，分別取出邊表L_i和L_j的下一個編碼繼續比較，直到找到不同的編碼且該不同編碼不為i；當找到不同的編碼且該不同編碼不為i或所有編碼均相同時，則直接在出邊表L_j中最后一個相同結點V_last處標記“i”；

步驟6、依次以L₁，L₂…L_i-1替換為參考出邊表L后，并轉至步驟4，直到在某一出邊表內標記“i”或在前i-1個結點的出邊表中都未能成功標記“i”時停止替換；