[已解决]求个脚本或工具能合并ip地址段的脚本

sh/bash/dash/ksh/zsh等Shell脚本
回复
头像
pocoyo
论坛版主
帖子: 25878
注册时间: 2008-03-25 15:49
来自: 谁知道?
送出感谢: 5 次
接收感谢: 9 次
联系:

[已解决]求个脚本或工具能合并ip地址段的脚本

#1

帖子 pocoyo » 2015-02-05 11:53

原始数据如下:

代码: 全选

111.5.0.0/16
111.6.0.0/16
111.7.0.0/16
111.7.0.0/18
211.138.17.0/24
211.138.18.0/24
211.138.20.0/22
211.138.25.0/24
211.138.26.0/23
211.138.28.0/24
211.138.30.0/23
221.177.217.0/24
221.177.218.0/24
221.177.219.0/24
221.177.220.0/24
221.177.233.0/24
221.177.234.0/24
221.177.235.0/24
221.177.236.0/24
223.88.0.0/16
223.89.0.0/16
223.90.0.0/16
223.91.0.0/16
需要合并成如下结果网段:

代码: 全选

111.5.0.0/16
111.6.0.0/15
211.138.17.0/24
211.138.18.0/24
211.138.20.0/22
211.138.25.0/24
211.138.26.0/23
211.138.28.0/24
211.138.30.0/23
221.177.217.0/24
221.177.218.0/23
221.177.220.0/24
221.177.233.0/24
221.177.234.0/23
221.177.236.0/24
223.88.0.0/14
头像
astolia
论坛版主
帖子: 3391
注册时间: 2008-09-18 13:11
送出感谢: 1 次
接收感谢: 569 次

Re: 求个脚本或工具能合并ip地址段的脚本

#2

帖子 astolia » 2015-02-05 12:11

这不是一道标准的ACM竞赛题么,以前还在某个OJ系统上作过类似的
头像
pocoyo
论坛版主
帖子: 25878
注册时间: 2008-03-25 15:49
来自: 谁知道?
送出感谢: 5 次
接收感谢: 9 次
联系:

Re: 求个脚本或工具能合并ip地址段的脚本

#3

帖子 pocoyo » 2015-02-05 12:15

astolia 写了:这不是一道标准的ACM竞赛题么,以前还在某个OJ系统上作过类似的
不知道 工作里倒是有点用处 想看看有什么好方法合并一下方便减少acl的条目
头像
susbarbatus
帖子: 2966
注册时间: 2010-04-10 16:14
系统: Arch Linux
送出感谢: 6 次
接收感谢: 68 次

Re: 求个脚本或工具能合并ip地址段的脚本

#4

帖子 susbarbatus » 2015-02-05 13:34

aggregate
沉迷将棋中……
头像
Kandu
帖子: 108
注册时间: 2008-12-24 12:02
送出感谢: 1 次
接收感谢: 4 次
联系:

Re: 求个脚本或工具能合并ip地址段的脚本

#5

帖子 Kandu » 2015-02-05 15:44

ocaml 源码。依赖 batteries ocamlgraph lwt ok_monad ok_parsec
ocaml 和依赖可通过 opam 安装
后两个依赖尚未推送到 opam 软件库,可在我的 bitbucket 下载

代码: 全选

open Ok_parsec
open Parsec

let decimalToBinary dec=
  let rec decimalToBinary= function
    | 0-> []
    | n-> string_of_int (n mod 2) :: decimalToBinary (n / 2)
  in
  decimalToBinary dec |> List.rev |> String.concat ""

let binaryToDecimal bin=
  ("0b" ^ bin) |> int_of_string |> string_of_int

(* 将 subnet, 类型为 string * int 转换为字符串,用于输出 *)
let subnetToStr subnet=
  let (ip, mask)= subnet in
  let cleanUp ip=
    (String.sub ip 0 mask) ^ (String.make (32-mask) '0')
  in
  let ip= cleanUp ip in
  let sec1= String.sub ip 0 8
  and sec2= String.sub ip 8 8
  and sec3= String.sub ip 16 8
  and sec4= String.sub ip 24 8 in
  ([sec1; sec2; sec3; sec4]
    |> List.map binaryToDecimal
    |> String.concat ".")
  ^ "/"
  ^ string_of_int mask

