PTOISBIOS (1 1-00)
`
`.4
`
`llllllllllllllllll
`
`
`
`F‘
`"'22
`US Pt
`—>
`t
`.
`.
`ice;
`ra emar
`,
`.
`. aen an
`Under the Papenlvork Reduction Act of 1995, no persons are required to respond to a collection of information unless it displays a valid OMB control number. ml‘
`
`UTILITY
`PATENT APPLIC/mow
`
`DgID
`Attorne Docket No. 801“ CH’ CON
`as
`F,-rs: Inventor
`Content Independent Data Compression Method... 3
`Exress Mail Label No. EV329488000US
`
`
`
`
`On!
`
`for new nonrovisional a Iications under 37 CFR 1.53 b
`
`
`
`
`_ Assistant Commissioner for Patents
`Box Patent Application
`Washinton. DC 20231
`(;D-RoM cD-R ' d
`r
`t
`I
`g
`t bi
`B Computerogrograrn"-2A;:;::i:) arge a e or
`8. Nucleotide and/or Amino Acid Sequence Submission
`(ifapplicable, all necessary)
`‘
`8. D Computer Readame F077“ (CRF)
`b. Specification Sequence Listing on:
`_
`'
`L D CD'R0M 0" CD‘R (2 C0Pi9S); 0’
`i L [3 paper
`c, E Statements verifying identity of above copies
`ACCOMPANYING APPLICATION PARTS
`
`9. - Assignment Papers (cover sheet 8. document(s))
`.
`) Statement
`Power Of
`37 CFR 3 73(1)
`(when there is an assignee)
`Attorney
`10.
`11- El E"9“$h T'a“S'a“°“ D°°Ume“l {'73PPCl06P’€) “D8
`
`Information Disclosure
`‘“
`OPIGS 0
`12-
`Statement (lDS)/PTO_1449
`Citations
`
`
` 13.
`Preliminary Amendment
`Return Receipt Postcard (MPEP 503)
`14'
`(Should be specifically itemized)
`
`«slj
`
`
`15 D Request and Certification under 35 U.S.C. 122
`'
`(b)(2)(B)(i). Applicant must attach tomw PTO/SB/35
`°' ‘*5 e‘*“‘V?‘.‘?'.‘.‘.~ PTO./SB/.1..7. ............... ..
`
`
`Other:
`ForrnPTO-2038
`17.
`
`18. If a CONTINUING APPLICATlON, check appropriate box, and supply the requisite information below and in a preliminary amendment,
`or in an Application Data Sheet under 37 CFR 1.76:
`-
`_
`
`
`ncauon Ng,;___1_Q______/__Q16,35§_ ________
`.-iota
`Continuation
`Divisional
`Continuationvin-part(clP)
`
`
`Group An Unit: _~_Z_8~1__9__”___________
`Prior application information:
`Examiner_PatrtCk M. Wamsley
`
`
`For CONTlNUATlON OR DIVISIONAL APPS only: The entire disclosure of the prior application, from which an oath or declaration is supplied under
`Box 5!), is considered a part of the disclosure of the accompanying continuation or divisional application and is hereby incorporated by reference.
`
`
`The incorporation can only be relied upon when a portion has been inadvertently omitted from the submitted application parts.
`
`
`19. CORRESPONDENCE ADDRESS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPUCA-“ON ELEMENTS
`
`ADDRESS
`See MPEP chater 600 concemin utili atent a /ication contents.
`
`
`Fee Transmittal Form (e.g., PTO/SBl17)
`
`1.
`{Submitan originalundodupiimlzjbrfeepracessing)
`2
`’°‘pp"°a”‘ °'a“'“5 sma" e"t‘tY 5ta‘“3'
`see 37 CFR 127-
`'
`;
`s
`‘r
`ti
`T t 1 P
`3. ' (prgzgeixffngrgemsnt set forth bglo?/)a
`ages
`‘ D95C”P“Ve ‘"39 0f the i”Ve““°”
`- Cross Reference to Related Applications
`- Statement Regarding Fed sponsored R & D
`- Reference to sequence listing, a table,
`or a computer program listing appendix
`- Background of the Invention
`- Brief Summary of the Invention
`- Brief Description of the Drawings (if filed)
`- Detailed Description
`,
`' C'a"”(5)
`- Abstract of the Disclosure
`{ Total Sheets
`Drawing(s) (35 use. 113)
`4,
`[ Total Pages
`5. Oath or Declaration
`a. [3 Newly executed (original orcopy)
`Copy from a prior application (37 CFR 1.63 (d))
`b.
`(for continuation/divisional with Box 18 completed)
`a. D DELETlON or= lNVENTOR(S)
`Signed statement attached deleting inventor(s)
`named in the prior application, see 37 CFR
`1.63(d)(2) and 1.33(b).
`
`7,
`
`-
`45
`
`I
`
`5
`
`
`
`
`
`
`
`
`
`
`1
`]
`
`
`
`
`
`6. D Application Data Sheet. See 37 CFR 1.75
`
`
`
`
`
`F
`
`of
`
`OD
`
`
`
`
`
`E CustomerNumberorBar Code Label
`
`1 wise“CuswmerM’ WMach bycode label hem}
`
`0!
`
`Correspondence address below
`
`Name
`
`Frank Chau
`
`Addmss
`
`F. CHAU & ASSOCIATES, LLP
`
`1900 Hempstcad Turnpike, Suite 501
`East Meadow
`
`New York
`
`Zip Code 1 1554
`
`
`Registration No. (Artorney/Agent) 43534
`Flank Vv DCROS3
`Name Print/T pe)
`/
`
` ' Sept 2% 2003
`
`ORACLE 1034
`
`

`
`PTOISBI17 (01-03)
`Approved for use through 04/30/2003. OMB 0651-0032
`u.s. Patent and Trademark once; u.s. DEPARTMENT OF COMMERCE
`- c - rsons are reui d to resend to a collection of information unless it disla
`a valid OMB control number.
`
`Complete if Known
`
`A lication Number
`
`
`
`
`
`for FY 2003
`Effective 01/01/2003. Patent fees are subject to annual revision.
`.
`
`Applicant claims small entity status. See 37 CFR 1.27
`
`' ($) 375.00
`
`
`
`
`' Attome Docket No.
`
`ningoaie E
`First Named inventor
`JamesJ Fallon
`Patrick M. Wamsley
`2819
`8011-1 ClP CON
`
`
`‘
`
`METHOD OF PAYMENT (check all that apply)
`
`FEE CALCULATION (continued)
`
`Credit card D lé1:>dneery
`Check
`E Deposit Account:
`A
`t
`Nf,°,§{,’;',
`.
`Deposit
`1-‘. Chau 8. Associates, LLP
`Amun,
`Name
`The Commissioner is authorized to: (check all that appty)
`Charge fee(s) indicated below D Credit any overpayments
`Dcharge any additional fee(s) during the pendency of this application
`Dcharge feels) indicated below. except for the filing fee
`to the above-identified deposit account.
`FEE CALCULATION
`1. BASIC FILING FEE
`Large Entity Small Entity
`
`1-955-0
`
`Fee Paid
`
`1051
`
`130
`
`2051
`
`1251
`1252
`
`110
`410
`
`2251
`2252
`
`930
`1253
`1254 1.450
`
`2253
`2254
`
`65 Surcharge-late filing fee or oath
`f
`S
`h
`_] t
`'
`*
`f’
`25 cg;g;';;§;e, aeP'°V'S'°"a‘ “ms 99°’
`2°52
`5°
`1052
`130 Non-English specification
`1053
`130
`1053
`_
`g
`1812 2.520 1812 2,520 For filing a request for ex parte reexamination
`_
`_
`_
`_
`920 gcfigglcatlon of SIR mm ‘D
`1804
`920
`1804
`1805 1,840‘ 1305 1,s4o* Requesting publication of SIR after
`EX3""'"e" 3°“°"
`55 Extension for reply within first month
`205 Extension for reply within second in
`°“
`465 Extension for reply within third month
`725 Extension for reply within fourth month
`
`th
`
`9
`
`1801
`1802
`
`2801
`1802
`
`900
`
`42 " Reissue independent claims
`examined (37 CFR 1'129(b))
`over original patent
`375 Request for Continued Examination (RCE)
`" Reissue claims in excess of 20
`900 Request for expedited examination
`and over original patent
`of a design application
`SUBTOTAL (2) — ‘Reduced by Basic Filing Fee Paid
` Other fee (specify)
`' reater; For Reissues, see above
`
`SUBMl‘l'l'ED BY
`
`’*’’‘’‘’> 43534
`
`SUBTOTAL (3)
`(Complete (if applicable)
`Telephone 516-357-0091
`Frank V. DeRosa
`September 22. 2003
`-_.1
`WARNING: lnfonnation on this form may become public. Credit card information should not
`be included on this fonn. Pr vide credit card information and authorization on PTO-2038.
`This collection of information is required by 37 CFR 1.17 and 1.27. The information is required to obtain or retain a benefit by the public which is to file (and by the
`USPTO to process) an application. Confidentiality is governed by 35 U.S.C. 122 and 37 CFR 1.14. This collection is estimated to take 12 minutes to complete,
`including gathering, preparing, and submitting the completed application form to the USPTO. Time will vary depending upon the individual case. Any comments on
`the amount of time you require to complete this form andlor suggestions for reducing this burden. should be sent to the Chief information Officer. U.$. Patent and
`Trademark Office. U.S. Department of Commerce. Washington, DC 20231. 00 NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS. SEND TO:
`Commissioner for Patents, Washington, DC 20231.
`If you need assistance in completing the form. Cali 1~800—PTO—9199 (1-800-786-9199) and select option 2.
`
`375
`2001
`2002 165
`2003 250
`2004 375
`2005
`go
`
`375 O0
`
`Ufimyfinngfee
`Design filing fee
`Plant ming fee
`Reissue filing fee
`pmvisgonai filing fee
`SUBTOTAL (1)
`($ 375 00
`
`1255 1,970
`1401
`320
`1402
`320
`1403
`280
`1451 1,510
`1452
`110
`1453 1,300
`Fee from
`2' EXTRA CLAIM FEES FOR UTILITY AND REISSUE 1501 1 300
`5
`.. ..
`Fee Paid
`Extra Cl
`lm
`1502
`470
`ITn"d“"C::j"“‘°'t
`-20" =
`X E] 1503
`630
`.. _
`e e
`Clairgis
`‘ 3
`‘ E XE = 1460
`130
`Mume D°"e"d°”t
`E 1807
`so
`1806
`180
`
`2255
`2401
`2402
`2403
`1451
`2452
`2453
`2501
`2502
`2503
`1460
`1307
`1806
`
`_
`
`985 Extension for replywithiri fifth month
`160 Notice of Appeal
`160 Filing a brief in support of an appeal
`140 Re*1UeS”°t Oral healing
`1,510 Petition to institute a public use proceeding
`55 Petition to revive — unavoidable
`650 Petition to revive - unintentional
`650 Utilityissueifee (or reissue)
`235 Design issue fee
`315 Plant issue fee
`130 Petitions to the Commissioner
`so Processing fee under 37 CFR 1 17(q)
`180 Submission of information Disclosure Stmt
`
`Fee Description
`
`8021
`
`40
`
`8021
`
`9 Claims in excess of 20
`_
`V
`42
`independent claims in excess of 3
`140 Multiple derzendentclaimfifnotpaid
`
`1809
`
`1810
`
`2809
`
`2810
`
`40 Recording each patent assignment per
`property (times number of properties)
`375 Filing a submission after final rejection
`(37 CFR 1429(3))
`375 Foreach additionalinvention to be
`
`en
`
`1203 280
`
`1204
`
`34
`
`15
`
`

`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`Atty. Docket No. 8011-1 CIP CON
`
`Commissioner for Patents
`P.O. Box 1450
`
`Alexandria, VA 22313-1450
`
`UTILITY APPLICATION FEE TRANSMITTAL
`
`Transmitted herewith for filing is the patent application of
`
`lnventor(s): James J . Fallon
`
`For:
`
`CONTENT INDEPENDENT DATA COMPRESSION METHOD AND
`SYSTEM
`
`This application is a:
`
`b
`[X] Continuation;
`I ] Continuation—ln-Part (CIP); or
`[ ] Divisional
`
`
`of co-pending U.S. application Serial No. 10/016 355 , filed on October 29 2001 .
`
`Enclosed are:
`
`[X] __3_§_
`
`page(s) of specification
`
`[X]
`
`page(s) of Abstract
`
`[X] _§__
`
`page(s) of claims
`
`[X] __3A_
`
`sheets of drawings [X] formal
`
`[] informal
`
`[X]
`
`2
`
`page(s) of previously executed Declaration and Power of Attorney
`
`[ ] An Assignment of the invention to
`
`
`CERTIFICATION UNDER 37 C.F.R. § 1.10
`
`I hereby certify that this Application Transmittal and the documents referred to as enclosed therein are being deposited with the United States
`Postal Service on this date September 22 2003 in an envelope as "Express Mail Post Office to Addressee" Mail Label Number EV329488000US
`addressed to: Commissioner of Patents, P.O. Box 1450, Alexandria. VA 22313-1450.
` _Frank V4 DeRosa
`
`

