一种基于前缀树的区域编码查询方法、系统及其用途

摘要

本发明公开了一种基于前缀树的区域编码查询方法、系统及其用途，将所有终端连接至服务端，并向服务端发送心跳包，所述心跳包中携带终端的数据源对象编码；服务端接收心跳包，解析心跳包并从数据源对象编码中提取区域编码；服务端建立前缀树，所述前缀树以区域编码为key、以终端在服务端的连接信息和终端基本信息为值；需要向某区域发送信息时，通过区域编码在前缀树中查询该区域内的终端基本信息。本发明提供一种基于前缀树的区域编码查询方法、系统及其用途，以解决现有技术中区域编码查询方式浪费储存空间、查询过程繁琐、效率低下的问题，实现节省存储空间、提升查询效率的目的。

权利要求

1.一种基于前缀树的区域编码查询方法，其特征在于，用于应急广播系统中向指定区域发送广播消息，包括：S1、所有终端连接至服务端，并向服务端发送心跳包，所述心跳包中携带终端的数据源对象编码；所述数据源对象编码由以下部分顺序组成：1位级别识别码+12位区域编码+4位资源类型编码+2位类型顺序码+2位子类型码+2位子类型顺序码；

S2、服务端接收心跳包，解析心跳包并从数据源对象编码中提取区域编码；

S3、服务端建立前缀树，所述前缀树以区域编码为key、以终端在服务端的连接信息和终端基本信息为值；

所述前缀树以区域编码为key的方法包括：将12位的区域编码从左往右依次插入前缀树中，一个节点放入一个数字，第一位数作为根节点，后面的数字依次作为子节点、直至将区域编码完全插入到前缀树中，并将终端基本信息放在最后的叶子节点中；

S4、需要向某区域发送信息时，通过区域编码在前缀树中查询该区域内的终端基本信息。

2.根据权利要求1所述的一种基于前缀树的区域编码查询方法，其特征在于，所述终端基本信息存储在前缀树的叶子节点上。

3.根据权利要求1所述的一种基于前缀树的区域编码查询方法，其特征在于，步骤S4中通过区域编码在前缀树中查询该区域内的终端基本信息的方法包括：服务端根据上游发布的区域编码查询前缀树，从左往右依次查询各个节点，若能够查询到，则获取对应的终端基本信息，若查询不到则返回一个空集。

4.基于权利要求1～3中任一项所述的区域编码查询方法的一种基于前缀树的区域编码查询系统，其特征在于，包括：终端，用于向服务端发送携带自身数据源对象编码的心跳包；

服务端，用于接收并解析从终端发来的心跳包，并从心跳包内的数据源对象编码中提取区域编码；

建模模块，用于在服务端建立前缀树，所述前缀树以各终端的区域编码为key、以各终端在服务端的连接信息和终端基本信息为值；

查询模块，用于通过区域编码在前缀树中查询该区域内的终端基本信息。

5.根据权利要求4所述的一种基于前缀树的区域编码查询系统，其特征在于，所述数据源对象编码由以下部分顺序组成：1位级别识别码+12位区域编码+4位资源类型编码+2位类型顺序码+2位子类型码+2位子类型顺序码。

6.根据权利要求4所述的一种基于前缀树的区域编码查询系统，其特征在于，建模模块中，前缀树以区域编码为key的方法包括：将12位的区域编码从左往右依次插入前缀树中，一个节点放入一个数字，第一位数作为根节点，后面的数字依次作为子节点、直至将区域编码完全插入到前缀树中，并将终端基本信息放在最后的叶子节点中；

查询模块中，通过区域编码在前缀树中查询该区域内的终端基本信息的方法包括：服务端根据上游发布的区域编码查询前缀树，从左往右依次查询各个节点，若能够查询到，则获取对应的终端基本信息，若查询不到则返回一个空集。

说明书

一种基于前缀树的区域编码查询方法、系统及其用途

技术领域

[0001] 本发明涉及数据查询领域，具体涉及一种基于前缀树的区域编码查询方法、系统及其用途。

背景技术

[0002] 在某些需要用到根据区域编码查询数据的情况，如应急广播系统中向某个区域发送广播消息，就需要根据区域编码查询对应的喇叭等广播设备，现有的解决方案大致以人工建表储存、人工查询为主，不仅浪费储存空间、而且查询过程繁琐、效率低下。

发明内容

