[發明專利]一種字典序分區雙數組的字符串批量查詢方法及裝置

在審

• 申請號: 202010151192.1
• 申請日: 2020-03-06
• 公開（公告）號: CN111339381A
• 公開（公告）日: 2020-06-26
• 發明（設計）人: 賈連印;張崇德;李孟娟;丁家滿;陳明鮮;唐季林
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F16/901;G06F40/242
• 代理公司: 昆明人從眾知識產權代理有限公司 53204
• 代理人: 沈艷尼

1.一種字典序分區雙數組的字符串批量查詢方法，其特征在于，包括如下步驟：

字符串數據集預處理步驟：將字符串數據集按字典序升序排序并統計數據集中所有字符串的總長度L；將查詢集同樣按字典序升序排序；

索引創建步驟：按照全部字符串長度將數據集分區并創建分區映射表PMT，為每個分區創建分區雙數組DA索引；

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

2.根據權利要求1所述的字典序分區雙數組的字符串批量查詢方法，其特征在于：所述的字符串數據集預處理步驟分為三個步驟：

步驟110：將字符串數據集按字典序升序排序；

步驟120：累加并計算所有字符串的總長度L；

步驟130：將查詢集按字典序升序排序。

3.根據權利要求1所述的字典序分區雙數組的字符串批量查詢方法，其特征在于：所述的索引創建步驟按如下步驟執行：

步驟210：給定分區個數K，按照數據集中字符串總長度將數據集均衡地劃分為K個分區，每個分區字符串總長度近似等于[L/K]；如果分區線從某個字符串內部劃過，將該字符串劃分成兩個臨時子串用于確定該字符串所屬分區，比較兩個臨時子串的大小，將該字符串劃分到臨時子串較大的分區；

步驟220：構建長度為K-1的分區映射表PMT，表中第i個位置(i＝0,1,……,k-2)存儲第i+1個分區的第一個字符串；

步驟230：為每個分區創建分區雙數組索引結構，對當前讀取的字符串s，將其特定長度的前綴中的字符插入到對應的分區雙數組中，其中特定長度的前綴指的是s中能與任何其他字符相區別的前綴，對于插入字符串s中的某個字符“c”，從狀態x轉換到狀態y，其狀態轉移公式為：

BASE[x]+CODE[c]＝y (1)

CHECK[y]＝x (2)

其中，用BASE和CHECK來存儲字符串的前綴部分，BASE和CHECK為存儲字符的數組名，“x”和“y”為數組下標，用TAIL數組來存儲字符串的剩余部分，CODE[s]表示字符s的數值編碼，將字符“#”，“a”，“b”，“c”···“z”的編碼值設置為1，2，3，4···27。

4.根據權利要求1所述的字典序分區雙數組的字符串批量查詢方法，其特征在于，所述的檢索步驟按如下步驟執行：

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

步驟320：依序從查詢池中讀取字符串，通過二分查找在PMT中確定字符串所在的分區號；

步驟330：根據獲取的分區號，在對應分區內執行DA的查詢算法，并返回查詢結果；

步驟340：取Q中下一個字符串；

步驟350：迭代執行步驟320-340，直至查詢池字符串為空。

5.一種字典序分區雙數組的字符串批量查詢裝置，其特征在于：采用權利要求1-4任一項所述的方法，包括：

字符串數據集預處理模塊：對字符串數據集進行升序排序并統計所有字符串的長度；

索引創建裝置：對字符串按照字符串長度根據分區數量K劃分成K個分區并根據分區位置構建分區映射表并為每個分區創建獨立的雙數組索引結構；

檢索裝置：對待查詢的字典序有序的一批字符串，根據分區映射表在相應的DA上進行檢索，獲取查詢結果。