Title :
Double-array compression by pruning twin leaves and unifying common suffixes
Author :
Yata, Susumu ; Oono, Masaki ; Morita, Kazuhiro ; Sumitomo, Torn ; Aoe, Jun-Ichi
Author_Institution :
Dept. of Inf. Sci. & Intell. Syst., Univ. of Tokushima, Tokushima, Japan
Abstract :
A minimal prefix (MP) trie is a tree structure for key retrieval, and a double-array is an efficient data structure for the MP trie. This paper presents two compression methods for the double-array. One method removes leaf nodes following two-way arcs (named twin leaves) from the MP trie. The other method unifies common suffixes. Experimental results show that space usage of the double-array is reduced to about 60% by the two methods.
Keywords :
information retrieval; tree data structures; MP trie; data structure; double-array compression; efficiency 60 percent; experimental result; key retrieval; leaf node; minimal prefix trie; pruning twin leaves; two-way arcs; unifying common suffix; Data engineering; Data structures; Information retrieval; Information science; Intelligent structures; Intelligent systems; Natural languages; Systems engineering and theory; Tail; Tree data structures;
Conference_Titel :
Computing & Informatics, 2006. ICOCI '06. International Conference on
Conference_Location :
Kuala Lumpur
Print_ISBN :
978-1-4244-0219-9
Electronic_ISBN :
978-1-4244-0220-5
DOI :
10.1109/ICOCI.2006.5276476
