五种算法实现IP到地址的转换

条件:

给出一个文件,其中每行一个IP段(IPv4,其实IPv6类似,只是规模剧增)及其对应的信息(例如物理地址信息),内容及格式为:

<start_IP> <end_IP> <country> <province/state> <city> <other_info>

内容说明:

1. <start_IP> <end_IP>都为包含状态,即[<start_IP>, <end_IP>]

2. 各IP段不重合

3. IP段有空洞,即有些IP不能找到对应段

问题:

给出一个IP,请实现算法返回其对应的<country> <province/state> <city> <other_info>等信息

算法一:

扩展每个IP段,构造每个IP与其对应<country> <province/state> <city> <other_info>信息的结构,以IP作key读入内存

优点:简单易实现

缺点:占用内容过大

算法二:

扩展每个IP段,构造每个IP与其对应<country> <province/state> <city> <other_info>信息的数据,以IP作key写入数据库

优点:简单易实现

缺点:需要额外的数据库服务,使用频繁时性能不高

算法三:

近似查找。此方法有两个关键点:

1. 查找过程中需要比较IP的大小,因此需要实现IP的比较。也有两种实现:1) 实现一个IP的比较器 2) 把IP转换为数字:IP看作是一个4位的数字,每位之间进制256,例如10.13.183.72=10 * 256^3 + 13 * 256^2 + 183 * 256^1 + 72 * 256 ^0,这样需把给定的IP和每一段IP的<start_IP>, <end_IP>都做相同转换,便于比较

代码:

long num = 16777216L * Long.parseLong(ips[0]) + 65536L
* Long.parseLong(ips[1]) + 256 * Long.parseLong(ips[2])
+ Long.parseLong(ips[3]); return num;

或更快速的移位实现:

long num = 0;
for (int i = 0; i < ips.length; i++) {
num += Long.parseLong(ips[i]) << (8 * (ips.length - 1 - i));
}
return num;

2. 查找算法需要改进,因为是查找一个值所属的范围,并非直接命中式的查找。以折半查找为例,改造如下:

1) 将IP段的<start_IP>转换为数字,构造查询有序数组A。以每段的<end_IP>构造另一个备查数组B,同一段的<start_IP> <end_IP>在各自数组中索引一致。

2) 命中算法改为近似算法,更精确的叫作向下最近算法,基于数组A执行折半查找

3) 以A中的索引位查找数组B,确认目标IP在对应段中。防止误查本应在空洞段中的IP

    #数组A
private List<Long> startIPNOsList = new ArrayList<Long>();
#数组B
private List<Long> endIPNOsList = new ArrayList<Long>();
#对应信息数组C
private List<Address> addressList = new ArrayList<Address>(); //...构造上述数组 /**
* 实现查找
*/
public Address detect(String ip) {
long ipNO = IPv4Util.convertIP2Long(ip); if (ipNO > 0) {
int idx = containBinSearch(ipNO, 0, startIPNOsList.size() - 1);
if (idx > 0 && ipNO <= endIPNOsList.get(idx)) {
return addressList.get(idx);
}
}
short zero = 0;
return new Address(zero, zero, zero);
} /**
* 如果arr[i] <= target && arr[i + 1] > target,则返回i
* @param target 查找目标
* @param low
* @param high
* @return
*/
private int containBinSearch(long target, int low, int high) {
//表示没查到
if (high < low) {
return -1;
} int mid = (low + high) / 2;
if (mid == startIPNOsList.size() - 1) {
return mid;
} if (startIPNOsList.get(mid) > target) {
return containBinSearch(target, low, mid - 1);
} else if (startIPNOsList.get(mid + 1) <= target) {
return containBinSearch(target, mid + 1, high);
} else {
return mid;
}
}

优点:占用内存小,查询速度不错

缺点:实现稍复杂

算法四:

Trie树实现。

“Trie树即字典树。

又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
它有3个基本性质:
根节点不包含字符,除根节点外每一个节点都只包含一个字符; 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 每个节点的所有子节点包含的字符都不相同。” -- 详见 字典树

具体实现:扩展每个IP段,将每个IP加入Trie树。每个ip位构造一个节点,每个叶子节点包含<country> <province/state> <city> <other_info>等信息,最后构造一个5层的trie树。
优点:查询速度快,实现较简单
缺点:占用内存超大

算法五:
近似trie树查找。基本结构与算法四相同,查找算法需改进,构造树时需在叶节点中包含<end_ip>。
实现:
对于IP第1-4位,分别在trie树第2-5层节点应用如下逻辑
  1 查找当前层中最大的不大于当前位的节点
     a) 如果当前节点是叶节点,验证目标IP是否大于<end_ip>:大于返回空,否则返回对应<country>等信息
     b) 如果查找到的节点值等于当前位的值,向下一层重复此逻辑
     c) 如果查找到的节点值小于当前位的值,返回本节点最大值的叶节点
  2 如果查找不到,本节点的父节点值 -1,本节点及其各子节点置为255,返回上一层重复此逻辑

优点:速度快,较算法4占内存小
确定:查找算法复杂,内存占用仍旧很大

上一篇:HTML5 应用程序缓存


下一篇:matlab函数int2str, num2str, str2num