DATA PROCESSING METHOD AND APPARATUS

• US 20190312589A1
• Filed: 06/24/2019
• Published: 10/10/2019
• Est. Priority Date: 07/03/2015
• Status: Active Grant

• Current Assignee: Sisp Technologies Ltd.
• Original Assignee: Sisp Technologies Ltd.
• Inventors: MARLOW, Stuart, STAVRINOU, Nicholas
• Granted Patent: US 10,700,701 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3093 using fixed length segments
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4025 constant length to or from Morse code conversion
• CPC Class Codes: H03M 7/4081 Static prefix coding
• CPC Class Codes: H03M 7/6076 Selection between compressors of the same type

Abstract

A method of compression is disclosed in which an input sequence of bits is divided into a plurality of portions. Each portion is sub-divided into a plurality of sub-divisions. Frequency analysis is performed to determine the number of occurrences of each sub-division permutation and new values are assigned, based on the frequency analysis, to each of the sub-division permutations. For each portion a label representing the permutation of bits in that portion is assigned. The label comprises a representation of a combined value resulting from combining the new values associated with the sub-division permutations of that portion. A processed sequence of bits is generated by replacing, within the input sequence of bits, bit portions with the respective label representing the permutation of bits in that portion.

Claims

1. A method of processing data comprising an input sequence of bits, the method comprising the steps of:

(i) identifying a current processing configuration defining a current processing bit length for use in processing said input sequence of bits, wherein the current processing configuration defines a plurality of sub-divisions of each portion, each sub-division having a respective sub-division bit length, wherein a sum of said respective sub-division bit lengths equals said current processing bit length;

(ii) dividing the input sequence of bits into a plurality of portions, each portion comprising one or more sub-divisions according to the current processing configuration, wherein each portion has a respective portion bit length equal to said current processing bit length and wherein the bits in each sub-division are arranged in a respective one of a number of possible sub-division permutations;

(iii) for each of a plurality of possible sub-division permutations, analysing the input sequence of bits to respectively identify how many times, within said input sequence of bits, a portion comprises a sub-division having that possible sub-division permutation occurs;

(iv) determining whether at least one predetermined processing criterion has been achieved by comparing results of said analysing with the predetermined processing criterion;

(v) processing said input sequence of bits based on said determining wherein said processing comprises;

when the determining determines that the predetermined processing criterion has not been achieved, performing at least one of;

identifying a new processing configuration that is different to the current processing configuration and repeating steps (ii) to (v) using said new processing configuration as the current processing configuration; and

ending processing of said input sequence of bits; and

when the determining determines that the at least one predetermined processing criterion has been achieved;

assigning a respective sub-division value to each of said plurality of possible sub-division permutations; and

forming a processed sequence of bits by replacing, within said sequence of bits, bit portions comprising a sub-division having bits arranged in one of said plurality of possible sub-division permutations with a portion label based on the sub-division values assigned to that sub-division permutation.

2. A method according to claim 1, wherein the respective sub-division value assigned to each of said plurality of possible permutations is based on how many times, within said input sequence of bits, a portion comprises a sub-division having bits arranged in that possible permutation.

3. A method according to claim 2, wherein the sub-division values assigned to each of the plurality of possible permutations are assigned such that sub-division values assigned to permutations which occur less often have higher levels of statistical redundancy than the sub-division values assigned to permutations which occur more often.

4. A method according to claim 1, wherein when the determining determines that the predetermined processing criterion has not been achieved and a new processing configuration is identified, the new processing configuration is selected in a predetermined order, for example ascending order of processing bit length.

5. A method according to claim 1, wherein the input sequence of bits comprises a processing segment, and wherein the processing segment is assigned a marker which represents a distribution characteristic of the data within the processing segment, and wherein said identification of current processing configuration is based on the marker of the processing segment.

6. A method according to claim 5, wherein identification of the current processing configuration comprises using the marker of the processing segment to identify a processing configuration which has previously been used to process a different processing segment (e.g. in a different file).

7. A method according to claim 5, wherein the marker is determined based on mathematical analysis of the distribution characteristic of the data within the processing segment.

8. A method according to claim 7, wherein the marker is determined by:

dividing the input sequence of bits into a plurality of portions, where the bits in each portion are arranged in a respective one of a number of possible portion permutations;

determining the occurrence of each possible portion permutation within the input sequence of bits; and

measuring the distribution of the occurrences of the possible portion permutations.

9. A method according to claim 5, wherein the distribution characteristic comprises at least one of:

the average byte value of the data within the processing segment, the average change in byte value of the data within the processing segment, and the average change in byte value occurrence of the data within the processing segment.

10. A method according to claim 5 marker wherein the marker comprises a multi-dimensional marker.

11. A method according to claim 1, wherein the processing configuration is one of a plurality of processing configurations, each having a respective reference number, and wherein said processing configuration is identified by means of its reference number.