`
`[]
`
`This application claims the benefit under 35 U.S.C.
`§1-19(e) of U.S. Provisional Application(s) No(s).:
`
`APPLICATION NO(S).:
`
`FILING DATE
`
`I I
`
`[1 Certified copy of applications
`
`County
`
`Appln. No.
`
`File
`
`from which priority under Title 35 United States Code, § 119 is claimed
`[] is enclosed.
`
`[] will follow.
`
`CALCULATION OF UTILITY APPLICATION FEE
`
`— romsmoo
`
`INDEPENDENT
`CLAIMS
`
`[X] Small Entity Status Under 37 C.F.R. § 1.27 is claimed. Reduced fees under 37
`C.F.R. § 1.9(f) (50% of total) paid herewith §375.00.
`
`‘includes all independent and single dependent claims and all claims referred to in multiple claims. See 37 C.F.R. § 1.75(c).
`
`

`
`Relate Back - 35 U.S.C. § 120
`
`[] Amend the specification by inserting before the first
`line the sentence:
`
`"This is a [] continuation [ ] continuation-in—part
`[] divisional of copending application Serial No.
`
`filed
`
`,
`
`[X] The amount of §375.00 (filing fee) is authorized to be charged to a Credit Card.
`Form PTO-2038 is enclosed.
`
`Check in the amount of §
`attached.
`
`to cover the [X] recording, [X] filing fee(s) are
`
`A Charge fee to Deposit Account No. 04-1121. Order No.
`TWO (2) COPlES OF THIS SHEET ARE ENCLOSED.
`
`[X]
`
`Please charge any deficiency as well as any other fee(s) which may become due
`under 37 C.F.R. § 1.16 and 1.17, at any time during the pendency of this
`application, or credit any overpayment of such fee(s) to Deposit Account No. 50;
`0_§_Z_Q. Also, in the event any extensions of time for responding are required for the
`pending application(s), please treat this paper as a petition to extend the time as
`required and charge Deposit Account No. 50-0679 therefor. TWO (2) COPlES OF
`THlS SHEET ARE ENCLOSED.
`
`Date: September 22, 2003
`
`F. CHAU & ASSOCIATES, LLP
`Suite 501
`
`1900 Hempstead Turnpike
`East Meadow, New York 11554
`Tel. No. (516) 357-0091
`Fax.
`(516) 357-0092
`
`Frank V. DeRosa
`
`Reg. No. 43,584
`
`

