著录项信息
专利名称 | 一种搜索预定地理范围内信息的方法和装置 |
申请号 | CN201210018900.X | 申请日期 | 2012-01-20 |
法律状态 | 授权 | 申报国家 | 暂无 |
公开/公告日 | 2013-07-24 | 公开/公告号 | CN103218370A |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | G06F17/30 | IPC分类号 | G;0;6;F;1;7;/;3;0查看分类表>
|
申请人 | 深圳市腾讯计算机系统有限公司 | 申请人地址 | 广东省深圳市南山区高新区高新南一路飞亚达大厦5-10楼
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 深圳市腾讯计算机系统有限公司 | 当前权利人 | 深圳市腾讯计算机系统有限公司 |
发明人 | 张慧斌;田密;张益菲;宋凡;张天乐 |
代理机构 | 北京德琦知识产权代理有限公司 | 代理人 | 张玉波;宋志强 |
摘要
本发明实施例公开了一种搜索预定地理范围内信息的方法和装置。该方法包括:接收查询关键字和用于确定地理范围的地理范围信息,确定能够覆盖所述地理范围的地图块的标识,根据所述查询关键字和所述标识进行信息搜索,得到初步搜索结果集合;从所述初步搜索结果集合中,过滤掉在地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合;其中,预先将所述地图划分为多个地图块,并为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识。应用本发明能够提高搜索预定地理范围内信息的速度。
1.一种搜索预定地理范围内信息的方法,其特征在于,该方法包括:
接收查询关键字和用于确定地理范围的地理范围信息,确定能够覆盖所述地理范围的地图块的标识,根据所述查询关键字和所述标识进行信息搜索,得到初步搜索结果集合;
从所述初步搜索结果集合中,过滤掉在地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合;
其中,预先将所述地图划分为多个地图块,并为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识;
所述预先将所述地图划分为多个地图块,并为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识包括:
预先将所述地图按照第一种至第四种坐标系分别划分地图块,为每一坐标系下的每一地图块分配唯一的标识,且不同坐标系下的地图块的标识也不同,为每一信息项分配该信息项在每种坐标系下所在地图块的标识;
其中,第一种坐标系为标准坐标系,第二种坐标系通过将所述标准坐标系的Y轴进行右移或左移单位长度L的奇数倍得到,第三种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍得到,第四种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍、且Y轴进行右移或左移单位长度L的奇数倍得到;其中,所述地图块是边长为2L的正方形,所述地理范围信息表示的地理范围是边长不大于L的正方形;
所述确定能够覆盖所述地理范围的地图块的标识包括:
确定采用坐标系的种类,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围,确定在该坐标系下能够覆盖所述地理范围的地图块的标识。
2.根据权利要求1所述的方法,其特征在于,根据所述查询关键字和所述标识进行信息搜索包括:
对所述查询关键字进行分词得到一个以上的词项,获取每个词项的信息搜索结果倒排表;以覆盖所述地理范围的地图块的标识作为附加词项,获取所有附加词项的信息搜索结果倒排表的并集;
对所述并集、以及从所述查询关键字分出的所有词项的信息搜索结果倒排表求交集,得到初步搜索结果集合。
3.根据权利要求2所述的方法,其特征在于,
所述附加词项的个数是一个,所述并集是该一个附加词项的信息搜索结果倒排表。
4.根据权利要求3所述的方法,其特征在于,所述确定采用坐标系的种类包括:
计算所述地理范围的边缘坐标值,根据所述边缘坐标值,计算同一种坐标系下所述地理范围的边缘所在的地图块的标识,选出所述地理范围的所有边缘所在的地图块的标识都相同的坐标系;
所述确定在该坐标系下能够覆盖所述地理范围的地图块的标识包括:
将选出的坐标系下所述地理范围的边缘所在的地图块的标识,确定为能够覆盖所述地理范围的地图块的标识。
5.一种搜索预定地理范围内信息的装置,其特征在于,该装置包括接收模块、搜索模块和存储模块;
所述接收模块,用于接收查询关键字和用于确定地理范围的地理范围信息;
所述搜索模块,用于确定能够覆盖所述地理范围的地图块的标识,根据所述查询关键字和所述标识进行信息搜索,得到初步搜索结果集合,从所述初步搜索结果集合中,过滤掉在地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合;
所述存储模块,用于存储预先从所述地图中划分出的每个地图块的信息,所述每个地图块的信息包括为每个地图块分配的唯一的标识,所述存储模块进一步用于存储为每个信息项分配的该信息项所在地图块的标识;
所述存储模块,用于存储将所述地图按照第一种至第四种坐标系分别划分地图块得到的地图块信息,其中,每一坐标系下的每一地图块分配有唯一的标识,且不同坐标系下的地图块的标识也不同,每一信息项分配有该信息项在每种坐标系下所在地图块的标识;
其中,第一种坐标系为标准坐标系,第二种坐标系通过将所述标准坐标系的Y轴进行右移或左移单位长度L的奇数倍得到,第三种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍得到,第四种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍、且Y轴进行右移或左移单位长度L的奇数倍得到;其中,所述地图块是边长为2L的正方形,所述地理范围信息表示的地理范围是边长不大于L的正方形;
所述搜索模块,用于确定采用坐标系的种类,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围,确定在该坐标系下能够覆盖所述地理范围的地图块的标识。
6.根据权利要求5所述的装置,其特征在于,
所述搜索模块,用于对所述查询关键字进行分词得到一个以上的词项,获取每个词项的信息搜索结果倒排表,以能够覆盖所述地理范围的地图块的标识作为附加词项,获取所有附加词项的信息搜索结果倒排表的并集,对所述并集、以及从所述查询关键字分出的所有词项的信息搜索结果倒排表求交集,得到初步搜索结果集合。
7.根据权利要求6所述的装置,其特征在于,
所述附加词项的个数是一个,所述并集是该一个附加词项的信息搜索结果倒排表。
8.根据权利要求7所述的装置,其特征在于,所述搜索模块包括周边范围转化模块、初步搜索模块和结果过滤模块;
所述周边范围转化模块,用于确定能够覆盖所述地理范围的地图块的标识;
所述初步搜索模块,用于对所述查询关键字进行分词得到一个以上的词项,获取每个词项的信息搜索结果倒排表,以能够覆盖所述地理范围的地图块的标识作为附加词项,获取所有附加词项的信息搜索结果倒排表的并集,对所述并集、以及从所述查询关键字分出的所有词项的信息搜索结果倒排表求交集,得到初步搜索结果集合;
所述结果过滤模块,用于从所述初步搜索结果集合中,过滤掉在所述地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合。
9.根据权利要求8所述的装置,其特征在于,
所述周边范围转化模块,用于计算所述地理范围的边缘坐标值,根据所述边缘坐标值,计算同一种坐标系下所述地理范围的边缘所在的地图块的标识,选出所述地理范围的所有边缘所在的地图块的标识都相同的坐标系,将该坐标系下所述地理范围的边缘所在的地图块的标识,确定为能够覆盖所述地理范围的地图块的标识。
10.根据权利要求5所述的装置,其特征在于,该装置还包括分块标识生成模块;
所述分块标识生成模块,用于将所述地图划分为多个地图块,并为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识。
一种搜索预定地理范围内信息的方法和装置\n技术领域\n[0001] 本发明涉及信息搜索技术领域,尤其涉及一种搜索预定地理范围内信息的方法和装置。\n背景技术\n[0002] 搜索预定地理范围内信息,是指根据查询关键字(query),搜索用户指定的地理范围内的相关信息,例如,用户指定地图上的一个点,选择搜索该点周边预定范围内的特定信息。\n[0003] 图1是目前搜索预定地理范围内信息的方法流程图。\n[0004] 如图1所示,该流程包括:\n[0005] 步骤101,接收查询关键字和地理范围信息。\n[0006] 其中,根据所述地理范围信息,可以确定指定的地理范围。地理范围信息的具体内容可以有多种形式,只要根据该地理范围信息能够确定出地理范围即可,例如,如果默认指定的地理范围是正方形,则所述地理范围信息可以包括正方形中心的坐标值和正方形边长,如果正方形的边长也取默认值,则所述地理范围信息可以只包括正方形中心的坐标值。\n[0007] 步骤102,对所述查询关键字进行分词,获取每个词项在整个地图范围内的信息搜索结果倒排表(Inverted index)。\n[0008] 步骤103,对所有词项在整个地图范围内的信息搜索结果倒排表求交集,得到满足所述查询关键字要求的初步搜索结果集合。\n[0009] 步骤104,根据所述初步搜索结果集合中每个搜索结果在所述地图上的坐标信息,确定所述初步搜索结果集合中每个搜索结果在所述地图上的坐标信息是否满足所述地理范围信息的要求,即是否在指定的地理范围内。\n[0010] 例如,当所述指定的地理范围为以指定点为中心、边长为L的正方形区域R,则需要判断所述初步搜索结果集合中的每个搜索结果是否在所述正方形区域R内。\n[0011] 步骤105,从所述初步搜索结果集合中,过滤掉在所述地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和指定的地理范围信息的最终搜索结果集合。\n[0012] 其中,步骤104~105可以称之为数值过滤,用于从满足查询关键字要求的初步搜索结果集合中,过滤掉不满足地理范围信息的搜索结果,即过滤掉无效数据,从而得到满足查询关键字要求和地理范围信息要求的最终搜索结果集合。\n[0013] 可见,由于步骤103所得到的初步搜索结果集合是基于整个地图范围的,因此所得到的初步搜索结果集合的信息量很大,其中包含大量的无效数据,即不满足地理范围信息要求的数据,最终导致数值过滤耗时较长,严重影响信息搜索速度。\n发明内容\n[0014] 有鉴于此,本发明提供了一种搜索预定地理范围内信息的方法和装置。能提高搜索预定地理范围内信息的速度。\n[0015] 本发明的技术方案具体是这样实现的:\n[0016] 一种搜索预定地理范围内信息的方法,该方法包括:\n[0017] 接收查询关键字和地理范围信息,确定能够覆盖所述地理范围的地图块的标识,根据所述查询关键字和所述标识进行信息搜索,得到初步搜索结果集合;\n[0018] 从所述初步搜索结果集合中,过滤掉在所述地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合;\n[0019] 其中,预先将地图划分为多个地图块,并为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识;\n[0020] 所述预先将所述地图划分为多个地图块,并为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识包括:\n[0021] 预先将所述地图按照第一种至第四种坐标系分别划分地图块,为每一坐标系下的每一地图块分配唯一的标识,且不同坐标系下的地图块的标识也不同,为每一信息项分配该信息项在每种坐标系下所在地图块的标识;\n[0022] 其中,第一种坐标系为标准坐标系,第二种坐标系通过将所述标准坐标系的Y轴进行右移或左移单位长度L的奇数倍得到,第三种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍得到,第四种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍、且Y轴进行右移或左移单位长度L的奇数倍得到;其中,所述地图块是边长为2L的正方形,所述地理范围信息表示的地理范围是边长不大于L的正方形;\n[0023] 所述确定能够覆盖所述地理范围的地图块的标识包括:\n[0024] 确定采用坐标系的种类,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围,确定在该坐标系下能够覆盖所述地理范围的地图块的标识。\n[0025] 一种搜索预定地理范围内信息的装置,该装置包括接收模块、搜索模块和存储模块;\n[0026] 所述接收模块,用于接收查询关键字和地理范围信息;\n[0027] 所述搜索模块,用于根据所述地理范围信息,确定能够覆盖所述地理范围的地图块的标识,根据所述查询关键字和所述标识进行信息搜索,得到初步搜索结果集合,从所述初步搜索结果集合中,过滤掉在所述地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合;\n[0028] 所述存储模块,用于存储从地图中划分出的每个地图块的信息,所述每个地图块的信息包括为每个地图块分配的唯一的标识,所述存储模块进一步用于存储为每个信息项分配的该信息项所在地图块的标识;\n[0029] 所述存储模块,用于存储将所述地图按照第一种至第四种坐标系分别划分地图块得到的地图块信息,其中,每一坐标系下的每一地图块分配有唯一的标识,且不同坐标系下的地图块的标识也不同,每一信息项分配有该信息项在每种坐标系下所在地图块的标识;\n[0030] 其中,第一种坐标系为标准坐标系,第二种坐标系通过将所述标准坐标系的Y轴进行右移或左移单位长度L的奇数倍得到,第三种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍得到,第四种坐标系通过将所述标准坐标系的X轴进行上移或下移单位长度L的奇数倍、且Y轴进行右移或左移单位长度L的奇数倍得到;其中,所述地图块是边长为2L的正方形,所述地理范围信息表示的地理范围是边长不大于L的正方形;\n[0031] 所述搜索模块,用于确定采用坐标系的种类,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围,确定在该坐标系下能够覆盖所述地理范围的地图块的标识。\n[0032] 由上述技术方案可见,本发明在搜索预定地理范围内的信息时,首先确定能够覆盖所述预定地理范围的地图块的标识,然后利用接收的查询关键字和确定出的地图块标识进行信息搜索,即将地图块的标识也作为查询词项进行信息搜索,使得搜索到的初步信息搜索结果都是在该地图块内的信息,而不包含该地图块以外的其他地图块内的信息,从而大大减少了初步信息搜索结果中包含的无效数据的数量,即不满足地理范围信息要求的数据数量,从而减少数值过滤的时长,提高信息搜索速度。\n附图说明\n[0033] 图1是目前搜索预定地理范围内信息的方法流程图。\n[0034] 图2是本发明提供的搜索预定地理范围内信息的方法流程图。\n[0035] 图3是本发明提供的第一种坐标系和第二种坐标系的地图分块示意图。\n[0036] 图4是确定能够覆盖预定地理范围的一个地图块的第一示意图。\n[0037] 图5是确定能够覆盖预定地理范围的一个地图块的第二示意图。\n[0038] 图6是本发明提供的搜索预定地理范围内信息的装置结构图。\n具体实施方式\n[0039] 图2是本发明提供的搜索预定地理范围内信息的方法流程图。\n[0040] 如图2所示,该方法包括:\n[0041] 步骤201,接收查询关键字和地理范围信息。\n[0042] 其中,根据所述地理范围信息可以确定出地理范围。地理范围信息的具体内容可以有多种形式,只要根据该地理范围信息能够确定出地理范围即可。\n[0043] 步骤202,确定能够覆盖所述地理范围的地图块的标识。\n[0044] 步骤203,根据所述查询关键字和所述标识进行信息搜索,得到初步搜索结果集合。\n[0045] 步骤204,从所述初步搜索结果集合中,过滤掉在地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合。\n[0046] 其中,需要预先将地图划分为多个地图块,并为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识。\n[0047] 其中,地图可以看成是一个二维坐标系,基于地图的信息搜索中,每个信息项都有一个坐标,因此可以看成是地图坐标系中的一个点,对地图分块,为每个地图块分配唯一的标识,并为信息项分配该信息项所在地图块的标识,本质上是对同一个地图块内的所有信息项统一分配一个唯一的标识。其中的信息项,是指可能成为信息搜索的对象,例如,在一张地图上有餐馆、银行、商店、公交站等信息项,每个信息项都有其在该地图上的坐标信息。\n[0048] 所述的地图,是指进行信息搜索时所基于的地图,例如,当基于北京市区的地图进行信息搜索时,所述地图是指北京市区的地图,当基于全国范围的地图进行信息搜索时,所述地图是指全国范围的地图。\n[0049] 根据查询关键字和确定出的地图块的标识进行信息搜索,具体可以包括:\n[0050] 对所述查询关键字进行分词,获取每个词项的信息搜索结果倒排表;以覆盖所述地理范围的地图块的标识作为附加词项,获取所有附加词项的信息搜索结果倒排表的并集;对所述并集、以及从所述查询关键字分出的所有词项的信息搜索结果倒排表求交集,得到初步搜索结果集合。\n[0051] 其中,如果覆盖所述地理范围的地图块有多个,则有多个附加词项,在获取每个附加词项的信息搜索结果倒排表以后,还需要对所有附加词项的信息搜索结果的倒排表求并集,这种求并集的操作一定程度上会降低信息搜索速度,因此,为了避免求并集的操作,本发明提出,在对地图划分地图块时,需要使得采用划分出的一个地图块,就可以覆盖接收的地理范围信息所表示的地理范围,从而使得所述附加词项的个数是一个,所述并集,实际上就是该一个附加词项的信息搜索结果倒排表,从而避免了实际的求并集的操作,进一步提高了信息搜索速度。\n[0052] 具体地,本发明提出,预先将地图按照第一种至第四种坐标系分别划分地图块,为每一坐标系下的每一地图块分配唯一的标识,且不同坐标系下的地图块的标识也不同,为每一信息项分配该信息项在每种坐标系下所在地图块的标识,其中,第一种坐标系为标准坐标系,第二种坐标系通过将所述标准坐标系的Y轴进行右移或左移得到,第三种坐标系通过将所述标准坐标系的X轴进行上移或下移得到,第四种坐标系通过将所述标准坐标系的X轴进行上移或下移、且Y轴进行右移或左移得到,并且,通过确定采用坐标系的种类,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围。\n[0053] 确定能够覆盖所述地理范围的地图块的标识的方法具体可以包括:\n[0054] 计算所述地理范围的边缘坐标值,根据所述边缘坐标值,计算同一种坐标系下所述地理范围的边缘所在的地图块的标识,选出所述地理范围的所有边缘所在的地图块的标识都相同的坐标系,将该坐标系下所述地理范围的边缘所在的地图块的标识,确定为能够覆盖所述地理范围的地图块的标识。\n[0055] 作为进一步具体的实施例,所述第二种坐标系可以通过将标准坐标系的Y轴右移或左移单位长度L的奇数倍得到,所述第三种坐标系可以通过将标准坐标系的X轴上移或下移单位长度L的奇数倍得到,所述第四种坐标系可以通过将标准坐标系的Y轴右移或左移单位长度L的奇数倍、且X轴上移或下移单位长度L的奇数倍得到,其中,在每一种坐标系下从地图上划分出的地图块均是边长为2L的正方形,所述地理范围信息表示的地理范围是边长不大于L的正方形。\n[0056] 在实际应用中,所述坐标系还可以包括多个层次,每个层次的坐标系均包括四种,即第一种至第四种坐标系,从同一个层次下的第一种至第四种坐标系划分出地图块的尺寸相同,而从不同层次下的坐标系划分出的地图块的尺寸不同,则在确定需要采用坐标系的种类时,首先根据所述地理范围信息所表示的地理范围的尺寸,选择坐标系的层次,然后从该层次的第一种至第四种坐标系中选择一种坐标系,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围。\n[0057] 下面,举一个具体的例子,对本发明提供的搜索预定地理范围内信息的方法进行示例性说明,所举例子不用于限制本发明。\n[0058] 在该具体的例子中,对地图使用四种坐标系进行分块,从每种坐标系中划分出的地图块均是边长为2L的正方形,其中,L是单位长度,第一种坐标系是标准坐标系,第二种坐标系是将标准坐标系的Y轴右移L得到的坐标系,第三种坐标系是将标准坐标系的X轴上移L得到的坐标系,第四种坐标系是将标准坐标系的Y轴右移L、且X轴上移L得到的坐标系,具体请参见图3。\n[0059] 图3是本发明提供的第一种坐标系和第二种坐标系的地图分块示意图。\n[0060] 图3给出了标准坐标系和Y轴右移L坐标系下的地图分块方法,假设L长度为单位1,图3(a)和(b)中每个粗实线正方形表示一个分块,为每个分块赋予一个唯一的标识。\n[0061] 标 准 坐 标 系 下,对 于 坐 标 值 (x,y)满 足 x ∈[m*2L,(m+1)*2L)、且y∈[n*2L,(n+1)*2L)条件的正方形,一种分配标识的方法为\n[0062] id1=1:m*2L/2L:n*2L/2L=1:m:n\n[0063] 其中,m和n均是整数,所分配的标识中,1表示标准坐标系;m*2L/2L为地图块的x轴下限除以正方形边长取整;n*2L/2L为地图块的y轴下限除以正方形边长取整,为坐标落在该正方形内的所有信息项,都分配一个相同的标识1:m:n。\n[0064] 类似的,在 Y轴右移L 的坐标系下,对于坐标值 (x,y)满足\nx∈[m*2L+L,(m+1)*2L+L)、且y∈[n*2L,(n+1)*2L)条件的正方形,一种分配的标识为:\n[0065] id2=2:(m*2L+L-L)/2L:n*2L/2L=2:m:n\n[0066] 其中,m和n均是整数,所分配的标识中,2表示Y轴右移L的坐标系;\n(m*2L+L-L)/2L为地图块的x轴下限减去L除以正方形边长取整;n*2L/2L为地图块的y轴下限除以正方形边长取整。坐标落在该正方形内的所有信息项,都分配有一个相同的标识\n2:m:n。\n[0067] 第三种和第四种坐标系下,使用类似的方法计算分块标识,此处不赘述。这些标识在同一个坐标系下和不同坐标系下都是唯一的,不会重复。给定一个信息项,根据它的坐标可以计算出四种坐标系下对应的标识。\n[0068] 基于该具体的例子中的地图分块方法,四种坐标系下为每个信息项各分配一个标识,为每个信息项共分配四个标识,作为该信息项的附加词项,参与倒排索引的构建。如标识id1=1:m:n的倒排表中会包含标识为“1:m:n”的地图块内的所有信息项。\n[0069] 基于该具体的例子中的地图分块方法,对于边长不大于L的正方形R,使用4种坐标系中的一种,总能使得在该坐标系下该正方形R落在一个分块内,其中,所述分块是边长为2L的正方形。\n[0070] 具体地,如果边长为L的正方形R落在标准坐标系下的一个边长为2L的分块内,则可以使用标准坐标系下的一个分块来覆盖正方形R。\n[0071] 图4是确定能够覆盖预定地理范围的一个地图块的第一示意图。\n[0072] 如图4所示,边长为L的正方形R的x轴跨越标准坐标系下的一个分块,则在Y轴右移L的坐标系下,该正方形R必落在一个正方形分块内,则可以使用Y轴右移L的坐标系下的一个分块来覆盖正方形R。\n[0073] 图5是确定能够覆盖预定地理范围的一个地图块的第二示意图。\n[0074] 如图5所示,在图5(a)中,边长为L的正方形R的y轴跨越标准坐标系下的一个分块,则在X轴上移L的坐标系下,该正方形R必落在一个正方形分块内,则可以使用X轴上移L的坐标系下的一个分块来覆盖正方形R。\n[0075] 在图5(b)中,边长为L的正方形R的x轴、y轴均跨越标准坐标系下的一个分块,则在X轴上移L、且Y轴右移L的坐标系下,该正方形R必落在一个正方形分块内,则可以使用X轴上移L、且Y轴右移L的坐标系下的一个分块来覆盖正方形R。\n[0076] 图4-图5已经证明了四种坐标系下肯定有一种可以使用一个分块覆盖预定的地理范围,即覆盖正方形R。如果正方形R的四个顶点在一个分块内,即四个顶点分块标识相同,那么该分块必然覆盖R。因此,确定能够覆盖正方形R的地图块的方法具体可以包括:\n[0077] 首先,计算出正方形R的四个顶点坐标;然后,计算四个顶点在四种坐标系下的分块标识,四种坐标系下,必然有一种坐标系下该正方形R的四个顶点分块标识是相同的,则该分块标识所代表的地图分块能够覆盖该正方形R,因此,选择该坐标系下的该分块标识作为进行信息搜索的附加词项。\n[0078] 在该具体的例子中,当用户进行周边信息搜索时,如果指定的地理范围是以指定点为中心点、边长为L的正方形R,则对用户查询关键字(query)分词,得到query包含的每个词项,另外,根据正方形R找到四种坐标系下可以使用一个分块覆盖R的分块方式,将对应的块标识作为一个附加词项。使用query中包含的词项和所述附加词项共同去信息检索系统拉取信息搜索结果倒排表,并对拉取的各个倒排表求交集得到集合S,从集合S中找到同时满足查询关键字和地理范围信息要求的最终的搜索结果集合。\n[0079] 由于根据分块标识(即附加词项)拉取的倒排表一般较短,因此,和其他倒排表共同求交集,能够大大提高倒排表多路合并的速度,优化了检索性能。\n[0080] 由于确定出的分块标识对应的地图块大于用户指定的地理范围,上述方法中求得的结果集合S中会有部分结果不满足用户指定的地理范围要求,再通过数据的坐标过滤,即可得到同时满足查询关键字和地理范围信息要求的最终的搜索结果集合。因为集合S包含的信息项数已经明显减少,因此,应用本发明能够明显提高检索性能,为开发基于位置服务(Location Based Service,LBS)的应用提供了技术保障。\n[0081] 根据本发明提供的上述方法,本发明还提供了一种搜索预定地理范围内信息的装置,具体请参见图6。\n[0082] 图6是本发明提供的搜索预定地理范围内信息的装置结构图。\n[0083] 如图6所示,该装置包括接收模块601、搜索模块602和存储模块603。\n[0084] 接收模块601,用于接收查询关键字和地理范围信息。\n[0085] 搜索模块602,用于根据所述地理范围信息,确定能够覆盖所述地理范围的地图块的标识,根据所述查询关键字和所述标识进行信息搜索,得到初步搜索结果集合,从所述初步搜索结果集合中,过滤掉在所述地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合。\n[0086] 存储模块603,用于存储从地图中划分出的每个地图块的信息,所述每个地图块的信息包括为每个地图块分配的唯一的标识,存储为每个信息项分配的该信息项所在地图块的标识。\n[0087] 其中的搜索模块602,具体用于对所述查询关键字进行分词,获取每个词项的信息搜索结果倒排表,以能够覆盖所述地理范围的地图块的标识作为附加词项,获取所有附加词项的信息搜索结果倒排表的并集,对所述并集、以及从所述查询关键字分出的所有词项的信息搜索结果倒排表求交集,得到初步搜索结果集合。\n[0088] 其中的存储模块603,用于存储将地图按照第一种至第四种坐标系分别划分地图块得到的地图块信息,其中,每一坐标系下的每一地图块分配有唯一的标识,且不同坐标系下的地图块的标识也不同,每一信息项分配有该信息项在每种坐标系下所在地图块的标识。\n[0089] 其中,第一种坐标系为标准坐标系,第二种坐标系通过将所述标准坐标系的Y轴进行右移或左移得到,第三种坐标系通过将所述标准坐标系的X轴进行上移或下移得到,第四种坐标系通过将所述标准坐标系的X轴进行上移或下移、且Y轴进行右移或左移得到。\n[0090] 搜索模块602,具体用于确定采用坐标系的种类,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围,确定在该坐标系下能够覆盖所述地理范围的地图块的标识。则,所述附加词项的个数是一个,所述并集是该一个附加词项的信息搜索结果倒排表。\n[0091] 其中,所述第二种坐标系和所述第四种坐标系具体可以通过如下方式得到:所述第二种坐标系通过将标准坐标系的Y轴右移或左移单位长度L的奇数倍得到,所述第三种坐标系通过将标准坐标系的X轴上移或下移单位长度L的奇数倍得到,所述第四种坐标系通过将标准坐标系的Y轴右移或上移单位长度L的奇数倍、且X轴上移或下移单位长度L的奇数倍得到。\n[0092] 其中,从每一坐标系下划分出的地图块是边长为2L的正方形,所述地理范围信息表示的地理范围是边长不大于L的正方形。\n[0093] 搜索模块602具体可以包括周边范围转化模块、初步搜索模块和结果过滤模块。\n[0094] 所述周边范围转化模块,用于确定能够覆盖所述地理范围的地图块的标识。\n[0095] 所述初步搜索模块,用于对所述查询关键字进行分词,获取每个词项的信息搜索结果倒排表,以能够覆盖所述地理范围的地图块的标识作为附加词项,获取所有附加词项的信息搜索结果倒排表的并集,对所述并集、以及从所述查询关键字分出的所有词项的信息搜索结果倒排表求交集,得到初步搜索结果集合。\n[0096] 所述结果过滤模块,用于从所述初步搜索结果集合中,过滤掉在所述地图上的坐标信息不满足所述地理范围信息要求的搜索结果,得到满足所述查询关键字和所述地理范围信息要求的最终搜索结果集合。\n[0097] 所述周边范围转化模块,用于计算所述地理范围的边缘坐标值,根据所述边缘坐标值,计算同一种坐标系下所述地理范围的边缘所在的地图块的标识,选出所述地理范围的所有边缘所在的地图块的标识都相同的坐标系,将该坐标系下所述地理范围的边缘所在的地图块的标识,确定为能够覆盖所述地理范围的地图块的标识。\n[0098] 所述坐标系可以包括多个层次,从同一个层次下的第一种至第四种坐标系划分出地图块的尺寸相同,从不同层次下的坐标系划分出的地图块的尺寸不同。\n[0099] 存储模块601,存储有从每一层次下的坐标系划分出的每个地图块的信息,存储为每个信息项分配的该信息项所在的每一层次下的地图块的标识。\n[0100] 所述周边范围转化模块,用于根据所述地理范围信息所表示的地理范围的尺寸,选择坐标系的层次,从该层次的第一种至第四种坐标系中选择一种坐标系,使得在该种坐标系下划分得到的一个地图块能够覆盖所述地理范围。\n[0101] 该装置还可以包括分块标识生成模块。\n[0102] 所述分块标识生成模块,用于将地图划分为多个地图块,为每个地图块分配唯一的标识,为每个信息项分配该信息项所在地图块的标识。\n[0103] 可见,应用本发明,由于初步搜索结果集合中包含的信息项都是能够覆盖用户指定地理范围的地图块中的信息项,包含的信息项数与现有技术相比,已经明显减少,因此,应用本发明能够明显提高检索性能,为开发基于位置服务(Location Based Service,LBS)的应用提供了技术保障。\n[0104] 以上所述仅为本发明的较佳实施例而已,并不用以限制本发明,凡在本发明的精神和原则之内,所做的任何修改、等同替换、改进等,均应包含在本发明保护的范围之内。
法律信息
- 2015-11-04
- 2013-08-21
实质审查的生效
IPC(主分类): G06F 17/30
专利申请号: 201210018900.X
申请日: 2012.01.20
- 2013-07-24
引用专利(该专利引用了哪些专利)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 |
1
| |
2008-06-11
|
2007-11-23
| | |
2
| |
2011-08-24
|
2011-01-11
| | |
3
| |
2011-08-10
|
2010-02-05
| | |
4
| |
2011-04-06
|
2010-12-08
| | |
被引用专利(该专利被哪些专利引用)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有被任何外部专利所引用! |