通用后缀树是一种对序列集合中的所有序列的后缀进行索引形成的数据结构。其不仅可以高效解决诸如序列匹配与查找、最长公共子序列查询等很多基本序列分析问题,而且在DNA序列匹配、代码克隆检测、语言模型、序列模式挖掘等场景下有很大的应用价值。通用后缀树构建是一个大型复杂算法,其构建过程涉及大量复杂计算和I/0,使得构建过程复杂而耗时。尤其是,大数据时代,很多应用问题的数据集规模巨大,使得大规模数据场景下的通用后缀树构建变得更为复杂,难以在较短时间内快速完成构建。因此,大规模通用后缀树构建成为领域内的一个基础性研究热点问题。过去数十年来,后缀树构建已有诸多相关的研究工作。但现有研究工作仍存在三方面的主要问题:第一,现有研究工作并没有直接解决通用后缀树的构建问题,而是研究通用后缀树的特例——后缀树的构建算法,再转换为通用后缀树,这种做法对通用后缀树构建问题的特殊性,例如输入形态的多样性考虑不足;第二,经过几十年的发展,现有的后缀树构建算法虽然取得了长足的进步,但仍存在着I/0难以优化、未考虑数据扩展性、性能不稳定等问题,难以支撑大规模场景下的后缀树构建任务;第三,现有研究工作大多基于单机或超级计算机设计,大数据应用需求背景下,基于单机设计的传统算法难以应对大规模数据集的处理,而基于超级计算机设计的算法应用门槛太高、代价较大。大数据时代,基于分布式集群的大数据并行处理平台搭建成本低、易于维护、扩展性好,已成为解决大规模问题的主流计算平台。但目前尚缺少大数据应用场景下高效可扩展的大规模通用后缀树构建算法,设计并实现大规模通用后缀树构建分布并行算法存在着诸多技术难点。首先,算法需要针对大规模分布式场景,充分发挥分布式存储以及并行计算的优势;其次,算法需要具有良好的通用性,对不同的输入序列形态(例如大量短序列、一条长序列、若干长度差异很大的序列等)均需具有良好的处理能力,并具备良好的可扩展性以及较高的计算性能。基于上述问题背景,本文研究实现了一种分布式场景下的大规模通用后缀树并行构建算法LMdst,支持对不同规模和各种输入形态的序列数据,构建通用后缀树。本文的主要工作内容以及贡献点如下:(1)研究提出了一种基于Lcp多路归并的高效可扩展的大规模通用后缀树构建分布并行算法LMdst。(2)研究实现了基于trie树的分布并行化子树划分方法,可以高效并行化统计子序列频数进而划分子树;针对子树划分,进一步提出了一种基于输入片段的数据划分方法,屏蔽了输入序列形态、数据存储等因素对算法性能的影响。(3)研究提出了基于Lcp-range的高效序列比较方法和基于败者树多路归并的后缀子树并行构建方法。以此为基础,设计实现了一套综合考虑计算和I/O的后缀子树批量构建优化方法。(4)研究提出了基于装箱和整数划分的子树构建任务分配方法,既能充分利用每个计算单元的计算资源又能在分布式场景中保持良好的负载均衡。(5)对算法进行了计算复杂度以及I/O开销等方面的理论分析,并基于Apache Spark平台设计实现了大规模通用后缀树构建分布并行算法LMdst,实验结果表明LMdst在大规模场景下具有优异的计算性能、近线性的可扩展性以及良好的通用性。本文工作所设计实现的大规模通用化后缀树构建分布并行化算法,在2017年教育部科技发展中心主办的第三届“全国高校云计算应用创新大赛”大数据技能赛全国总决赛上,以其优异的算法性能,获得第一名的成绩,荣获技能赛一等奖。