A memory-efficient Huffman decoding algorithm

Pi Chung Wang; Yuan Rung Yang; Chun Liang Lee; Hung Yi Chang

doi:10.1109/AINA.2005.33

A memory-efficient Huffman decoding algorithm

Pi Chung Wang^*, Yuan Rung Yang, Chun Liang Lee, Hung Yi Chang

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Scopus citations

Abstract

To reduce the memory size and fasten the process of searching for a symbol in a Huffman tree, we exploit the property of the encoded symbols and propose a memory-efficient data structure to represent the Huffman tree, which uses memory nd bits, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(logn)-time Huffman decoding algorithm. An adaptive version for single-side growing Huffman tree is also addressed. This version could improve the average performance from logn to ∑_i=1ⁿ⌈i/(h - 1)⌉ × w _ilogh/∑w_i, where W_iis the frequency for i_th symbol and h is a pre-defined value.

Original language	English
Title of host publication	Proceedings - 19th International Conference on Advanced Information Networking and Applications, AINA 2005
Pages	475-479
Number of pages	5
DOIs	https://doi.org/10.1109/AINA.2005.33
State	Published - 2005
Externally published	Yes
Event	19th International Conference on Advanced Information Networking and Applications, AINA 2005 - Taipei, Taiwan Duration: 28 03 2005 → 30 03 2005

Publication series

Name	Proceedings - International Conference on Advanced Information Networking and Applications, AINA
Volume	2
ISSN (Print)	1550-445X

Conference

Conference	19th International Conference on Advanced Information Networking and Applications, AINA 2005
Country/Territory	Taiwan
City	Taipei
Period	28/03/05 → 30/03/05

Access to Document

10.1109/AINA.2005.33

Cite this

Wang, P. C., Yang, Y. R., Lee, C. L., & Chang, H. Y. (2005). A memory-efficient Huffman decoding algorithm. In Proceedings - 19th International Conference on Advanced Information Networking and Applications, AINA 2005 (pp. 475-479). Article 1423737 (Proceedings - International Conference on Advanced Information Networking and Applications, AINA; Vol. 2). https://doi.org/10.1109/AINA.2005.33

@inproceedings{2f352509d6924d44ae119e23c2b3fac8,

title = "A memory-efficient Huffman decoding algorithm",

abstract = "To reduce the memory size and fasten the process of searching for a symbol in a Huffman tree, we exploit the property of the encoded symbols and propose a memory-efficient data structure to represent the Huffman tree, which uses memory nd bits, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(logn)-time Huffman decoding algorithm. An adaptive version for single-side growing Huffman tree is also addressed. This version could improve the average performance from logn to ∑i=1n⌈i/(h - 1)⌉ × w ilogh/∑wi, where Wiis the frequency for ith symbol and h is a pre-defined value.",

author = "Wang, {Pi Chung} and Yang, {Yuan Rung} and Lee, {Chun Liang} and Chang, {Hung Yi}",

year = "2005",

doi = "10.1109/AINA.2005.33",

language = "英语",

isbn = "0769522491",

series = "Proceedings - International Conference on Advanced Information Networking and Applications, AINA",

pages = "475--479",

booktitle = "Proceedings - 19th International Conference on Advanced Information Networking and Applications, AINA 2005",

note = "19th International Conference on Advanced Information Networking and Applications, AINA 2005 ; Conference date: 28-03-2005 Through 30-03-2005",

}

Wang, PC, Yang, YR, Lee, CL & Chang, HY 2005, A memory-efficient Huffman decoding algorithm. in Proceedings - 19th International Conference on Advanced Information Networking and Applications, AINA 2005., 1423737, Proceedings - International Conference on Advanced Information Networking and Applications, AINA, vol. 2, pp. 475-479, 19th International Conference on Advanced Information Networking and Applications, AINA 2005, Taipei, Taiwan, 28/03/05. https://doi.org/10.1109/AINA.2005.33

A memory-efficient Huffman decoding algorithm. / Wang, Pi Chung; Yang, Yuan Rung; Lee, Chun Liang et al.
Proceedings - 19th International Conference on Advanced Information Networking and Applications, AINA 2005. 2005. p. 475-479 1423737 (Proceedings - International Conference on Advanced Information Networking and Applications, AINA; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A memory-efficient Huffman decoding algorithm

AU - Wang, Pi Chung

AU - Yang, Yuan Rung

AU - Lee, Chun Liang

AU - Chang, Hung Yi

PY - 2005

Y1 - 2005

N2 - To reduce the memory size and fasten the process of searching for a symbol in a Huffman tree, we exploit the property of the encoded symbols and propose a memory-efficient data structure to represent the Huffman tree, which uses memory nd bits, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(logn)-time Huffman decoding algorithm. An adaptive version for single-side growing Huffman tree is also addressed. This version could improve the average performance from logn to ∑i=1n⌈i/(h - 1)⌉ × w ilogh/∑wi, where Wiis the frequency for ith symbol and h is a pre-defined value.

AB - To reduce the memory size and fasten the process of searching for a symbol in a Huffman tree, we exploit the property of the encoded symbols and propose a memory-efficient data structure to represent the Huffman tree, which uses memory nd bits, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(logn)-time Huffman decoding algorithm. An adaptive version for single-side growing Huffman tree is also addressed. This version could improve the average performance from logn to ∑i=1n⌈i/(h - 1)⌉ × w ilogh/∑wi, where Wiis the frequency for ith symbol and h is a pre-defined value.

UR - http://www.scopus.com/inward/record.url?scp=33744455504&partnerID=8YFLogxK

U2 - 10.1109/AINA.2005.33

DO - 10.1109/AINA.2005.33

M3 - 会议稿件

AN - SCOPUS:33744455504

SN - 0769522491

SN - 9780769522494

T3 - Proceedings - International Conference on Advanced Information Networking and Applications, AINA

SP - 475

EP - 479

BT - Proceedings - 19th International Conference on Advanced Information Networking and Applications, AINA 2005

T2 - 19th International Conference on Advanced Information Networking and Applications, AINA 2005

Y2 - 28 March 2005 through 30 March 2005

ER -

A memory-efficient Huffman decoding algorithm

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this