[發明專利]一種后綴數組和最長公共前綴的正確性驗證方法及系統

有效

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

本發明涉及一種后綴數組和最長公共前綴的正確性驗證方法及系統。該方法包括：從右向左掃描一遍T，按照后綴類型定義比較字符T[i]及其后繼字符T[i+1]的大小，計算T的字符T[i]和后綴suf(T,i)的類型，記錄于t[i]中；將SA1和LCPA1中的元素初始化為?1。從左到右掃描一遍SA，根據數組t找出SA中所有LMS后綴及其LCP值，分別依次記錄在SA1和LCPA1中；根據字符串T、數組t、SA1和LCPA1，對SA1中相鄰LMS后綴及其LCP值進行正確性驗證；根據字符串T、數組t、B、C、SA1和LCPA1，歸納排序T的L型后綴及其LCP值；根據字符串T、數組t、B、C、SA1和LCPA1，歸納排序T的S型后綴及其LCP值；順序掃描SA、SA1、LCPA和LCPA1一次，比較SA與SA1和LCPA與LCPA1是否相同，如果兩組比較全部相同則T的SA和LCPA正確。

技術領域

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

背景技術

后綴數組SA為任意給定一個字符串T，從T的任意位置開始至其結尾的所有字符組成的字符串稱為T的后綴。顯然，長度為n的字符串包含n個后綴，對這n個后綴按字典順序排序，并將其地址保存在一個整型數組中，該數組則稱為字符串的后綴數組。最長公共前綴是后綴數組中相鄰的兩個后綴之間公共前綴的字符數。長度為n的字符串對應的最長公共前綴數組LCPA長度也為n，LCPA第一個元素為0，從第二個元素開始依次保存n個后綴對應的n-1個LCP值。后綴數組SA和最長公共前綴數組LCPA二者結合起來可以實現數據的全文索引，廣泛應用于字符串處理、數據壓縮、模式匹配、基因重組等領域。

在SA和LCPA構造完成后，為了避免可能存在的缺陷或計算錯誤，對二者進行正確性驗證是必需的。目前已知的SA和LCPA正確性驗證方法是兩個相互獨立的過程，先驗證SA的正確性，然后再驗證LCPA的正確性。比如，現有的SA正確性驗證方法是在SA構造完成以后，執行兩輪整數排序來驗證SA的正確性。LCPA的正確性驗證通常是采用暴力的方法依次對后綴數組中相鄰兩個后綴的公共前綴進行比較來驗證。在數據集規模較大的情況下，由于兩個驗證過程相互獨立，時間和空間開銷相對較大。

發明內容

本發明提供一種后綴數組和最長公共前綴的正確性驗證方法及系統，以克服后綴數組和最長公共前綴的正確性驗證不能同時進行的問題。

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

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

一種后綴數組和最長公共前綴的正確性驗證方法，包括：從右向左掃描一遍T，按照后綴類型定義比較字符T[i]及其后繼字符T[i+1]的大小，計算T的字符T[i]和后綴suf(T,i)的類型，記錄于t[i]中；將SA1和LCPA1中的元素初始化為-1。從左到右掃描一遍SA，根據數組t找出SA中所有LMS后綴及其LCP值，分別依次記錄在SA1和LCPA1中；根據字符串T、數組t、SA1和LCPA1，對SA1中相鄰LMS后綴及其LCP值進行正確性驗證；根據字符串T、數組t、B、C、SA1和LCPA1，歸納排序T的L型后綴及其LCP值；根據字符串T、數組t、B、C、SA1和LCPA1，歸納排序T的S型后綴及其LCP值；順序掃描SA、SA1、LCPA和LCPA1一次，比較SA與SA1和LCPA與LCPA1是否相同，如果兩組比較全部相同則T的SA和LCPA正確，否則錯誤。