标签

排序链树GISPOI关键字搜索算法

概念阐述

链树及其相关概念

本来，数据结构教科书中，不存在一种叫做“链树”的数据结构，用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搜索出来。