后缀数组导论

后缀数组是一种用于字符串处理和模式匹配算法中的基本数据结构。它经常用于字符串搜索、子字符串查询以及许多与字符串相关的应用中。后缀数组在生物信息学、文本处理和信息检索中经常使用，对于解决这些问题特别有效。

要理解什么是后缀数组，我们首先必须理解字符串中“后缀”的概念。后缀是指在字符串中任意位置开始并延伸到字符串末尾的子字符串。例如，考虑单词“banana”。它有几个后缀，包括“banana”、“anana”、“nana”、“ana”、“na”和“a”。

后缀数组是一个排序数组，其中包含给定文本所有后缀的按字典序排列的起始位置（或索引）。换句话说，它是一个数组，其中包含每个后缀的起始位置，根据其对应的子字符串按升序排列。后缀数组只存储后缀的起始位置；后缀本身不存储在数组中。

特定字符串的所有后缀都排列在后缀数组中。这个概念与后缀树相似，后缀树是文本所有后缀的压缩树。任何使用后缀数组并补充更多信息并以相同时间解决相同问题的方法，都可以替代基于后缀树的方法（来源：维基百科）。

通过对后缀树执行深度优先遍历，可以从后缀树创建后缀数组。实际上，后缀数组和后缀树可以在线性时间内相互创建。

后缀数组相对于后缀树的优势在于：增强的空间需求、更简单的线性时间构建过程（例如与 Ukkonen 算法相比）以及增强的缓存局部性。

以下是如何为字符串“mississippi”构建后缀数组的示例：

原始字符串： Mississippi

为了构建后缀数组，我们首先找到字符串的所有后缀，然后根据它们对应的子字符串按字典序排序。

后缀

mississippi

ississippi

ssissippi

sissippi

issippi

ssippi

sippi

ippi

ppi

pi

i

后缀数组（排序索引）

11（对应“i”）

10（对应“pi”）

7（对应“ippi”）

4（对应“issippi”）

1（对应“issippi”）

0（对应“mississippi”）

9（对应“ppi”）

8（对应“ippi”）

5（对应“ssippi”）

2（对应“ssissippi”）

6（对应“sippi”）

3（对应“sissippi”）

我们可以使用后缀数组执行各种与字符串相关的操作

模式匹配： 使用模式匹配，假设我们想在单词“mississippi”中找到子字符串“iss”的所有实例。我们可以使用后缀数组和二分查找来快速找到这个子字符串的所有出现位置。

最长公共子字符串： 找到两个字符串（例如“mississippi”和“ipississippi”）之间的最长公共子字符串可以使用后缀数组完成。后缀数组可以轻松地将“ississippi”识别为这两个字符串之间最长的共享子字符串。

文本索引： 为了在大文本集合上实现快速搜索和模式匹配，全文索引可以使用后缀数组。例如，如果我们有一个大型文本语料库并且需要快速发现特定术语的所有实例，基于后缀数组的索引可以加快搜索过程。

数据压缩： 如前所述，数据压缩方法，如 Burrows-Wheeler 变换（BWT）和 FM-索引，都利用了后缀数组。流行的文件压缩工具利用这些原理来有效地压缩和解压缩数据。

DNA 序列分析：DNA 序列在生物信息学中经常表示为字符串，并且各种字符串方法（例如后缀数组）用于比较和分析这些序列。例如，后缀数组可以用于在 DNA 序列中定位重复的 DNA 基序或区域。

使用朴素方法构建后缀数组可以用各种编程语言实现

为了提高创建后缀数组的效率，使用了 Kärkkäinen-Sanders 算法、Manber-Myers 算法和 Skew 算法等高级技术。这些算法具有 O(n * log n) 或 O(n) 的时间复杂度，并且需要更少的额外内存，因此更适合长字符串。

朴素方法通常在实践中用于小字符串或出于教学目的，在这些情况下效率不是主要考虑因素。对于具有大量数据集的实际应用，建议使用一种更优化的方法来高效生成后缀数组。

用于为给定字符串创建后缀数组的朴素 Python 代码示例

输出

Suffix Array for 'banana' is:
[5, 3, 1, 0, 4, 2]

generate_suffixes(s)：此函数通过使用列表推导为输入字符串 s 创建所有后缀。

函数 naive_suffix_array(s) 为提供的输入字符串 s 创建后缀数组。在使用函数 generate_suffixes 创建后缀后，它根据后缀的词法位置对索引进行排序。

使用示例展示了如何使用 naive_suffix_array 函数获取输入字符串“banana”的后缀数组。生成的后缀数组是 [5, 3, 1, 0, 4, 2]。

这是用朴素方法创建后缀数组的 Java 代码

输出

Suffix Array for 'banana' is: [5, 3, 1, 0, 4, 2]

generateSuffixes(s)：此函数使用 String 数组从头开始创建字符串的所有后缀。

函数 naiveSuffixArray(s) 为提供的输入字符串 s 创建后缀数组。在调用函数 generateSuffixes 创建后缀后，它根据后缀的词法位置对索引进行排序。

可以在此处输入测试字符串，使用 naiveSuffixArray 函数，并打印完成的后缀数组。这是主要方法。

使用朴素方法，输入字符串“banana”的后缀数组为 [5, 3, 1, 0, 4, 2]。在后缀数组中，每个值对应于单词“banana”中关联后缀的开头。

使用朴素方法构造后缀数组的 C++ 代码

输出

Suffix Array for 'banana' is: 5 3 1 0 4 2

函数 generateSuffixes(s) 使用字符串向量从输入字符串 s 创建字符串的所有后缀。

函数 naiveSuffixArray(s) 为提供的输入字符串 s 创建后缀数组。在调用函数 generateSuffixes 创建后缀后，它根据后缀的词法位置对索引进行排序。

可以在主函数中输入测试字符串，然后调用 naiveSuffixArray 函数并打印后缀数组作为结果。

后缀数组的应用

子字符串搜索和模式匹配： 后缀数组经常用于基于文本的搜索和模式匹配。在给定一个模式的情况下，通过对排序的后缀数组进行二分查找，我们可以快速找到原始文本中该模式的所有实例。因此，它可以有效地用于文本搜索引擎、抄袭检测以及识别基因序列中的特定模式等任务。

最长公共子字符串： 后缀数组可用于识别两个或多个字符串之间的最长公共子字符串。通过查看排序数组中相邻后缀的共享前缀，可以找到最长公共子字符串的长度。这在文本比较、生物信息学和 DNA 序列分析中都有应用。

字符串压缩： 为了更有效地识别重复的子字符串并创建更高效的压缩算法，一些字符串压缩技术可以利用后缀数组。

文档聚类： 后缀数组可以用于文档聚类和自然语言处理，以根据共享单词或子字符串比较文档。

数据挖掘和信息检索： 后缀数组可以有效地应用于数据挖掘和信息检索活动，以从大量文本数据集中提取重要的模式和详细信息。

生物信息学和计算生物学： DNA 和蛋白质序列中的序列比对、基序发现和变异检测只是生物信息学和计算生物学应用中的几个例子，它们大量使用了后缀数组。