[發(fā)明專利]常數(shù)工作空間并行構造后綴數(shù)組的方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201810344030.2
• 申請日: 2018-04-17
• 公開（公告）號: CN108763170A
• 公開（公告）日: 2018-11-06
• 發(fā)明（設計）人: 勞斌;解靜儀;徐文濤;農(nóng)革
• 申請（專利權）人: 佛山市順德區(qū)中山大學研究院;廣東順德中山大學卡內(nèi)基梅隆大學國際聯(lián)合研究院;中山大學
• 主分類號: G06F17/22
• 分類號: G06F17/22;G06F17/30
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 左恒峰

1.常數(shù)工作空間并行構造后綴數(shù)組的方法，其特征在于，包括以下步驟：

S1、從右向左掃描一遍輸入的字符串X，按照后綴類型的定義比較當前掃描的兩個相鄰字符X[i]和X[i+1]，從而得到每一個字符和后綴的類型；

在掃描過程中，按照LMS子串的S⁺L⁺S類型模式定義找出所有LMS字符出現(xiàn)的位置，從而獲取字符串X中所有LMS子串的首字符指針，并記錄在數(shù)組P1中；

S2、通過數(shù)組P1和SA來對字符串X中所有的LMS子串進行常數(shù)工作空間內(nèi)的并行歸納排序，并將排序結果保存在SA1中；

其中,SA為用于記錄字符串X的后綴數(shù)組；SA1為用于記錄排序結果的后綴數(shù)組；

S3、根據(jù)排序結果在常數(shù)工作空間內(nèi)并行重命名字符串X中所有的LMS子串，從而形成字符串X1；

S4、檢查字符串X1中的每個字符是否唯一，若是則直接排序字符串X1的各后綴來計算字符串X1的后綴數(shù)組，保存至SA1中，否則以字符串X1和SA1作為新輸入?yún)?shù)替代字符串X和SA,分別遞歸調(diào)用至步驟S1和S2；

S5、根據(jù)獲得的保存在SA1中的字符串X1的后綴數(shù)組，在常數(shù)工作空間內(nèi)并行歸納計算字符串X的后綴數(shù)組，保存至SA中。

2.根據(jù)權利要求1所述的常數(shù)工作空間并行構造后綴數(shù)組的方法，其特征在于，所述步驟S1中從右向左掃描一遍字符串X，所采用的掃描方式包括分塊并行掃描、流水并行掃描以及前綴和并行掃描。

3.根據(jù)權利要求1所述的常數(shù)工作空間并行構造后綴數(shù)組的方法，其特征在于，所述步驟S2中，通過數(shù)組P1和SA來對字符串X中所有的LMS子串進行常數(shù)工作空間內(nèi)的并行歸納排序，包括以下步驟：

S21、初始化SA的所有元素為-1，并以前綴和并行方式掃描出字符串X中所有后綴在SA中所屬各桶的結束位置，記錄在大小為O(1)的桶數(shù)組B中；從右向左流水并行掃描字符串X，依次把掃描到的各LMS后綴填入其在SA中所屬桶的當前結束位置，并將該桶的結束位置向左移動一格；

S22、以前綴和并行方式掃描出字符串X中所有后綴在SA中所屬各桶的起始位置，記錄在大小為O(1)的桶數(shù)組B中，并對SA進行分塊并行掃描處理：

在當前塊內(nèi)從左向右掃描SA，針對掃描到的每個不為-1的元素SA[i]，從SA中讀取X[SA[i]]的前繼字符X[SA[i]-1]；若該前繼字符是L型，則將SA[i]-1的值以及suf(X,SA[i]-1)的后綴在SA中所屬桶的當前起始位置作為排序結果記錄在SA中，并將該桶的起始位置向右移動一格；

讀取前一塊的排序結果并記錄在SA中；

讀取后一塊的所有前繼字符并記錄在SA中；

S23、以前綴和并行方式掃描出字符串X中所有后綴在SA中所屬各桶的結束位置，記錄在大小為O(1)的桶數(shù)組B中，并對SA進行分塊并行掃描處理：

在當前塊內(nèi)從右向左掃描SA，針對掃描到的每個元素SA[i]，從SA中讀取X[SA[i]]的前繼字符X[SA[i]-1]；若該前繼字符是S型，則將SA[i]-1的值以及suf(X,SA[i]-1)的后綴在SA中所屬桶的當前結束位置作為排序結果記錄在SA中，并將該桶的結束位置向左移動一格；

讀取前一塊的排序結果并記錄在SA中；

讀取后一塊的所有前繼字符并記錄在SA中。

4.根據(jù)權利要求1所述的常數(shù)工作空間并行構造后綴數(shù)組的方法，其特征在于，所述步驟S3，根據(jù)排序結果在常數(shù)工作空間內(nèi)并行重命名字符串X中所有的LMS子串，從而形成字符串X1，包括以下步驟：S31、將SA1中已排序的LMS子串進行分塊，在每個分塊內(nèi)從左向右依次比較相鄰的兩個LMS子串的大小；對于每個LMS子串，用其在SA1中所屬桶的起始位置命名，第一個桶的起始位置從0開始，即得到各分塊內(nèi)LMS子串的局部名；

S32、利用前綴和方法統(tǒng)計每個分塊中可使用的全局名，將各分塊內(nèi)LMS子串的局部名替換為全局名，從而形成字符串Z1；

S33、從右到左對字符串Z1進行分塊并行掃描，針對每個被掃描到的字符Z1[i]，若Z1[i]為L型，則令X1[i]＝Z1[i]，否則將X1[i]設為Z1[i]在SA1中所屬桶的結束位置；待掃描Z1結束后，X1即為對Z1中各S型字符重命名后的結果。