A fast and compact elimination method of empty elements from a double‐array structure

Masaki Oono; El‐Sayed Atlam; Masao Fuketa; Kazuhiro Morita; Jun‐ichi Aoe

doi:10.1002/spe.545

journal article Aug 27, 2003

A fast and compact elimination method of empty elements from a double‐array structure

Masaki Oono El‐Sayed Atlam Masao Fuketa Kazuhiro Morita Jun‐ichi Aoe

Software: Practice and Experience Vol. 33 No. 13 pp. 1229-1249 · Wiley

View at Publisher Save 10.1002/spe.545

Abstract

AbstractA double‐array is a well‐known data structure to implement the trie. However, the space efficiency of the double‐array degrades with the number of key deletions because the double‐array keeps empty elements produced by the key deletion. This paper presents a fast and compact elimination method of empty elements using properties of the trie nodes that have no siblings. The present elimination method is implemented by C language. From simulation results for large sets of keys, the present elimination method is about 30–330 times faster than the conventional elimination method and maintains high space efficiency. Copyright © 2003 John Wiley & Sons, Ltd.

Topics

No keywords indexed for this article. Browse by subject →

References

11

[1]

Trie memory

Edward Fredkin

Communications of the ACM 10.1145/367390.367400

[2]

10.1145/360248.360258

[3]

Standish TA (1980)

[4]

Peterson JL (1980)

[5]

10.1145/360825.360855

[6]

Aoe J (1987)

[7]

LeskME.Lex—a lexical analyzer generator.Report CSTR 39 Bell Lab. NJ 1975;1–13.

[8]

Aho AV (1974)

[9]

Aho AV (1983)

[10]

An efficient digital search algorithm by using a double-array structure

J.-I. Aoe

IEEE Transactions on Software Engineering 10.1109/32.31365

[11]

MoritaK TanakaA FuketaM AoeJ.Implementation of update algorithms for a double‐array structure.IEEE International Conference on Systems Man and Cybernetics Tucson AZ 7–10 October2001;494–499. 10.1109/icsmc.2001.969862

Metrics

10

Citations

11

References

Details

Published: Aug 27, 2003
Vol/Issue: 33(13)
Pages: 1229-1249
License: View

Authors

Cite This Article

Masaki Oono, El‐Sayed Atlam, Masao Fuketa, et al. (2003). A fast and compact elimination method of empty elements from a double‐array structure. Software: Practice and Experience, 33(13), 1229-1249. https://doi.org/10.1002/spe.545

A fast and compact elimination method of empty elements from a double‐array structure

You May Also Like