字典树是一个入门的数据结构，但没有太多实际应用，主要的原因是其二次时间/空间复杂性，但它为理解、构建更节省空间的数据结构奠定了基础。

后缀树是一个强大的数据结构，源自字典树。它的优势在于使用线性空间和时间进行构建，这样更便于快速字符串操作，且非常适合需要密集和多样化字符串操作的应用，如基因组测序、子字符串查询和模式匹配。

再进一步，后缀数组为后缀树提供了一种更节省空间的替代方案，以略微增加查询时间为代价。通过添加最长公共前缀（LCP）阵列，它有近似于后缀树的功能，同时更易于实现和存储，适用于需要空间的大型文本。通过一个实例，文章详细介绍了后缀数组的构造，并提供了代码。

(I) 介绍

高级预处理工具

字符串处理在众多计算领域中至关重要^[1]，是能够实现高效的数据处理、数据操作和数据检索的重要组成部分。它涵盖了互联网搜索引擎的各种应用程序，它依靠字符串算法来处理和索引大量数据。我们可以把整个一篇文章看成一个字符串，可能对这篇文章做多次查询，我们可以预先处理一下，得到一个中间的数据结构，方便后面的查询。一些数据结构就被开发出来，后缀字典树、后缀树、后缀数组就是最常用的。

后缀字典树：一种空间密集型数据结构，表示给定字符串的所有可能后缀，方便进行大批量的与字符串相关的查询^[4]。

后缀树：后缀字典树的空间优化版本，它通过压缩公共前缀实现了高效的处理和查询。

后缀数组：一个排序后缀数组，在空间效率和查询时间之间提供平衡，通常由最长公共前缀（LCP）数组补充，以提高性能。

使用注意事项
这些结构和算法的应用取决于手头任务的性质。后缀树和数组适用于数据是静态的情况，并且预处理的成本可以分布在许多查询中。相比之下，更简单的字符串算法，如KMP或Boyer-Moore，对于单个搜索实例或处理流数据时可能更可取。

追加“$”对字符串处理的重要性

我们一般会在字符串的末尾加上'$'. 附加一个唯一的终止符（通常表示为`$`）在字符串的末尾是字符串处理中必不可少的一步，尤其是在构造后缀树或数组时。以下是为什么这么做的几个原因：

1. 独特性：“$”符号是一个不会出现在字符串其他位置的字符，确保没有任何一个字符串的后缀与另一个字符串的前缀混淆。

2. 字典序：通过附加“$”，这通常被认为是字典中最小的字符，我们可以确保后缀排序正确。这对于后缀数组尤其重要，因为二进制搜索和其他算法取决于后缀的字典顺序。

3. 终端：在后缀树中，“$”字符用作叶节点标记，表示与后缀表达式对应的路径的结束。这有助于高效的树遍历和模式匹配，因为添加了终端符号让每个后缀表达式都可以在树中进行明确的表示。

(II) 后缀字典树
在下面的段落里我们将用”banana$”这个字符串来说明,参看图1 
图 1

后缀字典树构造
节点创建:在后缀字典树中，每个节点表示字符串中的单个字符^[5]。从根节点开始，字符串后缀中的每个后续字符都对应于源于其父节点的子节点。例如，‘na$’ 有3个节点, ‘banana$’有7个节点。

1. 边：字典树中的每条边都对应于字符串中的一个字符。如果一个节点表示字符串中位置“i”处的字符，则有一条边将其连接到表示位置“i+1”处字符的另一个节点。对上面的例子’na$’，有一条边’n’从根节点(Root)到下个节点(16)，然后有一条边’a’从(16)到(17),又有一条边从(17)到(21)(叶节点)

2. 路径表示：从根到任何叶节点的路径都会拼写出字符串的后缀表示。因此，如果你沿着一条路径遍历并沿着边缘连接字符，你就会检索到一个完整的字符串后缀表达式^[6]。

