内蒙古java团队

j2se,j2ee开发组
posts - 139, comments - 212, trackbacks - 0, articles - 65
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

标签

排序 链树 GIS POI 关键字 搜索算法

概念阐述

链树及其相关概念

本来,数据结构教科书中,不存在一种叫做“链树”的数据结构,用Goolge也搜索不到。这种数据结构,是为了在GIS系统中进行POI关键字高速搜索,在n叉树的基础上,改进的一种数据结构,为了论述方便,姑且称之为链树。
链树,就是在n叉树的基础上,给每个树节点(包括树根和叶子),都挂接上一个链表而形成的数据结构。
下图就表示一棵典型的链树

图1

链树的2个显著特点是:
   1. 某树节点所挂接的链表元素,为该树节点的所有子孙节点(如果有)所挂接的链表元素之集合(无重复节点)。
   2. 链树的根结点,可以是一个虚拟节点,代表系统中所有实体节点的祖先。这样,就不必要形成链树森林了。图1的根结点就是一个虚拟节点,其余节点都为实体节点。 

排序链树搜索算法

该算法是指,根据关键字序列,从链树根结点出发,在链树中路由,最终找到一个链树路径和关键字序列最大匹配的树节点,然后取其挂接链表的算法。
以图1所示之排序链树为例,假定每个树节点的关键字即为其上的标签字符,假如我们需要搜索的关键字序列为“ACI”,那么该算法的执行顺序为:
1.从根结点出发,查找关键字为‘A’的树节点。
根节点Root下有2个孩子,分别为‘A’和‘X’,因为排序链树节点的所有孩子都按一定规则排序,所以这一步可以使用二分查找来进行,假定Root有n个孩子,那么这一步所花时间为lgn.
2.在‘A’的所有孩子中查找关键字为‘C’的孩子。
同样用二分查找,假定‘A’有m个孩子,那么这一步所花时间为lgm。
3.在‘C’的所有孩子中查找关键字为‘I’的孩子。
同样使用二分查找,假定‘C’有p个孩子,那么这一步所花时间为lgp
综上,关键字序列为“ACI”的搜索时间为lgn+lgm+lgp。
根据链树的特点,有n>=k>=p,所以搜索长度为3的关键字序列的时间复杂度为O(3lgn),推而广之,我们得到更一般的排序链树搜索算法复杂度:
假如关键字序列长度为k,系统中总的实体节点个数为n,那么在排序链树搜索算法的时间复杂度为O(klgn)。

关于POI

在GIS系统中,对于地图上的一个具有详细信息的点,我们称之为POI(Point Of Interest)。比如名称为“北京西单图书大厦”的POI,就包含了该地点的一系列详细信息,这些信息通常有:
   1.该POI的名称,这里是“西单图书大厦”
   2.该POI的经纬度
   3.该POI的地址
   4.该POI的类型
   5.该POI的描述信息
   6.该POI的电话号码
   7.该POI的网址
   8.该POI的照片
   9.该POI的音频,视频
   …...
通常,一个城市中,就存在千百万个这样的POI。其数据量是相当的巨大。

关于POI的关键字搜索

在GIS相关应用中,都会提供一种最基本的功能,就是根据用户输入的关键字,搜索到和该关键字相关的一系列POI,按照和用户输入字串匹配度由高到底的顺序,把这些POI呈现给用户。因为用户输入的关键字,可能和该POI的名称相关,也可能和该POI的地址,类型名称,描述信息,网址等字段相关。理论上,只要POI的某个字段,或者某几个字段的组合,和用户输入的关键字有关系,那么,这个POI就应该出现在搜索结果列表的合适位置上。
比如用户输入的关键字为“北大”,那么搜索出来的POI可能有:
  北大荒(名字中包含’北’,‘大’,且这2个字连在一起)
  北京大学(名字中包含’北’,‘大’,这2个关键字被隔开了,称之为跳字)
  北京邮电大学(名字中包含’北’,‘大’,跳字)
  大北窑(名字中包含‘北’,‘大’,但这2个关键字被颠倒了,称之为逆字)
  未名湖(地址中含有‘北‘,‘大’二字)
  ……
当然按照我们一般的思路,北京大学应该排在第一位,因为一般来说,北大指的就是它。所以GIS系统要求在本次搜索中,北京大学应该排在第一位。
为了简化问题,本文只限于对POI的名称这一字段进行关键字搜索。也就是说,只把名称字段和用户输入字串有关联的POI搜索出来。

