Data compression method for use in a computerized
informational and transactional network
|INVENTORS:|| Denenberg; Jeffrey N., Trumbull, CT 06611|
Weinberger; Edward D., New York, NY 10025
Gordon; Michael L., Dobbs Ferry, NY 10522
|ISSUED:||July 16, 1996|| ||FILED: ||Nov. 18, 1992|
|SERIAL NUMBER: ||978344|| ||MAINT. STATUS:
|INTL. CLASS (Ed. 6):||
H03M 7/30; H03M 7/48; G06F 15/16; |
341-055; 364-DIG.2; 364-919; 364-DIG.1; 364-260.6; 364-260.4; |
|FIELD OF SEARCH:||
Scifo; Paul C.]>; |
A method for compressing and subsequently decompressing digital data communicated in an interactive computer network, the network designed to provide informational and transactional services to a very large population of users. The method features steps for compressing bytes of network data before transmission by substituting variable-length code words obtained from a fixed, look-up table, and, reconstituting the bytes using a fixed, decompression look-up table when the code words are received at the data reception site. In accordance with the invention, the compression and decompression look-up tables are statistically compiled by sampling the occurrence frequency of byte pairs in the network data stream, and where byte pairs are found to occur above a predetermined frequency, code words having lengths inversely related to the occurrence frequency are created for inclusion in the table so that a code word may be substituted for one byte of a pair when the other byte of the pair is found to precede it during compression, and the byte reconstituted from the code word using the decompression table when the code word is received at the reception site. Additionally, where a byte and its preceding byte constitute a pair not found within the pairs compression table, the method features steps for transmitting the byte compressed in accordance with a context-free encoding scheme, together with a suitable escape code word. Yet further, the method features steps for combining other compression and decompression procedures with the byte-pair compression and decompression to produce a compound compression scheme for the network data stream.
|Patent No.|| Inventor ||Issued
|| DATA COMPACTION USING MODIFIED VARIABLE-LENGTH CODING|
||Raviv et al.||7 /1972
|| DATA COMPACTION USING VARIABLE-LENGTH CODING|
||Loh et al.||9 /1972
|| METHOD OF ACHIEVING DATA COMPACTION UTILIZING VARIABLE-LENGTH DEPENDENT CODING TECHNIQUES|
||Loh et al.||10 /1972
|| CODE PROCESSOR FOR VARIABLE-LENGTH DEPENDENT CODES|
|| Uniform decoding of minimum-redundancy codes|
||Thornburg et al.||1 /1976
|| Method of and system for adaptive run length encoding of image representing digital information|
||Arnold et al.||7 /1978
|| Markov processor for context encoding from given characters and for character decoding from given contexts|
|| Method and apparatus for digital Huffman encoding|
||Eastman et al.||8 /1984
|| Apparatus and method for compressing data signals and restoring the compressed data signals|
||Langdon, Jr. et al.||1 /1985
|| Adaptive source modeling for data file compression within bounded memory|
|| Data compression using run length encoding and statistical encoding|
||Jeppsson et al.||11 /1988
|| Arrangement for data compression|
||Imal et al.||6 /1989
|| Signal processing system|
||Kato et al.||7 /1989
|| Performance-based reset of data compression dictionary|
|| Data compression system for successively applying at least two data compression methods to an input data stream|
|| Compressing and decompressing text files|
EXEMPLARY CLAIM(s): Show all 9 claims
What we claim is:
- 1. A method for compressing streams of digital data, the data streams including successions of byte pairs in which a current byte immediately follows a prior byte, the data streams being generated by a data source for communication to a receiver, the method comprising:
- identifying a prior byte;
- identifying a current byte immediately following a prior byte;
- scanning a code word supply means for obtaining compression code words from a fixed table included in the code word supply means when a particular current byte immediately follows a particular prior byte, wherein the compression code words have respective lengths that are dependent upon the appearance of particular current bytes immediately following particular prior bytes, the codes words being generated with multiple codes, the multiple codes being determined by particular current bytes immediately following particular prior bytes, and having control parameters that may be adjusted so that the code word lengths are minimized where particular current bytes follow particular prior bytes, the compression code words provided in the table being created by analyzing byte streams of the data source produced prior to compression to develop occurrence frequency information concerning the appearance of current bytes immediately following prior bytes and providing code words at the code word supply means when the frequency of appearance of particular current bytes immediately following particular prior bytes, exceeds a predetermined value;
- determining whether a compression code word for the current byte can be obtained form the code word supply means; and
- communicating a compression code word for the current byte when the compression code word can be obtained from the code word supply means, and communicating an indication when a compression code word can not be obtained from the code word supply means when a particular current byte immediately follows a particular prior byte.
RELATED U.S. APPLICATIONS: none
FOREIGN APPLICATION PRIORITY DATA: none
FOREIGN REFERENCES: none
PRIMARY/ASSISTANT EXAMINERS: Lee; Thomas C.; Dinh; D.
- Bell et al., Modeling for Text Compression, Dec. 1989, ACM Computing Surveys, vol. 21, No. 4, pp. 557-590.
- Fila et al., Data Compression With Finite Windows, Apr. 1989, Communications Of The ACM, vol. 32, No. 4, pp. 490-505.
- Ziv et al., Compression Of Individual Sequences Via Variable--Rate Coding, Sep. 1978, IEEE Transactions On Information Theory, vol. IT-24, No. 5, pp. 530-505.
- Ziv et al., A Universal Algorithm For Sequential Data Compression, May 1977, IEEE Transactions On Information Theory, + vol. IT-23, No. 3, pp. 337-343.
ADDED TO DATABASE: Sep. 1 , 1996