`
`CONTENT INDEPENDENT DATA COMPRESSION METHOD AND SYSTEM_
`
`CROSS-REFERENCE TO RELATED APPLICATIONS
`
`This application is a Continuation-In-Part of U.S. Patent Application Serial No.
`
`09/705,446, filed on November 3, 2000, which is a Continuation of U.S. Patent
`
`Application Serial No. 09/210,491, filed on December 11, 1998, which is now U.S.
`
`Patent No. 6,195, 024, issued on February 27, 2001.
`
`10
`
`1. Technical Field:
`
`BACKGROUND
`
`The present invention relates generally to a data compression and decompression
`
`and, more particularly, to systems and methods for data compression using content
`
`independent and content dependent data compression and decompression.
`
`15
`
`2. Description of Related Art:
`
`Information may be represented in a variety of manners. Discrete information
`
`such as text and numbers are easily represented in digital data. This type of data
`
`representation is known as symbolic digital data. Symbolic digital data is thus an
`
`absolute representation of data such as a letter, figure, character, mark, machine code, or
`
`20
`
`drawing,
`
`Continuous information such as speech, music, audio, images and video,
`
`frequently exists in the natural world as analog information. As is well known to those
`
`skilled in the art, recent advances in very large scale integration (VLSI) digital computer
`
`technology have enabled both discrete and analog information to be represented with
`
`'25
`
`digital data. Continuous information represented as digital data is often referred to as
`
`diffuse data. Diffuse digital data is thus a representation of data that is of low
`
`information density and is typically not easily recognizable to humans in its native form.
`
`There are many advantages associated with digital data representation. For
`
`instance, digital data is more readily processed, stored, and transmitted due to its
`
`30
`
`inherently high noise immunity. In addition, the inclusion of redundancy in digital data
`
`representation enables error detection and/or correction. Error detection and/or
`
`1
`
`8011-ICIP
`
`

