Нужен алгоритм для свертывания диапазонов netblock в списки диапазонов надмножеств

Моя математика не справляется со мной! Мне нужен эффективный способ сокращения диапазонов сети до надмножеств, например. если я ввожу список диапазонов 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. Однако всякий раз, когда вы вставляете новый диапазон, это может быть надмножество существующих диапазонов, поэтому вам нужно проверить существующие диапазоны, чтобы увидеть, могут ли они быть свернуты (например, удалены из моего списка).

Ответ 1

Это объединение вычислений сегментов. Оптимальный алгоритм (в O (nlog (n))) состоит в следующем:

сортировать все конечные точки (начальную и конечную точки) в списке L (каждая конечная точка должна знать сегмент, к которому она принадлежит). Если конечная точка равна начальной точке, стартовая точка должна считаться меньшей, чем точка enpoint.
просмотрите отсортированный список L слева направо и сохраните номер LE-RE, где LE - количество оставшихся конечных точек, которые вы уже прошли, и RE - количество правильных конечных точек, которые вы уже прошли.
каждый раз, когда LE-RE достигает нуля, вы находитесь в конце связанного объединения сегментов, и вы знаете, что объединение сегментов, которые вы видели раньше (поскольку предыдущий возврат к нулю ) является одним надмножеством.
если вы также поддерживали min и max, между каждым возвратом в ноль, у вас есть границы надмножества.

В конце вы получите отсортированный список непересекающихся надмножеств. Тем не менее, два надмножества A и B могут быть смежными (конечная точка A находится непосредственно перед начальной точкой B). Если вы хотите объединить A и B, вы можете сделать это либо простым шагом постобработки, либо путем незначительного изменения шага 3: когда LE-RE достигнет нуля, вы считаете, что это конец superset, только если следующий элемент в L не является прямым преемником вашего текущего элемента.

Ответ 2

Вы знаете, что вы можете легко конвертировать адреса IPv4 в номера int (int32 numbers), не так ли? Работа с номерами 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 полностью находится в началеIP1-endIP1. Если только первая строка истинна, то startIP2 находится в пределах диапазона startIP1-endIP1, но конец выходит за пределы диапазона. Если выполняется только вторая строка, endIP находится в пределах диапазона, но начальный IP-адрес выходит за пределы диапазона. В этом случае, если выполняется только одна строка, вам необходимо расширить диапазон в начале или в конце. Если обе строки ложны, диапазоны полностью не пересекаются, в этом случае они представляют собой два полностью независимых диапазона.

Ответ 3

Вам нужно просто проверить диапазоны для перекрытия. Если два диапазона перекрываются, они объединяются в один диапазон. Диапазоны перекрываются, если правая сторона одного диапазона больше, чем левая сторона другого.

Ответ 4

Хорошо, мой коллега придумал этот ответ, который я считаю довольно хорошим. Дайте мне знать, если вы видите какие-либо проблемы:

Заказ диапазонов IP по StartIP
Для каждой строки "x" для вставки:
- Если в списке есть предыдущая строка "y", выберите:
  - Если x и y смежны, продолжите y до x EndingIP
  - Иначе, если x.StartingIP <= y.StartingIP и x.EndingIP > y.EndingIP, продолжите y до x.EndingIP
  - Иначе, если x - подмножество y, ничего не делать
  - Else, создайте новый диапазон
- Else, создайте новый диапазон и вставьте в список