一种知识图谱数据的多路归并方法、装置、设备及介质

1.本发明涉及数据存储技术领域，具体而言，涉及一种知识图谱数据的多路归并方法、装置、设备及介质。


背景技术：

2.知识图谱作为目前主流的知识存储介质之一，随着知识构建过程的自动化和作为资源库的互联网数据的膨胀，知识图谱数据量出现了大规模增长。利用紧凑存储结构和列存储方法可以较好的利用数据之间的关联性实现大规模知识图谱数据的压缩表示，一般参与压缩的数据规模越大，数据压缩率就越高，但相对地要求更高的临时工作空间。在多路压缩图谱数据的归并过程中，如果需要将全量的数据加载进入内存，则数据压缩的成本会被大幅度放大，相较于磁盘成本的减小，内存开销的提升可能使得数据压缩优化得不偿失。


技术实现要素：

3.本发明的目的在于提供一种知识图谱数据的多路归并方法、装置、设备及介质，以改善上述问题。为了实现上述目的，本发明采取的技术方案如下：
4.第一方面，本技术提供了一种知识图谱数据的多路归并方法，包括：
5.获取待归并的知识图谱数据，将所述识图谱数据映射为多个前缀树，所述前缀树包括多个结点，且结点与结点之间设置有前缀字符，每个前缀字符覆盖有至少一个子树；
6.构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的字符数组中；
7.计算每个位向量的超限值，基于所述超限值使用预设的数据结构为位向量建立索引；
8.从字符数组中读取前缀字符，并利用所述索引抽取所读取到的前缀字符所覆盖的子树的拓扑数据，直到所有的前缀字符读取完毕；
9.将抽取到的子树的拓扑数据构建为临时数组，归还子树所占用的位向量。
10.第二方面，本技术还提供了一种知识图谱数据的多路归并装置，包括：
11.获取模块：用于获取待归并的知识图谱数据，将所述识图谱数据映射为多个前缀树，所述前缀树包括多个结点，且结点与结点之间设置有前缀字符，每个前缀字符覆盖有至少一个子树；
12.构建模块：用于构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的字符数组中；
13.计算模块：用于计算每个位向量的超限值，基于所述超限值使用预设的数据结构为位向量建立索引；
14.读取模块：用于从字符数组中读取前缀字符，并利用所述索引抽取所读取到的前
缀字符所覆盖的子树的拓扑数据，直到所有的前缀字符读取完毕；
15.归还模块：用于将抽取到的子树的拓扑数据构建为临时数组，归还子树所占用的位向量。
16.第三方面，本技术还提供了一种知识图谱数据的多路归并设备，包括：
17.存储器，用于存储计算机程序；
18.处理器，用于执行所述计算机程序时实现所述知识图谱数据的多路归并方法的步骤。
19.第四方面，本技术还提供了一种可读存储介质，所述可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现上述基于知识图谱数据的多路归并方法的步骤。
20.本发明的有益效果为：
21.本发明通过采用基于位域的深度优先树路径压缩方法，实现了紧凑编码及知识图谱数据中实体和关系属性的自索引压缩，优化了多路精简知识图谱数据归并过程中内存开销过大的问题，最终实现归并紧凑图谱数据的有序存储。
22.本发明的其他特征和优点将在随后的说明书阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明实施例了解。本发明的目的和其他优点可通过在所写的说明书、权利要求书、以及附图中所特别指出的结构来实现和获得。
附图说明
23.为了更清楚地说明本发明实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本发明的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。
24.图1为本发明实施例中所述的知识图谱数据的多路归并方法流程示意图；
25.图2为本发明实施例中前缀树的结构示意图；
26.图3为本发明实施例中dfuds t i re编码示意图；
27.图4为本发明实施例中子树所对应的数据在位向量中的分布区间示意图；
28.图5为本发明实施例中待归并的子树结构示意图；
29.图6为本发明实施例中所述的知识图谱数据的多路归并装置结构示意图；
30.图7为本发明实施例中所述的知识图谱数据的多路归并设备结构示意图。
31.图中标记：
32.01、获取模块；02、构建模块；021、第一构建单元；022、遍历单元；023、第一存储单元；024、分割单元；03、计算模块；031、采集单元；032、第一获取单元；033、第二构建单元；034、索引建立单元；04、读取模块；041、第二获取单元；042、判断单元；05、归还模块；051、归还模块；052、第二存储单元；
33.800、知识图谱数据的多路归并设备；801、处理器；802、存储器；803、多媒体组件；804、i/o接口；805、通信组件。
具体实施方式
34.为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本发明实施例的组件可以以各种不同的配置来布置和设计。因此，以下对在附图中提供的本发明的实施例的详细描述并非旨在限制要求保护的本发明的范围，而是仅仅表示本发明的选定实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
35.应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。同时，在本发明的描述中，术语“第一”、“第二”等仅用于区分描述，而不能理解为指示或暗示相对重要性。
36.实施例1：
37.本实施例提供了一种知识图谱数据的多路归并方法。
38.参见图1，图中示出了本方法包括：
39.s1.获取待归并的知识图谱数据，将所述识图谱数据映射为多个前缀树，所述前缀树包括多个结点，且结点与结点之间设置有前缀字符，具体的，所述父结点与子结点之间设置有前缀字符，每个前缀字符覆盖有至少一个子树，如图2所示；
40.基于以上实施例，本方法还包括：
41.s2.构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的字符数组中；
42.具体的，所述步骤s2包括以下步骤：
43.s21.构建位向量，并将所述位向量初始化：
44.s22.获取前缀树，从前缀树的根结点开始遍历，将遍历到的结点以字符串的形式插入位向量中；
45.(1)初始化位向量bv，并插入“110”位至序列头部，用于维持位向量内0和1的平衡；
46.(2)从根节点深度优先遍历前缀树，假如遍历到的结点n的度为d，则将1d0插入bv的尾部，直到遍历完整棵前缀树树为止，除位向量头部的“110”外，其余的每个1都代表一个父子结点之间的边，每个0都代表一个结点；
47.(3)为bv初始化rank和se l ect等操作的索引。
48.本实施例中，通过采用位向量bv表示前缀树，实现了基于dfuds(depth-f i rst-unary-degree-sequence)数组的编码方式压缩前缀树，得到一种静态数据结构dfuds tr i e，编码后bv的长度为2n+2，其中n为结点数量。
49.s23.将结点之间的前缀字符首尾相邻存储在字符数组中；
50.具体的，将每个边所对应的前缀字符串首尾相邻存储在l abe l字符数组中；为了分辨出每个边对应的字符串片段，使用位向量seg标识每个字符串的起点和终点，使用个位向量term标识树结点是否为终态，由于实际应用中位向量seg和term较为稀疏，所以采用rrr格式存储，以便进一步提升其压缩率，如图3所示。
51.s24.将一个结点对应的位向量分割为多个区间，将一个结点所覆盖的所有子树的
树拓扑数据依次存储在多个区间内；
52.由于dfuds编码过程中按照深度优先的顺序填充位向量，所以dfuds编码有以下性质：
53.(1)任一子树在位向量中都是物理连续的；
54.(2)在任一子树序列化后对应的二进制序列中，0的数量一定比1的数量多1。在所述二进制序列中，首元素的超限值一定比尾元素的超限值大1，进而可以使用f i ndc l ose方法在二进制序列中定位任一子树所对应的区间。
55.请参阅图4，图中展示了前缀树的子树所对应的数据在位向量中的分布区间，两棵子树的数据有序存储且邻近。考虑使用dfuds数组作为前缀树的拓扑编码实现字符串集合顺序遍历的场景，即使深度优先遍历要求下探到最深层次，由于一个子树对应的数据区间连续且子树内结点和边对应的标签也与之对齐存储，因此可以将基于前缀树表示的先序遍历映射为dfuds数组内的多次局部顺序读取。且由于任一子树的表示都为连续的，所以一次读取的粒度为子树级别。
56.综上，通过使用基于dfuds编码的前缀树精简表示字符串序列，可以将相同前缀字符串的扫描映射为一次局部顺序读取，使内存访问的局部性较优。
57.基于以上实施例，本方法还包括：
58.s3.所述计算每个位向量的超限值，基于所述超限值使用预设数据结构为位向量建立索引；
59.具体的，所述步骤s3包括：
60.s31.在所述位向量的区间内采集超限值，具体的，对每个位bv[i]，计算一个超限值，即bv[0，i)区间内1和0数量的差值所有超限值都由excess数组管理，excess数组不需要显式存储，其中，i表示叶子节点；
[0061]
s32.获取采集到的超限值中的最大值和最小值；
[0062]
s33.将所述超限值中的最大值和最小值作为节点构建完全二叉树；
[0063]
本实施例中，采用range m i n-max tree(rmm-tree)完全二叉树，它的每个节点可以看作是对任意一个区间内待索引数据的采样结果，假设分块大小为b。由于完全二叉树管理的数据为bv，因此第i个叶子节点负责管理的区间是bv[(i-1)*b,i*b)，非叶子节点负责管理它所有孩子节点的区间。
[0064]
s34.利用所述完全二叉树为位向量建立索引，所述索引为f i ndc l ose(i)和f i ndopen(i)操作，f i ndc l ose(i)表示在excess[]右侧查找第一个比当前值小1的位置，f i ndopen(i)表示在excess[]左侧查找第一个比当前值大1的位置。
[0065]
基于以上实施例，本方法还包括：
[0066]
s4.从字符数组中读取前缀字符，并利用所述索引抽取所读取到的前缀字符所覆盖的子树的拓扑数据，直到所有的前缀字符读取完毕，本实施例中，为了最大化提升利用资源，应尽量提升由于构建子树的临时工作空间的内存占用率，所以需要确定待构建数据所对应的公共前缀。首先在构建阶段，在dfuds tr i e内记录某一前缀所管理的字符串的容量估计，由于同一前缀下的字符串容量通常不会超过单机内存的承载能力，因此选择只记录第一级和第二级前缀所对应的子树容量。
[0067]
具体的，所述步骤s4包括：
[0068]
s41.获取每个子树的容量，并根据每个子树的容量计算属于一个前缀字符的所有子树的容量总和；
[0069]
首先需要按照字符序顺序遍历第一级前缀，在dfuds数组中记录一级前缀和与之对应的字符和其他标记位。请参阅图5，图中记录的一级前缀分别为a，b和c，将所有参与归并的dfuds tr i e中对应a，b和c前缀的子树容量相加，并与配置文件中的预设内存占用阈值比较。
[0070]
s42.判断所述容量总和是否超过预设内存占用阈值：
[0071]
若不超过，则将所述前缀字符作为公共前缀，抽取所述公共前缀所包含的子树的拓扑数据：
[0072]
s421.根据子树所位于的位向量的超限值，利用索引定位至子树所在的位向量的区间：
[0073]
s422.从位向量的区间中抽取子树的拓扑结构，并将子树的拓扑结构转换为拓扑向量；在抽取过程中需要将l abe l字符数组、dfuds和term等位向量的对应部分读取至内存并构建为子树的dfuds tr i e；具体包括：
[0074]
(1)首先抽取子树的拓扑结构。假设树拓扑结构由向量dfuds表示，树结点在位向量中对应的下标是root，则可以从dfuds向量中抽取第i个子树的同态表示。以下操作中，如未说明待操作的位向量名称，则默认对象为dfuds树拓扑向量。
[0075]
第i个子树在位向量中的起始坐标为：
[0076]
findclose(select0(rank0(root)+1)-i)+1
[0077]
式中，select和rank均表示查询操作；
[0078]
相对的，第i个子树在位向量中的终止坐标为：
[0079]
findclose(select0(rank0(root)+1)-i-i)+1
[0080]
经过子树抽取后，子树的拓扑结构可以由dfuds[l,
…
,r]向量表示,l和r均表示子树的拓扑结构；
[0081]
(2)由抽取得到的子树拓扑，连续读取原始紧凑表示中部分位向量和标签，用于与抽取得到的树拓扑编码对齐。子树seg位向量的抽取中，在原始seg位向量中的起始坐标segbegin＝seg.select1(rank1(l))；相对的，子树seg位向量在原始seg位向量的终止坐标segend＝seg.select1(rank1(r))；
[0082]
(3)最后需要抽取子树的标签数据，子树标签数据在原始标签数据中起始坐标为：seg.rank0(segbegin)；在原始标签数据的终止坐标为：seg.rank0(segend)；
[0083]
s423.根据所述拓扑向量从位向量中读取子树的拓扑数据，所述拓扑数据包括拓扑结构编码和标签数据；
[0084]
s424.将所述拓扑结构编码和标签数据与子树的拓扑结构对齐。
[0085]
若超过，则放弃所述前缀字符，继续读取下一个前缀字符。
[0086]
本实施例中，dfuds tr i e中任一拥有相同前缀的字符串的集合所对应的树拓扑结构编码和与之对齐的标签数据都是物理邻近的，分别可以由一次顺序读取加载至内存。在一次归并中，需要分别抽取具有相同前缀或前缀之间有包含关系的多份数据参与，以此生成一份临时数组用于构建归并结果，即与dfuds tr i e同态的子树。首先利用子树区间内超限值的性质，使用f i ndc l ose方法定位任意一个子树在dfuds编码中的区间，再利
用以此生成一份临时数组用于构建归并结果中各类位向量和标签与dfuds编码对齐的性质，连续顺序读取原始dfuds tr i e中的部分位向量和标签，用于与抽取后的dfuds编码对齐。由于位向量分割后，原本存在于磁盘上的索引都立刻失效，所以需要对子树中的树操作建立新的索引。
[0087]
基于以上实施例，本方法还包括：
[0088]
s5.将抽取到的子树的拓扑数据构建为临时数组，归还子树所占用的位向量；
[0089]
具体的，所述步骤s5包括：
[0090]
s51.将所述临时数组进行紧凑编码，归还子树所占用的位向量，得到归并后的子树；采用dfud的编码形式压缩子树和临时数组，临时数组构建完毕后，由于子树再也不会在归并过程中被访问，所以子树对应的内存可以得到安全释放。
[0091]
s52.将所有的前缀字符读取完毕后，为每个前缀字符创建一个二进制表，并将归并后的全部子树存入对应的二进制表中。
[0092]
由于临时数组全部由内存存储，支持快速的随机查询和匹配，因此采用递归搜索待构建数据的最长公共前缀串，将前缀串而非前缀字母作为压缩前缀树中节点之间保存的导航数据，通过上述操作可以有效的降低由临时数组构建而成的dfuds tr i e的高度。一个虚拟前缀树结点在对应临时数组中的一个二维范围为[(r1，c1)，(r2，c2)]，该范围内的前缀串都共享相同的前缀，在扫描完毕一组包含公共前缀的前缀串之后，继续扫描该公共前缀的公共串以得到其最大长度，由于按字符序排序的数组中，共享相同前缀且排序最小的前缀串一定最短，因此使用字符序最小的前缀串作为基准，对由虚拟结点代表的子串集合执行扫描，从而实现dfuds tr i e归并过程中临时数组的最长前缀的获取。
[0093]
实施例2：
[0094]
如图6所示，本实施例提供了一种知识图谱数据的多路归并装置，所述装置包括：
[0095]
获取模块01：用于获取待归并的知识图谱数据，将所述识图谱数据映射为多个前缀树，所述前缀树包括多个结点，且结点与结点之间设置有前缀字符，每个前缀字符覆盖有至少一个子树；
[0096]
构建模块02：用于构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的字符数组中；
[0097]
计算模块03：用于计算每个位向量的超限值，基于所述超限值使用预设的数据结构为位向量建立索引；
[0098]
读取模块04：用于从字符数组中读取前缀字符，并利用所述索引抽取所读取到的前缀字符所覆盖的子树的拓扑数据，直到所有的前缀字符读取完毕；
[0099]
归还模块05：用于将抽取到的子树的拓扑数据构建为临时数组，归还子树所占用的位向量。
[0100]
基于以上实施例,所述构建模块02包括：
[0101]
第一构建单元021：用于构建位向量，并将所述位向量初始化；
[0102]
遍历单元022：用于获取前缀树，从前缀树的根结点开始遍历，将遍历到的结点以字符串的形式插入位向量中；
[0103]
第一存储单元023：用于将结点之间的前缀字符首尾相邻存储在字符数组中；
[0104]
分割单元024：用于将一个结点对应的位向量分割为多个区间，将一个结点所覆盖的所有子树的树拓扑数据依次存储在多个区间内。
[0105]
基于以上实施例,所述计算模块03包括：
[0106]
采集单元031：用于在所述位向量的区间内采集超限值；
[0107]
第一获取单元032：用于获取采集到的超限值中的最大值和最小值；
[0108]
第二构建单元033：用于将所述超限值中的最大值和最小值作为节点构建完全二叉树的节点上；
[0109]
索引建立单元034：用于利用所述完全二叉树为位向量建立索引。
[0110]
基于以上实施例,所述读取模块04包括：
[0111]
第二获取单元041：用于获取每个子树的容量，并根据每个子树的容量计算属于一个前缀字符的所有子树的容量总和；
[0112]
判断单元042：用于判断所述容量总和是否超过预设内存占用阈值：
[0113]
若不超过，则将所述前缀字符作为公共前缀，抽取所述公共前缀所包含的子树的拓扑数据；
[0114]
若超过，则放弃所述前缀字符，继续读取下一个前缀字符。
[0115]
基于以上实施例,所述归还模块05包括：
[0116]
归还模块051：用于将所述临时数组进行紧凑编码，归还子树所占用的位向量，得到归并后的子树；
[0117]
第二存储单元052：用于将所有的前缀字符读取完毕后，为每个前缀字符创建一个二进制表，并将归并后的全部子树存入对应的二进制表中。
[0118]
需要说明的是，关于上述实施例中的装置，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。
[0119]
实施例3：
[0120]
相应于上面的方法实施例，本实施例中还提供了一种知识图谱数据的多路归并设备，下文描述的一种知识图谱数据的多路归并设备与上文描述的一种知识图谱数据的多路归并方法可相互对应参照。
[0121]
图7是根据示例性实施例示出的一种知识图谱数据的多路归并设备800的框图。如图7所示，该知识图谱数据的多路归并设备800可以包括：处理器801，存储器802。该知识图谱数据的多路归并设备800还可以包括多媒体组件803，i/o接口804，以及通信组件805中的一者或多者。
[0122]
其中，处理器801用于控制该知识图谱数据的多路归并设备800的整体操作，以完成上述的知识图谱数据的多路归并方法中的全部或部分步骤。存储器802用于存储各种类型的数据以支持在该知识图谱数据的多路归并设备800的操作，这些数据例如可以包括用于在该知识图谱数据的多路归并设备800上操作的任何应用程序或方法的指令，以及应用程序相关的数据，例如联系人数据、收发的消息、图片、音频、视频等等。该存储器802可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，例如静态随机存取存储器(stat i crandom access memory，简称sram)，电可擦除可编程只读存储器(e l ectr i ca l l y erasab l e programmab l e read-on l y memory，简称eeprom)，可擦除可编程只读存储器(erasab l e programmab l eread-on l y memory，简称eprom)，可编程只
读存储器(programmab l eread-on l y memory，简称prom)，只读存储器(read-on l y memory，简称rom)，磁存储器，快闪存储器，磁盘或光盘。多媒体组件803可以包括屏幕和音频组件。其中屏幕例如可以是触摸屏，音频组件用于输出和/或输入音频信号。例如，音频组件可以包括一个麦克风，麦克风用于接收外部音频信号。所接收的音频信号可以被进一步存储在存储器802或通过通信组件805发送。音频组件还包括至少一个扬声器，用于输出音频信号。i/o接口804为处理器801和其他接口模块之间提供接口，上述其他接口模块可以是键盘，鼠标，按钮等。这些按钮可以是虚拟按钮或者实体按钮。通信组件805用于该知识图谱数据的多路归并设备800与其他设备之间进行有线或无线通信。无线通信，例如w i-f i，蓝牙，近场通信(near f i e l dcommun i cat i on，简称nfc)，2g、3g或4g，或它们中的一种或几种的组合，因此相应的该通信组件805可以包括：wi-f i模块，蓝牙模块，nfc模块。
[0123]
在一示例性实施例中，知识图谱数据的多路归并设备800可以被一个或多个应用专用集成电路(app l i cat i on spec i f i c i ntegrated c i rcu i t，简称as i c)、数字信号处理器(d i g i ta l s i gna l processor，简称dsp)、数字信号处理设备(d i g i ta l s i gna l process i ng dev i ce，简称dspd)、可编程逻辑器件(programmab l e log i c dev i ce，简称pld)、现场可编程门阵列(f i e l d programmab l e gate ar ray，简称fpga)、控制器、微控制器、微处理器或其他电子元件实现，用于执行上述的知识图谱数据的多路归并方法。
[0124]
在另一示例性实施例中，还提供了一种包括程序指令的计算机可读存储介质，该程序指令被处理器执行时实现上述的知识图谱数据的多路归并方法的步骤。例如，该计算机可读存储介质可以为上述包括程序指令的存储器802，上述程序指令可由知识图谱数据的多路归并设备800的处理器801执行以完成上述的知识图谱数据的多路归并方法。
[0125]
实施例4：
[0126]
相应于上面的方法实施例，本实施例中还提供了一种可读存储介质，下文描述的一种可读存储介质与上文描述的一种知识图谱数据的多路归并方法可相互对应参照。
[0127]
一种可读存储介质，可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现上述方法实施例的知识图谱数据的多路归并方法的步骤。
[0128]
该可读存储介质具体可以为u盘、移动硬盘、只读存储器(read-on l y memory，rom)、随机存取存储器(random access memory，ram)、磁碟或者光盘等各种可存储程序代码的可读存储介质。
[0129]
以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
[0130]
以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。