`
`correction capabilities are dependent upon the amount and type of data redundancy,
`
`available error detection and correction processing, and extent of data corruption.
`One outcome of digital data representation is the continuing need for increased
`
`capacity in data processing, storage, and transmittal. This is especially true for diffuse
`data where increases in fidelity and resolution create exponentially greater quantities of
`
`data. Data compression is widely used to reduce the amount of data required to process,
`
`transmit, or store a given quantity of infonnation. In general, there_ are two types of data
`
`compression techniques that may be utilized either separately or jointly to encode/decode
`
`data:
`
`lossless and lossy data compression.
`
`Lossy data compression techniques provide for an inexact representation of the
`
`original uncompressed data such that the decoded (or reconstructed) data differs from the
`
`original unencoded/uncompressed data. Lossy data compression is also known as
`
`irreversible or noisy compression. Entropy is defined as the quantity of information in a
`
`given set of data. Thus, one obvious advantage of lossy data compression is that the
`
`compression ratios can be larger than the entropy limit, all at the expense of infonnation
`
`content. Many lossy data compression techniques seek to exploit various traits within the
`
`human senses to eliminate otherwise imperceptible data. For example, lossy data
`
`compression of visual imagery might seek to delete information content in excess of the
`
`display resolution or contrast ratio.
`
`On the other hand, lossless data compression techniques provide an exact
`
`representation of the original uncompresseddata. Simply stated, the decoded (or
`
`reconstructed) data is identical to the original unencoded/uncompressed data. Lossless
`
`data compression is also known as reversible or noiseless compression. Thus, lossless
`
`data compression has, asuits current limit, a minimum representation defined by the
`
`10
`
`15
`
`20
`
`:5
`
`entropy of a given data set.
`
`There are various problems associated with the use of lossless compression
`
`techniques. One fundamental problem encountered with most lossless data compression
`
`techniques are their content sensitive behavior. This is often referred to as data
`
`dependency. Data dependency implies that the compression ratio achieved is highly
`
`30
`
`contingent upon the content of the data being compressed. For example, database files
`
`often have large unused fields and high data redundancies, offering the opportunity to
`
`losslessly compress data at ratios of_5 to l or more. In contrast, concise software
`
`2
`
`8011-ICIP
`
`