3. 叶节点：每个叶节点表示字符串后缀表达式的末尾。由于字符串后面附加了一个唯一的终端字符（通常为“$”），它保证每个后缀都以一个叶子结尾，没有两个叶子可以表示相同的字符串的后缀表达式。

4. 完全代表权：因为后缀字典树包含字符串的所有可能后缀表达式^[7]，它本质上在其结构中保存字符串的全部信息。这使得可以通过简单地根据查询子字符串中的字符序列从根进行遍历来搜索任何子字符串。

5. 字符串搜索：在字符串搜索的上下文中，后缀字典树可以用于高效地定位文本T中的模式P^[8]。一旦建立了T的后缀字典树，搜索P需要从根遍历字典树，遵循由P的字符定义的路径。如果路径结束于对应后缀T的节点，则该模式存在于文本中。这个过程可能比简单的字符串搜索算法快得多，尤其是当有多种模式需要搜索时，并且不需要为每次搜索重建字典树的时候。

(1) 时间/空间的复杂性

建立和使用后缀字典树的复杂性是其实际应用中的一个关键考虑因素^[9]。时间复杂度：

长度为n的字符串构造后缀字典树的时间复杂度为O（n^2），这是因为每个后缀都必须插入到字典树中，并且每次插入可能需要O（n）时间。此外，如果我们正在执行字符串搜索，则在预构建的字典树中搜索文本T中长度为m的模式的查询时间为O（m）。

空间复杂度：

后缀字典树的空间复杂度在最坏的情况下也是O（n^2）。这是因为每个节点最多可以有n个子节点（在大小为n的字母表的情况下），并且可能有O（n）个节点用于表示每个后缀表达式。然而，实际实现通常利用各种优化技术来减少内存使用，例如使用固定大小的数组或哈希图来表示边以存储子节点。

虽然后缀字典树尝试提供了强大的字符串处理能力，但它们的二次型时间和空间复杂性可能使它们对于非常长的字符串或大型数据集显得有点不切实际。后缀树和后缀数组等替代数据结构通常用于此类场景，因为它们在性能和内存使用之间提供了更平衡的折衷选择。

(III) 后缀树：压缩的后缀字典树
在下面的段落里我们依然将用”banana$”这个字符串来说明,参看图2

                    图2

后缀树实际上可以看作是后缀字典树的压缩版本^[10]，它合并了不必要的节点，并以此来在不丢失任何信息的情况下压缩结构。在后缀树中，信息被紧凑地存储，以节省空间并促进高效操作^[11]。有两种常用的方法来标记树的边：使用字符串本身或使用指向原始字符串中的子字符串的索引。

当使用实际字符串作为标签时，每条边都会用一系列字符进行注释。然而，对于大型文本，这种方法可能在空间上效率低下。更常见的情况是，边用引用原始文本中子字符串的开始和结束位置的成对索引进行标记。这不仅节省了空间，而且允许恒定的时间边缘长度计算，这对于实现（O（n））构建时间至关重要。参看图（2）

用Ukkonen算法实现O（n）复杂度

Ukkonen算法是在（O（n））时间复杂度内构造后缀树的关键^[12]。它通过只迭代文本一次来逐步构建树，避免了原始算法实现的（O（n^2））复杂性。这是通过巧妙地维护一个“后缀链接”来实现的，该链接允许算法在添加后缀后直接跳转到树中的下一个插入点，而不是从根部往下走。活动点的维护，算法中的边、长度和余数变量确保在不重新遍历整个树的情况下有效地添加新后缀。

可以使用后缀树加强的应用案例

后缀树可以快速执行几个强大的操作：

-使用子串检索：一旦构造了后缀树，就可以在（O（m））时间内搜索任何查询字符串（Q）^[13]，其中（m）是（Q）的长度。这比简单的搜索算法快得多。

-最长重复子字符串：通过找到至少有两个叶子的最深内部节点（根据字符串深度，而不是树深度），我们可以找到（O（n））时间内找到最长重复子字符串。

