Thumbnail
Access Restriction
Subscribed

Author Wagner, Robert A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
Language English
Subject Keyword Text storage ♦ Minimum space ♦ Error messages ♦ Dynamic programming ♦ Diagnostic messages ♦ Optimization ♦ Common phrases
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.
Description Affiliation: Cornell Univ., Ithaca, NY (Wagner, Robert A.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 16
Issue Number 3
Page Count 5
Starting Page 148
Ending Page 152


Open content in new tab

   Open content in new tab
Source: ACM Digital Library