[發明專利]一種基于排序網絡的動態霍夫曼編碼方法、裝置及設備

在審

• 申請號: 202110019434.6
• 申請日: 2021-01-07
• 公開（公告）號: CN112737596A
• 公開（公告）日: 2021-04-30
• 發明（設計）人: 秦臻;袁濤;王振;王金富
• 申請（專利權）人: 蘇州浪潮智能科技有限公司
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 張春輝

本申請公開了一種基于排序網絡的動態霍夫曼編碼方法，與傳統的動態霍夫曼編碼方案相比，該方法基于排序網絡實現排序，該排序過程不僅具有穩定性，能夠保證穩定的排序結果，而且排序步驟和相關操作更簡潔，大大簡化排序和迭代過程，因而排序效率更高。此外該排序過程更利于程序實現和移植，硬件軟件的實現均能夠取得很好的效果。此外，本申請還提供了一種基于排序網絡的動態霍夫曼編碼裝置、設備及可讀存儲介質，其技術效果與上述方法的技術效果相對應。

技術領域

本申請涉及計算機技術領域，特別涉及一種基于排序網絡的動態霍夫曼編碼方法、裝置、設備及可讀存儲介質。

背景技術

近幾年來，隨著科學技術的不斷發展，數據信息呈現出爆炸時的增長。云計算的興起，人工智能的推進，大數據時代的到來，新的工作負載不斷增大，海量數據傳輸和存儲的問題不斷引起關注。如何能夠高效的傳輸海量數據，同時不對處理器造成過于沉重負荷的問題亟待解決。

如果能夠在文件傳輸時進行預先壓縮，不僅可以節省數據流量，同時也降低了傳輸時間；如果在讀取磁盤文件之前對文件進行壓縮，就可以提高文件讀取的速率。總而言之，壓縮數據從一個新的角度提供了改善計算機性能的方法，對其的研究具有重要的現實意義。

廣泛應用的有效壓縮算法應具備三個重要的特性：通用、無損、高壓縮比。通用是指源數據的一般性，很多數據由于其本身的編碼方式決定了其特殊性，根據這些特殊性進行有針對性的研究可以大大提高壓縮效果，而本文關注的是適用于非特定數據的通用壓縮算法。無損是指數據壓縮后的編碼與源碼相比包含的信息量相同。高壓縮比是指壓縮后降低存儲空間比原存儲空間的結果盡可能大。就現狀而言，具有通用性的無損壓縮因數據特征未知且不允許信息丟失，造成壓縮效率難以得到大的提高而發展緩慢，使得無損壓縮成為必要的研究課題。

DEFLATE是一種經典的無損數據壓縮標準，該數據壓縮標準同時采用LZ77與霍夫曼編碼，其中LZ77是一種基于字典的滑動窗的無損壓縮算法，霍夫曼編碼用于對經過LZ77壓縮后的數據進行二次壓縮。然而，目前霍夫曼編碼過程中往往采用冒泡排序、插入排序、快速排序或堆排序，這些排序方案要么效率低下，要么不具備穩定性。

發明內容

本申請的目的是提供一種基于排序網絡的動態霍夫曼編碼方法、裝置、設備及可讀存儲介質，用以解決目前霍夫曼編碼算法中排序過程效率低下或不具備穩定性的問題。其具體方案如下：

第一方面，本申請提供了一種基于排序網絡的動態霍夫曼編碼方法，所述排序網絡包括n級排序模塊，n為正整數，該方法包括：

S1、獲取待排序元素，初始化i＝1，其中所述待排序元素包括Literal元素和Length元素，所述Literal元素用于描述目標文本中每個字符的出現次數，所述Length元素用于描述所述目標文本中不同長度區間的字符串的出現次數；

S2、在第i級排序模塊中，利用各個第i級排序單元通過i次并行比較根據前一級排序模塊的排序結果生成2ⁱ個待排序元素的排序結果，得到所述第i級排序模塊的排序結果，其中所述第i級排序模塊包括n/2ⁱ個并行的所述第i級排序單元；

S3、在i小于n時，令i遞增1，并進入S2；

S4、在i等于n時，確定所述第i級排序模塊的排序結果為所述待排序元素的排序結果；

S5、根據所述待排序元素的排序結果，構建霍夫曼樹，根據所述霍夫曼樹對所述目標文本進行編碼。

優選的，在所述獲取待排序元素之前，還包括：

根據目標文本確定Literal元素和Length元素；