跳到主要內容

臺灣博碩士論文加值系統

(216.73.216.176) 您好!臺灣時間:2025/09/06 07:44
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳宏綜
論文名稱:在霍夫曼樹上研究有效的記憶體表示法及快速解碼演算法
論文名稱(外文):A Memory-Efficient and Fast Huffman Decoding Algorithm
指導教授:王有禮
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:管理研究所資訊管理學程
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:中文
論文頁數:37
中文關鍵詞:資料結構演算法霍夫曼樹
外文關鍵詞:Data structureAlgorithmsHuffman tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:490
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  本論文探討如何在霍夫曼樹上提供有效的記憶體表示法,並且提供一個快速解碼(decoding)的演算法,能夠快速的查詢出一個字碼所對應之符號的問題。
  我們將整個演算法分為兩個部分,第一個部份是探討如何用一個有效的資料結構來表示一棵霍夫曼樹。第二個部份是解碼的演算法,利用造出資料結構的特性,我們可以使用二元搜尋法,在m個字碼中,共需O(mlog n)的時間,求出m個字碼在霍夫曼樹上所對應的符號。所需的空間複雜度是3n/2 + n/2logn + 1,其中n表示在霍夫曼樹上的符號數量。

To reduce the memory size and speed up the process of searching for a symbol in a Huffman tree, we propose a memory-efficient array data structure to represent the Huffman tree. Then, we present a fast Huffman decoding algorithm, which takes O(mlog n) time and uses 3n/2 + n/2logn + 1 memory space, where n is the number of symbols in a Huffman tree.

中文摘要I
英文摘要II
誌  謝III
目  錄IV
圖表索引VI
第一章 資料壓縮簡介1
第二章 霍夫曼樹介紹4
2-1 靜態霍夫曼編碼4
2-2 動態霍夫曼編碼8
第三章 靜態霍夫曼樹相關的研究13
3-1一般的霍夫曼樹13
3-2單邊成長的霍夫曼樹15
第四章 在霍夫曼樹上有效的記憶表示法及快速解碼演算法的基本概念 19
4-1 基本定義及記號之說明19
4-2 建立資料結構20
4-3解碼演算法21
4-4演算法的基本概念22
第五章 一個更有效率的版本25
5-1 更有效率的資料結構25
5-2 解碼演算法26
5-3 時間與空間複雜度的分析28
第六章 總結及未來研究方向30
參考文獻32