`
`‘'.r
`
`programs have little to no data redundancy and, typically, willnot losslessly compress
`better than 2 to 1.
`
`Another problem with lossless compression is that there are significant variations
`
`in the compression ratio obtained when using a single lossless data compression
`technique for data streams having different data content and data size. This process is
`known as natural variation.
`
`A further problem is that negativeflcompression may occur when certain data
`
`compression techniques act upon many types of highly compressed data. Highly
`
`compressed data appears random and many data compression techniques will
`
`substantially expand, not compress this type of data.
`
`For a given application, there are many factors that govern the applicability of
`
`various data compression techniques. These factors include compression ratio, encoding
`
`and decoding processing requirements, encoding and decoding time delays, compatibility
`
`with existing standards, and implementation complexity and cost, along with the
`
`adaptability and robustness to variations in input data. A direct relationship exists in the
`
`current art between compression ratio and the amount and complexity of processing
`
`required. One of the limiting factors in most existing prior art lossless data compression
`
`techniques is the rate at which the encoding and decoding processes are performed.
`
`Hardware and software implementation tradeoffs are often dictated by encoder and
`
`decoder complexity along with cost.
`
`Another problem associated with lossless compression methods is determining the
`
`optimal compression technique for a given set of input data and intended application. To
`
`combat this problem, there are many conventional content dependent techniques that may
`
`be utilized. For instance, file type descriptors are typically appended to file names to
`
`describe the application programs that normally act upon the data contained within the
`
`file. In this manner data types, data structures, and formats within a given file may be
`
`ascertained. Fundamental limitations with this content dependent technique include:
`
`(1)
`
`the extremely large number of application programs, some of which do not
`
`possess published or documented file formats, data structures, or data type descriptors;
`
`(2)
`
`the ability for any data compression supplier or consortium to acquire,
`
`store, and access the vast amounts of data required to identify known file descriptors and
`
`associated data types, data structures, and formats; and
`
`3
`
`8011-ICIP
`
`10
`
`15
`
`20
`
`:25
`
`30
`
`

`
`(3)
`the rate at which new application programs are developed and the need to
`update file format data descriptions accordingly.
`An alternative technique that approaches the problem of selecting an appropriate
`
`lossless data compression technique is disclosed, for example, in U.S. Patent No.
`
`5,467,087 to Chu entitled "High Speed Lossless Data Compression System" ("Chu").
`
`FIG. 1 illustrates an embodiment of this data compression and decompression technique.
`Data compression
`comprises two phases, a data pre—compression phase 2 and a data
`compression phase 3. Data decompression 4 of a compressed input data stream is also
`
`comprised of two phases, a data type retrieval phase 5 and a data decompression phased.
`
`During the data compression process 1, the data pre-compressor 2 accepts an
`
`uncompressed data stream, identifies the data type of the input stream, and generates a
`
`data type identification signal. The data compressor 3 selects a data compression method
`from a preselected set of methods to compress the input data stream, with the intention of
`
`producing the best available compression ratio for that particular data type.
`
`There are several limitations associated with the Chu method. One such
`
`limitation is the need to unambiguously identify various data types. While these might
`
`include such common data types as ASCII, binary, or unicode, there, in fact, exists a
`
`broad universe of data types that fall outside the three most common data types.
`
`Examples of these alternate data types include: signed and unsigned integers of various
`
`~.
`
`lengths, differing types and precision of floating point numbers, pointers, other forms of
`
`character text, and a multitude of user defined data types, Additionally, data types may
`
`be interspersed or partially compressed, making data type recognition difficult and/or
`
`impractical. Another limitation is that given a known data type, or mix of data types
`
`within a specific set or subset of input data, it may be difficult and/or impractical to
`
`10
`
`15
`
`20
`
`25
`
`predict which data encoding technique yields the highest compression ratio.
`
`Accordingly, there is a need for a data compression system and method that
`
`would address limitations in conventional data compression techniques as described
`
`above.
`
`SUMMARY OF THE INVENTION
`
`30
`
`The present invention is directed to systems and methods for providing fast and
`
`efficient data compression using a combination of content independent data compression
`
`and content dependent data compression. In one aspect of the invention, a method for
`
`4
`
`8011-ICIP
`
`

