United States Patent (19)
`Chu
`
`54 AUTOMATICELECTRONIC DATA TYPE
`IDENTIFICATION PROCESS
`Ke-Chiang Chu, Saratoga, Calif.
`75 Inventor:
`73 Assignee:
`Apple Computer, Inc., Cupertino,
`Calif.
`21 Appl. No.: 993,181
`(22
`Filed:
`Dec. 18, 1992
`51) int. Cl................................................. G06F 7/38
`52 U.S. Cl. ...............
`... 340/146.2: 364/715.02
`58) Field of Search ................. 340/146.2; 364/715.02
`56)
`References Cited
`U.S. PATENT DOCUMENTS
`4,479,217 10/1984 Philippides....................... 340/146.2
`4,588,302 12/1985 Welch ................................... 341/51
`4,612,532 9/1986 Bacon et al. .......................... 341/90
`4,648,059 3/1987 Gregorcyk ....................... 340/146.2
`4,881,075 11/1989 Weng .................................. 341/106
`4,933,662 6/1990 Szczepanck ...................... 340/146.2
`4,935,719 6/1990 McClure .......................... 340/146.2
`5,199,051 3/1993 Nakabayashi et al. ..
`... 375/17
`OTHER PUBLICATIONS
`IEEE, Computer, Jun. 1984, pp. 8-19, Terry A. Welch,
`Sperry Research Center, "A Technique for High-Per
`formance Data Compression'.
`IEEE, Transactions On Information Theory, vol. II 23,
`No. 3, May 1977, pp. 337-343.J. Ziv, A. Lempel, "A
`Universal Algorithm for Sequential Data Compres
`sion'.
`IEEE, Transactions On Information Theory, vol. II 24,
`No. 5, Sep. 1978, pp. 530-536, J. Ziv, A. Lempel,
`
`
`
`US005374916A
`Patent Number:
`Date of Patent:
`
`11
`45
`
`5,374,916
`Dec. 20, 1994
`
`“Compression of Individual Sequences via Variable--
`Rate Coding”.
`IEEE Transactions on Information Theory vol. II 21,
`No. 2, Mar. 1975, pp. 194-203. Peter Elias, “Universal
`Codeword Sets and Representations of the Integers'.
`Communications of the ACM, Apr. 1989 vol. 32 No. 4,
`pp. 490-504, Edward R. Riala and Daniel H. Greene,
`"Data Compression with Finite Windows'.
`Timothy C. Bell, John G. Cleary, Ian H. Witten, Text
`Compression, Prentice Hall, Englewood Cliffs, N.J.,
`1990, pp. 206-243.
`Primary Examiner-John S. Heyman
`Attorney, Agent, or Firm-V. Randall Gard
`57
`ABSTRACT
`A data compression process and system that identifies
`the data type of an input data stream and then selects in
`response to the identified data type at least one data
`compression method from a set of data compression
`methods that provides an optimal compression ratio for
`that particular data type, thus maximizing the compres
`sion ratio for that input data stream. Moreover, the data
`compression process also provides means to alter the
`rate of compression during data compression for added
`flexibility and data compression efficiency. Further
`more, a system memory allocation process is also pro
`vided to allow system or user control over the amount
`of system memory to be allocated for the memory inten
`sive data compression process. System memory alloca
`tion process estimates the memory requirement to com
`press the input data stream, and allocates only that
`amount of system memory as needed by the data com
`pression for memory allocation efficiency.
`
`12 Claims, 8 Drawing Sheets
`
`DAAYPE AND
`GENERATEDATATYPE
`D.S.GNAL
`
`COMPRESSDATA
`NACCORDANCE
`WHENFE
`DATAYF
`
`RREDATAYPE
`NFORATION
`OFCOMPRSSEDATA
`SREAM
`
`NACCORDANCE WITH
`DNFEDDATA
`TYPE
`
`IPR2018-01413
`Sony EX1037 Page 1
`
`

