Compressing and decompressing text files

• US 5,109,433 A
• Filed: 07/12/1990
• Issued: 04/28/1992
• 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): Moore, David K.
• Assistant Examiner(s): CAMMARATA, MICHAEL
• Application Number:
  US07/551,881
• Time in Patent Office: 656 Days
• Field of Search: 382/40, 382/49-56, 358/261.1, 358/427, 358/262.1
• US Class Current: 382/240
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• 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 creating a compressed text file stored in a computer memory in digital form, comprising:

generating a full text file having characters formed into phrases, said characters being digital data;

generating a first level compressed text file from said full 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 second level compressed text file from said first level compressed text file by replacing each unique string of bytes in said first level compressed text file with a unique string of bits.

6. The method according to claim 1, further including the steps of:

inputting as a user selected feature, the type of compression to be performed on said full text file; and

performing said inputted type of compression in said generating steps.

2. A method of creating a compressed text file stored in a computer memory in digital form, comprising:

generating a full text file having characters formed into phrases, said characters being digital data;

generating a first level compressed text file from said full text file by replacing digital data from said full text file with different digital data;

generating a second level compressed text file from said first level compressed text file by replacing digital data from said first level compressed text file with different digital data to provide a second level compressed text file; and

generating a third level compressed text file from said second level compressed text file by replacing digital data from said second level compressed text file with different digital data.

16. The method according to claim 2 wherein the type of compression performed at at least one of said three levels is selectable by a user from a plurality of choices.

17. The method according to claim 2 wherein the type of compression performed at the second level of compression is selectable by a user from a plurality of choices.

3. A method of creating a compressed text file stored in a computer memory in digital form, comprising:

generating a full text file having characters formed into phrases, said characters being digital data;

generating a first level compressed text file from said full text file by replacing digital data from said full text file with different digital data, the type of compression performed at the first level compression being selectable by a user from a plurality of choices; and

generating a second level compressed text file from said first level compressed text file by replacing digital data from said first level compressed text file with different digital data to provide a compressed text file.

18. The method according to claim 3 wherein the type of compression performed at the second level compression is selectable by a user from a plurality of choices.

4. A method of creating a compressed text file stored in a computer memory in digital form, comprising:

generating a full text file having characters formed into phrases, said characters being digital data;

generating a first level compressed text file from said full text file by replacing digital data from said full text file with different digital data;

generating a second level compressed text file from said first level compressed text file by replacing digital data from said first level compressed text file with different digital data to provide a second level compressed text file; and

generating a final compressed text file having a topic index, a context strings table, and said second level compressed text, wherein said topic index provides an address within said second level compressed text for obtaining selected information and said context strings table includes a listing of topics which are related to said information within said second level compressed text.

5. The method according to claim 4 wherein said final compressed text file further includes a context map which contains an address to said topic index for a selected topic within said context map.

7. A method of locating and decompressing text stored in the memory of a computer, comprising:

inputting a first sample string of data representing a phrase;

determining a first block of data within a compressed text file which relates to said sample string of data, said compressed text file including cross-reference data that defines topic relationships between data strings, said topic relationships being selectable by an author based on the context of said sample string as determined by said author;

retrieving said compressed text file from memory;

converting said compressed text file into a full format file ready for display on a computer monitor, said full format file including information for display to a viewer and cross-reference information; and

displaying said information to said viewer, said cross-reference information providing an address to a second block of data related to a second sample string within said displayed information.

8. The method according to claim 7 wherein said cross-reference information is related to said second sample string based on the context of said second sample string within said displayed information.

9. The method according to claim 8 wherein said second block of data is different than said first block of data for an identical sample string based on the context of sample strings being different from each other.

10. The method according to claim 8 wherein said compressed data file includes a context strings file and a compressed text file, and said first sample string is within said context strings file and said second sample string is not within said context strings file but not related topic data is within said compressed text file.

11. The method according to claim 7 wherein said determining step includes:

comparing said sample string to a plurality of reference strings; and

outputting an address for compressed data when a match is found for said sample string.

12. The method according to claim 8 wherein said determining step includes:

providing a reference to a topic index within said compressed text file which matches the topic of said sample string, the reference to said topic index being said sample strings on the same topic as said sample string within the context of the use as a data phrase; and

outputting from said topic index an address for compressed data.

13. A method of creating a compressed text file stored in a computer memory in digital form, comprising:

generating a full text file having characters formed into phrases, said characters being digital data;

generating a compressed text file containing said full text file in compressed data form;

generating a context string table having full text data strings selected from said full text file;

generating a topic index having addressed to different locations within said compressed text file; and

combining said compressed text file, said context string table, and said topic index in a single data file to provide an accessible file that contains some full text of phrases, compressed text of the same selected phrases, and said topic index for facilitating access to user selectable portions of said compressed text.

14. The method according to claim 13 wherein the addressed within said topic index are in the same sequence as the compressed text in said compressed text file, said addresses being the beginning address of a data block that is referenced by said topic index within said compressed text file and further including the steps of:

generating a context map that provides the location within said topic index for a given string in said context string table; and

combining said context map into said single data file.

15. The method according to claim 13, further including:

combining a first single data file with a second single data file to provide a data file having a plurality of topic indices maps, context string tables, and compressed text files.