Exclua intervalos IP sobrepostos no arquivo de texto

Question

Para expandir minha pergunta anterior , Eu tenho uma lista de intervalos de IP no formato:

Long description:20.1.1.0-20.1.1.14
Another description:5.5.5.0-5.5.5.100
Yet another description:20.1.1.0-20.1.1.40

Não há duplicatas, mas gostaria de excluir os intervalos IP sobrepostos.

Por exemplo, no exemplo acima, a primeira linha deve ser excluída, já que sua faixa já está incluída na terceira linha.

NOTA: eu preciso manter toda a linha (descrição incluída), não apenas os intervalos de IP.

    

Answer 1

Se você está bem com as linhas de entrada sendo reordenadas, eu tenho uma solução relativamente simples usando o GNU Awk e o comando "sort". A ideia básica é converter os endereços IP em números únicos em vez de pares pontilhados, o que torna muito fácil compará-los e usar o -k flag of sort que permite especificar que ele deve classificar apenas campos específicos.

Para compactação, isso também usa o recurso GNU awk dos coprocessos, o que torna muito fácil processar dados antes e depois de usar sort :

EDITAR: A linha de comando sort na versão original desta resposta estava um pouco errada: sort -k2,3r trata os campos 2 e 3 como uma única chave, para serem classificados em ordem reversa. sort -k2,2n -k3,3rn fará a coisa necessária da primeira classificação pelo campo 2 e usando o campo (invertido) 3 como desempatador:

# Run as: gawk -F: -f <thisfile.awk> <input file>
BEGIN {
  # Define the sort command that we will be using later as a variable
  # Sort by
  #   - the 1st ip, smallest-to-largest
  #   - the 2nd ip, largest-to-smallest
  sort="sort -n -t: -k2,2n -k3,3nr";
}

# For every line:
{
  # Store the individual components of the addresses into 'ips'
  match($2, /([[:digit:]]+).([[:digit:]]+).([[:digit:]]+).([[:digit:]]+)\
-([[:digit:]]+).([[:digit:]]+).([[:digit:]]+).([[:digit:]]+)/, ips);
  # Add the components together to get the IPs as a single number.
  # The print also uses : as the delimiter between the 2 IPS for simplicity
  print $1":"ips[4]+256*(ips[3]+256*(ips[2]+256*ips[1])) \
          ":"ips[8]+256*(ips[7]+256*(ips[6]+256*ips[5])) \
    |& sort
}

# After sending all lines to sort in the appropriate format
END {
  # Close sort's input stream, so that we can read its output
  close(sort, "to");
  # Keep track of the upper end of the previous range
  prevHigh=0;
  # Read & field-split all lines from sort's output
  while((sort |& getline) > 0) {
     # One range is contained in another if its low address is >= the
     # other's (guaranteed by the sort command) and its high address is <=
     # the other's. So, we should print this record when its high address is >
     # prevHigh:
    if ($3 > prevHigh) {
      print $1":"int($2/(256*256*256))%256"."int($2/(256*256))%256"." \
                 int($2/256)%256"."$2%256 \
              "-"int($3/(256*256*256))%256"."int($3/(256*256))%256"." \
                 int($3/256)%256"."$3%256 \
      # This is now the previous range
      prevHigh = $3
    }
  }
}