Parsing information onto packets using context-insensitive parsing rules based on packet characteristics

• US 5,414,650 A
• Filed: 03/24/1993
• Issued: 05/09/1995
• Est. Priority Date: 03/24/1993
• Status: Expired due to Term

• Current Assignee: Compression Technology Solutions LLC (Acacia Research Corporation)
• Original Assignee: Compression Research group Inc.
• Inventors: Hekhuis, Peter J.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): PAYNE, MATTHEW
• Application Number:
  US08/035,438
• Time in Patent Office: 776 Days
• Field of Search: 341/51, 395/700
• US Class Current: 708/203
• 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/3088 employing the use of a dictionary, e.g. LZ78

Abstract

Extremely localized parse rules, dependent only upon either intrinsic characteristics of each packet or upon transitions in characteristics between consecutive pairs or triples of packets, give a determinable fragmentation of an information stream which is relatively insensitive to imbedded error, insertion or deletion. Iterative application of such parsing on the stream of parsed fragments produces a corresponding hierarchy of levels of fragments of increasing length. The highest level fragments are matched to a dictionary or history, tokenized and presented for output to form a compressed data stream.

Claims

1. An information processor for processing an information stream comprising input packets, said information processor comprising

input means for receiving said information stream and for receiving an indication of the boundaries in said information stream for each of said input packets,

classification means for classifying said input packets according to intrinsic characteristics of said input packets,

parsing means responsive to said classification means for parsing said input packets into output packets and for generating an indication of the boundaries of said output packets, wherein each of said output packets comprises or represents one or more of said input packets, and

means for reiteratively classifying and parsing packets previously classified and parsed to generate further output packets comprising or representing one or more of said packets previously classified and parsed.

3. An information processor according to claim 1 or 2 wherein said parsing means generates an output stream comprising input packets parsed by said parsing means and said indication of the boundaries of said input packets.

5. An information processor according to claim 1 or 2 wherein said classification means comprises means for classifying said input packets according to a modification of said characteristics to reduce the correlation of packet classification occurrences.

6. An information processor according to claim 1 or 2, wherein said parsing means establishes said boundaries of said output packets in response to local maxima or local minima of a quantitative characteristic of packets in said information stream.

7. An information processor according to claim 6, wherein said parsing means establishes said boundaries of said output packets in response to local minima alternating with local maxima of said quantitative characteristic.

8. An information processor according to claim 6, wherein said parsing means establishes said boundaries of said output packets in response to only one of either local minima or local maxima of said quantitative characteristic.

2. An information processor for processing an information stream comprising input packets, said information processor comprising

input means for receiving said information stream and for receiving an indication of the boundaries in said information stream for each of said input packets,

classification means for classifying said input packets according to transitions in quantitative characteristics of two or more of said input packets, and

parsing means responsive to said classification means for parsing said input packets into output packets and for generating an indication of the boundaries of said output packets, wherein each of said output packets comprises or represents one or more of said input packets.

4. An information processor according to claim 2 further comprising means for reiteratively classifying and parsing packets previously classified and parsed to generate further output packets comprising or representing one or more of said packets previously classified and parsed.

9. An information processing method for processing an information stream comprising input packets, said method comprising

receiving said information stream and receiving an indication of the boundaries in said information strum for each of said input packets,

classifying said input packets according to intrinsic characteristics of said input packets or transitions in quantitative characteristics of two or more of said input packets, and

parsing said input packets into output packets in response to said classifying, and generating an indication of the boundaries of said output packets, wherein each of said output packets comprises or represents one or more of said input packets.

10. An information processing method according to claim 9 wherein said parsing generates an output stream comprising input packets parsed by said parsing and said indication of the boundaries of said input packets.

11. An information processing method for processing an information stream comprising input packets, said method comprising

receiving said information stream and receiving an indication of the boundaries in said information stream for each of said input packets, wherein each of said input packets comprises or represents one or more previously parsed packets, said previously parsed packets having been parsed according to one or more intrinsic characteristics of said previously parsed packets,

classifying said input packets according to intrinsic characteristics of said input packets, and

parsing said input packets into output packets in response to said classifying and generating an indication of the boundaries of said output packets, wherein each output packet comprises or represents one or more of said input packets.

12. An information processing method according to claim 9 or 11 further comprising reiteratively classifying and parsing said output packets to generate further output packets comprising or representing one or more packets previously classified and parsed.

13. An information processing method according to claim 9 or 11 wherein said classifying classifies said input packets according to a modification of said characteristics to reduce the correlation of packet classification occurrences.

14. An information processing method according to claim 9 or 11, wherein said parsing establishes said boundaries of said output packets in response to local maxima or local minima of a quantitative characteristic of packets in said information stream.

15. An information processing method according to claim 14, wherein said parsing establishes said boundaries of said output packets in response to local minima alternating with local maxima of said quantitative characteristic.

16. An information processing method according to claim 14, wherein said parsing establishes said boundaries of said output packets in response to only one of either local minima or local maxima of said quantitative characteristic.

17. An information processor for processing an information stream comprising a sequence of input packets, said information processor comprising

classification means for classifying said input packets into two or more classifications, and

parsing means for establishing the start of an output packet in said information stream by establishing an output boundary between two input packets, wherein said parsing means establishes said output boundary in response to classifications of a limited number of input packets in said sequence preceding said output boundary.

18. An information processor according to claim 17 wherein said classification means classifies an input packet according to either an intrinsic characteristic of said input packet or transitions in quantitative characteristics of two or more packets in said sequence of input packets.

19. An information processor according to claim 17 wherein said limited number of input packets is equal to two.

20. An information processor according to claim 17 or 18 wherein said parsing means is responsive to classifications of input packets preceding said output boundary by more than said limited number of input packets for input streams in which said input packets are established according to a criterion other than packet classification according to either intrinsic characteristics of said input packets or transitions in quantitative characteristics of two or more of said input packets.