如何在POI关键字搜索中应用链树搜索算法

如何在POI关键字搜索应用链树呢,我们举例来说。假定某城市中存在5个POI,其名称分别是:
  北京大学
  北京邮电大学
  大北窑
  未名湖
  北大荒
那么我们首先要做的工作就是建立排序链树,然后再依据排序链树,进行关键字搜索。

建立排序链树

建立排序链树的工作分成以下几步来做。
  1.分别给每个POI编号,指定其ID,如下
       北京大学(1)
       北京邮电大学(2)
       大北窑(3)
       未名湖(4)
       北大荒(5)
每个POI的详细信息,可以存在一个二进制文件(raw data)中,然后再建立一个索引文件,该文件包括5个索引条目,每个条目为一个POI在raw data文件中的偏移量(offset)与长度(size),该POI的索引条目序号(index),即为该POI的ID,这样,根据该POI的ID,查询索引文件,可以得到其在raw data中的offset和size,进而获取其详细信息。
  2.建立一个虚拟节点Root,作为排序链树之根,把所有POI的ID链表挂接在Root上,这些ID按以空字符为关键字进行POI查询的呈现结果为序。

图2

可以看到,如果以空字符进行POI关键字查询,输出结果顺序为
      北大荒
      北京大学
      北京邮电大学
      大北窑
      未名湖
很明显,这是按拼音排序的。
  3.找出该城市所有POI名称中涉及到的字符集合。
在我们的例子中,这个集合包括为:{‘北’,‘大’,‘荒’,‘京’,‘学’,‘邮’,‘电’,‘窑’,‘未’,‘名’,‘湖’},共11个汉字。把该集合中的元素按字符的UNICODE编码大小排序,我们姑且假定排序后的顺序不变。
  4.把字符集合中的每一个字符都作为一个树节点之关键字,并且让该树节点成为Root之子。如下图

图3

接下来,我们要以每个孩子为根,建立一颗子链树,为了论述方便,本文只讲述以‘北’字为树根的这棵子链树,其他子链树,可以依此类推。
  5.对于图3中每个子节点,挂接上一个ID链表,这些ID所代表的POI的名称中,都包含了该树节点所对应的字符。而且这些ID按照以该字符为关键字进行POI查询的呈现结果顺序为序。例如‘北’字形成的链表如下:

图4

之所以挂接链表是5,1,2,3,是因为我们在以‘北’字进行POI关键字查询时,GIS系统要求我们的输出POI的列表顺序必须是:北大荒,北京大学,北京邮电大学,大北窑这个顺序。

  6.对于每一个根节点,构建其子节点列表。构建规则为
   a.子节点所代表字符,能和其父节点所代表字符,出现在同一个POI的名称中。
   b.子节点列表,按其所代表字符的UNICODE大小排序。
比如‘北’字,其子节点列表为:

图5

在这里,我们假定这几个字的UNICODE排序结果如上图所示。 
大家可以看到,11个字符中,基本上所有字符都能和‘北’字组合,除了‘未’,‘名’,‘湖’这3个字符和‘北’字本身,当然,如果有个POI叫“北北 ”,那么‘北’字也会成为其本身的子节点。但是有一点是,父子节点的关键字可以相同,但是兄弟节点的关键字绝对不相同,他们是互斥的.
  7.结合父节点和每个子节点,形成每个子节点所挂接的ID链表。构建规则为:
  该ID链表所代表的POI列表,即为用户以链树路径作为关键字,查询出来的POI结果列表。
比如对于根为‘北’字的链树,到这一步的结果为:

图6

大家可以看到,对于路径“北大”,所挂接的ID链表为1,5,2,3,也就是
        北京大学
        北大荒
        北京邮电大学
        大北窑
这个顺序,也就是GIS系统所要求的输出顺序。
  8.按照以上规律,继续为第二层节点添加子节点。形成的高度为3的链树如下图所示

图7

从上图可以看到,颜色为红色的链树节点已经到达叶子,无法再向下伸展了。 
  9.依此类推,还可以继续向下扩展链树。最终的链树深度为6,对应着名称最长的POI节点,也就是“北京邮电大学”,由于篇幅所限,就不再给出图示了。
