[發明專利]一種基于區域劃分的標簽壓縮方法

在審

• 申請號: 202010620689.3
• 申請日: 2020-06-30
• 公開（公告）號: CN112100533A
• 公開（公告）日: 2020-12-18
• 發明（設計）人: 石鴻偉;李坤;黃韜;劉韻潔
• 申請（專利權）人: 網絡通信與安全紫金山實驗室
• 主分類號: G06F16/955
• 分類號: G06F16/955
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 賀翔

1.一種基于區域劃分的標簽壓縮方法，其特征在于，所述壓縮方法包括以下步聚：

步驟一：確定關鍵節點與普通節點；

步驟二：劃分區域，將節點按照直連關系劃分區域，當關鍵節同時屬于多個區域時，充當連接區域的媒介；

步驟三：計算屬于同一區域內任意兩點中間只包含普通節點的路徑；

步驟四：計算關鍵節點間的路徑；

步聚五：拼接除關鍵節點間以外的路徑；

步驟六：用鄰接標簽和節點標簽表示的路徑即為壓縮后的標簽棧。

2.根據權利要求1所述的一種基于區域劃分的標簽壓縮方法，其特征在于，所述步驟二的具體過程為：

步驟2.1，計算普通節點的直連關鍵節點列表keyList，其中直連關鍵節點指普通節點與關鍵節點之間存在一條不經過其他關鍵節點的路徑；

步驟2.2，如果多個普通節點的keyList完全相同，則這些普通節點以及keyList中的關鍵節點組成一個區域；

步驟2.3，一對鄰接的關鍵節點，如果沒有普通節點與它們組成一個區域，則它們組成一個只包含兩個關鍵節點的區域。

3.根據權利要求1所述的一種基于區域劃分的標簽壓縮方法，其特征在于，所述步驟三的具體過程為：

步驟3.1，屬于同一區域內任意兩節點間，利用K-Path算法計算全路徑，并將計算結果保存于pathList中；

步驟3.2，除去pathList中路徑中間包含關鍵節點的路徑，如果路徑中只有起點或終點是關鍵節點，不需要刪除；

步驟3.3，對pathList中的非唯一最短路徑，根據中繼算法標注中繼節點；

步驟3.4，針對所述pathList中每條路徑，判斷每個中間節點是否為中繼節點，如果是，則保留，否則刪掉；

步驟3.5，相臨節點間用“-”表示，非相臨節點間用“*”表示，得到全部普通節點間的路徑。

4.根據權利要求3所述的一種基于區域劃分的標簽壓縮方法，其特征在于，所述步驟四的具體過程為：

步驟4.1，簡化拓撲：去除所有的邊和所有的普通節點，處于同一區域的兩個關鍵節點，用一條邊連接；

步驟4.2，在簡化后的拓撲中，用K-Path算法計算任意兩關鍵節點間的路徑列表keyPathList；

步驟4.3，表示路徑，在相臨的關鍵節點間都用“-”連接，表示完整路徑；

步驟4.4，回歸原始拓撲，對于keyPathList中的每條路徑，使用步驟三得到的同一區域內兩關鍵節點間路徑進行細化與拼接。

5.根據權利要求1所述的一種基于區域劃分的標簽壓縮方法，其特征在于，所述步驟五的具體過程為：

步驟5.1，取路徑的起點和終點所在區域的關鍵節點列表：startKeyList和endKeyList，如果起點或終點本身是關鍵節點，則其keyList只包含自身；

步驟5.2，取startKeyList和endKeyList中的節點，隨機對應組合，全部組合存于組合列表pairList中；

步驟5.3，對于步驟5.2生成的pairList中每組組合，分別獲取三段路徑：

路徑1：起點到關鍵節點，中間不含關鍵節點的路徑；

路徑2：關鍵節點到關鍵節點的路徑；

路徑3：關鍵節點到終點，中間不含關鍵節點的路徑；

其中，路徑1中去除包含終點的路徑，路徑3中去除包含起點的路徑，路徑2中去除包含起點或終點的路徑；

步驟5.4，拼接路徑：按照路徑1——路徑2——路徑3的順序拼接路徑，所拼接路徑的數量為三段路徑數量的乘積；如果有任何一段的路徑數量為0，則最終路徑數量為0；

步驟5.5，如果起點與終點之間原本存在路徑，則與新拼接的路徑合并去重。