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

Question

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

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

Answer 2

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

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

Answer 3

Этот является объединением вычислений сегментов. Оптимальный алгоритм (в 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 4

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