US 2018/0191372 A1Published application

Data processing method and apparatus

AssigneeSISP Technologies Ltd.

InventorsStuart MARLOW, Nicholas STAVRINOU

Life of this patent

Estimating the term…

Loading patent…

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.

Claims50

Dependent claims

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

(i) identifying a processing bit length for use in processing said input sequence of bits;
(ii) dividing the input sequence of bits into a plurality of portions wherein each portion has a respective portion bit length equal to said processing bit length and wherein the bits in each portion are arranged in a respective portion permutation;
(iii) respectively sub-dividing each portion into a plurality of sub-divisions comprising at least a first sub-division and a second sub-division, wherein each sub-division of the plurality of sub-divisions comprises at least one bit, wherein the at least one bit of each first sub-division is arranged in a respective first sub-division permutation, and wherein the at least one bit of each second sub-division is arranged in a respective second sub-division permutation;
(iv) performing frequency analysis:
to determine, for each of a plurality of possible first sub-division permutations, how many times, within said input sequence of bits, a portion comprises a first sub-division having bits arranged in that possible first sub-division permutation;
and
to determine, for each of a plurality of possible second sub-division permutations, how many times, within said input sequence of bits, a portion comprises a second sub-division having bits arranged in that possible second sub-division permutation;
(v) assigning a respective sub-division value to each of said plurality of possible first sub-division permutations based on how many times, within said input sequence of bits, a portion comprises a first sub-division having bits arranged in that possible first sub-division permutation;
and assigning a respective sub-division value to each of said plurality of possible second sub-division permutations based on how many times, within said input sequence of bits, a portion comprises a second sub-division having bits arranged in that possible second sub-division permutation;
(vi) for each portion permutation of a plurality of possible portion permutations, generating a respective label representing that portion permutation, wherein said generating comprises combining:
the sub-division value assigned to the first sub-division permutation corresponding to the first sub-division of that portion permutation;
with
the sub-division value assigned to the second sub-division permutation corresponding to the second sub-division of that portion permutation;
wherein said respective label comprises a representation of a combined value resulting from said combining;
and
(vii) forming a processed sequence of bits by replacing, within said input sequence of bits, bit portions comprising bits arranged in one of said plurality of possible portion permutations, with the respective label representing that one of said plurality of possible portion permutations.

13 more elements

A method according to any preceding claim, wherein when generating, for each portion permutation, a respective label representing that portion permutation, said generating further comprises:

when a first particular sub-division value is assigned for a plurality of different first sub-division permutations:
generating, for each of said respective plurality of different first sub-division permutations having that first particular sub-division value, a different respective first additional value for use in discriminating between said respective plurality of first sub-division permutations having that first particular sub-division value;
and
when a second particular sub-division value is to be assigned for a plurality of different second sub-division permutations:
generating, for each of said respective plurality of different second sub-division permutations having that second particular sub-division value, a different respective second additional value for use in discriminating between said respective plurality of second sub-division permutations having that second particular sub-division value.

2 more elements

A method according to any preceding claim, wherein said frequency analysis comprises:

for each one of said plurality of possible first sub-division permutations:
determining a respective occurrence level which is the number of times, within said sequence of bits, that a portion occurs comprising that one of said plurality of possible first sub-division permutations;
and
for each one of said plurality of possible second sub-division permutations:
determining a respective occurrence level which is the number of times, within said sequence of bits, a portion occurs comprising that one of said plurality of possible second sub-division permutations.

2 more elements

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.

5 more elements

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.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/741,508Filed 4 Jul 2016
Priority: GB 1511740.13 Jul 2015
Published: 5 Jul 2018
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

H03M 7/40
Compression ; Expansion; Suppression of unnecessary data, e.g. redundancy reduction: conversion to or from variable length codes, e.g.…
G06F 21/602
Protecting data: providing cryptographic facilities or services
H03M 7/3084
Compression ; Expansion; Suppression of unnecessary data, e.g. redundancy reduction: using adaptive string matching, e.g. the Lempel-Ziv method
H03M 7/3093
Data deduplication: using fixed length segments