`

`U.S. Patent
`
`Dec. 20, 1994
`
`Sheet 1 of 8
`
`5,374,916
`
`c
`
`13
`
`c
`
`11
`
`%56%be.
`- - -
`Nis
`N16
`
`2-20
`
`?
`22 12 CO
`labelela.ul. ... Pole
`FIG. 1 (PRIOR ART)
`
`.
`
`13 Ef
`
`
`
`FIG. 2 (PRIOR ART)
`
`IPR2018-01413
`Sony EX1037 Page 2
`
`

`

`U.S. Patent
`
`Dec. 20, 1994
`
`Sheet 2 of 8
`
`5,374,916
`
`Off
`
`0NICJOOZT
`
`
`
`NOISSBHc]WOO WIW0
`
`IPR2018-01413
`Sony EX1037 Page 3
`
`

`

`U.S. Patent
`
`Dec. 20, 1994
`
`Sheet 3 of 8
`
`5,374,916
`
`
`
`IDENTFY INPUT
`DATA TYPE AND
`GENERATE DATA TYPE
`I.D. SIGNAL
`
`COMPRESS DATA
`NACCORDANCE
`WITH IDENTIFIED
`DATA TYPE
`
`RETRIEVE DATA TYPE
`INFORMATION
`OF COMPRESSED DATA
`STREAM
`
`DECOMPRESS DATA
`NACCORDANCE WITH
`DENTIFIED DATA
`TYPE
`
`IPR2018-01413
`Sony EX1037 Page 4
`
`

`

