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

有效

• 申請號: 201910666139.2
• 申請日: 2019-07-23
• 公開（公告）號: CN110457531B
• 公開（公告）日: 2022-11-01
• 發明（設計）人: 賈連印;張崇德;李孟娟;丁家滿;陳明鮮;唐季林
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 昆明人從眾知識產權代理有限公司 53204
• 代理人: 沈艷尼

本發明涉及一種基于OpenMP的并行字符串查詢方法，屬于數據庫技術領域。包括字符串數據集預處理步驟，對字符串數據集和查詢集按照字典序升序排序并統計各首字母下所有字符串的字符串數量；索引創建步驟，基于貪婪分區方法將數據集劃分成K個分區并創建分區表，然后基于OpenMP并行為每個分區創建獨立的雙數組Trie索引結構；檢索步驟，對一批待查詢的字典序有序的查詢集，根據分區表確定各查詢對應的分區號并在相應分區內進行并行檢索。本發明通過貪婪分區算法和OpenMP等技術創建分區雙數組，使分區負載更為均衡，進而可提高雙數組創建以及檢索的效率。

技術領域

本發明涉及一種基于OpenMP的并行字符串查詢方法，屬于數據庫技術領域。

背景技術

隨著信息量的急劇增長，大量的數據需要以字符串的形式存儲，例如文檔，網頁，基因組數據等等，提高字符串的存儲和檢索效率具有非常重要的意義。為了解決這一問題，許多學者提出了處理字符串數據的有效算法和數據結構，其中，在1989年AOE提出的一種雙數組索引結構(DA)是一個典型的代表。DA使用兩個一維數組BASE和CHECK來存儲每個字符串能與其他字符串區分的前綴部分，使用一維數組TAIL來存儲字符串的后綴部分。在查詢過程中，只需要通過數學加法運算即可確定每個字符是否存儲在DA中，但在DA的構造過程中，因不同字符競爭位置產生沖突，從而導致索引創建的開銷加大，隨著字符串數量的增加，DA構造效率急劇降低。

目前對DA的優化算法的目標大多是提高索引結構的空間利用率，這也就導致了其創建效率往往不高。例如Yata等人提出了一種壓縮的雙數組索引結構，其將字符信息存儲在CHECK數組中來提升空間效率，然而這種方法需要額外的開銷來滿足BASE值的唯一性，從而導致雙數組創建效率的降低。為提高索引創建效率，Jia等人提出了一種基于首字母分區的雙數組索引結構，這種結構根據字符串的首字母將字符串劃分到不同的分區中，從而可將沖突限定在分區內，降低了沖突的數量及沖突處理的代價。其算法可有效提高雙數組構造效率，但其各個分區的字符串數量并不均衡，因此并不適用于并行環境。上述工作多為串行算法，未能充分利用目前越來越廣泛的多核CPU的處理能力，因此效率有待提升。OpenMP是一種已被廣泛接受的，用于共享內存并行系統的多處理器程序設計的一套指導性編譯處理方案，可很好地用于實現并行分區雙數組的構建及字符串查詢工作。

發明內容

本發明要解決的技術問題是提供一種基于OpenMP的并行字符串查詢方法，用于解決上述問題。

本發明的技術方案是：一種基于OpenMP的并行字符串查詢方法，具體為：

字符串數據集預處理步驟：將字符串數據集按字典序升序排序，按首字母分區，并統計各分區的字符串的數量，將查詢集同樣按字典序升序排序；

索引創建步驟：基于貪婪分區方法將數據集分區并創建分區表簡稱PT，通過OpenMP并行為每個分區創建分區雙數組(DA)索引結構；

查詢步驟：對待查詢的字典序有序的一批字符串，在相應的DA上進行檢索，獲取查詢結果。

所述字符串數據集預處理步驟具體為：

Step110：將字符串數據集按字典序升序排序；

Step120：統計各首字母對應的字符串數量L_a，L_b，L_c…L_z；

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

所述索引創建步驟具體為：

Step210：構建分區表PT，將數據集劃分為K個近似均勻的分區；

Step220：基于OpenMP為每個分區構建獨立的DA索引結構。

所述Step 210具體為：