一种基于区域划分的标签压缩方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN112100533A(43)申请公布日2020.12.18(21)申请号202010620689.3(22)申请日2020.06.30(71)申请人网络通信与安全紫金山实验室地址210000江苏省南京市江宁区秣周东路9号(72)发明人石鸿伟李坤黄韬刘韵洁(74)专利代理机构江苏圣典律师事务所32237代理人贺翔(51)Int.Cl.G06F16/955(2019.01)权利要求书3页说明书9页附图3页(54)发明名称一种基于区域划分的标签压缩方法(57)摘要本发明提供一种基于区域划分的标签压缩方法，该方法包括以下步骤：步骤一：确定关键节点与普通节点；步骤二：划分区域，将节点按照直连关系划分区域，当关键节同时属于多个区域时，充当连接区域的媒介；步骤三：计算属于同一区域内任意两普通节点间的路径；步骤四：计算关键节点间的路径；步聚五：拼接除关键节点间以外的路径；该方法还针对拓扑中没有关键节点及没有普通节点的情况，提出了相应的路径计算方法，完成路径计算之后，只保留路径中的关键节点和中继节点，即完成了标签压缩，无需二次计算。该标签压缩方法降低了计算量，提供了灵活、轻便的动态更新能力，适用于拓扑复杂、拓扑变化频繁、实时性要求高、存在订制化需求等标签压缩场景。CN112100533ACN112100533A权利要求书1/3页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和2CN112100533A权利要求书2/3页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，如果起点