技术特征：
1.一种知识图谱数据的多路归并方法，其特征在于，包括：获取待归并的知识图谱数据，将所述识图谱数据映射为多个前缀树，所述前缀树包括多个结点，且结点与结点之间设置有前缀字符，每个前缀字符覆盖有至少一个子树；构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的字符数组中；计算每个位向量的超限值，基于所述超限值使用预设的数据结构为位向量建立索引；从字符数组中读取前缀字符，并利用所述索引抽取所读取到的前缀字符所覆盖的子树的拓扑数据，直到所有的前缀字符读取完毕；将抽取到的子树的拓扑数据构建为临时数组，归还子树所占用的位向量。2.根据权利要求1所述的知识图谱数据的多路归并方法，其特征在于,所述构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的字符数组中，包括：构建位向量，并将所述位向量初始化；获取前缀树，从前缀树的根结点开始遍历，将遍历到的结点以字符串的形式插入位向量中；将结点之间的前缀字符首尾相邻存储在字符数组中；将一个结点对应的位向量分割为多个区间，将一个结点所覆盖的所有子树的树拓扑数据依次存储在多个区间内。3.根据权利要求1所述的知识图谱数据的多路归并方法，其特征在于,所述计算每个位向量的超限值，基于所述超限值使用预设数据结构为位向量建立索引，包括：在所述位向量的区间内采集超限值；获取采集到的超限值中的最大值和最小值；将所述超限值中的最大值和最小值作为节点构建完全二叉树；利用所述完全二叉树为位向量建立索引。4.根据权利要求1所述的知识图谱数据的多路归并方法，其特征在于,所述从字符数组中读取前缀字符，并利用所述索引抽取所读取到的前缀字符所覆盖的子树的拓扑数据，直到所有的前缀字符读取完毕，包括：获取每个子树的容量，并根据每个子树的容量计算属于一个前缀字符的所有子树的容量总和；判断所述容量总和是否超过预设内存占用阈值：若不超过，则将所述前缀字符作为公共前缀，抽取所述公共前缀所包含的子树的拓扑数据；若超过，则放弃所述前缀字符，继续读取下一个前缀字符。5.一种知识图谱数据的多路归并装置，其特征在于，包括：获取模块：用于获取待归并的知识图谱数据，将所述识图谱数据映射为多个前缀树，所述前缀树包括多个结点，且结点与结点之间设置有前缀字符，每个前缀字符覆盖有至少一个子树；构建模块：用于构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的
字符数组中；计算模块：用于计算每个位向量的超限值，基于所述超限值使用预设的数据结构为位向量建立索引；读取模块：用于从字符数组中读取前缀字符，并利用所述索引抽取所读取到的前缀字符所覆盖的子树的拓扑数据，直到所有的前缀字符读取完毕；归还模块：用于将抽取到的子树的拓扑数据构建为临时数组，归还子树所占用的位向量。6.根据权利要求5所述的知识图谱数据的多路归并装置，其特征在于，所述构建模块包括：第一构建单元：用于构建位向量，并将所述位向量初始化；遍历单元：用于获取前缀树，从前缀树的根结点开始遍历，将遍历到的结点以字符串的形式插入位向量中；第一存储单元：用于将结点之间的前缀字符首尾相邻存储在字符数组中；分割单元：用于将一个结点对应的位向量分割为多个区间，将一个结点所覆盖的所有子树的树拓扑数据依次存储在多个区间内。7.根据权利要求5所述的知识图谱数据的多路归并装置，其特征在于，所述计算模块包括：采集单元：用于在所述位向量的区间内采集超限值；第一获取单元：用于获取采集到的超限值中的最大值和最小值；第二构建单元：用于将所述超限值中的最大值和最小值作为节点构建完全二叉树的节点上；索引建立单元：用于利用所述完全二叉树为位向量建立索引。8.根据权利要求5所述的知识图谱数据的多路归并装置，其特征在于，所述读取模块包括：第二获取单元：用于获取每个子树的容量，并根据每个子树的容量计算属于一个前缀字符的所有子树的容量总和；判断单元：用于判断所述容量总和是否超过预设内存占用阈值：若不超过，则将所述前缀字符作为公共前缀，抽取所述公共前缀所包含的子树的拓扑数据；若超过，则放弃所述前缀字符，继续读取下一个前缀字符。9.一种知识图谱数据的多路归并设备，其特征在于，包括：存储器，用于存储计算机程序；处理器，用于执行所述计算机程序时实现如权利要求1至4任一项所述知识图谱数据的多路归并方法的步骤。10.一种可读存储介质，其特征在于：所述可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现如权利要求1至4任一项所述知识图谱数据的多路归并方法的步骤。

技术总结
本发明提供了一种知识图谱数据的多路归并方法、装置、设备及介质，涉及数据存储技术领域，包括获取待归并的知识图谱数据，将所述识图谱数据映射为多个前缀树；构建位向量，基于预设的编码方式将每个前缀树中的子树的树拓扑数据存储在位向量的区间内，并将每个前缀树中所有的前缀字符分别存储在与位向量对应的字符数组中；计算每个位向量的超限值，使用预设的数据结构为位向量建立索引；从字符数组中读取前缀字符，利用索引抽取所读取到的前缀字符所覆盖的子树的拓扑数据；将抽取到的子树的拓扑数据构建为临时数组，归还子树所占用的位向量，本发明优化了多路精简知识图谱数据归并过程中内存开销过大的问题，实现了归并紧凑图谱数据的有序存储。谱数据的有序存储。谱数据的有序存储。


技术研发人员：滕飞 祝锦烨 赵越 马征 郝莉 韦洪雷
受保护的技术使用者：西南交通大学
技术研发日：2023.03.06
技术公布日：2023/7/11