12. A method according to claim 1, wherein each reference number provides a binary representation of the sub-divisions defined by the corresponding processing configuration.

13. A method according to claim 1, wherein said processing configuration is identified based on Fourier analysis of the input sequence of bits.

14. A method according to claim 13, wherein said processing configuration is identified by performing Fourier analysis on the input sequence of bits and obtaining at least one Fourier coefficient;

selecting a processing bit length based on the at least one Fourier coefficient; and

identifying a processing configuration indicating the selected processing bit length.

15. A method according to claim 1, wherein said predetermined processing criterion comprises whether 50% of the possible permutations which occur in the input sequence of bits occur at least twice as frequently as the other 50% of the possible permutations which occur in the input sequence of bits.

16. A method according to claim 1, wherein said predetermined processing criterion comprises whether 50% of the possible permutations occur in the input sequence of bits.

17. A method according to claim 1, wherein said predetermined processing criterion comprises whether at least one possible permutations does not occur in the input sequence of bits.

18. A method according to claim 1, wherein said predetermined processing criterion comprises whether a measure of a distribution (e.g. a coefficient of variation) of occurrences of the possible permutations within the sequence of bits exceeds a threshold.

19. A method of processing data, the method comprising the steps of:

(i) dividing the data into a plurality of processing segments wherein each processing segment comprises an input sequence of bits;

(ii) performing a mathematical analysis of a processing segment to determine a distribution characteristic of data within the processing segment and assigning at least one marker to the processing segment based on the mathematical analysis;

(ii) identifying, based on the marker assigned to the processing segment, a current processing configuration defining a current processing bit length for use in processing a current processing segment of said data to form a processed segment meeting at least one predetermined processing criterion;

(ii) dividing the current processing segment into a plurality of portions wherein each portion has a respective portion bit length equal to said current processing bit length and wherein the bits in each portion are arranged in a respective one of a number of possible permutations;

(iv) assigning a respective label to each of a plurality of said possible permutations; and

(v) forming a processed segment by replacing, within said current processing segment, bit portions comprising bits arranged in one of said plurality of possible permutations with the respective label assigned to that one of said possible permutations.

20. A method according to claim 19, wherein the current processing configuration defines a plurality of sub-divisions of each portion, each sub-division having a respective sub-division bit length, wherein a sum of said respective sub-division bit lengths equals said current processing bit length.

21. A method of processing data, the method comprising the steps of:

(i) dividing the data into a plurality of processing segments wherein each processing segment comprises an input sequence of bits;

(ii) identifying a current processing configuration defining a current processing bit length for use in processing a current processing segment of said data to form a processed segment meeting at least one predetermined processing criterion;

(ii) dividing the current processing segment into a plurality of portions wherein each portion has a respective portion bit length equal to said current processing bit length and wherein the bits in each portion are arranged in a respective one of a number of possible permutations;

(iv) assigning a respective label to each of a plurality of said possible permutations;

(v) forming a processed segment by replacing, within said current processing segment, bit portions comprising bits arranged in one of said plurality of possible permutations with the respective label assigned to that one of said possible permutations;

(vi) identifying a new processing configuration for use in processing a next processing segment of said data to form a processed segment meeting at least one predetermined processing criterion; and

(vii) repeating, for each of said plurality of processing segments, steps (ii) to (vi) wherein the new processing configuration is used as the current processing configuration and the next processing segment of said data is used as the current processing segment, and wherein the processing configuration used for at least one of said processing segments of said data defines a different processing bit length to a processing bit length defined by a processing configuration used for at least one other of said processing segments of said data.

22. A method according to claim 21, wherein each processing segment is assigned a marker which represents characteristics of the data within the processing segment, and wherein the current processing configuration is identified based on the marker assigned to the current processing segment.

23. A method according to claim 21, wherein each processing configuration defines one of:

a plurality of sub-divisions of each portion, each sub-division having a respective sub-division bit length, wherein a sum of said respective sub-division bit lengths equals said processing bit length; and

an undivided processing portion, the bit length of which is said processing bit length.

24. A method according to claim 23, wherein the processing configuration used for at least one of said processing segments of said data defines a first plurality of sub-divisions having a first combination of sub-division bit lengths;

and the processing configuration used for at least one other of said processing segments of said data defines a second plurality of sub-divisions having a second combination of sub-division bit lengths; and

wherein said first combination of sub-division bit lengths is different to said second combination of sub-division bit lengths.

25. A method according to claim 23, wherein the processing configuration used for at least one of said processing segments of said data defines a plurality of sub-divisions having a combination of sub-division bit lengths;

and the processing configuration used for at least one other of said processing segments of said data defines an undivided processing portion.

26. A method according to claim 21, further comprising, between steps (v) and (vi), identifying a new processing configuration for use in reprocessing the processed segment and repeating steps (ii) to (v) wherein the new processing configuration is used as the current processing configuration and the processed segment of said data is used as the current processing segment.