[發(fā)明專利]數(shù)據(jù)存儲方法及裝置、數(shù)據(jù)查詢方法及裝置、電子設(shè)備

有效

• 申請?zhí)枺?/td>: 201711053709.8
• 申請日: 2017-10-31
• 公開（公告）號: CN107862026B
• 公開（公告）日: 2021-01-01
• 發(fā)明（設(shè)計）人: 王粲
• 申請（專利權(quán)）人: 北京小度信息科技有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903;G06F16/9032
• 代理公司: 北京智信四方知識產(chǎn)權(quán)代理有限公司 11519
• 代理人: 宋海龍;鐘文芳

1.一種數(shù)據(jù)存儲方法，其特征在于，包括：

獲取待存儲數(shù)據(jù)；

根據(jù)待存儲數(shù)據(jù)構(gòu)建并存儲字典樹；

其中，所述字典樹的存儲結(jié)構(gòu)中，從根節(jié)點(diǎn)開始，當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)中存儲當(dāng)前節(jié)點(diǎn)對應(yīng)的字符；并且所述當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)中以比特映射結(jié)構(gòu)和單鏈表相結(jié)合的方式存儲子節(jié)點(diǎn)信息；所述單鏈表的結(jié)點(diǎn)存儲所述子節(jié)點(diǎn)的存儲結(jié)構(gòu)的地址信息，所述比特映射結(jié)構(gòu)包括多個字節(jié)，所述多個字節(jié)中的比特位映射存儲所述子節(jié)點(diǎn)對應(yīng)的字符。

2.根據(jù)權(quán)利要求1所述的數(shù)據(jù)存儲方法，其特征在于，所述比特映射結(jié)構(gòu)中的多個預(yù)定比特位與預(yù)設(shè)字符集中的字符一一對應(yīng)；所述待存儲數(shù)據(jù)由所述預(yù)設(shè)字符集中的字符構(gòu)成。

3.根據(jù)權(quán)利要求2所述的數(shù)據(jù)存儲方法，其特征在于，所述比特映射結(jié)構(gòu)中與所述子節(jié)點(diǎn)的字符對應(yīng)的比特位的值為M，其他比特位的值為N，N和M不同，且N和M的取值范圍為0或1。

4.根據(jù)權(quán)利要求2所述的數(shù)據(jù)存儲方法，其特征在于，所述單鏈表的結(jié)點(diǎn)個數(shù)與所述當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)個數(shù)相同，且所述單鏈表的結(jié)點(diǎn)的順序與所述子節(jié)點(diǎn)對應(yīng)的字符在所述比特映射結(jié)構(gòu)中對應(yīng)的比特位的順序相同。

5.一種數(shù)據(jù)查詢方法，其特征在于，包括：

獲取字典樹的當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)；所述字典樹由預(yù)設(shè)詞組集合構(gòu)建而成，所述當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)包括當(dāng)前節(jié)點(diǎn)對應(yīng)的字符、比特映射結(jié)構(gòu)和單鏈表；所述單鏈表的結(jié)點(diǎn)存儲所述當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的存儲結(jié)構(gòu)的地址信息，所述比特映射結(jié)構(gòu)包括多個字節(jié)，所述多個字節(jié)中的比特位映射存儲所述子節(jié)點(diǎn)對應(yīng)的字符；

利用當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)將待查詢數(shù)據(jù)的當(dāng)前字符與當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)對應(yīng)的字符進(jìn)行匹配；

在匹配成功后，利用當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)獲取匹配成功的子節(jié)點(diǎn)的存儲結(jié)構(gòu)，并與待查詢數(shù)據(jù)的下一字符進(jìn)行匹配，直至完成待查詢數(shù)據(jù)的匹配。

6.根據(jù)權(quán)利要求5所述的數(shù)據(jù)查詢方法，其特征在于，所述比特映射結(jié)構(gòu)中的多個預(yù)定比特位與預(yù)設(shè)字符集中的字符一一對應(yīng)；所述預(yù)設(shè)詞組集合中的詞組由所述預(yù)設(shè)字符集中的字符構(gòu)成。

7.根據(jù)權(quán)利要求6所述的數(shù)據(jù)查詢方法，其特征在于，利用當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)將待查詢數(shù)據(jù)的當(dāng)前字符與當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)對應(yīng)的字符進(jìn)行匹配，包括：

根據(jù)所述比特映射結(jié)構(gòu)中值為M的比特位確定所述當(dāng)前節(jié)點(diǎn)是否存在與所述待查詢數(shù)據(jù)的當(dāng)前字符相匹配的子節(jié)點(diǎn)，其中M為0或1。

8.根據(jù)權(quán)利要求6所述的數(shù)據(jù)查詢方法，其特征在于，所述單鏈表的結(jié)點(diǎn)個數(shù)與所述當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)個數(shù)相同，且所述單鏈表的結(jié)點(diǎn)的順序與所述子節(jié)點(diǎn)對應(yīng)的字符在所述比特映射結(jié)構(gòu)中對應(yīng)的比特位的順序相同。

9.根據(jù)權(quán)利要求8所述的數(shù)據(jù)查詢方法，其特征在于，利用當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)獲取匹配成功的子節(jié)點(diǎn)的存儲結(jié)構(gòu)，包括：

根據(jù)所述比特映射結(jié)構(gòu)確定與匹配成功的子節(jié)點(diǎn)對應(yīng)的所述單鏈表的結(jié)點(diǎn)；

從匹配成功的所述子節(jié)點(diǎn)對應(yīng)的所述單鏈表的結(jié)點(diǎn)獲取匹配成功的所述子節(jié)點(diǎn)的存儲結(jié)構(gòu)的存儲地址。

10.一種數(shù)據(jù)存儲裝置，其特征在于，包括：

第一獲取模塊，被配置為獲取待存儲數(shù)據(jù)；

存儲模塊，被配置為根據(jù)待存儲數(shù)據(jù)構(gòu)建并存儲字典樹；

其中，所述字典樹的存儲結(jié)構(gòu)中，從根節(jié)點(diǎn)開始，當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)中存儲當(dāng)前節(jié)點(diǎn)對應(yīng)的字符；并且所述當(dāng)前節(jié)點(diǎn)的存儲結(jié)構(gòu)中以比特映射結(jié)構(gòu)和單鏈表相結(jié)合的方式存儲子節(jié)點(diǎn)信息；所述單鏈表的結(jié)點(diǎn)存儲所述子節(jié)點(diǎn)的存儲結(jié)構(gòu)的地址信息，所述比特映射結(jié)構(gòu)包括多個字節(jié)，所述多個字節(jié)中的比特位映射存儲所述子節(jié)點(diǎn)對應(yīng)的字符。

11.根據(jù)權(quán)利要求10所述的數(shù)據(jù)存儲裝置，其特征在于，所述比特映射結(jié)構(gòu)中的多個預(yù)定比特位與預(yù)設(shè)字符集中的字符一一對應(yīng)；所述待存儲數(shù)據(jù)由所述預(yù)設(shè)字符集中的字符構(gòu)成。