[0003] 本发明提供一种基于前缀树的区域编码查询方法、系统及其用途，以解决现有技术中区域编码查询方式浪费储存空间、查询过程繁琐、效率低下的问题，实现节省存储空间、提升查询效率的目的。

[0004] 本发明通过下述技术方案实现：

[0005] 一种基于前缀树的区域编码查询方法，包括：

[0006] S1、所有终端连接至服务端，并向服务端发送心跳包，所述心跳包中携带终端的数据源对象编码；

[0007] S2、服务端接收心跳包，解析心跳包并从数据源对象编码中提取区域编码；

[0008] S3、服务端建立前缀树，所述前缀树以区域编码为key、以终端在服务端的连接信息和终端基本信息为值；

[0009] S4、需要向某区域发送信息时，通过区域编码在前缀树中查询该区域内的终端基本信息。

[0010] 针对现有技术中区域编码查询方式浪费储存空间、查询过程繁琐、效率低下的问题，本发明首先提出一种基于前缀树的区域编码查询方法，本方法首先将分布在各区域的终端连接之服务端，每个终端均向服务端发送心跳包，心跳包内包含了该终端的数据源对象编码。服务端在接收到任意一个心跳包后，对该心跳包进行解析，获取数据源对象编码、并从中提取出区域编码。之后由服务端建立前缀树，本申请中建立的前缀树以区域编码为key、以终端在服务端的连接信息和终端基本信息为值进行建立，即是将区域编和连接信息、终端基本信息键值对组合放到前缀树中，得到前缀树的完整结构。本申请基于前述步骤首先建立起前缀树，然后在需要向某些指定区域发送信息时，通过该指定区域的区域编码在前缀树中查询该区域内的终端基本信息即可。本申请将前缀树纳入区域编码的查询运用中，解决了现有技术中区域编码查询方式浪费储存空间、查询过程繁琐、效率低下的问题，充分利用了区域编码具有分级结构的特点和前缀树的树形结构的父子节点关系，使得区域编码的树状结构关系与前缀树的树形结构完美匹配，只需利用区域编码即可，无需额外进行其它分类建表等操作，不仅节省存储空间还可以显著提升查询效率。

[0011] 进一步的，所述数据源对象编码包括级别识别码、区域编码、资源类型编码、类型顺序码、子类型码和子类型顺序码。

[0012] 进一步的，所述数据源对象编码由以下部分顺序组成：1位级别识别码+12位区域编码+4位资源类型编码+2位类型顺序码+2位子类型码+2位子类型顺序码。

[0013] 进一步的，所述终端基本信息存储在前缀树的叶子节点上。

[0014] 进一步的，所述前缀树以区域编码为key的方法包括：将12位的区域编码从左往右依次插入前缀树中，一个节点放入一个数字，第一位数作为根节点，后面的数字依次作为子节点、直至将区域编码完全插入到前缀树中，并将终端基本信息放在最后的叶子节点中。本方案中前缀树的设置方法能够充分利用前缀树的树形结构，使该树形结构与区域编码的树状结构关系实现完美的结合。

[0015] 进一步的，步骤S4中通过区域编码在前缀树中查询该区域内的终端基本信息的方法包括：服务端根据上游发布的区域编码查询前缀树，从左往右依次查询各个节点，若能够查询到，则获取对应的终端基本信息，若查询不到则返回一个空集。通过本方案的查询方法，将指定区域内的终端基本信息统一收集，进而服务端即可向该指定区域内的所有终端统一发送相关信息。

[0016] 一种基于前缀树的区域编码查询系统，包括：

[0017] 终端，用于向服务端发送携带自身数据源对象编码的心跳包；

[0018] 服务端，用于接收并解析从终端发来的心跳包，并从心跳包内的数据源对象编码中提取区域编码；

[0019] 建模模块，用于在服务端建立前缀树，所述前缀树以各终端的区域编码为key、以各终端在服务端的连接信息和终端基本信息为值；

[0020] 查询模块，用于通过区域编码在前缀树中查询该区域内的终端基本信息。

[0021] 进一步的，所述数据源对象编码由以下部分顺序组成：1位级别识别码+12位区域编码+4位资源类型编码+2位类型顺序码+2位子类型码+2位子类型顺序码。

[0022] 进一步的，建模模块中，前缀树以区域编码为key的方法包括：将12位的区域编码从左往右依次插入前缀树中，一个节点放入一个数字，第一位数作为根节点，后面的数字依次作为子节点、直至将区域编码完全插入到前缀树中，并将终端基本信息放在最后的叶子节点中；