(* 定义 ip地址各小段的 parser *)
let ipSec=
  many num_dec |>> BatString.of_list

(* 定义后面的 mask 位的 parser *)
let mask=
  many num_dec |>> BatString.of_list

(* 得到 ip 地址的值表示 *)
let ip ipSecS=
  let (sum, _)= List.fold_right
    (fun num (sum, shift)->
      (sum + (int_of_string num) lsl shift, shift+8))
    ipSecS
    (0, 0)
  in sum

(* 定义 subnet 的分析器 *)
let subnet=
  let%m ipSecS= sepBy (char '.') ipSec in
  char '/' >>
  let%m mask= mask |>> int_of_string in
  let ip= ip ipSecS |> decimalToBinary in
  let ip= String.make (32 - (String.length ip)) '0' ^ ip in
  return (ip, mask)

(* 从输入产生一份 subnet 的列表 *)
let subnets input=
  input
  |> BatIO.lines_of
  |> BatEnum.fold
    (fun content line-> line::content)
    []

(* 尝试合并两个网域 *)
let merge net1 net2=
  let rec merge net1 net2=
    let (ip1, mask1)= net1
    and (ip2, mask2)= net2 in
    if mask1 = mask2 then
      if String.sub ip1 0 mask1 <> String.sub ip2 0 mask1 then
        if String.sub ip1 0 (mask1-1) = String.sub ip2 0 (mask1-1)
        then merge (ip1, (mask1-1)) (ip2, (mask1-1))
        else None
      else Some net1
    else
      if String.sub ip1 0 mask1 = String.sub ip2 0 mask1
      then Some net1
      else None
  in
  let (ip1, mask1)= net1
  and (ip2, mask2)= net2 in
  if mask1 > mask2 then
    merge net2 net1
  else
    merge net1 net2

(* 合并一份列表里面的所有网域 *)
let rec mergeAll res nets=
  let mergeRes net=
    match res with
    | []-> None
    | res::_-> merge res net
  in
  match nets with
  | net::left->
    (match mergeRes net with
    | Some net-> mergeAll (net::List.tl res) left
    | None-> mergeAll (net::res) left)
  | []-> res

let main ()=
  let subnets= subnets BatIO.stdin in (* 从 stdin 输入,得到网域列表 *)
  let subnets=
    subnets
    |> List.map (parse_string subnet) (* 对列表里面的每个网域通过 subnet 语法分析器进行并发分析,得到 subnet list 结构,也就是  (string * int) list *)
    |> List.map (fun thread->              (* 检查分析是否有误 *)
        match Lwt.state thread with
        | Lwt.Return Parsec.Ok (r, _)->r
        | _-> failwith "parse_error")
    |> List.rev
  in
  mergeAll [] subnets                       (* 无误就开始合并作业 *)
    |> mergeAll []
    |> List.map subnetToStr             (* 然后将列表里的每个 subnet 转换为字符串 *)
    |> List.iter print_endline             (* 并输出到标准输出 *)

let ()= main ()
上次由 Kandu 在 2015-08-05 12:40,总共编辑 1 次。
这些用户感谢了作者 Kandu 于这个帖子:
pocoyo (2015-02-05 18:48)
评价: 3.7%
头像
Kandu
帖子: 108
注册时间: 2008-12-24 12:02
送出感谢: 1 次
接收感谢: 4 次
联系:

Re: 求个脚本或工具能合并ip地址段的脚本

#6

帖子 Kandu » 2015-02-05 20:02

上傳了一個可執行檔的壓縮檔
ipMerge.bz2
(943.97 KiB) 下载 183 次
。讀寫 stdin, stdout. 利用重定向應該夠用。

以上寫法僅能處理非常好地排序好的網域條目。
若需要處理任意排列的網域條目的話,要稍作修改。
头像
pocoyo
论坛版主
帖子: 25878
注册时间: 2008-03-25 15:49
来自: 谁知道?
送出感谢: 5 次
接收感谢: 9 次
联系:

Re: 求个脚本或工具能合并ip地址段的脚本

#7

帖子 pocoyo » 2015-02-05 20:07

Kandu, 多谢 不明白这个语言看不懂得算法 其实本来是在路由器上以输出自动聚合路由的话是最省事的 但是还是不很熟悉路由命令 不知道这个合并算法到底该怎么理解

