5537551: Data compression method for use in a computerized informational and transactional network

ABSTRACT:   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.

U.S. REFERENCES:

(No patents reference this one)

Patent No. Inventor Issued Title 3675211 Raviv 7 /1972 DATA COMPACTION USING MODIFIED VARIABLE-LENGTH CODING 3675212 Raviv et al. 7 /1972 DATA COMPACTION USING VARIABLE-LENGTH CODING 3694813 Loh et al. 9 /1972 METHOD OF ACHIEVING DATA COMPACTION UTILIZING VARIABLE-LENGTH DEPENDENT CODING TECHNIQUES 3701108 Loh et al. 10 /1972 CODE PROCESSOR FOR VARIABLE-LENGTH DEPENDENT CODES 3883847 Frank 5 /1975 Uniform decoding of minimum-redundancy codes 3935379 Thornburg et al. 1 /1976 Method of and system for adaptive run length encoding of image representing digital information 4099257 Arnold et al. 7 /1978 Markov processor for context encoding from given characters and for character decoding from given contexts 4396906 Weaver 8 /1983 Method and apparatus for digital Huffman encoding 4464650 Eastman et al. 8 /1984 Apparatus and method for compressing data signals and restoring the compressed data signals 4494108 Langdon, Jr. et al. 1 /1985 Adaptive source modeling for data file compression within bounded memory 4626829 Hauh 12 /1986 Data compression using run length encoding and statistical encoding 4782325 Jeppsson et al. 11 /1988 Arrangement for data compression 4839649 Imal et al. 6 /1989 Signal processing system 4847619 Kato et al. 7 /1989 Performance-based reset of data compression dictionary 4988998 O'Brien 1 /1991 Data compression system for successively applying at least two data compression methods to an input data stream 5109433 Notenboom 4 /1992 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 OTHER REFERENCES: 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. PRIMARY/ASSISTANT EXAMINERS: Lee; Thomas C.; Dinh; D. ADDED TO DATABASE: Sep. 1 , 1996