跳至內容

字尾陣列

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
字尾陣列
類型陣列
發明者Manber & Myers (1990)
時間複雜度(大O符號)
平均 最壞情況
空間
構建

電腦科學里, 字尾陣列(英語:suffix array)是一個通過對字串的所有字尾經過排序後得到的陣列。此數據結構被運用於全文索引、數據壓縮演算法、以及生物資訊科學

字尾陣列被烏迪·曼伯爾英語Udi Manber尤金·邁爾斯英語Eugene Myers於1990年提出,作為對字尾樹的一種替代,更簡單以及節省空間。它們也被Gaston Gonnet 於1987年獨立發現,並命名為「PAT陣列」。

在2016年,李志澤,李建和霍紅衛頁面存檔備份,存於互聯網檔案館)提出了第一個時間複雜度(線性時間)和空間複雜度(常數空間)都是最佳的字尾陣列構造演算法,解決了該領域長達10年的open problem。

定義

令字串表示的子字串,下標從

的字尾陣列被定義為一個陣列,內容是的所有字尾經過字典排序後的起始下標。

對於所有的有::


例子

考慮字串 =banana$:

i 1 2 3 4 5 6 7
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

字尾陣列 包含這些字尾的起始位置:

i 1 2 3 4 5 6 7
7 6 4 2 1 5 3

外部連結