使用牛頓法之一新快速有效的赫夫曼解碼器

Abstract

本論文提出一個新的赫夫曼解碼方法。此方法既可提高解碼速度而且降低所需的記憶體空間。其解碼的方式主要是利用數值方法和分段技術來實現。本方法執行步驟為：首先將長度不等的赫夫曼碼補0，使其成為長度相等的碼，然後重新排序使其成為一單調遞增或單調遞減的數列；而數列的索引值可當作解碼時的參考值。 利用數值方法和數列可以找到相對於輸入資料的索引值，以作為解碼完成時標籤值的索引。在數值方法中，我們主要利用牛頓法來實現，因為牛頓法有搜尋快速的優點。而二分法或假位法則可以保證收斂。由於牛頓法在斜率變化不規則的曲線容易導致搜尋無法收斂。所以我們結合牛頓法和二分法或假位法來進行解碼。 由於將長度不等的赫夫曼碼經由重組後的曲線，有斜率變化不規則的特性，造成解碼速度過慢。於是將整個曲線區分成幾個較小的線段，使每一個線段斜率變化較有一致性。並將每個線段的啟始位置記錄成一個分段表。在解碼開始時，先讀取若干的位元進來，藉由分段表使每一個線段斜率變化較有規則，使得解碼速度加快。 而儲存分段表只需很小的記憶體空間。如此一來，只要額外付出少許記憶體空間的代價，搜尋速度將會隨著分段的線段數變多，搜尋速度將會加快。最後我們以MP3赫夫曼表為例子，分析所需記憶體的空間並且用電腦模擬進行解碼的過程，來驗證我們的方法。

This thesis presents a new Huffman decoder by numerical methods with the sectioning technique for increasing the decoding speed and reducing the memory requirement. The decoder is realized by first concatenating zeros in the rear of each codeword of a variable-length Huffman code and then reordering the resulting codewords to form a monotonic decreasing or increasing data sequence; this sequence is used as the data reference for decoding. The decoding is accomplished by numerical method using the input data for finding the corresponding codeword from the data reference. The numerical method mainly uses the Newton's method. Since the Newton's method, although fast in searching, may be unable to converge, the bisection (or Regula Falsi) approach is integrated to ensure the convergence of the numerical method. The variable-length Huffman code may make the data sequence having irregular slopes which make the numerical method converge slowly. This thesis tackles the problem by dividing the entire data sequence into a number of smaller sections such that the slopes of each section is smoother. This sectioning technique highly increases the searching speed at the cost of only small memory increment. In the thesis, the memory requirement and decoding speed are analyzed and simulated by using the example for decoding MP3 data. The analysis and simulation results are demonstrated to verify the usefulness of our approach.