复杂地理实体快速查询的空间语义模式图构建及搜索方法

技术领域

本发明属于自然语言位置查询技术领域，特别是涉及一种面向复杂地理实体快速查询的空间语义模式图构建及搜索方法。

背景技术

传统文本相似性方法不能充分利用语义匹配中的结构与词汇类别等语义信息。实际位置描述的省略性、模糊性及为保证召回率所输入的多条匹配结果，易导致组合爆炸问题，造成效率损失。当前空间数据的检索查询分为根据空间范围检索和根据关键词与空间的联合检索。前者包括四叉树、R树等，利于空间数据的快速检索。但其语义过滤较为简单而易为人所忽略。后者常用于结合关键词和空间区域查找最邻近的空间对象，空间检索一般用R索引或格网索引，文本索引一般为倒排形式。但其未利用到由语义匹配产生的位置概念层次语义特征，不适合包含复杂层次结构的位置描述解析。位置概念多字段联合检索依赖于对位置概念建立关系数据表表达，但这种自底往上的查询形式未充分利用位置描述的组合特征对位置概念进行表达和检索，未能融合位置概念的关联特征。

将位置概念描述与实体对应，需将语义搜索结合空间约束进行空间过滤。位置概念具有概念和空间关系的关联性。位置概念的关联关系具有网络性，节点代表位置概念，边表示两者间隶属或等价的关系。表述形式反映概念子部分的组成，展现了位置概念的层次型特征。人类在空间认知中遵循模板匹配的方法，在定位层次型的位置描述中，迭代子元素与记忆中的实体表达比对，找出最可能的结果。人们省略、关联等行为，造成位置描述与位置概念间多对多的关系。这也是歧义的根源之一。从位置描述到位置概念对象需利用位置概念的语义信息，包括组成形式、层次结构及关联关系。从位置描述要能快速得到空间特征。为了建立高效的查询检索，需要一种能快速获取经匹配后的位置描述对应的位置概念对象机制。

发明内容

为了解决上述技术问题，本发明将语义与空间联合索引，提出面向复杂地理实体快速查询的空间语义模式图构建及搜索方法，减少“由底向上”多属性联合查询的排列组合数，避免位置描述中的组合爆炸问题，降低效率损失。

本发明提供的一种复杂地理实体快速查询的空间语义模式图构建方法，包括以下步骤：

步骤1：输入实际位置概念对象；

步骤2：将位置概念对象模式分解入库；

步骤3：逐级构建模式节点，根据模式存储和查询策略利用模式节点的关系压缩模式图；

步骤4：更新模式的空间、统计特征及关联关系；

步骤5：相似性度量并重排序模式节点中的位置概念。

本发明提供的一种复杂地理实体快速查询的空间语义模式图搜索方法，包括以下步骤：

步骤1：输入虚拟位置概念对象lc及参数ls、lr和F；其中ls用于指示lc是否为某个父位置概念对象在模式入库过程中递归的子组成部分，lr代表当ls为真时该子概念对象模式是否需要进行关联搜索，F代表需要进行关联搜索的子概念位置对象；

步骤2：判断lc是否为基础位置概念；

若是，跳过此节点，遍历至下一模式节点，并回转执行步骤2；

若否，继续执行步骤3；

步骤3：初始化返回模式节点PR；

步骤4：遍历lc的子位置概念对象集合；

步骤5：调用要素分解算法获取各子部分的模式编码集合，组成数组PC＝(pc₁,pc₂，…，pc_n)，pc_i为第i个子位置概念对象的模式编码集合；

步骤6：得到此位置概念类型对应的模式定义图G_P；

步骤7：遍历模式定义节点；

步骤8：判断模式定义节点的要素集合F对应的要素模式编码集合是否为空；

若是，继续执行步骤9；

若不是，则进入下一个模式定义节点，回转执行步骤8；

步骤9：对PC进行模式编码的排列组合，得到模式编码数组C；