[0023] 查询模块中，通过区域编码在前缀树中查询该区域内的终端基本信息的方法包括：服务端根据上游发布的区域编码查询前缀树，从左往右依次查询各个节点，若能够查询到，则获取对应的终端基本信息，若查询不到则返回一个空集。

[0024] 基于上述区域编码查询方法的用途：用于应急广播系统中向某个区域发送广播消息，以此填补现有技术的空白。

[0025] 本发明与现有技术相比，具有如下的优点和有益效果：

[0026] 1、本发明一种基于前缀树的区域编码查询方法、系统及其用途，充分利用了区域编码具有分级结构的特点和前缀树的树形结构的父子节点关系，使得区域编码的树状结构关系与前缀树的树形结构完美匹配，只需利用区域编码即可，无需额外进行其它分类建表等操作，不仅节省存储空间还可以显著提升查询效率。

[0027] 2、本发明一种基于前缀树的区域编码查询方法、系统及其用途，其中前缀树的设置方法能够充分利用前缀树的树形结构，使该树形结构与区域编码的树状结构关系实现完美的结合。

[0028] 3、本发明一种基于前缀树的区域编码查询方法、系统及其用途，能够高效适用于应急广播系统中向某个区域发送广播消息，填补了现有技术的空白。

[0029] 4、本发明一种基于前缀树的区域编码查询方法、系统及其用途，优化了与行政区域编码相关联的数据的存储与查询效率。

附图说明

[0030] 此处所说明的附图用来提供对本发明实施例的进一步理解，构成本申请的一部分，并不构成对本发明实施例的限定。在附图中：

[0031] 图1为本发明具体实施例的流程示意图；

[0032] 图2为本发明具体实施例的系统示意图；

[0033] 图3为本发明具体实施例中区域编码查询的具体示意图；

[0034] 图4为本发明具体实施例中前缀树的示意图。

具体实施方式

[0035] 为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施例和附图，对本发明作进一步的详细说明，本发明的示意性实施方式及其说明仅用于解释本发明，并不作为对本发明的限定。在本申请的描述中，需要理解的是，术语“前”、“后”、“左”、“右”、“上”、“下”、“竖直”、“水平”、“高”、“低”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本申请保护范围的限制。

[0036] 实施例1：

[0037] 如图1所示的一种基于前缀树的区域编码查询方法，用于应急广播领域内：

[0038] S1：广播终端设备连接服务器，并发送心跳包，心跳包中会携带终端设备的数据源对象编码，数据源对象编码的组成部分为1位级别识别码+12位行政区域编码+4位资源类型编码+2位类型顺序码+2位子类型码+2位子类型顺序码。

[0039] S2：基于步骤S1，服务端接收到终端心跳包，解析心跳包并取出行政区域编码，将行政区域编码作为key，终端在服务器中的连接信息与终端基本信息作为值，将这个键值对组合放到前缀树中，只有前缀树的叶子节点才会存储终端信息，将12位的区域编码从左往右依次插入前缀树中，一个节点放入一个数字，第一位数作为根节点，后面的数字依次作为子节点，以此类似的步骤将区域编码插入到前缀树中，并将终端设备的信息放在最后的叶子节点中，解析后服务器存储各个终端的信息。

[0040] S3：向某个区域发送广播消息时，通过区域编码在前缀树中查询终端设备信息，根据上游发布的区域编码查询之前存储的终端信息，从左往右依次各个节点查询，最终查询到终端信息，若查询不到返回一个空集。

[0041] S4：基于步骤4，向终端设备发送广播消息。

[0042] 本实施例中使用的行政区域编码，本身是政府公布的行政区划分，具有分级结构，所以可以按照分级的方式进行存储与查询，对不同级的区域编码查询不同的表。在此基础上可以将区域编码数据放在一个表中，为每个节点添加执行其上一级的字段，组成树状的逻辑结构，这样可以免去查不同表的判断，但需要先用行政区编码生成树状结构的表。

[0043] 进一步进行优化处理，行政区域编码本身就包含了树形结构的特点，可以利用这个特点按前缀树(Trie)的方式进行存储，使用前缀树存储行政区域编码相关的数据，只需要区域编码即可，无需其它的操作，不仅节省存储空间还可以提升查询效率。

[0044] 实施例2：

[0045] 一种基于前缀树的区域编码查询系统，如图2所示，包括：

[0046] 终端，用于向服务端发送携带自身数据源对象编码的心跳包；

