后缀数组 nLogN 算法

2024年8月28日 | 阅读 7 分钟

特定字符串的所有后缀都排列在一个后缀数组中。这个概念与后缀树类似，后缀树是文本所有后缀的压缩树。

后缀数组是一种基本数据结构，被许多处理字符串的算法所使用。它显示了一个给定字符串的所有后缀的数组，这些后缀已经按字典顺序排列。使用最有效的方法构建后缀数组所需的时间复杂度通常是 O(n log n)，其中 n 是输入文本的长度。

使用 nlogn 算法构建后缀数组

使用暴力法，时间复杂度为 O(n^2 logn)。

对此进行了修改，并构建了一种优化的方法，其时间复杂度为 O(nlogn)。

基于 DC3（Difference Cover 3）技术的“偏斜算法”是一种众所周知的以 O(n log n) 时间复杂度构建后缀数组的方法。下面是该算法的一般描述：

1. 预处理

从给定字符串创建整数数组，每个整数代表一个字符。通常，这是通过为每个字符赋予一个不同的整数值来实现的，例如其 ASCII 码之一。
在字符串末尾添加一个特殊字符。该字符应小于字符串中的其他字符。例如，您可以使用 '0'（空字符）或 ASCII 值极低的字符。

2. 构建初始后缀数组

使用基数排序对字符串的所有后缀进行排序，这需要 O(n) 时间。

3. 诱导排序

当您遍历后缀数组时，如果每个后缀是 S 型（较小），则递归地对从 L 型（较大）位置开始的后缀进行排序，反之亦然。
此过程可以在 O(n) 时间复杂度内完成。

4. 合并步骤

将诱导排序阶段获得的两个已排序数组合并以创建最终后缀数组。

尽管从头开始实现偏斜方法可能很困难，但有一些开源工具和实现可供您使用。SuffixArray (C++)、SuffixArray.jl (Julia) 和 pysuffixarray (Python) 是几个著名的库。

例如，SA-IS（后缀数组诱导排序）方法是另一种以 O(n log n) 时间复杂度构建后缀数组的算法，但偏斜算法因其易用性和实际效率而经常受到青睐。

示例

让我们看一个例子，以便更好地理解如何为给定字符串创建后缀数组。以“banana$”一词为例。为了表示字符串已结束，我们附加特殊字符“$”（它小于所有其他字符）。DC3 算法用于按如下方式为该字符串创建后缀数组：

步骤 1 预处理

使用其 ASCII 值，字符串“banana$”中的字符可以表示为整数：

b -> 98
a -> 97
n -> 110
a -> 97
n -> 110
a -> 97
$ -> 36

步骤 2：创建初始后缀数组

使用基数排序对字符串的后缀进行排序。下面列出了后缀及其初始位置：

后缀

98 97 110 97 110 97 36（从索引 0 开始）
97 110 97 110 97 36（从索引 1 开始）
110 97 110 97 36（从索引 2 开始）
97 110 97 36（从索引 3 开始）
110 97 36（从索引 4 开始）
97 36（从索引 5 开始）
36（从索引 6 开始）

排序后，后缀重新排列如下：

36（从索引 6 开始）
97 36（从索引 5 开始）
97 110 97 36（从索引 3 开始）
97 110 97 110 97 36（从索引 1 开始）
110 97 36（从索引 4 开始）
110 97 110 97 36（从索引 2 开始）
98 97 110 97 110 97 36（从索引 0 开始）

步骤 3：诱导排序

后缀根据其类型（S 和 L）递归排序。在此阶段，我们区分 S 型和 L 型字符。S 型字符是小于其后字符的字符，L 型字符是大于其后字符的字符。为简单起见，特殊字符“$”被视为 S 型字符。

36（索引 6 处）和 97（索引 1、3、5 处）是 S 型（S）字符。

98（索引 0 处）和 97（索引 2、4 处）是 L 型（L）字符。

我们从末尾开始递归地对 S 型和 L 型后缀进行排序。结果是以下已排序的后缀：

后缀

36（从索引 6 开始）

97 36（从索引 5 开始）

97 110 97 36（从索引 3 开始）

97 110 97 110 97 36（从索引 1 开始）

110 97 36（从索引 4 开始）

110 97 110 97 36（从索引 2 开始）

98 97 110 97 110 97 36（从索引 0 开始）

步骤 4：合并步骤

在最后阶段，将诱导排序产生的两个已排序数组合并，同时考虑后缀的初始位置。

合并后缀

6（从索引 6 开始）

5 6（从索引 5 开始）

3 4 5 6（从索引 3 开始）

1 2 3 4 5 6（从索引 1 开始）

4 5（从索引 4 开始）

2 3（从索引 2 开始）

0 1 2 3 4 5 6（从索引 0 开始）

字符串“banana$”的最终后缀数组是 [6, 5, 3, 1, 4, 2, 0]。这些数字表示已排序后缀在原始字符串中的起始位置。值得注意的是，表示字符串末尾的特殊字符“$”对应于已排序数组中最短的后缀。

