转载

LBS应用的兴趣点与名称搜索

目前LBS应用已在智能手机中占据了主导地位，但LBS技术覆盖范围太广，很少有能深入描述LBS技术的资料。所以作者在《程序员》杂志开辟专栏来描述LBS核心技术，本文为该专栏的第五篇。

我们知道，美团与大众点评的涉及30亿美金的重量级合并是非常的吸引眼球的。在这一场合并中，美团主要看重的是大众点评的门店POI（Point of Interest，用户感兴趣的点的统称）数据。大众点评拥有1700万门店POI数据，比美团POI数据多2倍。在美团的800万POI数据中，有团购交易的商户接近150万左右，POI到交易的转化率很高。而大众点评的POI的转化率虽然没有美团高，但也是美团眼中的香饽饽。成了这场合并的重要筹码。

既然POI这么重要，那么，POI如何设计？又如何用于检索呢？

POI系统的设计

大众点评当年得到POI的方法是很笨的，是派人去“扫街”来采集POI，即：外业人员到商铺门口去采集，并利用GPS确定位置，内业人员将外业采集得到的数据更新到地理数据库。这种方法和高德/四维图新等图商的POI采集方法是相同的。

在采集POI完成后，下一步是设计POI系统。POI系统设计的核心就是加快POI数据的检索。为了实现POI的快速检索，可以对POI系统建立精细设计的存储及获取的架构，也可以对数据进行线性排序，也可以建立空间索引（参见本系列第一期《LBS数据的空间索引方法》（《程序员》10月B刊））。

【POI系统的存储及获取】

POI的名称由于可以重复，所以为了减少存储的容量，提高检索的速度，可以对所有的名称进行统一存储。这样，可以许多的POI对应一个名称，就减小了POI名称的存储容量。

与名称相同，由于POI的图标也可以重复，所以为了减少存储的容量，提高检索的速度，可以对所有的图标进行统一存储。一幅地图数据存储不到100个图标就满了，而POI只需要有一个对图标的引用即可。

POI除了一般信息外，就是其深度信息了。一般信息就是商铺的名称或者电话等常见信息。深度信息如：店铺的评价、店铺的营业时间，或者地图中需要更新的数据（如从网络得到的POI数据）等。可以想象，未来的地图数据必然是互动的地图，也必然是联网的地图。所以，未来的地图数据中有可能很大一部分是互动的深度数据，比如从其他网站（淘宝、天猫）得到的深度信息。这一点实际上百度和高德等已经在实施，百度的很多数据是靠爬虫从网页中爬来的。高德的很多POI的数据也是从淘宝/天猫得到的。

【线性排序】

如果把所有的几何类型归结为：点、线、面数据。那么，POI显然属于点类型。

点的设计可以非常简单，比如：可以只考虑做一个有经纬度的点到地图上就可以，也可以进行更精细的设计，除了建立更好的空间索引来检索外，也可以对点进行排序，以便能更快速地对点进行检索。

对点进行排序的方法主要有两种：希尔伯特曲线排序和Z排序。这两种排序方法都可以用来对POI进行排序，从而缩短名称搜索所需的时间。

希尔伯特曲线排序

希尔伯特曲线是一种能填充满一个平面正方形的分形曲线（空间填充曲线），由数学牛人大卫·希尔伯特在1891年提出。

由于它能填满平面，它的豪斯多夫维（Hausdorff-Becikovich Dimesion，目前主流的拓扑维度的度量）是2。

希尔伯特曲线本质上显现了一种排序，这种排序的L系统记法如下。

变量：L、R

常数：F、+、−

规则为：

L → + RF− LFL− FR+

R → LF+RFR+FL

其中，F表示向前；−表示右转90°；+表示左转90°。

排序的步骤如图1所示。

LBS应用的兴趣点与名称搜索

图1 希尔伯特排序

Z排序（莫顿排序）

与希尔伯特曲线排序一样，Z排序也是一种将多维空间利用曲线进行填满（实际上是一种点排序）的方法。

Z排序是一种很重要的方法，我们曾在《LBS数据的空间索引方法》一文中描述其原理。下面展现一下其排序效果，如图2所示。

图2 Ｚ排序 LBS应用的兴趣点与名称搜索

图2 Ｚ排序

这两种排序方法都是将二维空间化为一维的方法，从而可以将二维空间进行排序，可以很快地进行POI名称检索。

【POI系统的检索】

搜索是用户和LBS交互的主要渠道。各种LBS应用有所不同，但是搜索技术大致可归纳为以POI（兴趣点）为基础，以名称搜索为表现形式，以推荐系统为核心技术（我们将在下一期介绍推荐技术）。

