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

在審

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

本發明涉及一種字典序分區雙數組字符串批量查詢方法及裝置，屬于信息檢索領域。包括：字符串數據集預處理步驟，對字符串數據集和查詢集按照字典序升序排序并統計數據集中字符串的總長度；索引創建步驟，對字符串按照全部字符串長度劃分成K個分區并創建分區映射表，然后為每個分區創建獨立的雙數組索引結構；檢索步驟，對一批待查詢的字典序有序的查詢集，根據查詢集構建分區查詢表確定各查詢的分區號并在相應分區內進行檢索。本發明通過長度分區創建和檢索雙數組，使分區負載更為均衡，進而提高雙數組的創建效率。

技術領域

本發明一種字典序分區雙數組的字符串批量查詢方法及裝置，具體涉及一種對字符串數據集進行排序分區并建立分區雙數組索引的方法及裝置，屬于信息檢索領域。

背景技術

字符串存儲和查詢是很多領域的基本問題，提高字符串存儲和查詢效率有著較為重要的意義，而Trie是字符串存儲和查詢最為常見的結構，但對常見的trie的矩陣存儲和鏈式存儲來說，均難以兼顧查詢性能和存儲空間開銷之間的矛盾。Aoe等人提出的DA在查詢性能和存儲空間之間取得了較好的平衡，該結構基于BASE和CHECK兩個一維整型數組來壓縮存儲字符串，空間效率較高；此外，其在檢索某節點的特定孩子時只需要執行簡單的加操作，因此同樣具有較好的查詢性能。

隨著字符串數量的增加，雙數組的空間開銷和索引創建開銷也會增大，為了解決上述問題，許多學者針對DA的優化進行了研究，例如Yata等人提出了一種壓縮的雙數組索引結構，這種結果將字符信息存儲在CHECK數組中來提升空間效率，Kanda等人通過將雙數組分段并為每段設計對應的線性函數來確定BASE值，并針對動態雙數組索引構建時間和空間效率不高的問題，通過為空白位置鏈表來快速尋找可插入位置等優化措施來提升效率。

上述方法多致力于降低空間開銷，而忽視了索引創建效率。提高索引創建效率可提高索引的可管理性，這對在大規模數據集上創建索引非常重要。此外，對連接類操作而言，同樣重要，因為索引創建時間需計入到總操作用時中。于是又有學者對于如何提升其創建效率進行了研究，提出了一種基于首字母分區的雙數組索引結構，這種結構根據字符串的首字母將不同首字母的字符串劃分到不同的分區中，從而降低因為不同前綴而造成的沖突，但是這種分區方法中每個分區的字符的數量并不均衡，負載均衡上沒有做到最好。

發明內容

本發明提供了一種字典序分區雙數組的字符串批量查詢方法及裝置，根據數據集字符串的長度進行分區并為每個分區創建DA索引結構，能夠有效降低傳統DA索引創建過程中沖突的數量以及解決沖突的開銷，減少索引的創建時間，從而提高DA索引結構創建的效率。

本發明采用的技術方案是：一種字典序分區雙數組的字符串批量查詢方法，其特征在于，包括如下步驟：

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

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

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

所述的字符串數據集預處理步驟分為三個步驟：

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

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

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

所述的索引創建步驟按如下步驟執行：

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