当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 13 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : [已解决]求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 11:53 
头像

注册: 2008-03-25 15:49
帖子: 25878
地址: 谁知道?
送出感谢: 8
接收感谢: 10
原始数据如下:
代码:
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


页首
 用户资料  
 
2 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 12:11 
头像

注册: 2008-09-18 13:11
帖子: 2951
送出感谢: 1
接收感谢: 495
这不是一道标准的ACM竞赛题么,以前还在某个OJ系统上作过类似的


页首
 用户资料  
 
3 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 12:15 
头像

注册: 2008-03-25 15:49
帖子: 25878
地址: 谁知道?
送出感谢: 8
接收感谢: 10
astolia 写道:
这不是一道标准的ACM竞赛题么,以前还在某个OJ系统上作过类似的

不知道 工作里倒是有点用处 想看看有什么好方法合并一下方便减少acl的条目


页首
 用户资料  
 
4 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 13:34 
头像

注册: 2010-04-10 16:14
帖子: 2957
系统: Arch Linux
送出感谢: 8
接收感谢: 76
aggregate


_________________
沉迷将棋中……


页首
 用户资料  
 
5 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 15:44 
头像

注册: 2008-12-24 12:02
帖子: 108
送出感谢: 1
接收感谢: 4
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 次


_________________
评价: 3.7% pocoyo
 
页首
 用户资料  
 
6 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 20:02 
头像

注册: 2008-12-24 12:02
帖子: 108
送出感谢: 1
接收感谢: 4
上傳了一個可執行檔的壓縮檔
附件:
ipMerge.bz2 [943.97 KiB]
被下载 160 次
。讀寫 stdin, stdout. 利用重定向應該夠用。

以上寫法僅能處理非常好地排序好的網域條目。
若需要處理任意排列的網域條目的話,要稍作修改。


_________________
機器生命


页首
 用户资料  
 
7 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 20:07 
头像

注册: 2008-03-25 15:49
帖子: 25878
地址: 谁知道?
送出感谢: 8
接收感谢: 10
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;

}


页首
 用户资料  
 
8 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 20:37 
头像

注册: 2008-12-24 12:02
帖子: 108
送出感谢: 1
接收感谢: 4
忘了說依賴 libev4, apt-get install libev4 了才能用。因爲 ok_parsec 本來是用來做併發解析用的。

先轉成二進制就很好分析了。
原理就是,若兩個網域 mask 相同,僅僅最後的有效位不同的話,說明這兩個網域合起來覆蓋了 mask-1 的更大網域,可以合併。返回任一網域最後有效位置0,mask-1的網域即可。
若兩網域不同, mask 小的那個也就是大網域,若大網域覆蓋小網域,也能合併。直接返回大網域。


_________________
機器生命


页首
 用户资料  
 
9 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 20:40 
头像

注册: 2008-09-18 13:11
帖子: 2951
送出感谢: 1
接收感谢: 495
就是位运算呗。源里的aggregate的C源代码总看得懂了吧


页首
 用户资料  
 
10 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 20:46 
头像

注册: 2008-12-24 12:02
帖子: 108
送出感谢: 1
接收感谢: 4
aggregate 真是好用。贊樓上。


_________________
機器生命


页首
 用户资料  
 
11 楼 
 文章标题 : Re: 求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2015-02-05 21:47 
头像

注册: 2008-03-25 15:49
帖子: 25878
地址: 谁知道?
送出感谢: 8
接收感谢: 10
:em20 你们都是人才 我还以为 4#说的是路由器上的命令 原来linux有这工具 相当省事 :em11


页首
 用户资料  
 
12 楼 
 文章标题 : Re: [已解决]求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2017-10-31 23:20 

注册: 2017-10-31 23:15
帖子: 1
送出感谢: 0 次
接收感谢: 0 次
请问楼主,如何解决的,求解。 拜谢。 :Cry


页首
 用户资料  
 
13 楼 
 文章标题 : Re: [已解决]求个脚本或工具能合并ip地址段的脚本
帖子发表于 : 2018-05-04 16:15 

注册: 2008-04-17 10:22
帖子: 5
送出感谢: 0 次
接收感谢: 0 次
perl脚本不错,1000+行的路由条目经过两次合并变为100+行了,牛!


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 13 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 3 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译