An efficient deletion method for a minimal prefix double array

A minimal prefix (MP) double array is an efficient data structure for a trie. The MP double array only requires a small amount of space and enables fast retrieval. However, the space efficiency of the MP double array is degraded by deletion. This paper presents a fast and compact adaptive deletion m...

Full description

Saved in:
Bibliographic Details
Published in:Software, practice & experience practice & experience, 2007-04, Vol.37 (5), p.523-534
Main Authors: Yata, Susumu, Oono, Masaki, Morita, Kazuhiro, Fuketa, Masao, Aoe, Jun-ichi
Format: Article
Language:English
Subjects:
dictionary
information retrieval
trie search
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:A minimal prefix (MP) double array is an efficient data structure for a trie. The MP double array only requires a small amount of space and enables fast retrieval. However, the space efficiency of the MP double array is degraded by deletion. This paper presents a fast and compact adaptive deletion method for the MP double array. The presented method is implemented with C. Simulation results for English and Japanese keys show that the adaptive method is faster than the conventional method and maintains higher space efficiency. Copyright © 2006 John Wiley & Sons, Ltd.
ISSN:0038-0644
1097-024X
DOI:10.1002/spe.778