`
`10
`
`compressing data comprises the steps of:
`
`analyzing a data block of an input data stream to identify a data type of the data .
`
`block, the input data stream comprising a plurality of disparate data types;
`
`performing content dependent data compression on the data block, if the data type
`
`ofthe data block is identified;
`
`performing content independent data compression on the data block, if the data
`
`type of the data block is not identified.
`
`In another aspect, the step of performing content independent data compression
`
`comprises: encoding the data block with a plurality of encoders to provide a plurality of '
`
`encoded data blocks; determining a compression ratio obtained for each of the encoders;
`
`comparing each of the determined compression ratios with a first compression threshold;
`
`selecting for output the input data block and appending a null compression descriptor to
`
`the input data block, if all of the encoder compression ratios do not meet the first
`
`compression threshold; and selecting for output the encoded data block having the
`
`highest compression ratio and appending a corresponding compression type descriptor to
`
`the selected encoded data block, if at least one of the compression ratios meet the first
`
`compression threshold.
`
`In another aspect, the step of performing content dependent compression
`
`comprises the steps of: selecting one or more encoders associated with the identified data‘ ._
`
`type and encoding the data block with the selected encoders to provide a plurality of
`
`encoded data blocks; determining a compression ratio obtained for each of the selected
`
`encoders; comparing each of the determined compression ratios with a second
`
`compression threshold; selecting for output the input data block and appending a null
`
`10
`
`15
`
`20
`
`compression descriptor to the input data block, if all of the encoder compression do not
`
`25
`
`meet the second compression threshold; and selecting for output the encoded data block
`
`having the highest compression ratio and appending a corresponding compression type
`
`descriptor to the selected encoded data block, if at least one of the compression ratios
`
`meet the second compression threshold.
`
`In yet another aspect, the step of performing content independent data
`
`30
`
`compression on the data block, if the data type of the data block is not identified,
`
`comprises the steps of: estimating a desirability of using of one or more encoder types
`
`based one characteristics of the data block; and compressing the data block using one or
`
`5
`
`8011-ICIP
`
`

