在IP中将IP合并到范围中

Question

假设我有一个可能重叠或不重叠的IP范围列表(仅限上一个术语):

('1.1.1.1-7', '2.2.2.2-10', '3.3.3.3-3.3.3.3', '1.1.1.4-25', '2.2.2.4-6')

我正在寻找一种方法来识别任何重叠范围并将它们合并为单个范围.

('1.1.1.1-25', '2.2.2.2-10', '3.3.3.3-3')

当前的算法思想是将所有范围扩展为所有IP的列表,消除重复,排序和合并任何连续的IP.

还有更多python-esque算法的建议吗？

Answer 1

这是我的版本,作为一个模块.我的算法与他的答案中提到的一个lunixbochs相同,并且从范围字符串到整数和后面的转换很好地模块化.

import socket, struct

def ip2long(ip):
    packed = socket.inet_aton(ip)
    return struct.unpack("!L", packed)[0]

def long2ip(n):
    unpacked = struct.pack('!L', n)
    return socket.inet_ntoa(unpacked)

def expandrange(rng):
    # expand '1.1.1.1-7' to ['1.1.1.1', '1.1.1.7']
    start, end = [ip.split('.') for ip in rng.split('-')]
    return map('.'.join, (start, start[:len(start) - len(end)] + end))

def compressrange((start, end)):
    # compress ['1.1.1.1', '1.1.1.7'] to '1.1.1.1-7'
    start, end = start.split('.'), end.split('.')
    return '-'.join(map('.'.join,
          (start, end[next((i for i in range(4) if start[i] != end[i]), 3):])))

def strings_to_ints(ranges):
    # turn range strings into list of lists of ints
    return [map(ip2long, rng) for rng in map(expandrange, ranges)]

def ints_to_strings(ranges):
    # turn lists of lists of ints into range strings
    return [compressrange(map(long2ip, rng)) for rng in ranges]

def consolodate(ranges):
    # join overlapping ranges in a sorted iterable
    iranges = iter(ranges)
    startmin, startmax = next(iranges)
    for endmin, endmax in iranges:
        # leave out the '+ 1' if you want to join overlapping ranges
        # but not consecutive ranges.
        if endmin <= (startmax + 1):
            startmax = max(startmax, endmax)
        else:
            yield startmin, startmax
            startmin, startmax = endmin, endmax
    yield startmin, startmax

def convert_consolodate(ranges):
    # convert a list of possibly overlapping ip range strings
    # to a sorted, consolodated list of non-overlapping ip range strings
    return list(ints_to_strings(consolodate(sorted(strings_to_ints(ranges)))))

if __name__ == '__main__':
    ranges = ('1.1.1.1-7',
              '2.2.2.2-10',
              '3.3.3.3-3.3.3.3',
              '1.1.1.4-25',
              '2.2.2.4-6')
    print convert_consolodate(ranges)
    # prints ['1.1.1.1-25', '2.2.2.2-10', '3.3.3.3-3']