字尾陣列
外觀
![本頁使用了標題或全文手工轉換](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 |
外部連結
[編輯]
|