步骤10：遍历数组C；

步骤11：查询模式编码是否存在；

若存在，调出之前的模式节点p，将p加入初始化节点关系待更新组P；

若不存在，跳过该模式编码，继续执行步骤11；

步骤12：完成G_P遍历，对P向下扩展模式节点，形成新节点关系待更新组P’；

步骤13：对对象lc关联搜索；

步骤14：返回P’对应的模式节点编码集合。

本发明实现了面向复杂地理实体快速查询的空间语义模式图构建及搜索方法，将语义与空间联合索引，提出一种“由上向下”的模式查询策略，针对位置描述的自然语言形式查询，建立从匹配得出的虚拟位置概念对象到实际位置概念集合的快速映射，通过对象的语义层次建立位置概念对象的连接图，为定位过程提供高效的位置概念对象查询。

附图说明

图1：本发明实施例的位置概念语义构成示例图；

图2：本发明实施例的模式图组成及层次示意图；

图3：本发明实施例的模式图构建流程图；

图4：本发明实施例的模式图查询流程图。

具体实施方式

下面结合附图与实施例，对本发明进行更详尽的说明，来实现对该面向复杂地理实体快速查询的空间语义模式图构建及搜索方法的理解与应用。

如图1所示，为本发明的一种位置概念语义构成示例图，详述如下。

人类在空间认知中遵循模板匹配的方法，在定位层次型的位置描述中，迭代往返子元素与记忆中的实体表达比对，找出最可能的结果。描述时的省略、关联等行为，造成位置描述与位置概念间多对多的关系。因此应充分理解各类位置概念的语义信息，包括其组成形式、层次结构及关联关系。位置概念的组合特征可总结为位置概念的表达模式。例如，对于一条标准的地址“武汉市青山区钢都花园123街坊55门号1栋”，对其有若干种描述形式：

(1)武汉青山钢都123街坊55门号1栋

(2)武汉钢都123街坊55门号1栋

(3)青山区钢都花园123街坊55门号1栋

(4)青山区钢都123街坊55门号

(5)青山区钢都花园123街坊55门号

(6)青山区钢都花园123街坊

(7)钢都花园123街坊1栋

(8)钢都123街坊

(9)青山钢都

(10)……

这些表述形式反映出概念的子部分，一种组合形式对应一种模式。由于位置概念的层次型特征，子部分的组合也需考虑在内，如这条地址对象中的小区部分“钢都花园123街坊1栋”对应了“钢都花园123街坊”、“钢都123街坊”等若干种组合，每种组合对应一个模式节点。模式节点可能包含多个位置概念对象。如“钢都123街坊”对应的模式节点可能包含位于钢都123街坊下的若干地址对象。某一模式节点可能包含分布多个区域的若干对象，即分布在若干区的多地址子集。

如图2所示，为本发明的一种模式图组成及层次示意图，详述如下。

模式将查询对象进行了封装，将实际对象和代表的模式分开存储，在查询时对模式检索，实际定位需要时获取其对象。模式节点包含组合的编码、其对应的位置概念对象及综合后的空间特征。对应于同位置概念的模式具有关联关系，即在模式对象中形成模式节点网络，将一个位置概念的模式节点连接。

模式由大量的实际位置描述总结而来，一个实体位置概念对应一个模式组。模式节点p由一个七元组构成，p＝(c,i,L,R,m,n,g)。其中c代表模式节点编码，i代表模式节点ID,L代表模式节点的一阶子节点集合，R代表模式节点的强对应位置概念对象集合,m代表该模式对应的全部位置概念对象数目，n代表该模式所包含的全部子模式数量，g代表模式的空间外包矩形。

模式依赖图中每个模式对应一个模式定义节点。模式要素越少，所在树级别越往上，对象化的模式节点的位置概念对象越多。模式组内不同模式间有包含和被包含关系。引擎初始化时模式组对象PG由词法和语法分析编译而成，再根据PG生成该位置概念的模式依赖图。具体算法如下：

