Experiments in text file compression

ABSTRACT

A system for the compression of data files, viewed as strings of characters, is presented. The method is general, and applies equally well to English, to PL/I, or to digital data. The system consists of an encoder, an analysis program, and a decoder. Two algorithms for encoding a string differ slightly from earlier proposals. The analysis program attempts to find an optimal set of codes for representing substrings of the file. Four new algorithms for this operation are described and compared. Various parameters in the algorithms are optimized to obtain a high degree of compression for sample texts.

REFERENCES

• 1: Huffman, D.A. A method for the construction of minimum redundancy codes. Proc. IRE 40 (Sept. 1952), 1098.
• 2: Robert A. Wagner, Common phrases and minimum-space text storage, Communications of the ACM, v.16 n.3, p.148-152, March 1973 [doi>10.1145/361972.361982]
• 3: McCarthy, J.P. Automatic File Compression. International Computing Symp. 1973, North-Holland, Amsterdam, 1974, pp. 511-516.
• 4: Snyderman, M., and Hunt, B. The myraid virtues of text compaction. Datamation 16, 12 (Dec. 1970), 36-40.
• 5: Ruth, S.S., and Kreuzer, P.J. Data compression for large business files. Datamation 18, 9 (Sept. 1972), 62-66.
• 6: Kusmiss, J.M. An experiment in adaptive encoding. IBM Tech. Rep. TR 00.2524, Poughkeepsie, N.Y., 1974.
• 7: Hagamen, W.D., et al. Encoding verbal information as unique numbers. IBM Systems J. 11 (Oct. 1972), 278-315.

INDEX TERMS

Keywords:
Huffman codes, N-gram encoding, comparison of algorithms, data file compaction, text compression