公开(公告)号：CN107015868A

公开(公告)日：2017-08-04

申请号：CN201710232797.1

申请日：2017-04-11

Applicant: 南京大学

Inventor： 顾荣 ,  黄宜华 ,  郭晨 ,  朱光辉

IPC: G06F9/50

Abstract: 本发明公开了一种通用后缀树的分布式并行构建方法，包括以下步骤：第一步，整合输入序列并将其平均分配给每个计算节点；第二步，并行地统计子序列频数，确定所有的子树构建任务；第三步，将这些子树构建任务按规模尽量均匀地分配给不同的计算节点；第四步，分轮批量构建所有子树。每一轮批量构建可以分为以下三步：第一步，并行扫描输入以定位本轮构建任务需要的后缀并分别排序，将排序结果汇总至负责构建任务的计算节点；第二步，多路归并生成全局有序的后缀排序结果；第三步，利用排序结果生成对应的后缀子树。本发明可高效地并行构建通用后缀树，解决现有通用后缀树构建方法过于依赖I/O或主存容量、通用性不足、应对大规模输入困难等问题。

公开(公告)号：CN107015868B

公开(公告)日：2020-05-01

申请号：CN201710232797.1

申请日：2017-04-11

Applicant: 南京大学

Inventor： 顾荣 ,  黄宜华 ,  郭晨 ,  朱光辉

IPC: G06F9/50

Abstract: 本发明公开了一种通用后缀树的分布式并行构建方法，包括以下步骤：第一步，整合输入序列并将其平均分配给每个计算节点；第二步，并行地统计子序列频数，确定所有的子树构建任务；第三步，将这些子树构建任务按规模尽量均匀地分配给不同的计算节点；第四步，分轮批量构建所有子树。每一轮批量构建可以分为以下三步：第一步，并行扫描输入以定位本轮构建任务需要的后缀并分别排序，将排序结果汇总至负责构建任务的计算节点；第二步，多路归并生成全局有序的后缀排序结果；第三步，利用排序结果生成对应的后缀子树。本发明可高效地并行构建通用后缀树，解决现有通用后缀树构建方法过于依赖I/O或主存容量、通用性不足、应对大规模输入困难等问题。