US Patent 4,955,066

Number:	4,955,066
Title:	Compressing and Decompressing Text Files
Filed:	13-Oct-1989
Granted:	04-Sep-1990
Inventor:	Notenboom, L.A.
Assignee:	Microsoft

Comment by FAQ:Now extended as 5,109,433 [Noted in signon screen of Word 5.5 and on the outside of the MS-DOS 5.0 Upgrade.] A method of compressing a text file in digital form is disclosed. A full text file having characters formed into phrases is provided by an author. The characters are digitally represented by bytes. A first pass compression is sequentially followed by a second pass compression of the text which has previously been compressed. A third or fourth level of compression is serially performed on the compressed text. For example, in a first pass, the text is run-length compressed. In a second pass, the compressed text is further compressed with key phrase compression. In a third pass, the compressed text is further compressed with Huffman compression. The compressed text is stored in a text file having a Huffman decode tree, a key phrase table, and a topic index. The data is decompressed in a single pass and provided one line at a time as an output. Sequential compressing of the text minimizes the storage space required for the file. Decompressing of the text is performed in a single pass. As a complete line is decompressed, it is output rapidly, providing full text to the user.