algorithm - subconjunto - necesita un algoritmo para colapsar rangos netblock en listas de rangos de superconjunto

teoria de conjuntos

Question

¡Mi matemática fu me está fallando! Necesito una forma eficiente de reducir los rangos de red a superconjuntos, por ejemplo, si ingreso una lista de rangos de IP:

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

Quiero devolver los siguientes rangos:

• 1.1.1.1 a 2.2.2.5
• 10.5.5.5 a 155.5.5.5

Nota: las listas de entrada no están ordenadas (¿pero podrían ser?). La forma ingenua de hacerlo es verificar cada rango en la lista para ver si el rango de entrada x es un subconjunto, y si es así, NO inserte el rango x. Sin embargo, cada vez que inserte un nuevo rango, podría tratarse de un superconjunto de rangos existentes, por lo que debe verificar los rangos existentes para ver si pueden colapsarse (por ejemplo, eliminarlos de mi lista).

Answer 1

Bien, a mi compañero de trabajo se le ocurrió esta respuesta, que creo que es bastante excelente. Avíseme si ve algún problema:

• Ordene los rangos de IP por StartingIP
• Para cada fila "x" para insertar:
  • Si hay una fila "y" anterior en la lista, busque:
    • Si xey son contiguos, extiende y hacia x EndingIP
    • De lo contrario, si x.StartingIP <= y.StartingIP y x.EndingIP> y.EndingIP, extiende y hacia x.EndingIP
    • De lo contrario, si x es un subconjunto de y, no hagas nada
    • De lo contrario, crea un nuevo rango
  • De lo contrario, crea un nuevo rango e inserta en la lista

Answer 2

Esta es una unión de computación de segmentos. Un algoritmo óptimo (en O (nlog (n))) consiste en hacer lo siguiente:

2. ordenar todos los puntos finales (puntos inicial y final) en una lista L (cada punto final debe conocer el segmento al que pertenece). Si un punto final es igual a un punto de inicio, el punto de partida se debe considerar más pequeño que el enpoint.
3. recorra la lista ordenada L de izquierda a derecha y mantenga el número LE-RE , donde LE es la cantidad de puntos finales que ya aprobó, y RE es la cantidad de puntos finales derechos que ya aprobó.
4. cada vez que LE-RE llega a cero, se encuentra al final de una unión de segmentos conectada, y usted sabe que la unión de los segmentos que ha visto antes (desde el retorno anterior a cero) es un superconjunto.
5. si también mantuviste el mínimo y el máximo, entre cada vuelta a cero, tienes los límites del superconjunto.

Al final, obtienes una lista ordenada de superconjuntos disjuntos. Aún así, dos superconjuntos A y B pueden estar adyacentes (el punto final de A está justo antes del punto de inicio de B). Si desea fusionar A y B, puede hacerlo mediante un simple paso de posprocesamiento o modificando ligeramente el paso 3: cuando LE-RE llega a cero, lo consideraría el final de un superconjunto solo si el siguiente elemento de L no es el sucesor directo de su elemento actual.

Answer 3

Lo que necesita hacer es simplemente verificar los rangos de superposición. Si dos rangos se superponen, se fusionan en un solo rango. Los rangos se superponen si el lado derecho de un rango es mayor que el lado izquierdo de otro.

Answer 4

Usted sabe que puede convertir fácilmente direcciones IPv4 a números enteros (números int32), ¿verdad? Trabajar con números enteros es mucho más fácil. Entonces, básicamente, cada dirección es un número en el rango de 0 a 2 ^ 32. Cada rango tiene un número de inicio y un número final. Tu ejemplo

1.1.1.1 to 2.2.2.5
1.1.1.2 to 2.2.2.4

Se puede escribir como

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

Por lo tanto, es bastante fácil ver si un rango está dentro del otro rango. Un rango está completamente dentro del otro rango si se da la siguiente condición

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

En ese caso, el rango de inicioIP2-endIP2 está completamente dentro del inicioIP1-endIP1. Si solo la primera línea es verdadera, entonces startIP2 está dentro del rango de inicioIP1-endIP1, pero el final está más allá del rango. Si solo la segunda línea es verdadera, el endIP está dentro del rango, pero el IP de inicio está más allá del rango. En ese caso, si solo una línea es verdadera, necesita expandir el rango al principio o al final. Si ambas líneas son falsas, los rangos son completamente disjuntos, en ese caso son dos rangos completamente independientes.