`
`ll
`
`more desirable encoders.
`
`In another aspect, the step of performing content dependent data compression on
`the data block, if the data type of the data block is identified, comprises the steps of:
`
`estimating a desirability of using of one or more encoder types based on characteristics of
`the data block; and compressing the data block using one or more desirable encoders.
`
`In another aspect, the step of analyzing the data block comprises analyzing the
`
`data block to recognize one of a data type, data structure, data block format, file
`
`substructure, and/or file types. A further step comprises maintaining an association
`between encoder types and data types, data structures, data block formats, file
`‘
`
`substructure, and/or file types.
`
`In yet another aspect of the invention, a method for compressing data comprises
`
`the steps of:
`
`analyzing a data block of an input data stream to identify a data type of the data
`
`block, the input data stream comprising a plurality of disparate data types;
`performing content dependent data compression on the data block, if the data type
`of the data block is identified;
`4
`
`determining a compression ratio of the compressed data block obtained using the
`
`content dependent compression and comparing the compression ratio with a first
`
`compression threshold; and
`
`performing content independent data compression on the data block, if the data
`
`type of the data block is not identified or if the compression ratio of the compressed data
`
`block obtained using thecontent dependent compression does not meet the first
`
`compression threshold.
`
`10
`
`15
`
`20
`
`Advantageously, the present invention employs a plurality of encoders applying a
`
`2'5
`
`plurality of compression techniques on an input data stream so as to achieve maximum
`
`compression in accordance with the real-time or pseudo real—time data rate constraint.
`
`Thus, the output bit rate is not fixed and the amount, if any, of permissible data quality
`
`degradation is user or data specified.
`These and other aspects, features and advantages of the present invention will
`
`30
`
`become apparent from the following detailed description of preferred embodiments,
`
`which is to be read in connection with the accompanying drawings.
`
`6
`
`,
`
`8011-ICIP
`
`

`
`12
`
`V
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block/flow diagram of a content dependent high-speed lossless data _
`compression and decompression system/method according to the prior art;
`.
`
`FIG. 2 is a block diagram of a content independent data compression system
`
`according to one embodiment of the present invention;
`
`FIGS. 3a and 3b comprise a flow diagram of a data compression method
`
`according to one aspect of the present invention, which illustrates the operation of the
`
`data compression system of FIG. 2;
`
`FIG. 4 is a block diagram of a content independent data compression system >
`
`10_
`
`according to another embodiment of the present invention having an enhanced metric for
`
`selecting an optimal encoding technique;
`
`FIGS. 5a and 5b comprise a flow diagram of a data compression method
`
`according to another aspect of the present invention, which illustrates the operation of the
`
`15
`
`20
`
`as
`
`30
`
`data compression system of FIG. 4;
`
`FIG. 6 is a block diagram of a content independent data compression system
`
`according to another embodiment of the present invention having an a priori specified
`
`timer that provides real—time or pseudo rea1—time of output data;
`
`FIGS. 7a and 7b comprise a flow diagram of a data compression method
`
`according to another aspect of the present invention, which illustrates the operation of the V
`
`data compression system of FIG. 6;
`
`FIG. 8 is a block diagram of a content independent data compression system
`
`according to another embodiment having an a priori specified timer that provides real_-
`
`time or pseudo real—time of output data and an enhanced metric for selecting an optimal
`
`encoding technique;
`
`FIG. 9 is a block diagram of a content independent data compression system
`
`according to another embodiment of the present invention having an encoding
`
`architecture comprising a plurality of sets of serially cascaded encoders;
`
`FIGs. 10a and 10b comprise a flow diagram of a data compression method
`
`according to another aspect of the present invention, which illustrates the operation of the
`
`data compression system of FIG. 9;
`
`FIG. I1 is block diagram of a content independent data decompression system
`
`according to one embodiment of the present invention;
`
`7
`
`'
`
`8011-ICIP
`
`

