New methods for compression of MP double array by compact management of suffixes

Minimal Prefix (MP) double array is an efficient data structure for a trie. However, its space efficiency is degraded by the non-compact management of suffixes. This paper presents three methods to compress the MP double array. The first two methods compress the MP double array by accommodating shor...

Full description

Saved in:
Bibliographic Details
Published in:Information processing & management 2010-09, Vol.46 (5), p.502-513
Main Authors: Dorji, Tshering C., Atlam, El-sayed, Yata, Susumu, Rokaya, Mahmoud, Fuketa, Masao, Morita, Kazuhiro, Aoe, Jun-ichi
Format: Article
Language:English
Subjects:
Arrays
Bibliometrics. Scientometrics
Bibliometrics. Scientometrics. Evaluation
Comparative analysis
Compressing
Computerized information retrieval
Data compression
Data structure
Deletion
Exact sciences and technology
Information and communication sciences
Information retrieval
Information science. Documentation
Insertion
Library and information science. General aspects
Management
Markers
Matrix and list forms
Minimal Prefix double array
Retrieval
Sciences and techniques of general use
Size reduction
Studies
Ternary Search Tree
Trie
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Minimal Prefix (MP) double array is an efficient data structure for a trie. However, its space efficiency is degraded by the non-compact management of suffixes. This paper presents three methods to compress the MP double array. The first two methods compress the MP double array by accommodating short suffixes inside the leaf nodes, and pruning leaf nodes corresponding to the end marker symbol. These methods achieve size reduction of up to 20%, making insertion and deletion faster at the same time while maintaining the retrieval time of O(1). The third method eliminates empty spaces in the array that holds suffixes, and improves the maximum size reduction further by about 5% at the cost of increased insertion time. Compared to a Ternary Search Tree, the key retrieval of the compressed MP double array is 50% faster and its size is 3–5 times smaller.
ISSN:0306-4573
1873-5371
DOI:10.1016/j.ipm.2009.08.004