[發明專利]一種后綴數組的正確性驗證方法及系統

有效

• 申請號: 201710183201.3
• 申請日: 2017-03-24
• 公開（公告）號: CN107015951B
• 公開（公告）日: 2020-08-18
• 發明（設計）人: 韓凌波;農革;徐文濤
• 申請（專利權）人: 廣東順德中山大學卡內基梅隆大學國際聯合研究院;中山大學
• 主分類號: G06F40/194
• 分類號: G06F40/194
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

本發明涉及一種后綴數組的正確性驗證方法和系統，所述方法包括：從右向左掃描一遍T，按照后綴類型的定義比較當前掃描的字符T[i]與后繼字符T[i+1]的大小，計算T的字符T[i]和suf(T,i)的類型，記錄于t[i]中；從左向右掃描一遍T，找出其中所有LMS字符出現的位置，從而獲取所有LMS子串的首字符指針，用數組P1來記錄；根據數組P1、B和SA，使用歸納排序的方法對T的LMS子串進行排序，結果保存在數組SA1；從左向右掃描SA，如果SA[i]為LMS類型，將SA[i]保存至SA1中；判斷T1中的字符是否唯一，若是則直接根據T1的名字計算出SA1，且用SA1更新C數組；根據T1和SA1歸納計算T的后綴數組SA，計算過程中使用C數組驗證SA的正確性，如果SA正確，用SA更新C數組。

技術領域

本發明涉及后綴數組的驗證領域，更具體地，涉及一種后綴數組的正確性驗證方法及系統。

背景技術

后綴數組是指可以在更小的空間內實現等同后綴樹的數據結構，是后綴樹的緊湊型替代，廣泛應用于字符串處理、生物信息檢索、數據壓縮和模式匹配等諸多領域。任意給定一個字符串，從其中的任意位置開始至其結尾的所有字符組成的字符子串稱為字符串的后綴(suffix)。顯然，長度為n的字符串包含n個后綴，對這n個后綴按字典順序排序，將其地址保存在一個整型數組中，該數組則稱為字符串的后綴數組。

現有的后綴數組正確性驗證方法是在后綴數組構造完成以后，執行兩輪整數排序來驗證后綴數組的正確性。隨著數據集規模的不斷增長，后綴數組的正確性驗證時間甚至會超過構造時間，現有的驗證方法已經不再完全適用。

發明內容

本發明為克服上述現有技術所述的至少一種缺陷，提供一種后綴數組的正確性驗證方法及系統。

本發明旨在至少在一定程度上解決上述技術問題。

為了達到上述技術效果，本發明的技術方案如下：

一種后綴數組的正確性驗證方法，包括：從右向左掃描一遍T，按照后綴類型的定義比較當前掃描的字符T[i]與后繼字符T[i+1]的大小，計算T的字符T[i]和suf(T,i)的類型，記錄于t[i]中；從左向右掃描一遍T，找出其中所有LMS字符出現的位置，從而獲取所有LMS子串的首字符指針，用數組P1來記錄；根據數組P1、B和SA，使用歸納排序的方法對T的LMS子串進行排序，結果保存在數組SA1；從左向右掃描SA，如果SA[i]為LMS類型，將SA[i]保存至SA1中；判斷T1中的字符是否唯一。若是則直接根據T1的名字計算出SA1，且用SA1更新C數組；根據T1和SA1歸納計算T的后綴數組SA，計算過程中使用C數組驗證SA的正確性，如果SA正確，用SA更新C數組；其中C數組保存的是當前遞歸層已有序的LMS后綴地址。

優選地，根據數組P1、B和SA，使用歸納排序的方法對T的LMS子串進行排序，結果保存在數組SA1的步驟包括：初始化SA所有元素的值為-1。計算SA中各字符桶的結束位置，保存在數組B。從右向左掃描P1，將P1的值保存至SA中B[T[P1[i]]]指向的位置，將B[T[P1[i]]]更新為B[T[P1[i]]]-1。掃描結束后，SA中各字符桶尾部記錄了T中相同LMS字符的地址；計算SA中各字符桶的開始位置，保存在數組B。從左向右掃描SA一次，如果當前掃描到的元素SA[i]的值為-1或在T中的前繼T[SA[i]-1]的類型是S類型，則繼續掃描下一個元素，否則將SA[i]-1保存至SA中B[T[SA[i]-1]]所指向的位置，然后將B[T[SA[i]-1]]更新為B[T[SA[i]-1]]+1；計算SA中各字符桶的結束位置，保存在數組B。從右向左掃描SA，判斷當前元素SA[i]在T中的前繼T[SA[i]-1]是否是L型，若是則繼續掃描下一個元素，否則將SA[i]-1保存至SA中B[T[SA[i]-1]]所指向的位置，然后將B[T[SA[i]-1]]更新為B[T[SA[i]-1]]-1。