(1)构建节点关系；

(2)赋予模式节点匹配顺序值mo，对应了从顶端节点到该模式节点的深度；

(3)由mo对模式定义节点按降序排序；

如图3所示，为本发明的模式图构建流程图，其在位置概念对象入库阶段完成，详述如下。

首先模式分解位置概念对象，逐级构建模式节点，根据模式存储和查询策略两方面利用模式节点的关系压缩模式图；最后更新模式的空间、统计特征及关联关系，相似性度量并重排序模式节点中的位置概念。

其中，模式分解入库是将位置概念对象的语义对象树进行模式分解并对应到具体模式对象。即构建适合快速检索的模式对象网络，网络节点再与位置概念对象关联，进而产生新模式节点或更新模式对象。具体步骤如下：

步骤2.1：输入实际位置概念对象lc及参数ls，ls用于指示lc是否为某个父位置概念对象在模式入库中递归的子组成部分；

步骤2.2：判断lc是否已存入模式缓存M；

若是，则直接返回模式缓存中的对象，然后执行步骤4；

步骤2.3：判断lc是否为基础位置概念；

若是，则根据ls值返回分解或独立形式的编码集合，然后执行步骤4；

步骤2.4：初始化返回模式节点PR；

步骤2.5：遍历lc的子位置概念对象集合；

步骤2.6：调用要素分解算法获取子部分的模式编码集合，组成数组PC＝(pc₁,pc₂，…，pc_n)，pc_i为第i个子位置概念对象的模式编码集合；

其中要素分解算法，具体实现过程是：根据要素不同类型，执行不同操作；

若要素为基础概念对象时，则返回分解形式的编码；

若要素为数组类型，则对数组元素重新组合，调用模式分解入库算法；

若要素为其他原生对象类型，则直接进行编码；

若要素是复杂位置概念(本文主要基于位置概念中的基础词汇构建小型的关联数据模型，并将其融入到位置概念查询过程当中)，则调用模式分解入库算法；将ls参数设为真，指示当前为一个子部分，底层返回组成形式的编码集合。

步骤2.7：得到此位置概念类型的模式定义图G_P；

步骤2.8：遍历模式定义节点；

步骤2.9：判断模式定义节点的要素集合F的要素模式编码集合是否为空；

若是，则继续执行下述步骤2.10；

若否，则跳过此节点，针对下一定义模式节点，回转执行步骤2.9；

步骤2.10：进行模式条件前筛选；

步骤2.11：判断是否满足筛选条件(用筛选函数进行筛选是本专位置概念建模基础上提出的一种针对查询的语义结构筛选方法，具体过程是扩展模式语法中的Pattern定义形式，加上筛选函数，即从组合PC中某子部分模式编码集合里去除符合筛选条件(符合实际表述中不太可能的模式)的模式编码)；

若是，则继续执行下述步骤2.12；

若否，则跳过此节点，针对下一模式定义节点，回转执行步骤2.9；

步骤2.12：判断模式定义节点是否为该位置概念的强匹配模式sm；

步骤2.13：初始化节点关系待更新组P；

步骤2.14：遍历模式编码数组C；

步骤2.15：查询模式编码是否存在；

若是，则调出之前的模式节点，然后判断sm的真假；若sm为真，将位置概念存入该模式节点的位置概念集合；若sm为假，则创建新的模式节点；

若否，则创建新模式节点；

步骤2.16：完成C的遍历，通过模式依赖图更新P间的相互关系；

步骤2.17：判断模式节点p₁和p₂的模式定义节点pd₁和pd₂间是否呈父子关系；

若是，则验证p₁的语义组成是否包含p₂的语义组成；若则将p₁加入p₂的模式子节点列表；否则两节点不连接；其中模式节点的语义组成即为其拥有的要素集合，定义为ps＝{f₁,f₂,…,f_n}；

