DATA COMPRESSION METHOD AND SYSTEM THAT USE A REGRESSIVE STRING REFERENCE, POINTING TO AND DELIMITING AN ENCODED POINTEE STRING, AND IDENTIFY THE REFERENCE THROUGH A SIGNALLING ELEMENT, AN ENCODING DEVICE AND A DECODING DEVICE ARRANGED FOR IMPLEMENTING THE METHOD, AND A STORAGE MEDIUM PROVIDED WITH INFORMATION PRODUCED BY SUCH ENCODING DEVICE AND/OR ARRANGED FOR DECODING BY SUCH DECODING DEVICE

• US 6,642,860 B2
• Filed: 01/08/2002
• Issued: 11/04/2003
• Est. Priority Date: 01/11/2001
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Meulenbroeks, Franciscus Johannes Henricus Maria
• Primary Examiner(s): WAMSLEY, PATRICK G
• Application Number:
  US10/042,462
• Publication Number:
  US 20020091886A1
• Time in Patent Office: 665 Days
• Field of Search: 341/51, 341/65, 375/240, 709/247, 709/330, 709/102, 709/201, 235/431, 345/622, 365/189.01, 711/6, 717/116, 717/140, 717/149
• US Class Current: 341/51
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

Data is compressed through implementing the inserting of a regressive reference string scheme, each such reference replacing a particular data string through referring to an associated earlier data string of identical content. In particular, the regressive string reference item to an encoded object is inserted as being based on pointing and delimiting a pointee string, and identifying the reference item through an associated signalling element.

Claims

1. A method for executing compression of a data stream through systematically implementing the inserting of regressive pointer-length reference strings along such stream, each such reference indicating the replacing of a particular data string through referring to an associated earlier data string of identical content as said particular data string,

said method being characterized by the steps of:

inserting said regressive reference string as referring to an encoded object, through pointing to a pointee object, identifying said regressive reference string through a respectively associated value of a signalling element, as well as identifying unreplaced data through a respectively associated further value of a signalling element, and providing a back-reference scheme for straightforwardly backreferencing to such reference strings.

2. A method as claimed in claim 1, implemented through executing it in a sequence of two steps, wherein a first step will evaluate all back-references and indicate all pointer-line pairs and their associated pointee strings, and a second step will actually replace pointer-line pairs by their pointee strings.

3. A method as claimed in claim 1, wherein such back-reference scheme is provided through effecting such pointing on the level of single bits.

4. A method as claimed in claim 1, wherein such back-reference scheme is provided through effecting such pointing by a pointer that has a standard character length, combined with a string length indication that has a standard character length, plus a discriminatory signalling indication for effecting such pointing.

5. A method as claimed in claim 1, wherein such back-referencing scheme is provided by having such regressive reference strings alternating in sequence with standard characters, whilst suppressing discriminatory indication between such regressive reference strings and standard characters.

6. A method as claimed in claim 1, wherein such back-referencing scheme is provided through providing with a discriminatory indication discriminating between such regressive reference strings and standard characters, and by providing separate storage pointers between a first standard-length part of said regressive reference strings and of said standard characters that contains said discriminatory indication on the one hand, and any remaining part of said regressive reference strings and standard characters, on the other hand.

7. A method as claimed in claim 1, wherein said reference string has a length indication signalling the number of encoded objects.

8. A method as claimed in claim 1, wherein said reference string has a length indication signalling the number of uncoded characters.

9. A method as claimed in claim 1, wherein said reference string comprises a skip element for signalling an initial or terminal sub-length of an associated pointee string that is to be skipped when copying the remainder of that string.

10. A method as claimed in claim 1, whilst specifying the pointer in character units.

16. A storage medium provided with compressed information produced by a compression method as claimed in claim 1.

11. A compression system being arranged for executing compression of a data stream through inserting means for systematically implementing the inserting of regressive pointer-length reference strings along such stream, each such reference indicating the replacing of a particular data string through referring to an associated earlier data string of identical content as said particular data string,

said system being characterized in that:

said inserting means are arranged for inserting said regressive reference string as referring to an encoded object, through pointing to a pointee object, identifying said regressive reference string through a respectively associated value of a signalling element, as well as identifying unreplaced data through a respectively associated further value of a signalling element, and referencing means for providing a back-reference scheme for straightforwardly backreferencing to such reference strings.

12. A system as claimed in claim 11, and having sequencing means that are arranged for implementing said compression in a sequence of two steps, wherein a first step will evaluate all back-references and indicate all pointer-line pairs and their associated pointee strings, and a second step will actually replace pointer-line pairs by their pointee strings.

13. A system as claimed in claim 11, and being arranged for providing such back-referencing scheme through having providing means for providing a discriminatory indication discriminating between such regressive reference strings and standard characters, and by providing separate storage pointers between a first standard-length part of said regressive reference strings and of said standard characters that contains said discriminatory indication on the one hand, and any remaining part of said regressive reference strings and standard characters, on the other hand.

14. An encoding device arranged for use in a system as claimed in claim 11, and comprising inserting means that are arranged for inserting said regressive reference string as referring to an encoded object, through pointing to a pointee object, identifying said regressive reference string through a respectively associated value of a signalling element, as well as identifying unreplaced data through a respectively associated further value of a signalling element, and referencing means for providing a back-reference scheme for straightforwardly backreferencing to such reference strings.

15. A decoding device arranged for use in a system as claimed in claim 11, and having read means for reading said back-reference scheme, replace means for replacing pointer-length pairs through an associated pointee string, and output means for outputting a decoded data stream.