허프만 코드의 효율적인 복호화에 관한 연구
A Study on Efficient Decoding of Huffman Codes
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 허프만 코드의 효율적인 복호화를 위하여 균형이진 트리와 정규 허프만 트리를 이용한 복호화 방법을 제안하였다. 균형이진 트리 방식은 트리의 높이를 낮추고 이진탐색이 가능하도록 하여 검색횟수를 줄일 수 있었지만 심벌의 발생확률이 아니라 코드의 크기에 트리를 만드는 것이 단점이다. 이러한 단점을 보완하기 위하여 트리의 레벨 마다 심벌의 발생확률에 따른 균형이진 트리를 구성하고 이진탐색을 레벨 별로 수행하였다. 최상위 레벨부터 순차적으로 검색을 하지 않고 코드가 있는 레벨을 찾아 검색하기 위하여 정규 허프만 트리를 사용하여 검색횟수를 최소화하였다.
Abstract
In this paper, we propose a decoding method using a balanced binary tree and a canonical Huffman tree for efficient decoding of Huffman codes. The balanced binary tree scheme reduces the number of searches by lowering the height of the tree and binary search. However, constructing a tree based on the value of the code instead of frequency of symbol is a drawback of the balanced binary tree. In order to overcome these drawbacks, a balanced binary tree is reconstructed according to the occurrence probability of symbols at each level of the tree and binary search is performed for each level. We minimize the number of searches using a canonical Huffman tree to find level of code to avoid searching sequentially from the top level to bottom level.
참고문헌 (6)
- D. Huffman, "A method for the construction of minimum redundancy codes", Proc. of the IRE, 40(90), pp.1098~1101 (1952)[DOI]
- L. Larmore, "Efficient decoding of prefix codes", Comm. of the ACM, 33, pp.449~459 (1990)[DOI]
- 박상호, "정규 허프만 트리를 이용한 허프만 코드의 효율적인 디코딩", 한국컴퓨터정보학회논문지, 12(4), pp.111~118 (2007), 한국컴퓨터정보학회
- 김혜란, "허프만 복호화를 위한 균형이진 검색 트리", 한국통신학회논문지C, 30(5), pp.383~390 (2005), 한국통신학회
- 박인혜, "임베디드 시스템을 위한 허프만 복호화의 최적화", 정보과학회 컴퓨팅의 실제 논문지, 18(12), pp.881~885 (2012), 한국정보과학회
- Y. Takishima, "Reversible variable length codes", IEEE Trans. Comm, 43, pp.158~162 (1995)[DOI]