An efficient deletion method for a minimal prefix double array

Susumu Yata; Masaki Oono; Kazuhiro Morita; Masao Fuketa; Jun‐ichi Aoe

doi:10.1002/spe.778

journal article Oct 24, 2006

An efficient deletion method for a minimal prefix double array

Susumu Yata Masaki Oono Kazuhiro Morita Masao Fuketa Jun‐ichi Aoe

Software: Practice and Experience Vol. 37 No. 5 pp. 523-534 · Wiley

View at Publisher Save 10.1002/spe.778

Abstract

AbstractA 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.

Topics

No keywords indexed for this article. Browse by subject →

References

7

[1]

10.1145/367390.367400

[2]

Peterson JL (1980)

[3]

10.1145/360825.360855

[4]

Aoe J (1987)

[5]

10.1109/32.31365

[6]

Morita K (2001)

[7]

10.1002/spe.545

Cited By

9

Compressed double-array tries for string dictionaries supporting fast lookup

Shunsuke Kanda, Kazuhiro Morita · 2016

Knowledge and Information Systems

Metrics

9

Citations

7

References

Details

Published: Oct 24, 2006
Vol/Issue: 37(5)
Pages: 523-534
License: View

Authors

Cite This Article

Susumu Yata, Masaki Oono, Kazuhiro Morita, et al. (2006). An efficient deletion method for a minimal prefix double array. Software: Practice and Experience, 37(5), 523-534. https://doi.org/10.1002/spe.778

An efficient deletion method for a minimal prefix double array

You May Also Like