複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/後綴數組/8989867
複製
複製成功

後綴數組

鎖定
在計算機科學裏, 後綴數組（英語：suffix array）是一個通過對字符串的所有後綴經過排序後得到的數組。此數據結構被運用於全文索引、數據壓縮算法、以及生物信息學。
後綴數組被烏迪·曼伯爾與尤金·邁爾斯於1990年提出，作為對後綴樹的一種替代，更簡單以及節省空間。它們也被Gaston Gonnet 於1987年獨立發現，並命名為“PAT數組”。
中文名
後綴數組
外文名
Suffix Array
子    串
字符串 S 的子串

目錄

  1. 1 簡介
  2. 2 定義
  3. 3 例子

後綴數組簡介

在計算機科學裏,後綴數組（英語：suffix array）是一個通過對字符串的所有後綴經過排序後得到的數組。此數據結構被運用於全文索引、數據壓縮算法、以及生物信息學。
後綴數組被烏迪·曼伯爾與尤金·邁爾斯於1990年提出，作為對後綴樹的一種替代，更簡單以及節省空間。它們也被Gaston Gonnet 於1987年獨立發現，並命名為“PAT數組”。 [1] 

後綴數組定義

令字符串
，
表示S的子字符串，下標從i到j。
S的後綴數組A被定義為一個數組，內容是S的所有後綴經過字典排序後的起始下標。對於所有的有：
。 [1] 

後綴數組例子

考慮字符串S=banana$:
i
1
2
3
4
5
6
7
[i]
b
a
n
a
n
a
$
字符串的結尾是特殊字符$，用作特殊標誌。該字符串有以下後綴：
後綴
i
banana$
1
anana$
2
nana$
3
ana$
4
na$
5
a$
6
$
7
後綴經過升序排序後：
後綴
i
$
7
a$
6
ana$
4
anana$
2
banana$
1
na$
5
nana$
3
後綴數組A包含這些後綴的起始位置：
i
1
2
3
4
5
6
7
A[i]
7
6
4
2
1
5
3
參考資料
  • 1.    Kulla, Fabian; Sanders, Peter (2007). "Scalable parallel suffix array construction". Parallel Computing. 33 (9): 605. doi:10.1016/j.parco.2007.06.004.