[發明專利]一種基于分區雙數組Trie的字符串檢索方法及裝置

有效

• 申請號: 201810179880.1
• 申請日: 2018-03-05
• 公開（公告）號: CN108509505B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 陳文焰;賈連印;丁家滿;李孟娟;游進國;章露露;呂曉偉
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/9032
• 分類號: G06F16/9032;G06F16/901
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及一種基于分區雙數組Trie的字符串檢索方法及裝置，屬于數據庫技術領域。本發明包括數據預處理步驟，對字符串排序并統計不同首字符的字符串數量；索引創建步驟，根據輸入的分區數量N進行分區劃分，生成分區映射表并為每個分區創建獨立的雙數組Trie索引結構；檢索步驟，輸入檢索的字符串，在分區雙數組Trie索引結構上進行檢索。本發明通過創建分區雙數組，可有效降低傳統雙數組創建過程的沖突和處理沖突的代價，能夠大幅提高索引創建的效率以及檢索的效率。

技術領域

本發明涉及一種基于分區雙數組Trie的字符串檢索方法及裝置，屬于數據庫技術領域。

背景技術

近年來，數據庫領域對字符串的檢索進行了大量的研究。Trie是字符存儲在邊上的一個有序樹結構，可廣泛應用在詞法分析器、書目搜索、拼寫檢查的字典、語言模型的實現、IP路由地址的查找、字符串或集合的相似度查詢和連接等領域。目前有兩種常見的Trie存儲方式，1)矩陣存儲，2)鏈式存儲。上述兩種方式均需要創建完整的Trie，從而導致較大的存儲開銷，尤其在數據集比較稀疏的情況下。為降低Trie的空間開銷，Aoe,Yata等人提出了雙數組Trie數據結構，該結構采用BASE和CHECK兩個數組存儲每個字符串能與所有其它字符串相區分的前綴部分，用另一個字符數組存TAIL存儲字符串的后綴部分，其檢索時僅涉及到數組的訪問和加兩種操作，因此效率較高。

盡管如此，雙數組Trie還存在空間開銷較高，索引創建開銷大等問題，有較多針對DAT進行的一些優化研究，例如在索引創建的過程中，優先處理分支更多的結點，這種優化策略可以提高空間的利用，但其比較分支的過程引入額外的開銷，從而降低了雙數組Trie索引創建的效率；還有CDA(Compression Double Array，一種空間更加壓縮的雙數組Trie)將字符信息存儲在CHECK數組中來壓縮存儲空間，但這種方法需要額外的開銷來滿足BASE值的唯一性，同樣導致索引創建效率的降低；在CDA的基礎上，又有學者提出了單數組Trie的結構，該結構移除了BASE數組，僅使用CHECK數組存儲字符信息，但是該方法主要應用于如郵政編碼等固定長度的字符串。

上述對DAT的優化算法多集中于最大化壓縮存儲空間，往往導致其創建效率的大幅降低。

而從雙數組Trie索引的創建過程進行剖析，發現索引的創建過程伴隨著沖突(在雙數組Trie中插入字符串時，不同的父位置爭奪同一子位置的情況稱為沖突)的產生，且沖突次數隨著字符串數量的增加而有所增加。

發明內容

本發明要解決的技術問題是提供一種基于分區雙數組Trie的字符串檢索方法與裝置，目的在于減少DAT索引創建過程中沖突的數量以及解決沖突的開銷，從而提高DAT索引結構創建的效率；有效解決因數據量增多而導致DAT索引創建效率急劇下降的問題，同時提高DAT的檢索效率。

本發明的技術方案是：一種基于分區雙數組Trie的字符串檢索方法，包括以下步驟：

數據預處理步驟：對字符串數據集進行排序并統計不同首字符的字符串數量；

索引創建步驟：根據輸入的分區數量N，進行分區的劃分，再生成分區映射表(以下簡稱PMT，所謂PMT是前綴與分區之間的一種映射關系)并為每個分區創建獨立的雙數組Trie(double array trie，以下簡稱DAT)索引結構；

檢索步驟：輸入檢索的字符串，在分區DAT索引結構上進行檢索。

數據預處理步驟分為兩個步驟：

步驟110：對字符串數據集進行字典序升序排序；

步驟111：統計不同首字符的字符串數量。

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

步驟210：分區的劃分；

步驟220：生成PMT；