转载

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  Z排序 LBS应用的兴趣点与名称搜索

图2  Z排序

这两种排序方法都是将二维空间化为一维的方法,从而可以将二维空间进行排序,可以很快地进行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版)。

正文到此结束
Loading...