Common phrases and minimum-space text storage

ABSTRACT

A method for saving storage space for text strings, such as compiler diagnostic messages, is described. The method relies on hand selection of a set of text strings which are common to one or more messages. These phrases are then stored only once. The storage technique gives rise to a mathematical optimization problem: determine how each message should use the available phrases to minimize its storage requirement. This problem is nontrivial when phrases which overlap exist. However, a dynamic programming algorithm is presented which solves the problem in time which grows linearly with the number of characters in the text. Algorithm 444 applies to this paper.

REFERENCES

• 1: James R. Bell, The quadratic quotient method: a hash code eliminating secondary clustering, Communications of the ACM, v.13 n.2, p.107-109, Feb 1970 [doi>10.1145/362007.362040]
• 2: Nemhauser, G.L. Introduction to Dynamic Programming. John Wiley, New York, 1966.
• 3: Conway, R.W., et al. PL/C-A high performance subset of PL/I. TR 70-55, Comput. Sci. Dept., Cornell U., Ithaca, N.Y.
• 4: Saul Rosen , Robert A. Spurgeon , Joel K. Donnelly, PUFFT—The Purdue University fast FORTRAN translator, Communications of the ACM, v.8 n.11, p.661-666, Nov. 1965 [doi>10.1145/365660.365671]
• 5: Conway, R.W., and Maxwell, W.L. CUPL-An approach to introductory computing instruction. Comput. Sci. Dept., Cornell U., Ithaca, N.Y.
• 6: R. A. Wagner, Algorithm 444: an algorithm for extracting phrases in a space-optimal fashion, Communications of the ACM, v.16 n.3, p.183-185, March 1973 [doi>10.1145/361972.361998]

INDEX TERMS

Keywords:
common phrases, diagnostic messages, dynamic programming, error messages, minimum space, optimization, text storage