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

有效

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

技術領域

本發明實施例涉及數據壓縮技術領域，尤其涉及一種數據匹配方法和數據匹配裝置。

背景技術

目前，為了減少數據需要的存儲介質，提高數據傳輸效率，數據壓縮在互聯網、數據庫、存儲應用中應用非常廣泛，包括數據庫應用、數據備份、壓縮文件系統、網頁(web)前端服務等。其中，GZIP壓縮算法是目前應用最廣泛的一種壓縮算法，例如，在Web服務器軟件(例如，apache、IIS)上使用GZIP對網頁進行壓縮，從而提高訪問響應速度。

在相關技術中，GZIP壓縮算法包括兩部分：Lz77算法與哈夫曼(Huffman)編碼。Lz77算法通過對原始數據進行去冗余處理以達到壓縮的目的。該算法的軟件實現方法是在一個數據窗口內(該數據窗口的大小一般為32KB)，不斷的迭代尋找最佳的匹配數據串進而消除冗余，并依賴中央處理器(Central?Processing?Unit；以下簡稱：CPU)對數據進行壓縮。

在匹配查找過程中，為了快速向前定位可能匹配的數據，對每個比特(byte)的待輸入字符，會計算一個hash值，如果兩個字符的hash值相同，則可能存在匹配。在目前的實現方法中，會用一個鏈表數據結構保存所有hash值相同的字符索引，對每個輸入字符，首先計算其hash值，然后使用hash值尋址到對應的鏈表，依次把字符索引取出進行匹配查找，最后會把當前字符的索引插入鏈表供后面字符的匹配查找使用。

在實現本發明過程中，發明人發現現有技術中至少存在如下問題：

使用軟件對Lz77算法進行串行處理的效率非常低，并且消耗大量的CPU與存儲器(memory)資源，成為軟件實現Lz77算法的性能瓶頸。

發明內容

本發明實施例提供一種數據匹配方法和數據匹配裝置，用以解決現有技術中使用軟件對Lz77算法進行串行處理的效率低、且消耗大量的CPU與存儲器資源的缺陷，實現通過基于可編程門陣列的硬件來實現Lz77算法。

本發明實施例提供一種數據匹配方法，包括：

歷史數據存儲窗口將待輸入字符之前預定字節的歷史字符保存在歷史數據存儲窗口的隨機存儲器中；哈希計算單元計算待輸入字符的哈希值，根據哈希值確定與待輸入字符對應的字符索引，并將字符索引存儲在哈希計算單元的隨機存儲器中，其中，字符索引為與待輸入字符對應的歷史字符在歷史數據存儲窗口的隨機存儲器中的位置信息；匹配查找單元獲取哈希計算單元的隨機存儲器中的字符索引，并根據字符索引對待輸入字符和歷史字符進行匹配。

本發明實施例還提供一種數據匹配裝置，包括：

歷史數據存儲窗口，用于保存待輸入字符之前預定字節的歷史字符；哈希計算單元，用于計算待輸入字符的哈希值，根據哈希值確定與待輸入字符對應的字符索引，并將字符索引存儲在哈希計算單元的隨機存儲器中，其中，字符索引為與待輸入字符對應的歷史字符在歷史數據存儲窗口的隨機存儲器中的位置信息；匹配查找單元，用于獲取哈希計算單元的隨機存儲器中的字符索引，并根據字符索引對待輸入字符和歷史字符進行匹配。

本發明實施例的數據匹配方法和數據匹配裝置，通過基于可編程門陣列的硬件來實現Lz77算法，克服了現有技術中使用軟件對Lz77算法進行串行處理的效率低、且消耗大量的CPU與存儲器資源的缺陷，能夠提高Lz77算法的處理效率，極大地節省了CPU與存儲器的資源。

附圖說明

為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作一簡單地介紹，顯而易見地，下面描述中的附圖是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。

圖1是根據本發明實施例的數據匹配裝置的結構示意圖；

圖2是根據本發明實施例的歷史數據存儲窗口分布式存儲結構的示意圖；

圖3是根據本發明實施例的交叉存儲方式的示意圖；

圖4是根據本發明實施例的哈希計算單元的隨機存儲器的結構示意圖；

圖5是根據本發明實施例的哈希計算單元的結構示意圖；

圖6是根據本發明實施例的匹配查找單元的結構示意圖；

圖7是根據本發明實施例的前端處理單元的結構示意圖；

圖8是根據本發明實施例的地址管理模塊的結構示意圖；

圖9是根據本發明實施例的數據選擇模塊的結構示意圖；

圖10是根據本發明實施例的查詢匹配模塊的結構示意圖；

圖11是根據本發明實施例的后端處理單元的結構示意圖；