-最长公共子串：后缀树可以用来查找两个字符串之间最长的公共子字符串^[14]，方法是用唯一的分隔符连接字符串，并为此连接的字符串构造后缀树。包含两个字符串路径的叶节点的最深内部节点表示最长的公共子字符串。

虽然后缀树功能强大，但它们的构造和管理可能很复杂，并且可能消耗大量内存，这导致了某些应用程序开发和使用后缀数组等替代结构。

(IV) 后缀数组：后缀树的一种有效替代方法

后缀数组是后缀树的一种节省空间的替代方案^[15]，它由一个整数数组组成，该数组提供给定字符串的所有后缀的起始位置，并按字典顺序排列。LCP（最长公共前缀）数组是一种辅助数据结构，用于保存后缀数组中每对连续后缀之间最长公共后缀的长度^[16]。

后缀数组的构造

后缀数组的构造可以通过各种算法来实现，最容易想到的算法费时O(n^2 log n), 因为n个元素排序要 n log n, 每两个字符串的比较又需要 n. 我们下面介绍一种简单而又快速的O(nlog n)算法，该算法根据后缀的词典排名对后缀进行排序。这种方法采用前缀加倍技术，其中，在每次迭代中，所有后缀根据前2^k个字符进行排序，并且在k递增的情况下重复该过程，直到它超过字符串的长度为止^[17]。计数排序，一种稳定的线性时间排序算法，通常与排序方法结合使用，以实现所需的复杂性，尤其是在每次迭代加倍技术时对秩进行排序时。下面我们用’banana$’来做一点说明，我们需要把下面的后缀排序：
banana$, anana$,nana$,ana$,na$,a$,$.

我们首先找出每个字母的序：$à0, aà1,bà2,nà3. 然后把字符串转化为数组：2131310。下面我们用计数排序来给数组排序得到0111233.换成原来的字符串后缀就是：
（$,anana$,ana$,a$,banana$,nana$,na$),换成整数索引就是 (6,1,3,5,0,2,4).这一步可以看成是用字符串的第一个字母来排序。接下来我们可以用每个字符串的头两个字母来排序，接下来用每个字符串的头四个字母来排序。

 (1) 排序可以直接用字母的序，不必用字母本身。

（2 注意当第二次排序时，数组已按照第一个字母排序，所以只需要按照第二个字母排序。并且因为计数排序是稳定排序，所以只有第一个字母相同的后缀才会在这一轮交换位置。

（3）如果一个字符串的长度小于2^k，后面的序当然用0来补充。
下面的几张表详细地说明了算法的执行过程。”.”代表’\0’,即在字符串后面的字符。

第一次，考虑后缀的头1个字母，只能区分$/a/b/n，只有4种类别，不能区分anana$,ana$,a$，也不能区分nana$,na$。

第二次，考虑后缀的头2个字母，a$/an(ana$ 和anana$ 的头2个字符)可以区分开；但是an(an$的头2个字符)/an(anana$的头2个字符)仍然不能区分，na(na$的头2个字符)/na(nana$的头2个字符)仍然不能区分。

第三次，考虑后缀的头4个字母，anan (anana$的头4个字符)/ana$可区分开，nana(nana$的头4个字符)/na$. 可以区分开。可以看到，所有后缀都可区分开，程序结束。

LCP数组的构建

LCP阵列的构造:Kasai的算法是一种流行的方法^[18]，用于在创建后缀阵列后在线性时间内构造LCP阵列。它按后缀的原始顺序迭代后缀，并使用先前计算的LCP值和后缀数组中的秩信息计算（O（n））时间内的LCP。它是基于基本的观察：如果”anana$”和”ana$”的LCP值是3($没有算在里面)，把两个字符串的第一个字符去掉， 那么”nana$”和”na$”至少是2(3-1).下表是最后结果：

从后缀数组构造后缀树

尽管后缀树和后缀数组是不同的数据结构，后缀树可以由后缀数组及其相应的LCP数组构成。这是通过创建一个与数组中表示的LCP间隔相对应的通用后缀树来实现的，有效地重新创建后缀树的分支结构。

