需要一种算法将网络范围折叠成超集范围列表

Question

我的数学功能让我失望!我需要一种将网络范围减少到超集的有效方法,例如,如果我输入IP范围列表:

• 1.1.1.1至2.2.2.5
• 1.1.1.2至2.2.2.4
• 10.5.5.5至155.5.5.5
• 10.5.5.6至10.5.5.7

我想返回以下范围:

• 1.1.1.1至2.2.2.5
• 10.5.5.5至155.5.5.5

注意:输入列表没有排序(虽然它们可能是？).执行此操作的简单方法是检查列表中的每个范围,以查看输入范围x是否为子集,如果是,则不插入范围x.但是,无论何时插入新范围,它都可能是现有范围的超集,因此您必须检查现有范围以查看它们是否可以折叠(例如,从我的列表中删除).

Answer 1

这是段计算的联合.最优算法(在O(nlog(n))中包括执行以下操作:

2. 对列表L中的所有端点(起始点和结束点)进行排序(每个端点应该知道它所属的段).如果端点等于起点,则应将起点视为小于enpoint.
3. 从左到右遍历排序列表L并保持数字LE-RE,其中LE是您已经通过的左端点数,RE是您已经传递的右端点数.
4. 每当LE-RE达到零时,你就处于一个连接的段连接的末尾,你知道你之前看到的段的并集(从前一个返回到零)是一个超集.
5. 如果你还保持最小值和最大值,每次返回零之间,你就有超集的界限.

最后,您将获得不相交的超集的排序列表.两个超集A和B可以相邻(A的端点恰好在B的起点之前).如果你想要合并A和B,你可以通过一个简单的后处理步骤,或者通过稍微修改第3步来做到这一点:当LE-RE达到零时,你会认为它只是一个超集的结尾,只有下一个元素在L不是当前元素的直接继承者.

Answer 2

您知道可以轻松地将 IPv4 地址转换为 int 数字（int32 数字），对吗？使用 int 数字要容易得多。所以基本上每个地址都是 0 到 2^32 范围内的数字。每个范围都有一个开始编号和一个结束编号。你的榜样

1.1.1.1 to 2.2.2.5
1.1.1.2 to 2.2.2.4

可以写成

16,843,009 to 33,686,021
16,843,010 to 33,686,020

所以很容易看出一个范围是否在另一个范围内。如果给出以下条件，则一个范围完全在另一个范围内

startIP2 >= startIP1 && startIP2 <= endIP1 &&
endIP1 >= startIP1 && endIP2 <= endIP1

在这种情况下，范围 startIP2-endIP2 完全在 startIP1-endIP1 内。如果只有第一行为真，则 startIP2 在 startIP1-endIP1 范围内，但 end 超出范围。如果只有第二行为真，则endIP在范围内，但起始IP超出范围。在这种情况下，如果只有一行为真，则需要在开头或结尾扩展范围。如果两行都为假，则范围完全不相交，在这种情况下，它们是两个完全独立的范围。

Answer 3

您需要做的只是检查重叠范围。如果两个范围重叠，那么它们将合并为一个范围。如果一个范围的右侧大于另一个范围的左侧，则范围重叠。