[發明專利]一種數據檢索優化方法、裝置和計算機設備

有效

• 申請號: 201811632444.1
• 申請日: 2018-12-29
• 公開（公告）號: CN111382323B
• 公開（公告）日: 2023-08-11
• 發明（設計）人: 吳義譜;李文博;張炎潑
• 申請（專利權）人: 貴州白山云科技股份有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F16/901
• 代理公司: 北京名華博信知識產權代理有限公司 11453
• 代理人: 白瑩;苗源

1.一種數據檢索優化方法，其特征在于，包括：

對原始前綴樹的單分支節點進行裁剪；

創建位圖數組，所述位圖數組中的位圖元素與所述原始前綴樹中的中間節點一一對應，一個位圖元素存儲所述原始前綴樹中一個中間節點的分支信息；

創建跳數數組，所述跳數數組中的元素與所述原始前綴樹的中間節點一一對應，一個跳數數組中的元素存儲所述原始前綴樹中一個中間節點裁剪掉的從單分支起始的節點至單分支結束的節點之間的節點數量；

創建葉子節點數組，所述葉子節點數組中的元素與用戶數據一一對應，一個葉子節點數組中的元素存儲所述原始前綴樹中一個索引字符串對應的文件位置；

從所述跳數數組、位圖數組、葉子節點數組進行檢索，按照前綴樹自根節點向葉子節點的方向，比較檢索的字符串或字符串集合與前綴樹；

查詢當前匹配到的中間節點的可跳過的節點數；

跳過所述可跳過的節點數，繼續比較檢索的字符串或字符串集合與所述前綴樹；

在存在與所述檢索的字符串或字符串集合匹配的葉子節點時，返回所述葉子節點的數據。

2.根據權利要求1所述的數據檢索優化方法，其特征在于，所述可跳過的節點數為：

在查找的字符串值指向單分支節點時，從單分支起始的節點至單分支結束的節點之間的節點數量。

3.根據權利要求1所述的數據檢索優化方法，其特征在于，查詢當前匹配到的中間節點的可跳過的節點數的步驟包括：

根據當前匹配的中間節點查找所述跳數數組；

在所述中間節點對應的所述跳數數組中的元素存儲有所述中間節點作為單分支起始的節點至單分支結束的節點之間的節點數量時，以所述節點數量作為可跳過的節點數。

4.根據權利要求1所述的數據檢索優化方法，其特征在于，所述跳數數組、位圖數組和葉子節點數組的元素均為限制預設存儲容量所能表示的最大數組元素個數。

5.根據權利要求4所述的數據檢索優化方法，其特征在于，所述限制預設存儲容量為2byte。

6.一種數據檢索優化裝置，其特征在于，包括：

跳數匹配模塊，用于查詢當前匹配到的中間節點的可跳過的節點數；

比較檢索模塊，用于從跳數數組、位圖數組、葉子節點數組進行檢索，按照前綴樹自根節點向葉子節點的方向，比較檢索的字符串或字符串集合與前綴樹，跳過所述可跳過的節點數，繼續比較檢索的字符串或字符串集合與所述前綴樹；

數據返回模塊，用于在存在與所述檢索的字符串或字符串集合匹配的葉子節點時，返回所述葉子節點的數據；

該裝置還包括：

前綴樹裁剪模塊，用于對原始前綴樹的單分支節點進行裁剪；

中間節點存儲模塊，用于創建位圖數組，所述位圖數組中的位圖元素與所述原始前綴樹中的中間節點一一對應，一個位圖元素存儲所述原始前綴樹中一個中間節點的分支信息；

跳數存儲模塊，用于創建跳數數組，所述跳數數組中的元素與所述原始前綴樹的中間節點一一對應，一個跳數數組中的元素存儲所述原始前綴樹中一個中間節點裁剪掉的從單分支起始的節點至單分支結束的節點之間的節點數量；

用戶數據存儲模塊，用于創建葉子節點數組，所述葉子節點數組中的元素與用戶數據一一對應，一個葉子節點數組中的元素存儲所述原始前綴樹中一個索引字符串或字符串集合對應的文件位置。

7.根據權利要求6所述的數據檢索優化裝置，其特征在于，所述跳數匹配模塊包括：

數組查找單元，用于根據當前匹配的中間節點查找所述跳數數組；

跳數確定單元，用于在所述中間節點對應的所述跳數數組中的元素存儲有所述中間節點作為單分支起始的節點至單分支結束的節點之間的節點數量時，以所述節點數量作為可跳過的節點數。

8.一種計算機設備，其特征在于，包括存儲器和處理器，所述存儲器上存儲有計算機程序，所述處理器運行所述計算機程序時實現如權利要求1－5中任意一項所述的方法的步驟。