[發(fā)明專利]一種基于流水線的數(shù)據(jù)匹配方法和裝置

有效

• 申請?zhí)枺?/td>: 201410197834.6
• 申請日: 2014-05-12
• 公開（公告）號: CN103997346B
• 公開（公告）日: 2017-02-15
• 發(fā)明（設(shè)計）人: 董乾;劉勇;李冰;趙霞;王剛
• 申請（專利權(quán)）人: 東南大學
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 江蘇永衡昭輝律師事務(wù)所32250
• 代理人: 王斌

技術(shù)領(lǐng)域

本發(fā)明實施例涉及數(shù)據(jù)壓縮技術(shù)領(lǐng)域，尤其涉及一種基于流水線的數(shù)據(jù)匹配方法和裝置。??

背景技術(shù)

目前，為了節(jié)省數(shù)據(jù)存儲空間，減少存儲介質(zhì)需求，同時提高數(shù)據(jù)傳輸效率，數(shù)據(jù)壓縮技術(shù)在物聯(lián)網(wǎng)、數(shù)據(jù)庫、云存儲等領(lǐng)域有著廣泛的應(yīng)用。其中，Gzip壓縮算法是目前應(yīng)用最廣泛的一種高效且開源壓縮算法，例如，使用Gzip壓縮算法在Web服務(wù)器上將網(wǎng)頁進行壓縮，可以提高訪問響應(yīng)速度。?

Gzip壓縮算法具體包括兩部分：LZ77算法和哈夫曼（Huffman）編碼。其中哈夫曼編碼不在本專利討論范圍之內(nèi)。LZ77算法通過匹配替換將原始源文件進行去冗余，以達到壓縮的目的。LZ77算法的軟件實現(xiàn)方法是：先使用哈希算法，將可能匹配的字符串的地址構(gòu)成鏈表；然后在匹配范圍內(nèi)（也被稱為滑動窗口，大小為32768，32KB)，將當前處理字符串與上述鏈表中字符串，不斷迭代尋找最佳匹配；最后將匹配串替換來去冗余。??

目前LZ77算法軟件實現(xiàn)時，會使用哈希算法構(gòu)造鏈表；從文件頭開始，為原始源文件中每3個連續(xù)字節(jié)（3?byte?:?24bit）計算得出一個15比特（15bit）哈希值（根據(jù)哈希算法，哈希值相同，即有可能存在匹配），然后會用一個鏈表數(shù)據(jù)結(jié)構(gòu)保存所有哈希相同的字符索引；對每個進行匹配的字符，首先計算其和其后2個字節(jié)（Byte），一共連續(xù)3個字節(jié)（Byte），的哈希值；然后維護哈希鏈表的同時，使用哈希鏈表循環(huán)取出匹配范圍內(nèi)可能匹配的字符串地址，根據(jù)地址依次將字符串取出進行匹配比較；匹配成功部分字符串也需要通過哈希計算并插入鏈表，供后面字符匹配查找時使用。

在實現(xiàn)本發(fā)明過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)中至少存在如下問題：?

使用軟件對LZ77算法進行順序串行（哈希計算→鏈表維護→取值比較（循環(huán)迭代取值比較））處理時，處理效率非常低，消耗大量的處理器與存儲器資源；目前LZ77算法軟件實現(xiàn)哈希計算方法存在缺陷，相鄰編碼字符串的哈希值之間容易沖突（字符串不同，哈希值相同），造成無效匹配；兩者是軟件實現(xiàn)LZ77算法的性能瓶頸。?

發(fā)明內(nèi)容

本發(fā)明提供一種基于流水線的數(shù)據(jù)匹配方法和裝置，以解決現(xiàn)有技術(shù)中，軟件實現(xiàn)LZ77算法，順序串行迭代處理的匹配成功率低，效率差、且消耗大量處理器與存儲器資源的缺陷，該LZ77算法實施例現(xiàn)通過基于可編程門陣列的硬件來實現(xiàn)。??

本發(fā)明提供一種基于流水線的數(shù)據(jù)匹配方法，包括：

字典存儲器用于分部存儲將要被匹配壓縮的文件，根據(jù)匹配壓縮的進度適時，字典存儲器循環(huán)從參與匹配壓縮原始源文件中順序逐次分塊讀入并更新內(nèi)容，直至整個文件匹配壓縮完畢；哈希單元使用改進哈希算法計算當前處理字符及隨后2個字節(jié)的字符（共3個字節(jié)（Byte）的字符，以下簡稱為：當前處理字符段）的哈希值，并以此哈希值為地址，將當前處理字符在字典存儲器中的位置信息為內(nèi)容，存儲到的鏈頭存儲器中；根據(jù)上述地址中鏈頭隨機存儲器中內(nèi)容的情況，對鏈頭存儲器、回溯存儲器和相關(guān)鏈頭匹配先入先出存儲器進行維護；匹配比較單元，從鏈頭匹配先入先出存儲器和回溯存儲器中順序取得可能匹配的字符串索引，并依次使用改進匹配比較方法取值比較，同時維護回溯存儲器，直至匹配比較結(jié)束。以上均為并行操作同時進行，流水線操作。由于讀入操作和哈希計算速度很快，流水線數(shù)據(jù)依賴性很小。所述改進匹配比較方法，區(qū)別于每次只匹配比較1個字節(jié)舊方法，通過從字典存儲器取值、拼接，使每次匹配比較8個字節(jié)（Byte），匹配比較后輸出匹配失敗或匹配成功字節(jié)數(shù)；若匹配成功字節(jié)數(shù)為8，則繼續(xù)匹配后8個字節(jié)（Byte），直至得到最長匹配長度為止。?

本發(fā)明實施例還提供一種基于流水線的裝置，包括：

字典存儲器，用于順序分塊存儲參與匹配壓縮原始源文件，并且根據(jù)匹配壓縮情況更新；哈希單元，用于計算當前處理字符段的哈希值，并以哈希值為地址，將當前處理字符在字典存儲器中的位置信息存入鏈頭存儲器。如果在鏈頭存儲器中已經(jīng)存儲有以哈希值為地址的舊位置信息，則使用新位置信息替代所述舊位置信息。哈希單元使用新位置信息替代舊位置信息時，會將新位置信息和舊位置信息拼接后，放入鏈頭匹配先入先出存儲器中；匹配比較單元在匹配比較時，再從鏈頭匹配先入先出存儲器中取出該信息，用于遍歷回溯存儲器得到哈希值相同的地址。以上述地址從字典存儲器中取值，匹配替代去冗余。?