A new compression method for double-array structures by a hierarchical representation Online publication date: Fri, 22-Jan-2016
by Shunsuke Kanda; Masao Fuketa; Kazuhiro Morita; Akio Tomotoshi; Jun-ichi Aoe
International Journal of Intelligent Systems Technologies and Applications (IJISTA), Vol. 14, No. 3/4, 2015
Abstract: To store and retrieve keyword sets, a trie that is a tree structure is utilised in many applications for processing strings. The double-array and level-order unary degree sequence (LOUDS) efficiently represent the trie. The double-array provides fast retrieval for the trie, but its space usage is not so compact. On the other hand, LOUDS represents the trie compactly, but its retrieval speed is not so fast. This paper presents a new compression method for the double-array. Our new method represents the double-array by a hierarchical structure and changes allocations of the double-array. Theoretical observations show that the new method reduces the space usage of the double-array to ∼60%. Moreover, experimental results for English keywords show that the new method reduces the space usage of the double-array to ∼60-62% without impairing the high-speed performance. The retrieval speed of the new method is ∼17-24 times faster than that of LOUDS.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Intelligent Systems Technologies and Applications (IJISTA):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook