Common Phrases and Minimum-Space Text Storage
Wagner, Robert A.
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 non-trivial when phrases which overlap exist. However, we present a dynamic programming algorithm which solves the problem in time which grows linearly with the number of characters in the text. Keywords and Phrases: diagnosic messages, error messages, common phrases, minimum space, text storage, optimization, dynamic programming.
computer science; technical report
Previously Published As