[發明專利]數據匹配方法和數據匹配裝置

有效

• 申請號: 200910091700.5
• 申請日: 2009-08-28
• 公開（公告）號: CN101996139A
• 公開（公告）日: 2011-03-30
• 發明（設計）人: 歐陽劍;劉承輝;盛克華;唐會軍
• 申請（專利權）人: 百度在線網絡技術(北京)有限公司
• 主分類號: G06F12/06
• 分類號: G06F12/06;G06F17/30;H03M7/30
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 張紅蓮

1.一種數據匹配方法，其特征在于，包括：

歷史數據存儲窗口將待輸入字符之前預定字節的歷史字符保存在所述歷史數據存儲窗口的隨機存儲器中；

哈希計算單元計算所述待輸入字符的哈希值，根據所述哈希值確定與所述待輸入字符對應的字符索引，并將所述字符索引存儲在所述哈希計算單元的隨機存儲器中，其中，所述字符索引為與所述待輸入字符對應的歷史字符在所述歷史數據存儲窗口的隨機存儲器中的位置信息；

匹配查找單元獲取所述哈希計算單元的隨機存儲器中的字符索引，并根據所述字符索引對所述待輸入字符和所述歷史字符進行匹配。

2.根據權利要求1所述的方法，其特征在于，所述歷史數據存儲窗口的隨機存儲器為16個可單獨尋址的分布式隨機存儲器，其中，每個可單獨尋址的分布式隨機存儲器均具有兩個獨立的讀端口。

3.根據權利要求2所述的方法，其特征在于，所述歷史數據存儲窗口將待輸入字符之前預定字節的歷史字符保存在所述歷史數據存儲窗口的隨機存儲器中包括：

所述歷史數據存儲窗口從第1個可單獨尋址的分布式隨機存儲器開始，將所述歷史字符順序放入所述16個可單獨尋址的分布式隨機存儲器中，如果將所述歷史字符放入最后1個可單獨尋址的分布式隨機存儲器后，還存在未放入的歷史字符，則將所述未放入的歷史字符從所述第1個可單獨尋址的分布式隨機存儲器開始，再次順序放入所述16個可單獨尋址的分布式隨機存儲器，依次循環，直到將所述預定字節的歷史字符全部放入所述16個可單獨尋址的分布式隨機存儲器中為止，其中，每個可單獨尋址的分布式隨機存儲器最多存儲1千字節歷史字符。

4.根據權利要求3所述的方法，其特征在于，所述預定字節為16千字節。

5.根據權利要求4所述的方法，其特征在于，所述哈希計算單元將所述字符索引存儲在所述哈希計算單元的隨機存儲器中包括：

所述哈希計算單元以所述哈希值為地址，將對應于所述哈希值的至少兩個字符索引分別存儲在不同的哈希計算單元的隨機存儲器中，其中，所述哈希計算單元的隨機存儲器包括至少兩個隨機存儲器；

如果在所述哈希計算單元的隨機存儲器中，已經存儲以所述哈希值為地址的舊字符索引，則使用新字符索引替代所述舊字符索引。

6.根據權利要求5所述的方法，其特征在于，所述匹配查找單元獲取所述哈希計算單元的隨機存儲器中的字符索引之前，所述方法還包括：

所述哈希計算單元讀取所述字符索引，并將所述字符索引發送到所述匹配查找單元。

7.根據權利要求6所述的方法，其特征在于，所述哈希計算單元讀取所述哈希計算單元的隨機存儲器中的字符索引包括：

所述哈希計算單元直接從所述哈希計算單元的隨機存儲器中讀取所述字符索引；或者，

在所述字符索引還未寫入所述哈希計算單元的隨機存儲器的情況下，直接讀取未存儲的所述字符索引。

8.根據權利要求7所述的方法，其特征在于，所述匹配查找單元根據所述字符索引對所述待輸入字符和所述歷史字符進行匹配包括：

所述匹配查找單元根據所述字符索引產生并存儲所述歷史數據存儲窗口的讀地址；

所述匹配查找單元根據所述讀地址從所述歷史數據存儲窗口中的所述16個可單獨尋址的分布式隨機存儲器中讀取并存儲32字節的歷史字符，并根據所述讀地址的低4位從所述32字節的歷史字符中選擇并存儲有效的26字節的歷史字符；

在新發起的匹配查找中，所述匹配查找單元根據所述字符索引對所述匹配查找單元的移位寄存器的低24位中存儲的3字節的待輸入字符和所述26字節的歷史字符中的3字節歷史字符進行匹配；

如果所述3字節的待輸入字符匹配命中，在第二個周期內，所述匹配查找單元獲取與當前待輸入字符對應的至少兩個字符索引，并根據與所述當前待輸入字符對應的至少兩個字符索引對存儲在所述匹配查找單元的移位寄存器的16至23位中的所述當前待輸入字符和所述26字節的歷史字符中相應的1字節歷史字符進行匹配操作，如果所述當前待輸入字符匹配成功，則繼續對下一個當前待輸入字符進行匹配，依次類推，直到匹配結束，如果所述當前待輸入字符匹配失敗，則結束匹配；

在匹配結束后，得到第一匹配結果。