跳转至

无先验知识的GIS数据抓取算法研究

1 问题背景

ArcGIS Server将GIS空间库中的数据可以以服务的方式发布出来,服务中提供了查询接口,可以将关心的字段等内容返回给我们,也可以选择将所有的数据返回回来。其中有一个小问题:服务端默认是返回查询记录的1000条记录。在默认情况下,如果查询记录大于1000,那么就会丢失剩余的查询数据,通常有两种解决办法:

  1. 修改服务端的默认返回值,可以修改为大于1000的数据,如2000、2500…..
  2. 设计一个简单的算法,分段进行检索,因为返回结果中的编号ID通常是从1开始,在查询条件中设置为ID每1000会返回一次,这样就可以一个不剩的获取所有数据

ArcGIS Server抓取服务查询

ArcGIS Server查询返回结果1

ArcGIS Server查询返回结果2

但是,本文遇到的问题要复杂的多,采用上面两种方法都无法解决,概括起来主要是对待抓取的数据中的ID没有先验知识,这种没有先验知识表现在:

  1. ID不是从0开始编号
  2. 返回结果的个数(即ID个数)远大于1000,服务端无法事先指定(指定太多可能导致返回超时)
  3. 不知返回结果中ID的起止,相邻ID也可能不是连续,例如:4, 7, 15, 29, 765 …
  4. 返回结果的ID分布也不清楚,有可能(2000, 5000)比(6000, 10000)分布的数据更多

正是上面条件的限制,给数据的批量抓取带来了新的问题和挑战。

2 解决思路

问题的解决应该分为两步:

  1. 第一步:通过探查法获取ID的大致范围,这个探查不需要获取准确范围,同时探测时只关心ID的字段,其他字段不必关心(这样可以减小请求次数,以及请求的内容大小,从而减少处理时间)
  2. 第二步:精确获取所有的目标结果,此时不能遗漏结果,以及各个字段的值

3 算法1:获取ID大致范围

算法的思路用一句话概括起来:跨数量级,两边逼近。 我们的目标是获得最小ID和最大ID所在的数量级,前面提到的“大致范围”就体现在这里的“所在的数量级”上,之所有采用跨数量级是因为第一步只是初步获取一个范围,时间是放在第一位的,没有必要非要提取出准确的最大最小ID值(与其将时间花费在求取准确的最大最小ID上还不如花费在后面的准确抓取上)。 两边逼近说的是最小ID从个位数开始往大的方向茶皂,最大ID从一个足够大的数(例如1亿、10亿)往小的方向查找。 查找过程中需要注意如何判断是否找到最大最小ID值。废话不多说,看下面代码:

   def estimate_interval(self):
        #  估计id最大最小值所在区间
        self.estimate_lower()
        self.estimate_upper()

        if self.LOWER >= self.UPPER:
            return [False, 'self.LOWER >= self.UPPER']
        else:
            # 区间入栈
            self.interval_stack.push([self.LOWER, self.UPPER])
            return [True, 'Succeed']


    def estimate_upper(self):
        # 确定最大id所在数量级
        upper = self.iter_estimate_upper(self.MAX_VALUE)
        self.UPPER = upper


    def iter_estimate_upper(self, max_value):
        # 迭代确定最大id所在数量级
        feature_num = self.stat_feature_num(max_value/10, max_value)
        if feature_num > 0:
            return max_value-1
        else:
            return self.iter_estimate_upper(max_value/10)


    def estimate_lower(self):
        # 确定最小id所在数量级
        lower = self.iter_estimate_lower(1)
        self.LOWER = lower


    def iter_estimate_lower(self, min_value):
        # 迭代确定最小id所在数量级
        feature_num = self.stat_feature_num(min_value, min_value * 10)
        if feature_num > 0:
            return min_value
        else:
            return self.iter_estimate_lower(min_value * 10)

4 算法2:精确抓取所有数据

精确抓时,采用了二分法,用stack存取所有区间,以及递归调用,代码如下:

def fetch_features(self):

        if self.interval_stack.size() < 1:
            return

        # 分批抓取features
        [id_lower, id_upper] = self.interval_stack.pop()
        print '** fetch_features() [id_lower, id_upper]=[', id_lower, ', ', id_upper, '], size=', self.interval_stack.size()  

        if id_upper - id_lower <= self.batch_size:
            # 直接查找、抓取入库
            self.fetch_export_toGdb(id_lower, id_upper)
            self.fetch_features() # 继续迭代
        else:
            # 探查[lower, upper)对应的feature个数
            feature_num = self.stat_feature_num(id_lower, id_upper)
            if feature_num < self.batch_size:
                # 直接查找、抓取入库
                self.fetch_export_toGdb(id_lower, id_upper)
                self.fetch_features() # 继续迭代
            else:
                # 折半探查
                id_middle = (int)(id_lower + id_upper)/2
                self.interval_stack.push([id_middle, id_upper])
                self.interval_stack.push([id_lower, id_middle])
                self.fetch_features() # 继续迭代

5 爬取结果

爬取了接近6万条记录的所有字段值

6 算法改进方向

  • 算法1:在坚持“只获取大致范围”和“时间花费尽量小”的原则上,尽可能的精确范围,毕竟精确一点还是好的;
  • 算法2:原算法中采用stack存取每一步的搜索区间这个想法是不错的,但二分发的思路可以改进一下,其实“算法1的跨数量级搜索”也是受了二分法思路的影响【二分法只是一个思路,而不是一个公式】。