US4955066A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compressing and decompressing text files
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1989-10-13
•
Granted: 1990-09-04
•
Expires: 2009-10-13
Abstract
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.
Inventors
- 👤 Leo A. Notenboom
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 17:24
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
130 words
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.
Claim 2
Independent Claim
130 words
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.
Claim 3
Dependent Claim
76 words
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.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
36 words
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.
Claim 6
Dependent Claim
43 words
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.
Claim 7
Independent Claim
95 words
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.
Claim 8
Independent Claim
95 words
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.
Claim 9
Dependent Claim
37 words
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.
Claim 10
Dependent Claim
71 words
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.
Claim 11
Dependent Claim
62 words
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.
Claim 12
Dependent Claim
34 words
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.
Claim 13
Dependent Claim
37 words
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
Claim 14
Dependent Claim
35 words
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.
References Cited (Backward Citations)
US4494150A
Cited
US4626829A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-09-03 | 1994-03-05 | 1994-09-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-09-03 | 1998-03-05 | 1998-09-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-09-03 | 2002-03-05 | 2002-09-04 | $7700.00 | Window Closed / Lapsed |