Compressing and decompressing text files

• US 4,955,066 A
• Filed: 10/13/1989
• Issued: 09/04/1990
• Est. Priority Date: 10/13/1989
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Notenboom, Leo A.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Santos, Daniel
• Application Number:
  US07/421,466
• Time in Patent Office: 326 Days
• Field of Search: 382/40, 382/56, 358/261.1, 358/427
• US Class Current: 382/240
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

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 compression is serially performed on the previously 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 a user.

Claims

1. A method of compressing a text file stored in a computer memory in digital form, comprising:

generating a full text file having characters formed into phrases, said characters being digitally represented by bytes;

generating a first level compressed text file from said text full file by replacing runs of identical characters with a run flag, the character and a repetition count;

generating a second level compressed text file from said first level compressed text file by replacing frequently occurring phrases in said first level compressed text file with a key phrase flag byte and an index byte; and

generating a third level compressed text file from said second level compressed text file by replacing frequently occurring bytes in said second level compressed text file with a unique string of bits.

2. The method according to claim 1 further including:

counting the number of occurrences of each phrase in said full text file;

determining the storage saving achieved by replacing each occurrence of each different phrase with a flag byte and an index byte based on the number of occurrences of each said phrase and the size of each said phrase;

replacing only those phrases with a flag byte and an index byte which provide significant space savings.

3. The method according to claim 2 wherein a threshold number of phrases that provide the most significant savings are replaced with a flag byte and an index byte.

4. The method according to claim 2 wherein a first flag is used to indicate a space after said phrase and a second flag is used, to indicate that there is not a space after said phrase.

5. The method according to claim 2 wherein said phrase forms only a portion of a word, and said portion of said word is represented by a flag byte and an index byte and the remainder of said word is represented by individual characters.

6. The method of locating and decompressing text stored in the memory of a computer comprising:

comparing a sample string to a plurality of reference strings until a match is found;

stepping to a topic address in memory based on which reference string matches said sample string;

stepping to an address containing compressed text stored in memory based on an address provided by said topic address;

retrieving compressed text from memory;

decompressing said text from compressed form to a standard full format form ready for display on a computer monitor; and

outputting said full format text.

7. The method according to claim 6 wherein each line of said full format text includes cross reference information from a string in said line to a different compressed text file which contains information related to said string.

8. The method according to claim 6 wherein said decompressing step includes the steps of:

decompressing a portion of said compressed text;

testing said decompressed portion to determine if it is in full format form;

outputting said decompressed portion if it is in full format form, further decompressing said portion if it is not in full format form until it is in full format form and then outputting said further decompressed text.

9. The method according to claim 8 wherein said compressed text includes a unique bit code corresponding to each byte and some of said bytes correspond to a full format character and some of said bytes correspond to a flag byte which indicates that the next byte contains additional information to uniquely identify a group of characters from of said full format text.

10. The method according to claim 6 wherein said compressed text file is formed into a file containing compressed text, a Huffman decode tree, a key phrase table and an index to said compressed text.

11. The method according to claim 10 wherein said index includes a topic index, a context string table and a context map, said context map providing an address location reference of a context string within said topic index

12. The method according to claim 10 wherein said step of testing said text to determine if it is in full format form includes determining whether said text is a standard character or a flag character.