[發(fā)明專利]一種基于OpenMP的并行字符串查詢方法

有效

• 申請?zhí)枺?/td>: 201910666139.2
• 申請日: 2019-07-23
• 公開（公告）號: CN110457531B
• 公開（公告）日: 2022-11-01
• 發(fā)明（設(shè)計）人: 賈連印;張崇德;李孟娟;丁家滿;陳明鮮;唐季林
• 申請（專利權(quán)）人: 昆明理工大學(xué)
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 昆明人從眾知識產(chǎn)權(quán)代理有限公司 53204
• 代理人: 沈艷尼

1.一種基于OpenMP的并行字符串查詢方法，其特征在于：

字符串?dāng)?shù)據(jù)集預(yù)處理步驟：將字符串?dāng)?shù)據(jù)集按字典序升序排序，按首字母分區(qū)，并統(tǒng)計各分區(qū)的字符串的數(shù)量，將查詢集同樣按字典序升序排序；

索引創(chuàng)建步驟：基于貪婪分區(qū)方法將數(shù)據(jù)集分區(qū)并創(chuàng)建分區(qū)表簡稱PT，通過OpenMP并行為每個分區(qū)創(chuàng)建分區(qū)雙數(shù)組索引結(jié)構(gòu)；

查詢步驟：對待查詢的字典序有序的一批字符串，在相應(yīng)的DA上進(jìn)行檢索，獲取查詢結(jié)果；

所述字符串?dāng)?shù)據(jù)集預(yù)處理步驟具體為：

Step110：將字符串?dāng)?shù)據(jù)集按字典序升序排序；

Step120：統(tǒng)計各首字母對應(yīng)的字符串?dāng)?shù)量L_a，L_b，L_c…L_z；

Step130：將查詢集按字典序升序排序；

所述索引創(chuàng)建步驟具體為：

Step210：構(gòu)建分區(qū)表PT，將數(shù)據(jù)集劃分為K個近似均勻的分區(qū)；

Step220：基于OpenMP為每個分區(qū)構(gòu)建獨立的DA索引結(jié)構(gòu)；

所述Step 210具體為：

Step211：初始化分區(qū)表PT，PT的每一項包含首字母C、字符串?dāng)?shù)量L、分區(qū)號P三個屬性，并依次寫入預(yù)處理階段得到的每個首字母及其對應(yīng)的字符串?dāng)?shù)量，分區(qū)號均初始化為0；第i行，0≤i≤25對應(yīng)的字符、字符串?dāng)?shù)量和分區(qū)號分別用C_i，L_i和P_i表示；

Step212：將分區(qū)表PT按照字符串?dāng)?shù)量降序排序，置PT的前K項，0到K-1項的分區(qū)號為1,2,3…K；

Step213：按照L的大小，為PT中前K個表項建造一個小根堆，記堆頂元素對應(yīng)的字符串?dāng)?shù)量和分區(qū)號分別為L_H和P_H；

Step214：將PT的第i項，K≤i≤25歸并到堆頂，置P_i＝P_H，更新堆頂元素L_H＝L_H+L_i后調(diào)整小根堆；

Step215：重復(fù)步驟214直到PT中的所有項都?xì)w并到堆中；

Step216：將分區(qū)表PT按照首字母C升序排序。

2.根據(jù)權(quán)利要求1所述的基于OpenMP的并行字符串查詢方法，其特征在于所述Step220具體為：

Step221：基于OpenMP啟動K個線程，并行地為每個分區(qū)創(chuàng)建分區(qū)雙數(shù)組索引結(jié)構(gòu)，第i個線程負(fù)責(zé)第i個分區(qū)雙數(shù)組的構(gòu)建；對線程i讀取的字符串s，將其特定長度的前綴中的字符插入到第i個分區(qū)雙數(shù)組中；對待插入字符ch，從狀態(tài)x轉(zhuǎn)換到狀態(tài)y，對應(yīng)的狀態(tài)轉(zhuǎn)移公式為：

BASE[x]+CODE[ch]＝y(tǒng) (1)

CHECK[y]＝x (2)

式中，CODE[ch]表示字符ch的數(shù)值編碼，將字符“#”，“a”，“b”，“c”···“z”的編碼值設(shè)置為1，2，3，4···27。

3.根據(jù)權(quán)利要求1所述的基于OpenMP的并行字符串查詢方法，其特征在于所述查詢步驟具體為：

Step310：將一系列按字典序有序排序的字符串集Q組成一個查詢池；

Step320：每個線程取Q中一個字符串，根據(jù)所取字符串的首字母ch在P_{ch-‘a(chǎn)’}對應(yīng)的分區(qū)內(nèi)執(zhí)行DA的檢索算法，并返回檢索結(jié)果。