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

sh/bash/dash/ksh/zsh等Shell脚本
回复
头像
astolia
论坛版主
帖子: 6396
注册时间: 2008-09-18 13:11

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

#1

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

这不是一道标准的ACM竞赛题么,以前还在某个OJ系统上作过类似的
头像
susbarbatus
帖子: 2966
注册时间: 2010-04-10 16:14
系统: Arch Linux

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

#2

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

aggregate
沉迷将棋中……
头像
Kandu
帖子: 108
注册时间: 2008-12-24 12:02
联系:

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

#3

帖子 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
帖子: 108
注册时间: 2008-12-24 12:02
联系:

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

#4

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

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

以上寫法僅能處理非常好地排序好的網域條目。
若需要處理任意排列的網域條目的話,要稍作修改。
头像
Kandu
帖子: 108
注册时间: 2008-12-24 12:02
联系:

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

#5

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

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

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

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

#6

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

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

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

#7

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

aggregate 真是好用。贊樓上。
feifeifeifei521
帖子: 1
注册时间: 2017-10-31 23:15

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

#8

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

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

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

#9

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

perl脚本不错,1000+行的路由条目经过两次合并变为100+行了,牛!
efsp
帖子: 1
注册时间: 2019-05-14 9:07
系统: ubuntu

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

#10

帖子 efsp » 2019-05-14 9:13

aggregate 这个工具具体在哪呢? :Aadterboom 大神们指导下
头像
astolia
论坛版主
帖子: 6396
注册时间: 2008-09-18 13:11

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

#11

帖子 astolia » 2019-05-14 12:39

efsp 写了: 2019-05-14 9:13 aggregate 这个工具具体在哪呢? :Aadterboom 大神们指导下
sudo apt install aggregate
回复