[發明專利]一種基于LZ77的數據壓縮方法、設備及終端

有效

• 申請號: 201710299371.8
• 申請日: 2017-04-28
• 公開（公告）號: CN108809320B
• 公開（公告）日: 2021-05-18
• 發明（設計）人: 陳國濤;孫忠巖
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 郝傳鑫;熊永強

1.一種LZ77數據壓縮設備，其特征在于，所述設備包括：第一緩存裝置、第二緩存裝置、比較裝置、檢測裝置以及編碼裝置；其中，

所述第一緩存裝置包括M個寄存器，用于依次緩存M個待輸入字符；M為正整數；

所述第二緩存裝置包括由M行并行路徑的N位移位寄存器組成的M行N列的寄存器陣列，所述寄存器陣列用于緩存歷史已輸入字符串的前K個字符；N、K為正整數；K≤M*N；

所述比較裝置與所述第一緩存裝置和所述第二緩存裝置耦合，用于將緩存在所述第一緩存裝置的字符與緩存在部分所述第二緩存裝置中的字符相比較；其中，所述第一緩存裝置包括寄存器a1和寄存器a2，所述比較裝置中的比較單元的輸入端分別連接所述第一緩存裝置中的寄存器a2與所述第一緩存裝置中的寄存器a1，用于所述比較裝置將寄存器a1中緩存的字符與寄存器a2中緩存的字符相比較，并向所述檢測裝置輸出比較結果；

所述檢測裝置連接所述比較裝置，用于：記錄至少一個時鐘周期所述比較裝置的比較結果，并根據所述比較裝置的比較結果檢測匹配字符串的位置和長度；

所述編碼裝置用于：根據所述檢測裝置檢測到的匹配字符串的位置和長度編碼成標記。

2.根據權利要求1所述的設備，其特征在于，所述第一緩存裝置與所述第二緩存裝置連接形成M行并行路徑的N+1位移位寄存器；所述寄存器陣列第1至N列用于緩存歷史已輸入字符串的前K個字符；所述K＝M*N。

3.根據權利要求1所述的設備，其特征在于，所述寄存器陣列的第1列寄存器用于緩存M個待輸入字符；所述寄存器陣列第2至N列用于緩存歷史已輸入字符串的前K個字符；K＝M*N-M。

4.根據權利要求1-3任一權利要求所述的設備，其特征在于，所述比較裝置包括由M²*(N-1)個比較單元組成的M行M*(N-1)列的比較單元陣列；

所述比較單元陣列中第i行的比較單元用于將緩存在所述第一緩存裝置的第i個寄存器的字符與緩存在部分所述第二緩存裝置中的字符相比較；i≤M；

其中，所述比較單元陣列中比較單元的排列方式使得相鄰字符的連續匹配發生在同一列比較單元中；連續匹配的總行數為匹配長度，連續匹配所在的列數即為匹配距離。

5.根據權利要求4所述的設備，其特征在于，所述M行N列的寄存器陣列劃分為P個分塊歷史矩陣；所述M行M*(N-1)列的比較單元陣列劃分為與所述P個分塊歷史矩陣一一對應的P個分塊比較矩陣。

6.根據權利要求5所述的設備，其特征在于，所述檢測裝置包括與所述P個分塊比較矩陣一一對應的P個一級優先編碼器；所述一級優先編碼器用于根據至少一個時鐘周期中與所述一級優先編碼器對應的分塊比較矩陣的比較結果輸出用于指示壓縮率最高的匹配字符串的位置和長度的信號。

7.根據權利要求6所述的設備，其特征在于，所述檢測裝置還包括二級優先編碼器；所述二級優先編碼器連接所述P個一級優先編碼器，用于根據從所述P個一級優先編碼器輸入的信號，輸出用于指示壓縮率最高的匹配字符串的位置和長度的信號。