一种通用后缀树的分布式并行构建方法

摘要

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