[0047] 服务端，用于接收并解析从终端发来的心跳包，并从心跳包内的数据源对象编码中提取区域编码；

[0048] 建模模块，用于在服务端建立前缀树，所述前缀树以各终端的区域编码为key、以各终端在服务端的连接信息和终端基本信息为值；

[0049] 查询模块，用于通过区域编码在前缀树中查询该区域内的终端基本信息。

[0050] 优选的，所述数据源对象编码由以下部分顺序组成：1位级别识别码+12位区域编码+4位资源类型编码+2位类型顺序码+2位子类型码+2位子类型顺序码。

[0051] 优选的，建模模块中，前缀树以区域编码为key的方法包括：将12位的区域编码从左往右依次插入前缀树中，一个节点放入一个数字，第一位数作为根节点，后面的数字依次作为子节点、直至将区域编码完全插入到前缀树中，并将终端基本信息放在最后的叶子节点中；

[0052] 查询模块中，通过区域编码在前缀树中查询该区域内的终端基本信息的方法包括：服务端根据上游发布的区域编码查询前缀树，从左往右依次查询各个节点，若能够查询到，则获取对应的终端基本信息，若查询不到则返回一个空集。

[0053] 本实施例的系统可用于实现如实施例1中所记载的方法步骤。

[0054] 实施例3：

[0055] 应急广播系统中的指定区域广播方法，如图3与图4所示：

[0056] 在应急广播系统中，需要根据行政区域编码发送广播消息，将连接到服务端的终端设备按区域编码组成前缀树，查询时只需按照所需查询行政区的区域编码进行查询，就能查到该区域下的所有终端设备信息，然后再向设备发送广播消息。具体的：

[0057] 以武汉市行政区为例进行说明，现有6个终端设备用ti表示，其中i＝[1,6]，其中t1,t2,t3的资源编码分别为64201060120010314010101、64201060120010314010102、64201060120010314010103，它们的所在区域的行政区编码均为420106012001，表示这些设备在湖北省(42)武汉市(01)武昌区(06)水果湖街(012)东湖路社区(001)；其中t4、t5、t6的资源编号分别为64201060110030314010101、64201060110030314010102、
64201060110030314010103，表示这些设备在湖北省(42)武汉市(01)武昌区(06)中南路街(011)长春社区(001)。

[0058] 当终端设备t1连接到服务器并发送心跳包后，服务端解析出该设备的资源编码并提取其区域编码，如t1的区域编码为420106012001，从左往右遍历t1的区域编码，第一位的4作为前缀树根节点的子节点(n1)插入到前缀树中，将第二位2作为n1子节点(n2)插入到前缀树中，将第三位0作为n2的子节点插入到前缀树中，以此类似的步骤将区域编码插入到前缀树中，并将终端设备的信息放在最后的叶子节点中。

[0059] 当终端设备t2连接到服务器并发送心跳包后，如t2的区域编码也为420106012001，同样从左往右遍历t2的区域编码，第一位为4，当检查到前缀树的根节点有4这个节点时，继续检查第二位2，发现4的子节点中存在2这个节点，则继续检查第三位，依次检查区域编码中的其它位，由于t2的区域编码与t1的区域编码相同，因此t2的终端设备信息也放在最后的叶子节点中。

[0060] 当终端设备t4连接到服务器并发送心跳包后，如t4的区域编码也为420106011003，同样从左往右遍历t4的区域编码，前8位与t2的步骤相同，由于节点n8的子节点中没有1，因此将第9位1作为n8的新的子节点插入到前缀树中，依次将区域编码的其它位插入到前缀树中。

[0061] 服务端在收到上游服务的广播指令时，根据指令中的目标区域编码，在前述使用终端设备区域编码构建的前缀树T中查询所有目标区域的终端设备信息。如广播指令中的目标区域编码为420106012，搜索前缀树T的根节点中是否有值为区域编码第一个值(4)的节点，如果存在则继续在刚找到的节点中查找有值为区域编码第二个值(2)的节点，依次查区域编码的其它位，如区域编码所有位都能在前缀树T中找到，在最后查到的节点的所有子树中，查找所有叶子节点中保持的终端信息；如在查询过程中没有查到节点则终止搜索直接返回一个空集。

[0062] 优选的，本实施例中行政区域编码按照省、市、区、街道、社区这几个级别进行区分。

[0063] 以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

[0064] 需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其它变体，意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。此外，在本文中使用的术语“连接”在不进行特别说明的情况下，可以是直接相连，也可以是经由其他部件间接相连。