从后缀和LCP数组构造树涉及创建与LCP值相对应的内部节点，并以保持树属性的方式链接它们。这个过程也需要（O（n））时间，从而提供了一种在这两种强大的字符串处理工具之间切换的紧凑且省时的方式。

后缀数组和LCP数组广泛用于文本处理、生物信息学和数据压缩中的各种应用，其中内存效率与处理速度一样重要。它们允许许多与后缀树相同的操作，诸如子串搜索和重复时间最长的子串，但具有较低的内存占用。

具体情况请参阅附录：代码列表。

(V) 总结
开发的难度：
-后缀字典树
-概念上更容易理解，但在大型数据集中实现起来不切实际
-后缀树
-实现起来很复杂，尤其是使用像Ukkonen这样的线性时间算法。
-带LCP的后缀数组
-实现起来比后缀树更简单，但实现最佳构造可能具有挑战性
(VI) 附录

后缀字典树, 后缀树，带LCP的后缀数组 时间和空间复杂性对比表
 

参考文献：

[1]马锐彦.KMP算法的优化与应用[J].电脑知识与技术,2023,19(20):73-75.

[2]赵林洁. 应用于大数据的Trie树存储结构及算法研究[D]. 中国计量大学, 2021. .

[3]林志鸿,王李进,吴清寿.广义后缀树的概念生成算法[J].武夷学院学报,2023,42(06):6-10.

[4]郭晨. 大规模通用后缀树构建分布并行算法研究与实现[D]. 南京大学, 2017.

[5]Magdi S S Z R . A fast algorithm for constructing suffix arrays for DNA alphabets [J]. Journal of King Saud University - Computer and Information Sciences, 2022, 34 (7): 4659-4668.

[6]Dina S M G E A A . Reconstructing parameterized strings from parameterized suffix and LCP arrays [J]. Theoretical Computer Science, 2024, 981.

[7]刘纳. 基于后缀树和后缀数组的带有通配符多模式匹配研究[D]. 合肥工业大学, 2020. .

[8]Momin M A A ,Parimala T ,Noman M .Parallel and private generalized suffix tree construction and query on genomic data.[J].BMC genomic data,2022,23(1):45-45.

[9]Manuel C ,Gonzalo N .Faster repetition-aware compressed suffix trees based on Block Trees[J].Information and Computation,2022,285(PB):

[10]晁健楠.基于后缀树的多序列星比对算法研究[D].电子科技大学,2022.

[11]赵林洁,肖英,张宇.应用于大数据的Trie树排序算法[J].计算机工程与设计,2022,43(02):427-433.

[12]Xu ,Wentao,Nong , et al.A study for extracting keywords from data with deep learning and suffix array[J].Multimedia Tools and Applications,2022,81(5):1-19.

[13]林婧,何震瀛.基于广义后缀树结合过滤因子的正则表达式匹配算法[J].计算机应用与软件,2022,39(01):266-270+286.

[14]Ziyuan W ,Junjie T ,Yanling L , et al.SaAlign: Multiple DNA/RNA sequence alignment and phylogenetic tree construction tool for ultra-large datasets and ultra-long sequences based on suffix array[J].Computational and Structural Biotechnology Journal,2022,201487-1493.

[15]Wentao X ,Haoyu C ,Yidong H , et al.Full-text search engine with suffix index for massive heterogeneous data[J].Information Systems,2022,104

[16]Alevizos ,Elias,Artikis , et al.Complex event forecasting with prediction suffix trees[J].The VLDB Journal,2021,(prepublish):1-24.

[17]W. J D ,Neerja M ,W.F. S .Computation of the suffix array, Burrows-Wheeler transform and FM-index in V-order[J].Theoretical Computer Science,2021,88082-96.

[18]Ravindra S P N .Rabin-karp algorithm based microsatellite searching in whole-genome[J].BIOINFOLET - A Quarterly Journal of Life Sciences,2021,18(1a):25-31.