[1] M. A. Bassionui and A. Mukherjee, Efficient decoding of
compressed data, Journal of American Society Information
Science, vol. 46, pp. 1-8, Jan 1995.
[2] K. L. Chung, Efficient Huffman Decoding, Information
Processing Letters, Vol. 61, 1997, pp. 97-99.
[3] H. C. Chen, Y. L. Wang, Y. F. Lan, A memory-efficient and
fast Huffman decoding algorithm, Information Processing
Letters , Vol. 69, 1999, pp.119-122.
[4] D. Chevion, E. D. karnin and E. Walach, High efficiency,
multiplication free approximation of arithmetic coding, in:
J. A. Storer and J. H. Reif, Eds., Processing Data
Compression Conference, Snowbird, UT, 1991, pp.43-52.
[5] Y. Choueka, S. T. Klein, and Y. Perl, Efficient variants of
Huffman code in high level languages, in Proceedings 8th
ACM-SIGIRE Conference Information Retrieval, Montreal,
Canada, June 1985, pp. 122-130, ACM, NY.
[6] J. B. Connell, A Huffman-Shannon-Fano code, Proceedings
IEEE, vol. 61, pp. 1046-1047, July 1973.
[7] N. Faller, An Adaptive system for data compression, Record
of the 7th Asilomar Conference on Circuit, System and
Computers. 1973, pp.593-597.
[8] T. J. Ferguson and J. H. Rabinowitz, Self-synchronizing
Huffman Codes, IEEE Transactions on Information Theory,
Vol. IT-30, 1984, pp. 687-693.
[9] R. G. Gallager and D. C. Van Voorhis, Optimal source codes
for geometrically distributed integer alphabets, IEEE
Transactions Information Theory. Vol. 21, 1975, pp.228-230.
[10] R. G. Gallager, Variations on a theme by Huffman, IEEE
Transactions Information Theory IT-24, 6 Nov. 1978, pp.668-
674.
[11] R. W. Hamming, Coding and Information Theory, Prentice-
Hall International Book Company 1986, Second Edition.
[12] M. Hankamer, A modified Huffman procedure with reduced
memory requirements, IEEE Transactions Communication, vol.
27, pp. 930-932, June 1979.
[13] R. Hashemian, Memory Efficient and High-Speed Search
Huffman Coding, IEEE Transactions on Communications, Vol.
43, No. 10, 1995, pp. 2576-2581.
[14] D. S. Hirschberg and D. A. Lelewer, Efficient decoding of
prefix codes, Communication ACM, vol. 33, pp. 449-459,
Apr. 1990.
[15] D. A. Huffman, A Method for the Construction of Minimum
Redundancy Codes, Proceedings IRE, Vol. 40, 1952, pp. 1098-
1101.
[16] Ho-Chao Huang, Ja-Ling Wu , Design and Analysis of
Residual Huffman Algorithm, Proceedings of National
Computer Symposium 1991, pp.200-205.
[17] P. G. Howard and J. S. Vitter, Fast progressive lossless
image compression, in: Image and Video Compression
Conference, Symposium on Electronic Imaging: Science and
Technology, SPIE-2186, San Jose, CA, 1994, pp.98-109.
[18] P. G. Howard and J. S. Vitter, New methods for lossless
image compression using arithmetic coding, Information
Processing Management Vol.28,1992, pp.765-779.
[19] S. Ho, P. Law, Efficient hardware decoding method for
modified Huffman code, IEE Electron Letter Vol.27. ,1991,
pp.855-856.
[20] Vikram Iyengar, Krishnendu Chakrabarty, An efficient
finite-state machine implementation of Huffman decoders,
Information Processing Letter Vol.64, 1997, pp.271-275.
[21] M. Jakobssen, Huffman coding in bit-vector compression,
Information Processing Letter Vol.7, 1978, pp. 304-307.
[22] J. KataJainen, A Moffat, and A. Turpin, A fast and space-
economical algorithm for length-limited coding, in
Proceedings International Symposium Algorithms and
Computation, J. Staples, P. Eades, N. Katoh, and A.
Moffat, Eds., Cairns, Australia, Dec. 1995, pp. 12-21,
Springer-Verlag, LNCS 1004.
[23] D. E. Knuth , Dynamic Huffman Coding, Journal of
Algorithms, 6 1985, pp.163-180.
[24] S. M. Lei and M. T. Sun, An Entropy Coding System for
Digital HDTV Applications, IEEE Transactions on Circuit
Systems and Video Technology, Vol. 1, 1991, pp. 147-155.
[25] D. A. Lelewer and D. S. Hirschberg, Data Compression,
Computer Surveys, vol. 19, pp. 261-296, Sept. 1987.
[26] M. E. Lukacs, Variable Word Length Coding for a High Data
Rate DPCM Video Coder, Proceedings on Picture Coding
Symposium, 1986, pp. 54-56.
[27] J. van Leeuwen, On the construction of Huffman trees, in
Proceedings 3rd Int. Colloquium Automata, Languages, and
Programming, Edinburgh Univ., Scotland, July 1976, pp. 382-
410.
[28] Alistair Moffat and Andrew Turpin , On the implementation
of Minimum Redundancy Prefix Codes, IEEE Transactions On
Communications, Vol. 45, No. 10, October 1997.
[29] Alistair Moffat, J. Zobel, and N. Sharman, Text
compression for dynamic document databases, IEEE
Transactions Knowledge Data Engineering, vol. 9, pp. 302-
313, Mar. 1997.
[30] D. R. McIntyre and F. G. Wolff, An efficient
implementation of Huffman decode tables, Congressus
Numerantium, vol. 91, pp. 79-92, 1992.
[31] J. J. Rissanen and K. M. Mohiuddin, A multiplication-free
multialphabet arithmetic code, IEEE Transactions
Communication Vol. 37, 1989, pp.93-98.
[32] E. S. Schwartz and B. Kallick, Generating a canonical
prefix encoding, Commnuication ACM, vol. 7, pp. 166-169,
Mar. 1964.
[33] Sieminski, Fast decoding of the Huffman codes, Information
Processing Letter, vol. 26, pp. 237-241, May 1988.
[34] H. Tanaka, Datastructure of the Huffman codes and its
application to efficient encoding and decoding, IEEE
Transactions Information Theory, vol. IT-33, pp. 154-156,
Jan. 1987.
[35] K. H. Tzou, High-order Entropy Coding for Images, IEEE
Transactions on Circuit Systems and Video Technology, Vol.
2, 1992, pp.87-89.
[36] J. S. Vitter , Design and Analysis of Dynamic Huffman
Codes, Journal of the Association for Computer Machinery.
Vol. 34, No. 4, October 1987, pp. 825-845.
[37] J. S. Vitter, Dynamic Huffman Coding, ACM Transactions on
Mathematical Software. June 1989, Vol.15 , No.2, pp.158-
167.
[38] H. Witten, R. M. Neal and J. G. Cleary, Arithmetic coding
for data compression, Communication ACM , Vol.30, 1987,
pp.520-540.
[39] J. Ziv and A. Lempel, A universal algorithm for sequential
data Compression, IEEE Transactions Information Theory,
vol. IT-23, no. 3, pp. 337-343, 1997.
[40] 資料壓縮,戴顯權,松崗電腦圖書資料股份有限公司.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top