若不是，则两节点不连接；

步骤2.18：G_P遍历完成；

步骤2.19：对PR进行模式后筛选(针对底层较为简单形式的复杂位置概念，在入库过程中会以子位置概念对象的形式出现在地址和POI当中，在模式分解入库过程中，下层的这类子位置概念在一定条件下可以只往上输送模式叶节点，而在模式分解查询过程中利用模式节点之间的关系往下自动分解到叶节点模式来进行查询。定义这个过程为模式后筛选。)，形成新节点关系待更新组P’；

步骤2.20：更新模式缓存PC，返回P’的模式节点编码集合。

模式节点压缩策略是通过底层节点往上输送的模式节点进行筛选来减少模式图的规模。第一种是模式前筛选，即筛选掉实际表述中不太可能的模式。另一种是模式后筛选，针对底层较简单的复杂位置概念。如行政区地名、道路、小区等，这些位置概念入库时会以子位置概念对象出现在地址和POI中，并且一般由两个基础位置概念构成，分别代表其名称和后缀特征词，如“武汉”+“市”、“古田”+“三路”。本质上是利用小量的查询计算来替换一部分模式节点的存储。

模式空间与统计特征生成是位置概念分解入库完成后，遍历模式节点，从底至上对特征进行递归计算。对象重排序是通过模式节点的扩展编码形式构造虚拟位置概念对象lp，并通过lp与模式节点位置概念Rp的语义相似度对Rp重排序。

如图4所示，为本发明的模式图查询流程图，详述如下。

模式查询实现了由位置描述匹配形成的位置概念虚拟对象递归式的分解查询，通过子概念的模式编码组合搜寻到各层符合的模式节点返回给上层，得到顶层模式节点，并取出位置概念数据库中的位置概念对象。具体步骤如下：

步骤1：输入虚拟位置概念对象lc及参数ls、lr和F。ls用于指示lc是否为某个父位置概念对象在模式入库过程中递归的子组成部分。lr代表当ls为真时该子概念对象模式是否需要进行关联搜索。F代表需要进行关联搜索的子概念位置对象；

步骤2：判断lc是否为基础位置概念；

若是，跳过此节点，遍历至下一模式节点；

若不是，继续执行步骤3；

步骤3：初始化返回模式节点PR；

步骤4：遍历lc的子位置概念对象集合；

步骤5：调用要素分解算法获取各子部分的模式编码集合，组成数组PC＝(pc₁,pc₂，…，pc_n)，pc_i为第i个子位置概念对象的模式编码集合；

步骤6：得到此位置概念类型对应的模式定义图G_P；

步骤7：遍历模式定义节点；

步骤8：判断某模式定义节点的要素集合F对应的要素模式编码集合是否为空；

若是，继续执行步骤9；

若不是，则进入下一个模式定义节点，回转执行步骤8；

步骤9：对PC进行模式编码的排列组合，得到模式编码数组C；

步骤10：遍历数组C；

步骤11：查询模式编码是否存在；

若存在，调出之前的模式节点p，将p加入初始化节点关系待更新组P；

若不存在，跳过该模式编码，继续遍历过程；

步骤12：完成G_P遍历，对P向下扩展模式节点，形成新节点关系待更新组P’；

步骤13：对对象lc关联搜索；具体实现包括以下子步骤：

步骤13.1：输入参数lc、ls、lr和F；

步骤13.2：判断lr是否为真；

若是，则遍历P，调用关联图搜索得到关联模式P’，将P’加入P；

若不是，则判断模式节点集合P是否为空；

若集合P是空，令F等于当前模式定义节点的要素，调用模式分解查询算法更新搜索；

若不是，令F等于P中未用到的要素集合，调用模式分解查询算法搜索。

步骤14：返回P’对应的模式节点编码集合。

应当理解的是，本说明书未详细阐述的部分均属于现有技术。

应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。