这是如何为给定字符串创建后缀数组的简单示例。在实际使用中，该技术即使对于非常长的字符串也有效。

nlogn 算法的实现

SA-IS 或偏斜算法必须完全用 C 语言实现，这超出了单个答案的范围。不过，我可以为您提供 C 语言中该算法的精简版本。尽管此实现可能不如优化的库有效，但它将帮助您理解算法的结构。

C 代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Structure to store information about suffixes
struct Suffix {
    int index; // Starting index of the suffix
    int rank[2];  // Rank and next rank (to be used in sorting)
};
// Helper function to compare two suffixes
int compare_suffixes(const void* a, const void* b) {
    struct Suffix* sa = (struct Suffix*)a;
    struct Suffix* sb = (struct Suffix*)b;
    return (sa->rank[0] == sb->rank[0]) ? 
        (sa->rank[1] - sb->rank[1]) : (sa->rank[0] - sb->rank[0]);
}
// Helper function to build the suffix array using merge-sort
void merge_sort(struct Suffix* suffixes, int* index_array, int left, int right) {
    if (left < right) {
        int mid = left + (right-left) / 2;
        merge_sort(suffixes, index_array, left, mid);
        merge_sort(suffixes, index_array, mid + 1, right);
        // Merge the sorted halves
        int i, j, k;
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int* L = (int*)malloc(sizeof(int) * n1);
        int* R = (int*)malloc(sizeof(int) * n2);
        for (i = 0; i < n1; i++)
            L[i] = index_array[left + i];
        for (j = 0; j < n2; j++)
            R[j] = index_array[mid + 1 + j];
        i = 0;
        j = 0;
        k = left;
        while (i < n1 && j < n2) {
            if (compare_suffixes(&suffixes[L[i]], &suffixes[R[j]]) <= 0)
                index_array[k++] = L[i++];
            else
                index_array[k++] = R[j++];
        }
        while (i < n1)
            index_array[k++] = L[i++];
        while (j < n2)
            index_array[k++] = R[j++];

        free(L);
        free(R);
    }
}

// Function to construct the suffix array
void build_suffix_array(const char* str, int* suffix_array, int size) {
    // Create an array of Suffix structures to store information about suffixes
    struct Suffix* suffixes = (struct Suffix*)malloc(sizeof(struct Suffix) * size);
    int* index_array = (int*)malloc(sizeof(int) * size);

    // Populate the Suffix array
    for (int i = 0; i < size; i++) {
        suffixes[i].index = i;
        suffixes[i].rank[0] = str[i];
        suffixes[i].rank[1] = (i + 1 < size) ? str[i + 1] : -1;
    }

    // Sort the suffixes using merge-sort with counting sort for comparison
    qsort(suffixes, size, sizeof(struct Suffix), compare_suffixes);

    // Store the sorted suffix indexes in the suffix array
    for (int k = 4; k < 2 * size; k *= 2) {
        int rank = 0;
        int prev_rank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        index_array[suffixes[0].index] = 0;

        for (int i = 1; i < size; i++) {
            if (suffixes[i].rank[0] == prev_rank &&
                suffixes[i].rank[1] == suffixes[i - 1].rank[1]) {
                suffixes[i].rank[0] = rank;
            } else {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = ++rank;
            }
            index_array[suffixes[i].index] = i;
        }

        for (int i = 0; i < size; i++) {
            int next_index = suffixes[i].index + k / 2;
            suffixes[i].rank[1] = (next_index < size) ? suffixes[index_array[next_index]].rank[0] : -1;
        }

        merge_sort(suffixes, index_array, 0, size - 1);
    }

    for (int i = 0; i < size; i++) {
        suffix_array[i] = suffixes[i].index;
    }

    free(suffixes);
    free(index_array);
}

// Function to print the suffix array
void print_suffix_array(const char* str, const int* suffix_array, int size) {
    printf("Suffix Array for the string \"%s\":\n", str);
    for (int i = 0; i < size; i++) {
        printf("%d: %s\n", suffix_array[i], &str[suffix_array[i]]);
    }
}

int main() {
    const char* str = "banana$";
    int size = strlen(str);

    int* suffix_array = (int*)malloc(sizeof(int) * size);

    build_suffix_array(str, suffix_array, size);
    print_suffix_array(str, suffix_array, size);

    free(suffix_array);
    return 0;
}

输出

Suffix Array for the string "banana$":
6: $
5: a$
3: ana$
1: anana$
0: banana$
4: na$
2: nana$

Time Complexity: O(nlogn).

下一个主题后缀树介绍：

后缀数组 nLogN 算法

使用 nlogn 算法构建后缀数组

示例

nlogn 算法的实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

后缀数组 nLogN 算法

使用 nlogn 算法构建后缀数组

示例

nlogn 算法的实现

相关帖子

数据结构中图的树边和回边区别

股票买卖问题

双向链表上的归并排序

二叉树的高度

使用递归反转栈

重轻分解导论

和大于给定值的最小子数组

B 树插入

数据结构中矩阵中回文路径的数量

移除链表中的循环

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器