後綴數組
外觀
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
後綴數組 | ||
---|---|---|
類型 | 數組 | |
發明者 | Manber & Myers (1990) | |
時間複雜度(大O符號) | ||
平均 | 最壞情況 | |
空間 | ||
構建 |
在計算機科學里, 後綴數組(英語:suffix array)是一個通過對字符串的所有後綴經過排序後得到的數組。此數據結構被運用於全文索引、數據壓縮算法、以及生物信息學。
後綴數組被烏迪·曼伯爾與尤金·邁爾斯於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 |
外部連結
[編輯]
|