가변형 키코드를 이용한 집약 이진 트리
Compact Binary Tree Using Variant Length Key Codes
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
가변 길이를 가지는 문자열 탐색을 위해 널리 사용되는 트라이 자료구조의 효율적인 저장을 위해 이진 비트열 형태의 선형 구조로 표현하는 집약 이진 트리 방법이 제안 되었다. 이 방법에서는 키를 구성하는 각 문자를 동일한 크기를 갖는 이진 코드로 매핑한 후 처리한다. 본 논문에서는 키를 구성하는 각 문자의 출현 빈도가 높은 문자일수록 짧은 길이를 갖는 이진 코드로 매핑하여 집약 이진 트리를 구성하는 방법을 소개한다. 시뮬레이션을 통한 평가 결과 가변형 이진 비트열을 사용한 제안 방법에서 사용한 저장 공간은 기존의 방법에서 보다 약간 적게 사용하였으나 생성된 트리의 버켓 분포 결과를 분석한 결과 제안 방법은 낮은 깊이에서는 기존 방법보다 많은 버켓을 유지하고, 깊은 깊이에서는 적은 버켓을 유지하였다. 이는 키 탐색을 위한 버켓 접근을 위한 경로 탐색 시간을 축소할 수 있게 되어 제안 방법이 기존 방법보다 검색 성능 측면에서 우수한 것으로 분석되었다.
Abstract
In order to efficiently store the data structure 'trie' which is widely used in retrieving variable-length strings, an compact binary tree was proposed, which expresses it as a linear sequence of the binary bit string. In the previous way, each character constituting the key is mapped to a binary code having the same length. In this paper, we introduce a new approach of constructing an compact binary tree by mapping to binary codes with shorter characters as the characters with higher occurrence frequencies of each character constituting the key. We found in the simulation results the storage space used in the proposed approach using the variable bit stream is slightly less than that of the conventional way. As a result of analyzing the result of the bucket distribution of the generated tree, the proposed approach maintains more buckets at the lower depth and fewer buckets at the lower depth. It is shown that the our new approach has better search performance than the conventional way because the path retrieval time for accessing the bucket for key search can be reduced.
참고문헌 (9)
- Sunho Lee, "Data Structure" (2008), C, Kyobo Pub
- Woosuk Joo, "Data Structure in C·C++" (2004), Hanvit Media
- Jonge, D., "Two access methods using compact binary trees", IEEE Trans. Software Eng, 13(7), pp.799~810 (1987)
- Y. Manolopoulos, "Advanced Signature Indexing for Multimedia and Web Applications" (2003), Springer Science+Business Media
- G. Badr, "Tries in Data Retireval and Syntactic Pattern Recognition", Ph.D, pp.2006
- 김연희, "시맨틱 검색 시스템에서의 검색 결과 랭킹 방안", 창의정보문화연구, 3(2), pp.55~63 (2017), 한국창의정보문화학회[DOI]