首页 > 代码库 > 【数据结构】Trie树的应用:查询IP地址的ISP(Java实现)

【数据结构】Trie树的应用:查询IP地址的ISP(Java实现)

查询IP地址的ISP

给定一个IP地址,如何查询其所属的ISP,如:中国移动(ChinaMobile),中国电信(ChinaTelecom),中国铁通(ChinaTietong)?

  • 现在网上有ISP的IP地址区段可供下载,比如中国移动的IP地址段

    103.20.112.0/22
    103.21.176.0/22
    111.0.0.0/10
    112.0.0.0/10
    117.128.0.0/10
    120.192.0.0/10
    183.192.0.0/10
    211.103.0.0/17
    211.136.0.0/14
    211.140.0.0/15
    211.142.0.0/17
    211.142.128.0/17
    211.143.0.0/16
    218.200.0.0/14
    218.204.0.0/15
    218.206.0.0/15
    221.130.0.0/15
    221.176.0.0/13
    223.112.0.0/14
    223.116.0.0/15
    223.120.0.0/13
    223.64.0.0/11
    223.96.0.0/12
    36.128.0.0/10
    39.128.0.0/10

    上述网络地址是CIDR记法:IP地址/网络id位数,其中IP地址分为两部分

    • 网络id
    • 主机id

    比如,192.168.23.35/21,其子网掩码为11111111 11111111 11111000 00000000即255.255.248.0,网络ID:192.168.00010111

  • ip地址103.20.112.168,发现与103.20.112.0/22前22位相匹配,则此IP地址属于中国移动


Trie树实现查询

Trie树使用公共前缀,降低查询时间,减小了存储空间。为了构建Trie树,将IP地址二进制化,这样Trie树变成了一棵二叉树,左孩子节点为0,右孩子节点为1。叶子节点存储IP地址所对应的ISP。

Trie树的Java实现

/*
 * Trie树,用于存储、检索ip地址
 * 叶子节点标记为ip地址对应的ISP
 */
public class TrieTree {
     private Node root = null;   //根节点

    /*二叉树的节点*/
    private static class Node {
        String element;  //非叶子节点为空 叶子节点标记为ISP
        Node[] children; //左孩子节点为0 右孩子节点为1

        public Node() {
            element = "";
            children = new Node[2];
            for (int i = 0; i < children.length; i++) {
                children[i] = null;
            }
        }
    }

    public TrieTree() {
        root = new Node();
    }   

    /*插入ip地址*/
    public void insert(Node root, String ipAddress, String isp) {
        if(ipAddress.length() > 32) {
            System.out.println("ip地址处理错误");
        } else {
            Node crawl = root;
            for(int i=0; i<ipAddress.length(); i++) {
                int index = (int) ipAddress.charAt(i) - ‘0‘;
                if(crawl.children[index] == null) {
                    crawl.children[index] = new Node();
                }
                crawl = crawl.children[index];              
            }
            crawl.element = isp;
        }
    }

    public void insert(String ipAddress, String isp) {
        insert(root, ipAddress, isp);
    }

    /*
     * 检索ip地址,返回其所对应的ISP
     * 若不在Trie树中,则返回null
     * */
    public String search(String binaryIP) {
        Node crawl = root;
        for(int i = 0; crawl.element.length() == 0; i++) {
            int index = (int) binaryIP.charAt(i) - ‘0‘;
            if(crawl.children[index] == null) {
                return null;
            }
            crawl = crawl.children[index];
        }
        return crawl.element;
    }
}

IP地址格式化

下面的class给出两个方法,实现

  • 将IP地址转变成二进制
  • 从CIDR记法的IP地址中得到网络ID部分
/*
 * IP地址CIDR记法:network.host/size
 * 比如:103.20.112.0/22
 * 功能:将IP地址转换成其network地址
 */

public class IPFormat {
    /*将ip地址转换成32位的二进制*/
    public static String toBinaryNumber(String ipAddress) {
        String[] octetArray = ipAddress.split("\\.");
        String binaryNumber = "";
        for(String str: octetArray) {
            int octet = Integer.parseInt(str, 10);
            String binaryOctet = Integer.toBinaryString(octet);
            int bolength = binaryOctet.length();
            if(bolength < 8) {
                for (int i = 0; i < 8 - bolength; i++) {
                    binaryOctet = ‘0‘ + binaryOctet;            //补前导0
                }
            }
            binaryNumber += (binaryOctet);
        }
        return binaryNumber;
    }

    /*获取network地址部分*/
    public static String getNetworkAddress(String cidrAddress) {
        String[] cidrArray = cidrAddress.split("/");
        String binaryNumber = toBinaryNumber(cidrArray[0]);
        int size = Integer.parseInt(cidrArray[1]);
        return binaryNumber.substring(0, size);
    }

    /*main方法用于测试*/
    public static void main(String[] args) {
        String ip = "103.20.112.0/20";
        String bn = getNetworkAddress(ip);
        System.out.println(bn);
    }
}