Experience with a space efficient way to store a dictionary

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.

REFERENCES

• 1: Larry Carter , Robert Floyd , John Gill , George Markowsky , Mark Wegman, Exact and approximate membership testers, Proceedings of the tenth annual ACM symposium on Theory of computing, p.59-65, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804332]
• 2: Knuth, Donald E. TEX: A system for technical text. Tech. Rep. AIM-217, Stanford Univ., Stanford, CA, November, 1978.
• 3: James L. Peterson, Computer programs for detecting and correcting spelling errors, Communications of the ACM, v.23 n.12, p.676-687, Dec. 1980 [doi>10.1145/359038.359041]
• 4: Steven R. Wood, Z - the 95% program editor, Proceedings of the ACM SIGPLAN SIGOA symposium on Text manipulation, p.1-7, June 08-10, 1981, Portland, Oregon, United States
• 5: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Documentation, Languages