欢迎来到Doc100.Net免费学习资源知识分享平台!
您的位置:首页 > 程序异常 >

排序链树搜索算法在gis poi关键字搜寻中的应用

更新时间: 2014-01-05 02:58:48 责任编辑: Author_N1

 

排序链树搜索算法在GIS POI关键字搜索中的应用

 

转:http://www.etcn.cn/Tech/Program/Java/2012/1020/29090.html

 

排序链树搜索算法在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(PointOfInterest)。比如名称为北京西单图书大厦的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关键字搜索应用链树呢,我们举例来说。假定某城市中存在5个POI,其名称分别是:
北京大学
北京邮电大学
大北窑
未名湖
北大荒
那么我们首先要做的工作就是建立排序链树,然后再依据排序链树,进行关键字搜索。

建立排序链树
建立排序链树的工作分成以下几步来做。
1.分别给每个POI编号,指定其ID,如下
北京大学(1)
北京邮电大学(2)
大北窑(3)
未名湖(4)
北大荒(5)
每个POI的详细信息,可以存在一个二进制文件(rawdata)中,然后再建立一个索引文件,该文件包括5个索引条目,每个条目为一个POI在rawdata文件中的偏移量(offset)与长度(size),该POI的索引条目序号(index),即为该POI的ID,这样,根据该POI的ID,查询索引文件,可以得到其在rawdata中的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关键字查询了。例如用户如果输入的关键字为北大2字,先从Root根节点出发,根据关键字序列,逐级向下路由,得到查询结果1,5,2,3。然后根据这些POIID,从rawdata文件中检索出详细信息即可。因为采用了排序链树搜索算法,对于长度为k的关键字,在POI总量为n的情况下,POI关键字查询的时间复杂度为:
T=O(klgn)
比一般的时间复杂度为O(kn)的GISPOI关键字搜索算法,搜索速度有了较大的提升。

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

 

随机推荐程序问答结果

 

 

如对文章有任何疑问请提交到问题反馈,或者您对内容不满意,请您反馈给我们DOC100.NET论坛发贴求解。
DOC100.NET资源网,机器学习分类整理更新日期::2014-01-05 02:58:48
如需转载,请注明文章出处和来源网址:http://www.doc100.net/bugs/t/16926/
本文WWW.DOC100.NET DOC100.NET版权所有。