排序链树搜索算法在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端硬件条件下，应该都不是大问题。