A compressed trie structure using divided keys. (4th March 2009)

• Record Type: Journal Article
• Authors: Oono, Masaki; Atlam, El-Sayed; Fuketa, Masao; Morita, Kazuhiro; , Jun-ichi Aoe
• Is Part Of: International journal of computer applications technology. Volume 34:Number 2(2009)
• Page Start: 101
• Page End: 107
• Publication Date: 2009-03-04
• Subjects: dictionary -- trie search -- data compression -- information retrieval -- natural language processing -- divided keys -- storage capacity; Technology -- Data processing -- Periodicals; 620.00285
• Languages: English
• ISSNs: 0952-8091

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.