`U.S. Patent
`
`Dec. 20, 1994
`
`Sheet 4 of 8
`
`5,374,916
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`O
`
`------ (-
`
`102
`
`SELECTPMAX ANDMAX
`
`GENERATE DATA TYPE
`.D. SIGNAL AND
`PROVIDESIGNATO
`COMPRESSION PHASE
`
`SELECTAT LEAST ONE
`DATA COMPRESSION
`METHOD FROM ASET
`OF DATA COMPRESSION
`METHODSACCORDING TO
`INPUT DATA TYPESIGNAL
`AND CONTROL RATE
`SIGNAL
`
`COMPRESS INPUT
`DATASTREAM
`USING SELECTED
`COMPRESSION METHOD
`
`108
`
`IPR2018-01413
`Sony EX1037 Page 5
`
`

`

`U.S. Patent
`
`Dec. 20, 1994
`
`Sheet 5 of 8
`
`5,374,916
`
`
`
`ESTMATE
`MEMORY
`REOUREMENT
`
`ALLOCATE
`MEMORY
`FOR DATA
`COMPRESSION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`126
`
`MONITOR
`COMPRESSION
`RATE CONTROL
`SIGNAL
`
`128
`
`DOES
`RATE CONTROL
`SIGNAL INDICATE
`TO SPEEDUP
`COMPRESSION
`
`
`
`
`
`
`
`
`
`
`
`INCREASE
`THE SPEED
`OFCOMPRESSION
`BYSWITCHENG
`LZMETHOD OR
`DECREASE
`PMAXLMAX
`
`COMPRESS DATAUSING
`A SELECTED Z-TYPE
`COMPRESSION METHOD
`
`130
`
`COMPRESS DATAUSING
`A SELECTED HUFFMAN
`CODEMETHOD
`
`IPR2018-01413
`Sony EX1037 Page 6
`
`

`

`U.S. Patent
`
`Dec. 20, 1994
`
`Sheet 6 of 8
`
`5,374,916
`
`
`
`112
`
`SELECT AHUFFMAN
`LOOKUPTABLE
`ASSOCATED WITH THE
`IDENTIFIED DATA TYPE
`
`DECOMPRESS DATA
`USING SELECTED
`LOOKUPTABLE TO
`GENERATE ASET OF(p'')
`
`DECOMPRESS THE
`p''TO GENERATE
`EXPANDED DATA
`
`FIG. 7
`
`IPR2018-01413
`Sony EX1037 Page 7
`
`

`

`U.S. Patent
`
`Dec. 20, 1994
`
`Sheet 7 of 8
`
`5,374,916
`
`002
`
`
`
`WIWO
`
`NOISSE|HdWOO
`
`WELSÅS
`WIWO
`NOISSE|HdWOO-H Hd
`
`IPR2018-01413
`Sony EX1037 Page 8
`
`

`

`US. Patent
`
`Dec. 20, 1994
`
`Sheet 8 of 8
`
`5,374,916
`
`DATADECOMPRESSION
`
`SYSTEM
`
`300
`
`D.
`
`FIG.9
`
`Z 9
`
`.CD
`(0
`Lu
`
`<E
`"2
`<"o
`GoLu
`9Lu
`0:
`
`|PR2018—O1413
`
`Sony EX1037 Page 9
`
`IPR2018-01413
`Sony EX1037 Page 9
`
`

`

`1.
`
`AUTOMATICELECTRONICDATA TYPE
`IDENTIFICATION PROCESS
`
`This patent application relates to copending and con
`currently filed patent application having the following
`patent application serial number and filing date: Ser.
`No. 07/992,972, filed Dec. 18, 1992. This patent applica
`tion and this copending patent application are com
`monly owned at the time offiling of this patent applica
`10
`tion.
`
`5,374,916
`2
`data type of an input data stream. Most prior art data
`manipulation processes rely on the user or another
`source external to the data manipulation process itself to
`supply such data type information. For example, in a file
`transfer program ("FTP”), the FTP process queries the
`user to supply the data type information of the input
`data stream. Other prior art data manipulation processes
`include requiring a user to set a data type mode bit, or
`to assume a particular data type of the input data stream.
`Assuming a particular data type is an inefficient method
`of manipulating data. If an electronic data manipulation
`process always assumes the data type to be 8 bits, when
`in reality the input data type comprise 7 bits, the data
`type assumption by the process then results in a substan
`tial waste of system memory to reserve an additional bit
`for each data symbol in the input data stream. Thus, it
`would be desirable to provide a method to automati
`cally detect the data type of an input data stream.
`Additionally, typical prior art data compression tech
`niques are classified either as a statistical or a dictionary
`type of data compression method. A statistical type of
`data compression is based on single symbol coding.
`Single symbol coding is accomplished by assigning to
`each possible data symbol in the input data stream a
`probability for the appearance of that symbol. Examples
`of this type of data compression method are the Huff
`man code method and the widely published variations
`of this code. With the Huffman coding method, a sym
`bol having a greater probability of appearance is en
`coded with a short binary string, while a symbol having
`a lower probability of appearance in the input data
`stream is encoded with a longer binary string.
`A dictionary type data compression method associ
`ates groups of consecutive characters, as in phrases, to
`a dictionary of indices. The dictionary type data com
`pression methods are also commonly referred to as a
`"codebook” or a "macrocoding” approach. The vari
`ous coding schemes in the Ziv-Lempel (“LZ”) family of
`data compression techniques are all examples of the
`dictionary type of data coding method. In the LZ fam
`ily of data compression methods, a typical LZ-type
`compression method processes an input data stream by
`checking first if each current data string encountered in
`the input data stream matches a data string already
`stored in the output data buffer. If no match of the
`current data string to previously stored data strings is
`detected, the current data string is stored into the output
`buffer. If, however, a match is detected between the
`current data string and a data string already stored in a
`memory location of the output data buffer, a pointer
`indicating that memory location is stored into the out
`put buffer instead of the data string.
`Shown in FIGS. 1 and 2 are two examples of LZ data
`compression methods. The LZ-1 compression method
`shown in FIG. 1 processes an uncompressed input data
`stream 10 to generate a compressed data output stream
`20 by comparing an uncompressed portion 13 of input
`data stream 10 to data in a history, buffer 11 of already
`processed input data. If a matching data string 12 is
`located in history buffer 11 for current data string 14,
`data string 14 is encoded in compressed data stream 20
`as a pointer (po, lo) 24, corresponding to an offset po15
`and a data length lo 16. The shorter length data of
`pointer (po, lo) 24 thus replaces longer data string 14 in
`output compressed data stream 20.
`History buffer 11 is considered to comprise no data at
`the time prior to data compression of input data stream
`10. As the compression process progresses, history
`
`FIELD OF INVENTION
`This invention relates to electronic data manipulation
`processes. More specifically, this invention relates to
`15
`electronic data compression systems used with a com
`puter.
`
`BACKGROUND
`Having an efficient data compression system is in
`20
`creasingly significant as electronics manufacturers com
`pete with each other for compactness and improved
`performance in their electronic products. In particular,
`an increasing market demand for a variety of portable
`electronic products has resulted in requiring a substan
`25
`tial reduction to the system real estate available for
`electronic data storage and data manipulation in the
`designs of these products. Thus, with less electronic
`memory available, having an efficient data compression
`method is even more critical in the designs of portable
`30
`electronics, if these devices are to achieve the compara
`ble operation of a larger electronic system.
`A variety of data compression techniques are known.
`The performances of each of these various data com
`pression techniques are measured by the compression
`35
`ratio, which is the length of an uncompressed input data
`stream to the length of its corresponding compressed
`data stream following data compression. The compres
`sion ratio for each data compression technique, how
`ever, also varies depending on the data type of the input
`data stream. Some data compression techniques have a
`higher compression ratio for ASCII type input data
`than for binary data type, while other data compression
`techniques result in a lower compression ratio for
`ASCII data type and a higher ratio for binary data type.
`45
`Thus, for each data type, one or more data compression
`techniques can be identified which will provide an opti
`mal data compression ratio according to that data type,
`while other data compression techniques producing a
`lower compression ratio for that particular data type
`50
`should be avoided.
`A variety of data types are known and used by the
`industry to encode characters, punctuation marks, and
`other symbols found in texts and communication proto
`cols. Known data types include ASCII standard format,
`55
`binary standard format, and unicode standard format.
`Although ASCII standard comprises a set of 8-bit bi
`nary numbers, only 7 of these bits are typically used to
`represent an actual data symbol, while binary standard
`format encodes one data symbol in 8 bits. Unicode rep
`60
`resents each data symbol with two bytes, or a set of
`16-bit binary numbers. The first byte, or the first 8-bit
`prefix, indicates a data characteristic information of the
`16-bit data symbol. For example, the first byte might
`indicate that the 16-bit data symbol is a Kanji character.
`65
`However, despite the variety of data types that are
`commonly used in the industry, prior art data manipula
`tion processes do not include automatic detection of the
`
`IPR2018-01413
`Sony EX1037 Page 10
`
`

`

`5,374,916
`3
`4.
`buffer 11 expands within a given system memory re
`also do not maximize the usage of the CPU, such as to
`serve according to how much of input data stream 10
`provide normal rate of data compression during the
`has been processed until history buffer 11 reaches the
`CPU's idle time, but increasing the rate of data com
`maximum system memory allocation available for data
`pression when the CPU is preparing to process another
`compression. Thus, in the case where no matching
`task. It is therefore also desirable to have a data com
`string is found, as in the case for data string 12 during
`pression system that provides controlling means to in
`the initial data compression stage of input data stream
`crease or decrease the system's rate of data compres
`10, unmatched string 12 is stored into output data
`SO.
`stream 20 in the form of a literal length header (LL) 22
`followed by data string 12 duplicated from original data
`10
`stream 10. Literal length header 22 encodes the number
`of characters, n, in unmatched string 12 that follows
`literal length header 22. This encoded information is
`recovered during data decompression to notify the de
`compression process of the number of data characters
`15
`following literal length header 22, corresponding to the
`original input data that need not be expanded.
`The LZ-2 data compression method of FIG. 2
`searches for matching current data string 14 in a dictio
`nary 30 of indices. Dictionary 30 comprises a limited
`20
`buffer length and data strings from input data stream 10.
`If a matching data string 12 is located in dictionary 30
`for current data string 14, current data string 14 is then
`encoded in the output data stream with index 32 corre
`sponding to the location of data string 12 in dictionary
`25
`30. Because the LZ-1 method of FIG. 1 searches for a
`matching data string character by character through
`the history buffer, the time required to compress input
`data stream 10 is substantially greater when using the
`LZ-1 method of FIG. 1 than with the LZ-2 method of
`30
`FIG. 2. However, the LZ-1 method provides a greater
`data compression ratio than the LZ-2 method.
`Data decompression is the conversion of a stream of
`compressed data back to its original expanded form.
`Decompression is typically accomplished with a lookup
`35
`table, if the data was compressed using a statistical or a
`Huffman type coding scheme. If the data was com
`pressed using a dictionary type data compression
`method, such as the LZ-1 method (as explained above
`with reference to FIG. 1), original data stream 10 is
`reconstructed by replacing each pointer (p, 1) encoun
`tered in compressed data stream 20 with the data string
`in the history buffer located at offset p. If the data was
`compressed with an LZ-2 data compression scheme (as
`explained above with reference to FIG. 2), the dictio
`45
`nary generated during data compression is used to re
`trieve the indexed data strings.
`FIG. 3 illustrates a typical prior art data compression
`system. Data compression system 40 receives an input
`uncompressed data stream 10 and processes data stream
`10 through a first data compression phase 42 using a first
`predefined data compression technique. Alternatively,
`prior art data compression system 40 may also provide
`a second data compression phase 44 using a second data
`compression technique also predefined by the design of
`55
`data compression system 40. Prior art data compression
`systems thus use the same data compression techniques
`incorporated by the data compression system design
`regardless of the data type encountered in the input data
`stream. Because each data compression technique typi
`cally provides a different compression ratio for different
`data types, prior art compression systems are unable to
`maximize the data compression ratio when encounter
`ing a variety of input data types in the input data stream.
`There is therefore a need to provide an efficient and
`65
`flexible data compression system that maximizes the
`data compression ratios according to the input data type
`detected. Moreover, prior art data compression systems
`
`BRIEF DESCRIPTION OF DRAWINGS
`FIG. 1 illustrates an example of the prior art LZ-1
`data compression;
`FIG. 2 illustrates an example of the prior art LZ-2
`data compression;
`FIG. 3 illustrates an example of a prior art data com
`pression system;
`FIG. 4 shows a block diagram of one embodiment of
`a lossless data compression and decompression process
`taught in accordance with the principles of this inven
`tion;
`FIG. 5 illustrates a detailed block diagram of one
`embodiment of the data compression process of FIG. 4;
`FIG. 6 illustrates a detailed block diagram of one
`embodiment of the input data compression process of
`FIG. 5;
`FIG. 7 illustrates a detailed block diagram of one
`embodiment of the data decompression process shown
`of FIG. 4;
`FIG. 8 shows a block diagram of one embodiment of
`a lossless data compression system constructed in accor
`dance with the principles of this invention; and
`FIG. 9 illustrates a block diagram of one embodiment
`of a data decompression system constructed in accor
`dance with the principles of this invention.
`DETAILED DESCRIPTION
`FIG. 4 shows one embodiment of a high speed loss
`less data compression and decompression process 100 of
`the present invention. Data compression process 102
`comprises two phases: a data pre-compression phase
`106 and a compression phase 108. Similarly, data de
`compression process 104 also comprises two phases: a
`data type retrieval phase 110 and a decompression
`phase 112. During data compression process 102, data
`pre-compression phase 106 first receives an uncom
`pressed input data stream 101 and identifies the data
`type of the input data stream. Data precompression 106
`also generates a data type identification signal. Com
`pression phase 108 then selects a data compression
`method from a set of data compression methods accord
`ing to the data type identification signal.
`It is envisioned as within the scope of the principles
`taught in accordance with this invention that the set of
`data compression methods can include a variety of data
`compression methods, such as the data compression
`methods from the LZ-type family of data compression
`methods, the Huffman code family of data compression
`methods, or other such data compression methods, in
`cluding the Arithmetic code, or combinations of such
`data compression methods. In the preferred embodi
`ment of this invention, the set of compression methods
`comprises a combination of LZ-type/Huffman-type
`compression methods. For example, if the input data
`type is identified as ASCII, the data type identification
`signal from pre-compression phase 106 indicates to
`compression process 108 to select an LZ-1 and a Huff
`man type HA combination of compression methods that
`is designed to provide an optimal compression ratio for
`
`SO
`
`IPR2018-01413
`Sony EX1037 Page 11
`
`

`

`Data Type
`ASCII
`Binary
`
`15
`
`lmax Range
`16-2048 bytes
`16-256 bytes
`
`5,374,916
`5
`6
`ASCII type data. According to the selected combina
`the LZ-1 data compression method. Selecting a lower
`tion of compression methods, compression process 108
`pmax typically increases the rate of data compression,
`then compresses the input data stream first with the
`while typically decreasing the compression ratio. Simi
`LZ-1 data compression method to generate a first set of
`larly, selecting a lowerlmax also typically increases the
`compressed data. The first set of compressed data is
`rate of data compression, since a shorter character
`then processed with the Huffman type compression
`length 1 requires less search time. Selecting a lower lina.
`method, HA, to provide a second set of compressed
`also typically results in a lower compression ratio.
`data. Likewise for other data types, one or more LZ
`Thus, varying the pmax and the limax parameters typi
`type/Huffman type combinations of compression meth
`cally produces a different compression time and a dif.
`ods, which provide an optimal data compression ratio
`ferent compression ratio.
`10
`for one or more particular data types, can be included in
`TABLE 1.
`the set of compression methods used during compres
`sion process 108.
`pnar Range
`FIG. 5 illustrates a detailed block diagram of the
`2K-8K bytes
`preferred embodiment of data compression process 102
`16K-32K bytes
`of FIG. 4. During data pre-compression 106, the data
`type of input data stream 101 is first identified with data
`type identification process 114. In the preferred em
`bodiment, data type identification process 114 detects
`the input data type as either ASCII, binary, or unicode
`20
`by analyzing a predefined number of bytes of input data
`stream 101.
`Typically, in the ASCII format, a data symbol is
`encoded in only 7 bits out of a set of 8 bits, while the
`binary format uses all 8 bits to represent a data symbol.
`25
`Consequently, a byte of ASCII data corresponds to a
`decimal equivalent value in the range of 0-127, while a
`byte of data in binary format represents a decimal equiv
`alent value in the range of 0-255. Thus, data type identi
`fication process 114 detects whether each byte of input
`data stream 101 corresponds to a decimal equivalent
`value of greater than 127. If the current data byte corre
`sponds to a decimal equivalent value greater than 127,
`than the data type of input data stream 101 is identified
`as binary. If the current data byte corresponds to a
`35
`decimal equivalent value of less than 127, data type
`identification process 114 continues to check the next
`byte of input data until the end of the input data stream.
`A consistent pattern of data bytes, each comprising a
`decimal equivalent of less than 127, indicates that the
`input data type is ASCII.
`In the preferred embodiment, data type identification
`process 114 also detects for unicode format data type by
`comparing the first bytes of a predefined number of
`pairs of bytes in input data stream 101. A typical data
`45
`symbol in unicode is represented by a pair of bytes, with
`the first byte always indicating the data characteristic
`(e.g., Kanji character type) of the data encoded in the
`pair of bytes. Thus, if the first bytes of the predefined
`number of pairs of data bytes matches, then the data
`type of input data stream 101 is identified as unicode.
`Once the data type is identified, data pre-compression
`106 also preferably encodes this data type information
`in any known standard used in the industry as means for
`denoting the data type of a data stream. The typical
`standard used for denoting a data type of a data stream
`is to encode the data type information in a header lo
`cated at the beginning of an output data buffer. The data
`type information is then retrieved by decoding the
`header during data decompression to identify the data
`type of the compressed data stream being decom
`pressed.
`In the preferred embodiment of the present invention,
`during data pre-compression phase 106, a pna and limax
`value are also selected which provide an optimal LZ-1
`65
`data compression ratio according to the identified data
`type. Table 1 illustrates a range of pnax and imax values
`for ASCII and binary type data that may be used with
`
`As shown in FIG. 5, oncepmax and limax are selected,
`data type signal generation process 116 generates a type
`identification signal to be provided to compression
`phase 108. Compression method selection process 118
`selects an LZ-type/Huffman-type combination com
`pression method in accordance with the data type iden
`tification signal, and input data compression process 120
`compresses the input data stream according to the se
`lected data compression method. In the preferred em
`bodiment of this invention, selection process 118 selects,
`in accordance with the data type identification signal, a
`compression method having a first data compression
`phase comprising an LZ-1 compression and a second
`data compression phase comprising a Huffman-type
`compression or Arithmetic code compression.
`FIG. 6 illustrates a detailed block diagram of one
`embodiment of compress input data process 120 of FIG.
`5. In the preferred embodiment of compress input data
`process 120, a system memory allocation process 140 is
`provided to allow the system or the user control of the
`amount of system memory to be allocated for data com
`pression. Memory allocation process 140 estimates the
`memory requirement necessary to compress input data
`stream 101 and then allocates that estimated amount of
`system memory for data compression process 120. In
`the preferred embodiment, memory allocation process
`140 estimates the memory requirement in accordance to
`the identified input data type, a selected compression
`ratio, a selected speed of data compression, a selected
`pmax and limax value, or a selected combination of these
`features. As data compression process 120 progresses
`and more system memory is needed to complete data
`compression of the input data stream, memory alloca
`tion process 140 then allocates additional increments of
`system memory to data compression process 120. Alter
`natively, it is also envisioned as within the scope of the
`principles taught by this invention to have memory
`allocation process 140 provide an initial memory alloca
`tion of a predefined range of system memory for data
`compression process 120 without first estimating a
`memory allocation requirement. Memory allocation
`process 140 then subsequently provides additional in
`crements of system memory during the compression
`process as is needed.
`Once the initial system memory is allocated, first data
`compression process 122 commences data compression
`of the input data stream using the LZ-type data com
`pression method to generate a first set of compressed
`data. During a second compression process 124, the first
`set of compressed data is compressed using the Huff
`man-type code compression method.
`
`5
`
`30
`
`50
`
`55
`
`IPR2018-01413
`Sony EX1037 Page 12
`
`

`

`10
`
`5,374,916
`7
`8
`In an alternative embodiment of input data compres
`data type identification and data type signal generation
`sion process 120 also shown in FIG. 6, a compression
`process 106 and data compression system 204 comprises
`rate control signal 103 is provided to data compression
`compression data process 108 as explained with refer
`process 120. Data compression rate adjustment process
`ence to FIG. 4.
`130 adjusts the values of limax, pna, or both limax and
`FIG. 9 illustrates one embodiment of a data decom
`pm to increase or decrease the compression process
`pression system 300 constructed in accordance with the
`speed in response to data compression rate control sig
`principles of this invention. Data pre-decompression
`nal 103. In an alternative embodiment of data compres
`system 302 receives a compressed data stream 107 and
`sion rate adjustment process 130, adjustment process
`identifies its data type. In response to the identified data
`130 indicates to LZ-type compression process 122
`type, data pre-decompression system 302 generates a
`whether to use LZ-1 or LZ-2 compression in accor
`compressed data type identification signal 109. Data
`dance with data compression rate control signal 103 to
`decompression system 304, which also receives com
`adjust the compression time for compressing data.
`pressed data stream 107, is coupled to data pre-decom
`Thus, data compression rate adjustment process 130
`pression system 302 to receive compressed data type
`provides data compression process 120 with the flexibil
`identification signal 109. Data decompression system
`15
`ity to adjust the compression speed during data com
`304 selects at least one data decompression method
`pression. This flexibility provides compression system
`from a set of data decompression methods in response to
`100 means to maximize the CPU's idle time to do data
`compressed data type identification signal 109. Com
`compression and means to increase the data compres
`pressed data stream 107 is then decompressed by data
`sion speed when the CPU is in preparation to begin
`decompression system 304 using the selected decom
`20
`another process.
`pression method to generate as output expanded origi
`FIG. 7 illustrates an example of a detailed block dia
`nal data stream 111.
`gram of the preferred embodiment of data decompres
`In the preferred embodiment of data decompression
`sion process 112 of FIG. 4. Once the data type informa
`system 300, data pre-decompression system 302 prefera
`tion of compressed data stream 107 is retrieved by de
`bly comprises data type retrieval process 110, while
`25
`coding the header of compressed data stream 107,
`data decompression phase 304 comprises data decom
`lookup table selection process 132 selects a correspond
`pression process 112 as explained with reference to
`ing Huffman code lookup table that is associated with
`FIG. 4.
`that data type. A first data decompression process 134
`Data compression and decompression process 100
`then processes the compressed data using the selected
`that identifies the data type of a data stream and then
`30
`lookup table to generate a first set of decompressed
`selects according to the identified data type at least one
`data. A second decompression process 136 then pro
`data compression method, which provides optimal data
`cesses the first set of decompressed data using the se
`compression ratio for that identified data type, thus
`lected LZ type decompression codebook to provide as
`maximizes the compression ratio of the input data
`output an expanded original data stream. It is also envi
`stream. Moreover, data compression process 100 also
`35
`sioned as within the scope of the principles taught by
`provides means to control the memory allocation for
`this invention that other such data decompression algo
`the data compression process and means to alter the rate
`rithms may be substituted during data decompression
`of compression during data compression process. Each
`process 112 to decompress compressed data stream 107,
`of these features provides an added flexibility that maxi
`if another compression algorithm was selected during
`mizes data compression efficiency.
`data compression process 102 in response to the particu
`I claim:
`lar data type of the original data stream.
`1. An electronic data type identification process for
`FIG. 8 illustrates the preferred embodiment of a data
`automatically identifying a data type of information
`compression system 200 constructed in accordance
`contained in an input data stream, the input data stream
`with the principles of this invention. Data pre-compres
`including a plurality of bytes of data the process com
`45
`sion system 202 receives an input data stream 101 and
`prising the computer-implemented steps of:
`identifies its data type. Data pre-compression system
`receiving the input data stream;
`202 also generates a data type identification signal 105 in
`selecting at least one byte of data of the plurality of
`response to the identified data type of input data stream
`byte; of data in the input data stream;
`101. Data compression system 204, which also receives
`detecting whether the at least one byte of data repre
`50
`input data stream 101, is coupled to data pre-compres
`sents a corresponding decimal value greater than a
`sion system 202 to receive data type identification signal
`predetermined decimal value; and
`105. Data compression system 204 thus compresses
`generating a data type indicator representing a prede
`input data stream 101 in accordance with the identified
`termined data type if the at least one byte of data
`input data type. In one embodiment of this invention,
`represents a corresponding decimal value greater
`55
`data compression system 204 selects in response to