New methods for compression of MP double array by compact management of suffixes
作者:
Highlights:
•
摘要
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.
论文关键词:Minimal Prefix double array,Data structure,Trie,Matrix and list forms,Ternary Search Tree
论文评审过程:Received 7 July 2008, Revised 11 August 2009, Accepted 17 August 2009, Available online 13 September 2009.
论文官网地址:https://doi.org/10.1016/j.ipm.2009.08.004