Experience with a space efficient way to store a dictionary
- 1 May 1981
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 24 (5) , 297-298
- https://doi.org/10.1145/358645.358654
Abstract
The paper, “Computer Programs for Detecting and Correcting Spelling Errors” by James L. Peterson [3], listed methods for checking and correcting spelling errors. One significant method, however, was not included: a probabilistic technique suggested by Carter, Floyd, Gill, Markovsky, and Wegman [1]. The present note discusses aspects of these practical space efficient algorithms for testing set membership—a simple abstraction of looking a word up in a dictionary. An implementation of one of these algorithms uses only 20 percent of the space used by the Stanford SPELL program described by Peterson.Keywords
This publication has 4 references indexed in Scilit:
- Z - the 95% program editorPublished by Association for Computing Machinery (ACM) ,1981
- Computer programs for detecting and correcting spelling errorsCommunications of the ACM, 1980
- Exact and approximate membership testersPublished by Association for Computing Machinery (ACM) ,1978
- BLISSCommunications of the ACM, 1971