至此,我们的排序链树已经建好了。关于链树的建立,还有几个地方要说明一下:
    a.关于ID链表的排序
ID链表的顺序,需要我们的POI数据处理程序按照一定的规则来实现,除了通用的一些规则外,还有些特定的简称数据要处理,比如“北大”所对应的POI列表,第一条通常应该是“北京大学”,而不是“北大荒”。  
    b.关于排序链树的存储
为了加快搜索速度,排序链树森林中的冗余数据很多,所以实现者应该认真考虑文件存储格式,以便节约存储空间。 

根据排序链树,按关键字搜索POI

建立了排序链树之后,我们就可以按排序链树搜索算法,来进行POI关键字查询了。例如用户如果输入的关键字为“北大”2字,先从Root根节点出发,根据关键字序列,逐级向下路由,得到查询结果1,5,2,3。然后根据这些POI ID,从raw data文件中检索出详细信息即可。因为采用了排序链树搜索算法,对于长度为k的关键字,在POI总量为n的情况下,POI关键字查询的时间复杂度为:
        T = O(klgn)
比一般的时间复杂度为O(kn)的GIS POI关键字搜索算法,搜索速度有了较大的提升。

算法优劣分析

综上分析可知,采用排序链树搜索算法进行POI关键字查询,其优势在于:
    * 搜索时间少,时间复杂度为O(klgn)
    * 可以让用户边输入,边路由,边搜索,实现实时搜索的功能,对于采用ajax效果的Web GIS来说,犹为合适。
    * 此算法对通配符支持友好,比如用户输入的关键字串为“北大*”或者“北?荒”,此算法都能够比较容易的适应。
其主要劣势在于其ID链表的数据冗余度较大,而且建树过程比较复杂,对POI数据处理程序的要求比较高。但是因为这些工作都在Server端完成,在目前多核,巨量内存,集群的server端硬件条件下,应该都不是大问题。

作者信息

Jagie,软件开发爱好者,可以通过chen_cwf@163.com与他联系。本文来自于Jagie的google page:http://chencwf.googlepages.com/linktree

评论

# re: 排序链树搜索算法在GIS POI关键字搜索中的应用  回复  更多评论   

2010-10-29 14:44 by liuxuejin
很好的文章!每个POI的详细信息,可以存在一个二进制文件(raw data)中,然后再建立一个索引文件,该文件包括5个索引条目,每个条目为一个POI在raw data文件中的偏移量(offset)与长度(size),该POI的索引条目序号(index),即为该POI的ID,这样,根据该POI的ID,查询索引文件,可以得到其在raw data中的offset和size,进而获取其详细信息。
如果有一个类来实现(java)每一个POI,那么每一次都序列化?

# re: 排序链树搜索算法在GIS POI关键字搜索中的应用  回复  更多评论   

2011-06-01 00:10 by doctor
这种树状的索引理论上虽然行,但是实际应用完全不可能,占用的存储空间巨大,无法想象。内存只能驻留一小部分,检索时内存交换的时间就受不了,硬盘占用更不用说。
总结:小儿科,没经验!

# re: 排序链树搜索算法在GIS POI关键字搜索中的应用  回复  更多评论   

2012-12-05 10:30 by chenzep
没有实用价值啊。
假设一个POI的长度为n,按照此方法生成的节点有f(n),则
f(n)=f(n-1)+f(n-2)+...+f(0) + 1= 2^n
以“北京大学”为例,则有2^4=16个节点,分别如下:
空字符串, 1个
“北",”北京“,“北大”,“北学”,“北京大”,“北京学”,“北大学”,“北京大学” f(3)=8个
"京" "京大" "京学” “京大学” f(2)=4个
“大”,“大学” f(1)=2个
"学“ f(0)=1个

假设一个POI的长度为8,则节点个数为2^8=256个,一个省的POI数据为1M,
则节点为256M,就算节点只是一个4字节的索引,所要空间也到达了1G,这是不现实的。

# re: 排序链树搜索算法在GIS POI关键字搜索中的应用  回复  更多评论   

2013-12-17 11:23 by 郭建山
想法确实很好,使用起来没法用呀!加入常用汉字3000,POI最长8个字,那索引要建3000的8次方那么多吗?

只有注册用户登录后才能发表评论。


网站导航: