[發明專利]數據存儲方法及裝置、數據查詢方法及裝置、電子設備

有效

• 申請號: 201711053709.8
• 申請日: 2017-10-31
• 公開（公告）號: CN107862026B
• 公開（公告）日: 2021-01-01
• 發明（設計）人: 王粲
• 申請（專利權）人: 北京小度信息科技有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F16/9032
• 代理公司: 北京智信四方知識產權代理有限公司 11519
• 代理人: 宋海龍;鐘文芳

本公開實施例公開了數據存儲方法及裝置、數據查詢方法及裝置、電子設備。所述數據存儲方法包括：獲取待存儲數據；根據待存儲數據構建并存儲字典樹；其中，所述字典樹的存儲結構中，從根節點開始，當前節點的存儲結構中存儲當前節點對應的字符；并且所述當前節點的存儲結構中以比特映射結構和單鏈表相結合的方式存儲子節點信息；所述單鏈表的結點存儲所述子節點的存儲結構的地址信息，所述比特映射結構包括多個字節，所述多個字節中的比特位映射存儲所述子節點對應的字符。本公開實施例在不增加字典樹節點內存消耗與字典樹查找時間復雜度的前提下，有效降低了維護子節點的內存冗余，提高了數據匹配速度。

技術領域

本公開涉及計算機技術領域，具體涉及一種數據存儲方法及裝置、數據查詢方法及裝置、電子設備及計算機可讀存儲介質。

背景技術

Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個26叉樹，數字的字典樹是一個10叉樹。與二叉查找樹不同，Trie樹的鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。

事先將已知的一些字符串的有關信息保存到字典樹樹里，查找另外一些未知字符串是否出現過或者出現頻率。例如，數據查詢系統中，將查詢關鍵詞集合中的所有關鍵詞構建成一個字典樹，并將該構建成的字典樹按照預設結構存儲起來；在用戶查詢時，通過匹配用戶輸入的查詢詞與字典樹存儲結構里的內容確定用戶當前要查詢的關鍵詞，進而為用戶輸出關鍵詞相關的結果。例如，如圖1所示的字典樹結構中，從字典樹根節點開始，參考用戶的部分輸入，尋找查找路徑。部分輸入完成匹配后，從當時的節點向下深度優先遍歷，即可獲取部分輸入對應的完整字符串。對于數字字典樹和字符字典樹來說，每個節點的字符可以是0-9這10個數字和a-z這26個字母。例如用戶輸入的字符串為“mo”，在圖1所示的字典樹中最左側第三層節點“o”處完成上述字符串“mo”的匹配，深度優先遍歷該第三層節點“o”下的子節點，可以獲取字符串“mop”和“moth”兩個完整字符串，作為用戶待查詢的關鍵詞。如果輸入字符串為“moa”，則無匹路徑，不能獲取任何數據。字典樹中，每個節點維護了自己的子節點。當前節點可以根據字符獲取對應的子節點。例如圖1中最左側第三層節點“o”，維護了標記為“p”和“t”的兩個子節點。

發明內容

本公開實施例提供一種數據存儲方法及裝置、數據查詢方法及裝置、電子設備及計算機可讀存儲介質。

第一方面，本公開實施例中提供了一種數據存儲方法。

具體的，所述數據存儲方法，包括：

獲取待存儲數據；

根據待存儲數據構建并存儲字典樹；

其中，所述字典樹的存儲結構中，從根節點開始，當前節點的存儲結構中存儲當前節點對應的字符；并且所述當前節點的存儲結構中以比特映射結構和單鏈表相結合的方式存儲子節點信息；所述單鏈表的結點存儲所述子節點的存儲結構的地址信息，所述比特映射結構包括多個字節，所述多個字節中的比特位映射存儲所述子節點對應的字符。

結合第一方面，本公開在第一方面的第一種實現方式中，所述比特映射結構中的多個預定比特位與預設字符集中的字符一一對應；所述待存儲數據由所述預設字符集中的字符構成。

結合第一方面的第一種實現方式，本公開在第一方面的第二種實現方式中，所述比特映射結構中與所述子節點的字符對應的比特位的值為M，其他比特位的值為N，N和M不同，且N和M的取值范圍為0或1。

結合第一方面的第一種實現方式，本公開在第一方面的第三種實現方式中，所述單鏈表的結點個數與所述當前節點的子節點個數相同，且所述單鏈表的結點的順序與所述子節點對應的字符在所述比特映射結構中對應的比特位的順序相同。