在計算機科學中，后綴數組是一個字符串的所有后綴的排序數組。 它是一種用于全文索引、數據壓縮算法和文獻計量學等領域的數據結構。

后縮數字組由 Manber & 介紹 Myers (1990) 作為后綴樹的一種簡單、節省空間的替代方法。 它們在 1987 年由 Gaston Gonnet 獨立發現，名稱為 PAT 陣列 (Gonnet, Baeza-Yates & Snider 1992)。

Li, Li & Huo (2016) 給出了xxx個在時間和空間上都最優的in-place O ( n ) {\displaystyle {\mathcal {O}}(n)} 時間后綴數組構造算法，其中in-place是指 該算法只需要 O ( 1 ) {\displaystyle {\mathcal {O}}(1)} 超出輸入字符串和輸出后綴數組的額外空間。

增強型后綴數組 (ESA) 是帶有附加表的后綴數組，這些表重現后綴樹的全部功能，同時保持相同的時間和內存復雜度。字符串所有后綴的子集的后綴數組稱為稀疏后綴數組。 已經開發了多種概率算法來最小化額外的內存使用，包括最佳時間和內存算法。

讓 S = S [1] S [2]。 . . S [ n ] {\displaystyle S=S[1]S[2]...S[n]} 是一個 n {\textstyle n} -string 并且讓 S [ i , j ] {\displaystyle S [i,j]} 表示 S {\displaystyle S} 的子串，范圍從 i {\displaystyle i} 到 j {\displaystyle j} 包括在內。

S {\displaystyle S} 的后綴數組 A {\displaystyle A} 現在被定義為一個整數數組，提供按字典順序排列的 S {\displaystyle S} 后綴的起始位置。 這意味著，條目 A [ i ] {\displaystyle A[i]} 包含第 i {\displaystyle i} 的起始位置 - S {\displaystyle S} 中的xxx個最小后綴，因此對于所有 1 ≤ i ≤ n {\displaystyle 1\leq i\leq n} : S [ A [ i ? 1 ] , n ] <; S [ A [ i ] , n ] {\displaystyle S[A[i-1],n]<S[A[i],n]} 。

S {\displaystyle S} 的每個后綴在 A {\displaystyle A} 中只出現一次。 后綴是簡單的字符串。 這些字符串在它們的起始位置（整數索引）保存在 A {\displaystyle A} 之前被排序（就像在紙質字典中一樣）。

考慮文本 S {\displaystyle S} =banana$ 被索引：

文本以特殊標記字母 $ 結尾，它是xxx的，并且在字典序上比任何其他字符都小。 文本具有以下后綴：

這些后綴可以按升序排序：

后綴數組 A {\displaystyle A} 包含這些排序后綴的起始位置：

為清楚起見，后綴數組在下方垂直寫出：

因此，例如， A [ 3 ] {\displaystyle A[3]} 包含值 4，因此指的是 S {\displaystyle S} 中從位置 4 開始的后綴，即后綴 ana$。

后綴數組與后綴樹密切相關：

• 后綴數組可以通過執行后綴樹的深度優先遍歷來構造。 后綴數組對應于在遍歷期間按訪問順序給出的葉標簽，如果邊是按其xxx個字符的字典順序訪問的。
• 通過使用后綴數組和LCP 數組的組合，可以在線性時間內構造后綴樹。 有關算法的說明，請參閱 LCP 陣列文章中的相應部分。

已經表明，每個后綴樹算法都可以系統地替換為使用使用附加信息增強的后綴數組（例如 LCP 數組）的算法，并以相同的時間復雜度解決相同的問題。后綴數組相對于后綴樹的優勢 包括改進的空間要求、更簡單的線性時間構造算法（例如，與 Ukkonen 的算法相比）和改進的緩存局部性。

后縮數字組由 Manber & 介紹 Myers (1990) 為了改進后綴樹的空間需求：后縮數組存儲 n {\displaystyle n} 整數。 假設一個整數需要 4 {\displaystyle 4} 字節，一個后綴數組總共需要 4 n {\displaystyle 4n} 字節。 這明顯少于謹慎的后綴樹實現所需的 20 n {\displaystyle 20n} 字節。

然而，在某些應用程序中，后綴數組的空間要求可能仍然過高。 按位分析，后綴數組需要 O ( n log ? n ) {\displaystyle {\mathcal {O}}(n\log n)} 空間，而原始文本在大小為 σ {\ displaystyle \sigma } 只需要 O ( n log ? σ ) {\displaystyle {\mathcal {O}}(n\log \sigma )} 位。對于 σ = 4 {\displaystyle \sigma =4} 和 n = 3.4 × 10 9 {\displaystyle n=3.4\times 10{9}} 因此，后綴數組占用的內存比基因組本身多 16 倍。