`
`13
`
`FIG. 12 is a flow diagram of a data decompression method according to one
`aspect ofthe present invention, which illustrates the operation of the data compression _
`system of FIG. 11;
`4
`
`FIGS. Ba and 13b comprise a block diagram of a data compression system
`
`comprising content dependent and content independent data compression, according to an
`
`_ embodiment of the present invention;
`
`FIGs. l4a-14d comprise a flow diagram of a data compression method using both
`
`content dependent and content independent data compression, according to one aspect of
`
`b the present invention;
`
`10
`
`FIGS. 15a and 15b comprise a block diagram of a data compression system
`
`comprising content dependent and content independent data compression, according to
`
`another embodiment of the present invention;
`
`FIGS. 16a—16d comprise a flow diagram of a data compression method using both
`
`content dependent and content independent data compression, according to another
`‘aspect of the present invention;
`
`15
`
`FIGs. 17a and 17b comprise a block diagram of a data compression system
`comprising content dependent and content independent data compression, according to
`
`another embodiment of the present invention; and
`
`FIGS. 18a-18d comprise a flow diagram of a data compression method using both
`
`20
`
`content dependent and content independent data compression, according to another
`
`aspect of the present invention.
`
`DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
`
`The present invention is directed to systems and methods for providing data
`
`as
`
`compression and decompression using content independent and content dependent data
`
`compression and decompression. In the following description, it is to be understood that
`
`system elements having equivalent or similar functionality are designated with the same
`
`reference numerals in the Figures.
`
`It is to be further understood that the present invention
`
`may be implemented in various forms of hardware, software, firmware, or a combination
`
`30
`
`thereof. In particular, the system modules described herein are preferably implemented
`
`in sofiware as an application program that is executable by, e.g., a general purpose
`
`computer or any machine or device having any suitable and preferred microprocessor
`
`8'
`
`i
`
`"
`
`8011-ICITP
`
`

`
`14
`
`architecture. Preferably, the present invention is implemented on a computer platform
`including hardware such as one or more central processing units (CPU), a random access
`memory (RAM), and input/output (I/O) interface(s). The computer platform also
`
`includes an operating system and microinstruction code. The various processes and
`
`functions described herein may be either part of the microinstruction code or application
`
`programs which are executed via the operating system. In addition, various other
`
`peripheral devices may be connected to the computer platfomi such as an additional data
`
`storage device and a printing device.
`
`It is to be further understood that, because some of the constituent system
`
`components described herein are preferably implemented as software modules, the actual
`
`system connections shown in the Figures may differ depending upon the manner in which
`
`the systems are programmed.
`
`It is to be appreciated that special purpose microprocessors
`
`may be employed to implement the present invention. Given the teachings herein, one of
`
`ordinary skill in the related art will be able to contemplate these and similar
`
`implementations or configurations of the present invention.
`
`Referring now to FIG. 2 a block diagram illustrates a content independent data
`
`compression system according to one embodiment of the present invention. The data
`
`compression system includes a counter module 10 that receives as input an uncompressed
`
`or compressed data stream.
`
`It is to be understood that the system processes the input data .
`
`stream in data blocks that may range in size from individual bits through complete files
`
`or collections of multiple files. Additionally, the data block size may be fixed or
`
`variable. The counter module l0 counts the size of each input data block (i.e., the data
`block size is counted in bits, bytes, words, any convenient data multiple or metric, or any
`
`combina