搜到下面的perl 脚本 可以使用 同样不明白原理 :em06

http://www.perlmonks.org/?node_id=118346
http://www.perlmonks.org/?node_id=118596

代码: 全选

#!/usr/bin/perl -w
use strict;
$|++;

use Socket qw(inet_aton inet_ntoa);

sub cidr2bits {
  my $cidr = shift;
  my ($addr, $maskbits) = $cidr =~ /^([\d.]+)\/(\d+)$/
    or die "bad format for cidr: $cidr";
  
  substr(unpack("B*", inet_aton($addr)), 0, $maskbits);
}

sub bits2cidr {
  my $bits = shift;
  
  inet_ntoa(pack "B*",
            substr("${bits}00000000000000000000000000000000", 0, 32))
    . "/" . length($bits);
}

sub mergecidr {
  local $_ = join "", sort map { cidr2bits($_)."\n" } @_;
  1 while s/^(\d+)0\n\1[1]\n/$1\n/m or s/^(\d+)\n\1\d+\n/$1\n/m;
  map bits2cidr($_), split /\n/;
}

my @first = qw(
               209.152.214.112/30
               209.152.214.116/31
               209.152.214.118/31
              );

my @second = qw(
                209.152.214.112/30
                209.152.214.116/32
                209.152.214.118/31
               );

my @third = qw(
               209.152.214.112/31
               209.152.214.116/31
               209.152.214.118/31
              );

if (1) {

  print join "----\n", map
    join("",
         "from:\n", map("  $_\n", @$_),
         "to:\n", map("  $_\n", mergecidr(@$_))),
           \@first, \@second, \@third;

}
头像
Kandu
帖子: 108
注册时间: 2008-12-24 12:02
送出感谢: 1 次
接收感谢: 4 次
联系:

Re: 求个脚本或工具能合并ip地址段的脚本

#8

帖子 Kandu » 2015-02-05 20:37

忘了說依賴 libev4, apt-get install libev4 了才能用。因爲 ok_parsec 本來是用來做併發解析用的。

先轉成二進制就很好分析了。
原理就是,若兩個網域 mask 相同,僅僅最後的有效位不同的話,說明這兩個網域合起來覆蓋了 mask-1 的更大網域,可以合併。返回任一網域最後有效位置0,mask-1的網域即可。
若兩網域不同, mask 小的那個也就是大網域,若大網域覆蓋小網域,也能合併。直接返回大網域。
头像
astolia
论坛版主
帖子: 3391
注册时间: 2008-09-18 13:11
送出感谢: 1 次
接收感谢: 569 次

Re: 求个脚本或工具能合并ip地址段的脚本

#9

帖子 astolia » 2015-02-05 20:40

就是位运算呗。源里的aggregate的C源代码总看得懂了吧
头像
Kandu
帖子: 108
注册时间: 2008-12-24 12:02
送出感谢: 1 次
接收感谢: 4 次
联系:

Re: 求个脚本或工具能合并ip地址段的脚本

#10

帖子 Kandu » 2015-02-05 20:46

aggregate 真是好用。贊樓上。
头像
pocoyo
论坛版主
帖子: 25878
注册时间: 2008-03-25 15:49
来自: 谁知道?
送出感谢: 5 次
接收感谢: 9 次
联系:

Re: 求个脚本或工具能合并ip地址段的脚本

#11

帖子 pocoyo » 2015-02-05 21:47

:em20 你们都是人才 我还以为 4#说的是路由器上的命令 原来linux有这工具 相当省事 :em11
feifeifeifei521
帖子: 1
注册时间: 2017-10-31 23:15
送出感谢: 0
接收感谢: 0

Re: [已解决]求个脚本或工具能合并ip地址段的脚本

#12

帖子 feifeifeifei521 » 2017-10-31 23:20

请问楼主,如何解决的,求解。 拜谢。 :Cry
yangdianqiang
帖子: 5
注册时间: 2008-04-17 10:22
送出感谢: 0
接收感谢: 0

Re: [已解决]求个脚本或工具能合并ip地址段的脚本

#13

帖子 yangdianqiang » 2018-05-04 16:15

perl脚本不错,1000+行的路由条目经过两次合并变为100+行了,牛!
回复

回到 “Shell脚本”