[發明專利]編碼方法和裝置

有效

• 申請號: 201710432892.6
• 申請日: 2017-06-09
• 公開（公告）號: CN107332567B
• 公開（公告）日: 2019-06-28
• 發明（設計）人: 楊磊;鐘炎培
• 申請（專利權）人: 西安萬像電子科技有限公司
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 趙囡囡;褚敏

本發明公開了一種編碼方法和裝置。其中，該方法包括：獲取待編碼數據中每個編碼符號出現的概率；根據每個編碼符號出現的概率所對應的概率范圍，對每個編碼符號進行分層；按照概率范圍中門限值由小至大的順序，將概率范圍對應的層中的編碼符號按照預設規則上升至上一層，直至最小概率范圍對應的層中的編碼符號上升至頂層，得到待編碼數據的編碼樹；根據編碼樹編碼待編碼數據。本發明解決了現有技術中哈夫曼樹建立較慢，導致編碼速度慢的技術問題。

技術領域

本發明涉及編碼領域，具體而言，涉及一種編碼方法和裝置。

背景技術

哈夫曼編碼(Huffman Coding)是一種編碼方式，是可變字長編碼(VLC)的一種。Huffman于1952年提出該編碼方法，該方法對于出現次數較多的符號使用較短的編碼表示，對于出現次數較少的符號使用較長的編碼表示，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數據的目的。哈夫曼算法需要掃描兩遍數據。第一遍掃描計算符號在數據中出現的頻數，然后根據符號頻數構建一顆哈夫曼樹，第二次掃描數據將符號按哈夫曼樹進行編碼。

構建哈夫曼樹的計算方法如下：首先建立一個n個字符組成的編碼字符集，保存其字符標志及每個字符的頻數f，以f值的大小進行排序構成優先隊列Q，2棵具有最小概率的數進行合并。一旦2棵具有最小概率的樹合并后，產生一個新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優先隊列Q。經過n-1次的合并后，優先隊列中只剩下一棵樹，即所要求的哈夫曼樹。構建哈夫曼樹后即可以對這棵哈夫曼樹按照左0右1的分配方案進行編碼。常規的哈夫曼樹建立方法其時間復雜度為o(n^2)。

下面以圖1為例對現有技術中哈夫曼樹的構造過程進行說明。六個編碼符號a、b、c、d、e、f根據其出現的頻數由小至大排序為：“f：5、e：9、c：12、b：13、d：16、 a：45”，首先將f和e合并得到14，將14插入隊列中的b和d之間；將c和b合并得到25，將25插入隊列中的d和a之間；將14和d合并得到30，將30插入到隊列中的25和a之間；將25和30合并得到55，將55排在a之后，最終將a和55合并為 100。然后對這棵哈夫曼樹按照左0右1的分配方案對其進行編碼。

在哈夫曼編碼算法中引入堆排序思想可以較大幅度的減少運算量，避免重復性的比較。若采用最小堆排序，則尋找最小節點的時間復雜度變為O(logn)，整體的復雜度就減少為O(nlogn)。但即使哈夫曼編碼采用了堆排序思想，但當n比較大時排序運算仍會較耗較長的時間，從而使得哈夫曼樹建立較慢，影響編碼的速度。

針對現有技術中哈夫曼樹建立較慢，導致編碼速度慢的問題，目前尚未提出有效的解決方案。

發明內容

本發明實施例提供了一種編碼方法和裝置，以至少解決現有技術中哈夫曼樹建立較慢，導致編碼速度慢的技術問題。

根據本發明實施例的一個方面，提供了一種編碼方法，包括：獲取待編碼數據中每個編碼符號出現的概率；根據每個編碼符號出現的概率所對應的概率范圍，對每個編碼符號進行分層；按照概率范圍中門限值由小至大的順序，將概率范圍對應的層中的編碼符號按照預設規則上升至上一層，直至最小概率范圍對應的層中的編碼符號上升至頂層，得到待編碼數據的編碼樹；根據編碼樹編碼待編碼數據。

進一步地，獲取每個編碼符號出現的頻次和待編碼數據中所有編碼符號的數量；根據每個編碼符號出現的頻次和待編碼數據中所有編碼符號的數量確定每個編碼符號的出現的概率。

進一步地，確定概率范圍以及概率范圍對應的層，其中，概率范圍包括：概率范圍對應的分層為k層，k∈[1,m]，m為待編碼數據中概率最小且概率非零的編碼符號所屬的層；查找每個編碼符號所屬的概率范圍，并將每個編碼符號歸類至所屬的概率范圍對應的層；將每層中概率最大的編碼符號排列在所在層的最末端。