Title: A compressed trie structure using divided keys

Authors: Masaki Oono, El-Sayed Atlam, Masao Fuketa, Kazuhiro Morita, Jun-ichi Aoe

Addresses: Department of Information and Computer Science, Faculty of Science and Technology, Keio University, 3-14-1 Hiyoshi, Yokohama 223-8522, Japan. ' Department of Information Science and Intelligent Systems, Faculty of Engineering, Tokushima University, 2-1 Minami josanjima, Tokushima 770-8506, Japan. ' Department of Information Science and Intelligent Systems, Faculty of Engineering, Tokushima University, 2-1 Minami josanjima, Tokushima 770-8506, Japan. ' Department of Information Science and Intelligent Systems, Faculty of Engineering, Tokushima University, 2-1 Minami josanjima, Tokushima 770-8506, Japan. ' Department of Information Science and Intelligent Systems, Faculty of Engineering, Tokushima University, 2-1 Minami josanjima, Tokushima 770-8506, Japan

Abstract: A link-trie structure is an efficient data structure for collocation information using a trie structure. The link-trie stores two basic words into the trie and defines link-information by a link-function. This paper presents how to apply the link-trie into a general set of keys and compress the storage capacity. The method divides a key into several sub-keys and defines link-information between these sub-keys. From simulation results for 100,000 keys, it turns out that the presented method compresses the storage capacity by 30% smaller than the normal trie.

Keywords: dictionary; trie search; data compression; information retrieval; natural language processing; divided keys; storage capacity.

DOI: 10.1504/IJCAT.2009.023615

International Journal of Computer Applications in Technology, 2009 Vol.34 No.2, pp.101 - 107

Published online: 03 Mar 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article