实际上，推荐技术就是搜索技术，因为推荐技术往往是进行网页排名（谷歌发明的一种网页排名技术）的，所以推荐技术就是最核心的搜索技术。

但是，搜索技术除了出现用户最感兴趣的内容（推荐系统）外，还有效率的需求。提高搜索技术的效率往往有两种技术：大规模的哈希（Hash）技术（如Hadoop中所用到的海量数据存储技术）和构建树的技术。其中大规模的哈希技术在大型的搜索引擎（比如搜狗输入法/百度搜索）中使用比较普遍，往往是先对文本建立分词库，然后建立一些大规模的哈希化的倒排索引等，这种技术实现起来有一定的难度。

而构建树的技术相对于大规模的哈希技术而言，简单且易行。最常见的构建树的技术就是FTS（利用B-树的全文搜索）或自动提示。

FTS

FTS往往是利用与SQLITE的FTS3或FTS4类似的技术来建立的，本质上是一种利用B-树的技术，使用起来比较简单，比如：可以在sqlite3种利用一两句sql语句，就可以实现FTS搜索。

自动提示

自动提示技术大概有如下4种。

在线式技术（利用分词）：这种技术往往有一个庞大的分词数据库，利用庞大的服务器的运算能力，以单词（中文或英文）为单位生成自动提示的词汇。这种技术一般用于搜索引擎，比如谷歌/百度。

离线式技术（利用分词库）：这种技术与在线式分词技术类似，一般是利用预先生成的或用户操作生成的词库。利用词库间单词的关系来自动提示下一个单词。由于这种技术所生成的词汇并非一一对应网页或文本地址。所以，这种技术往往应用于输入法。如果应用于离线式引擎，则需要将分词对应多个网页或文本。

离线（不利用分词库）这种情况下，往往使用NVC（next valid character，下一有效字符）技术。

NVC技术是在国外应用很普遍的一种技术，先于分词技术而产生，最早应用在车载引擎上，并一直在车载引擎上占据统治地位。这是因为NVC技术可以在查找到单词的同时，同步生成唯一对应的POI或道路的索引。所以，方法（3）相比于方法（1）、（2）来说，具有精确、技术实现简单、维护简单的特点。

进行道路或兴趣点名称的NVC的方法如下：

通过在数据库中预先存储所有的道路或兴趣点的名称，并预先存储NVC的数据内容，实现预先判断用户输入的下一个有效字符，从而可以在很短的时间内实现下一字符的自动提示。各名称字符间的关系如图3所示：

LBS应用的兴趣点与名称搜索

图3 NVC的结构

名称的全文提示。这种方法近似自动补全功能，这种自动提示方法通过用户输入的前几个字符，在名称的下拉框中提示1个或多个道路或兴趣点的名称字符串。比如：

LBS应用的兴趣点与名称搜索

图4 自动提示

总的来说，第（1）、（2）种技术所用的方法是非常好的，并且已经普遍应用在大型搜索引擎中，比如百度、谷歌或搜狗输入法。但由于这种方法的开发成本比较高，且对硬件或网络的要求也较高，所以并没有普遍应用于高端车载导航产品及低端的LBS产品。

没有用于低端的LBS产品的原因主要在于开发成本的关系。没有在高端的车载导航中成为主流是因为，高端车载导航需要精确、快速更甚于界面的友好，比如，用第①、②种方法，如果不花费巨额的研发成本，往往不能满足“用户的输入词汇与对应的网页／文本地址一一对应”的要求。比如，用户要查找：望京商业楼，所寻找到符合要求的POI可能有多条，而用户真正希望寻找的那个POI因是冷门的POI，如果采用第①、②种做法，可能被放在第一页之后，或者被忽视。这种情况是高端汽车导航所无法接受的，特别是在目前的车厂的思维仍然比较原始的情况下。

所以，以上四种方法在实现LBS应用时各有优点，开发者需要根据自身的研发实力和需求来制定相应的技术方案。

综上所述，我们已经把POI的设计和名称搜索讲完了。由于这两者都是为了搜索而服务的，推荐系统才是搜索的核心技术。所以，我们将在下一期讲述推荐系统。

作者简介

贾双成，阿里巴巴资深工程师，擅长于数据编译、数据挖掘的系统分析和架构设计，主持研发过多个高端车载导航及adas数据编译器。曾发表发明专利、论文四十余篇，著有《LBS核心技术揭秘》、《数据挖掘核心技术揭秘》。

本文选自程序员电子版2015年12月B刊，该期更多文章请查看这里。2000年创刊至今所有文章目录请查看程序员封面秀。欢迎订阅程序员电子版（含iPad版、Android版）。

正文到此结束