[發明專利]一種哈希表滾動查找方法、系統及芯片有效

申請號：	202110769814.1	申請日：	2021-07-07
公開（公告）號：	CN113377819B	公開（公告）日：	2023-02-03
發明（設計）人：	張洪柳;司浩	申請（專利權）人：	山東方寸微電子科技有限公司;青島方寸微電子科技有限公司
主分類號：	G06F16/2455	分類號：	G06F16/2455;G06F16/22
代理公司：	濟南圣達知識產權代理有限公司 37221	代理人：	張慶騫
地址：	250000 山東省濟南市高新區***	國省代碼：	山東;37
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	一種哈希表滾動查找方法系統芯片
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

本發明提供一種哈希表滾動查找方法、系統及芯片。其中該方法包括將已壓縮歷史數據和待壓縮數據均調入到壓縮核并分別對應組裝及更新到線性移位寄存窗和待壓縮數據窗；將待壓縮數據窗中的數據進行哈希計算并根據計算結果滾動建立第一數組，第一數組存有待壓縮的鍵值；將線性移位寄存窗在歷史數據緩沖器中依次往后流水滾動并通過哈希計算構建第二數組，第二數組存有搜尋的歷史窗中與第一數組中待壓縮鍵值的哈希計算結果相同的鍵值的位置；將第一數組與第二數組進行流水并行一級模糊匹配，得到一級模糊匹配的可能最大候選位置；再基于歷史數據緩沖器和待壓縮數據窗進行第二級流水精準匹配，得到二級精準匹配候選位置，即最大字串匹配結果。

技術領域

本發明屬于軟件線程數據處理領域，尤其涉及一種哈希表滾動查找方法、系統及芯片。

背景技術

本部分的陳述僅僅是提供了與本發明相關的背景技術信息，不必然構成在先技術。

傳統設計基于軟件線程的hash查詢壓縮方法，其壓縮速度慢、硬件實現借助于采用的CPU處理器、整體的架構決定于采用的CPU以及對應周圍外設的固定第三方硬件平臺，軟件hash數據壓縮需要消耗大量的CPU周期，壓縮速度決定于CPU的最快固有頻率，并且hash壓縮線程將會占用CPU處理時間片。即傳統軟件hash壓縮處理方法，不方便應用于追求高速、實時的面向物聯網IoT(Internet of Things)應用的數據壓縮處理場景或相應的數據壓縮嵌入式硬件設備、硬件系統，以及由此類嵌入式硬件構建的硬件底層平臺。同時，傳統hash軟件壓縮處理線程，不具有IP自適應移植到硬件SoC的能力；軟件hash處理不能滿足實時壓縮/解壓的低延遲需求。

發明內容

為了解決上述背景技術中存在的技術問題，本發明提供一種哈希表滾動查找方法、系統及芯片，其能夠降低壓縮歷史數據搜尋及匹配的處理時間代價，使得壓縮率不損失。

為了實現上述目的，本發明采用如下技術方案：

本發明的第一個方面提供一種哈希表滾動查找方法。

一種哈希表滾動查找方法，其包括：

將已壓縮歷史數據和待壓縮數據均調入到壓縮核并分別對應組裝及更新到線性移位寄存窗和待壓縮數據窗；

將待壓縮數據窗中的數據進行哈希計算并根據計算結果滾動建立第一數組，所述第一數組存儲有待壓縮的鍵值；

將線性移位寄存窗在歷史數據緩沖器中依次往后流水滾動，并通過哈希計算構建第二數組，所述第二數組存儲有搜尋的歷史窗中與第一數組中待壓縮鍵值的哈希計算結果相同的鍵值的位置；

將第一數組與第二數組進行流水并行一級模糊匹配，得到一級模糊匹配的可能最大候選位置；

對于第一級匹配結果，基于歷史數據緩沖器和待壓縮數據窗進行第二級流水精準匹配，得到二級精準匹配候選位置，即最大字串匹配結果。

本發明的第二個方面提供一種哈希表滾動查找系統。

一種哈希表滾動查找系統，其包括：