动态霍夫曼编码之计算时间与空间关系之探讨.PDFVIP

動態霍夫曼編碼之計算時間與空間關係之探討 On the time v.s. space complexity of Adaptive Huffman coding 計畫編號：NSC 882815C260002E 執行期限：八十七年十一月一日至八十八年六月三十日 游逸平 蔡錫鈞 Yi-Ping You Shi-Chun Tsai 國立暨南國際大學資訊工程學系 國立暨南國際大學資訊工程學系 Department of Computer Science and Department of Computer Science and Information Engineering Information Engineering National Chi-Nan University National Chi-Nan University E-mail: u5321009 @ncnu.edu.tw E-mail: tsai@csie.ncnu.edu.tw 摘要 buffered adaptive Huffman coding. This approach dynamically changes the structure 霍夫曼編碼法是一種有效且廣受使用 of Huffman code trees when encoding and decoding. Unlike original adaptive Huffman 的資料壓縮技術。在本文中，我們將重點 coding, the time when to update the tree is 著眼在其編碼時所需計算時間與空間的關 adjusted to not change the tree every time we 係，並且提出緩衝式動態霍夫曼編碼改良 read a symbol. It is changed only when the 傳統的編碼方式，其運作方式是在編碼與 updating point is reached and it will save the 解碼的同時動態的改變霍夫曼樹的結構， number of updating the adaptive Huffman 不同於傳統的動態霍夫曼編碼方式，我們 tree. The scheme is fast and useful to on-line 並不是每讀取一個字元就更新樹狀結構， encoding. We also propose a method of nonbinary Huffman coding based on adaptive 只有在更新點時才做修正的動作，這可使 en